Formulation of Hierarchical Task Network
Service (De)composition
Seiji Koide1 and Hideaki Takeda2
1

The Graduate University for Advanced Studies (SOKENDAI), 2-1-2, Hitotsubashi,
Chiyoda-ku, Tokyo 101-8430 Japankoide@nii.ac.jp,
WWW home page: http://www-kasm.nii.ac.jp/~koide/2
National Institute of Informatics and SOKENDAI, 2-1-2, Hitotsubashi,
Chiyoda-ku, Tokyo 101-8430 Japan
takeda@nii.ac.jp

Abstract. The Hierarchical Task Network (HTN) planning method isconceived of as a useful method for Web service composition as well
as classical task planning. However, there are no complete successes ofservice composition by HTN as yet. The reason is the Web service composition process involves the interactive dataﬂow between variables inpreconditions and input/output parameters of services. Since values ofvariables in service IOPEs are required to compose services with theclassical HTN method, we are compelled to perform services in the composition process. However, we cannot perform any world-altering Web
service in practice in the composition process. In this paper, we address
more radical approach of HTN planning method for Web service composition and decomposition with premising the openness and uncertainty of
WWW. We capture composite services, which include abstract meanings
with respect to the variables of Web services, as abstract programs to
be tailored to individual users and instantiated to executable programs.
In this view, the Web service composition process can be conceived of
as a sort of automated programming process, and HTN is deemed as astructured workﬂow or a prototype of actual programs. In this paper,
we formalize Web service composition/decomposition by HTN method
using the term of satisﬁability of situation calculus, and address the algorithm for Web service (de)composition that does not require performing
services.

1

Introduction

The Hierarchical Task Network (HTN) planning method is conceived of as a
useful method for Web service composition as well as task planning, and several
works on the web service composition have been attempted with HTN [6]. However, there are a few but serious discrepancies between task planning and service
composition. First, a web service involves inputs and outputs in addition to theprecondition and the eﬀects. Second, the constraint in web service composition
is not partial-orders of tasks but control constructs, in which a subtask may be2composite and there are dataﬂows and control ﬂows between subtasks. Therefore,
the semantics of Web service composition are much more complex and analogous
to automated programming rather than automated planning. The realization of
the service composition ought to diﬀer from that of task planning.
Sirin, et al. [11] achieved the Web service composition using the HTN planning method. They invented the translator from the OWL-S service description
to the SHOP2 [6] task planning domain. In order to enable the translation fromthe web service composition domain to the HTN task planning domain, they
assumed that an atomic Web service is either a strict information-providing
Web service, which does not have the eﬀects, or a world-altering Web service,
which does not have outputs, but they do not assume world-altering informationproviding services.
This assumption is ascribed to the fact that they used SHOP2, which was
originally developed for classical task planning problems, and they did not reformalize HTN method for Web services. A precondition of method/operator in
HTN is evaluated to test whether the precondition hold on the state or not. In
case that a variable in a precondition is uniﬁed to some output datum of a Web
service in planning, we need to know the value of the output. They state that we
do not want to actually aﬀect the world during planning, and do want to gather
information from information-providing Web Services.
Besides the complexity in the service composition, Semantic Webs stand on
the assumption that the world is open and dynamic. Therefore, we must consider
the uncertainty of the world in service composition and execution processes.
More precisely, we cannot expect service preconditions that hold in a composition
process also hold in a execution process. As a result, we cannot help but abandon
the soundness and completeness of planning when we consider both compositionand execution processes in the dynamic world. In fact, the authors embrace theproblem how to deal with the progression of situation in our application [5]from light anomalies in planning time to heavy anomalies in execution time andfrom one control mode to another control mode in the rocket launch operation
process.
The authors claim that the uncertainty of WWW must be coped with by
Web service agents situated in circumstances instead of planning systems. Suchan agent is known as situated planning agent [9], which can replan and adapt
failed plans to changeable situation. The behavior under the uncertainty is thecommon observation among animals and intelligent human beings in the realworld, and it is the same on even Web service agents in use.
Under the premise of the situated planning agent in the future, in this paper,
we formalize the web service composition and decomposition with expanding the
HTN formalization using the idea of automated planning [2] and situation calculus [8]. In Section 2, we review the formalization of task planning by HTN. Then,we expand it for Web service composition. We deﬁne the concept of applicability, satisﬁability, executability for Web services from the viewpoint of situation
calculus, and address an algorithm for service composition/decomposition. In
Section 3, we describe the implementation of the service (de)composition algo-3rithm, which is straightforwardly embodied of the algorithm using undeterministic search technique with continuation. The algorithm is incomplete because of
the open world assumption but do not compel to perform services in planning.
In Section 4, we discuss the related work, and we conclude at Section 5.

2

Formalisation of HTN for Web Services

2.1

Hierarchical Task Network Planning

In this subsection, we review the classical task planning by HTN according to
the description in [2]. The expansion of HTN to web service composition anddecomposition is described after the next subsection.
Let L be a ﬁrst-order language for planning, in which there are predicate
symbols, constant symbols, and variable symbols. If an atomic formula, which
does not contain logic connectives, does not contain any variable symbol, it iscalled ground atom, otherwise unground atom.
A state s is a set of ground literals, i.e., ground atoms or negations of groundatoms in L. S denotes a set of states. An atom p holds in s iﬀ p ∈ s.
Deﬁnition 1. A planning operator in task planning is a triple such thato = ⟨name(o), precond(o), effects(o)⟩.
– name(o) is a name of operator, which has a syntactic expression of the formn(x1 , ..., xk ) where n is a unique symbol called operator symbol, and x1 , ..., xk
are all of variable symbols that appear anywhere in o.
– precond(o) is the preconditions of o, and effects(o) is the eﬀects of o. Bothare a set of literals, i.e., atoms and negations of atoms.
Deﬁnition 2. An HTN method in task planning is a 4-tuple, that is,m = ⟨name(m), task(m), subtasks(m), constr(m)⟩.
Where name(m) is an expression of the form n(x1 , ..., xn ), n is a unique symbol
for the method, and x1 , ..., xn are all of variables that occur anywhere in m. A
set of pair ⟨subtasks(m), constr(m)⟩ makes a task network.
A task is an expression of the form t(r1 , ..., rk ) like the name of operator but
has a diﬀerent name from and fewer parameters than the name of method. t
is called task symbol, and r1 , ..., rk are terms. Every operator symbol is a task
symbol, and every operator can be a task. When a task symbol t is an operator
symbol and its terms can be uniﬁed to variables of the operator, the task iscalled primitive, otherwise it is nonprimitive. A task in method is nonprimitive.
Deﬁnition 3. A task network in task planning is a pairw = ⟨U, C⟩.
Where U is a set of all of task nodes in the network and C is a set of constraint
such as partial task ordering and preconditions for tasks.
Each task node u ∈ U contains a task tu . If all of tasks in U {tu | u ∈ U }are ground, then w is called ground, otherwise w is unground. If all of tasks{tu | u ∈ U } are primitive, then w is called primitive, otherwise nonprimitive.

4

2.2

Web Service Network by HTN

In this subsection and hereafter, we formalize Web service network by extending
HTN task planning described above.
We expand the deﬁnition of state in Web services so that it includes not only
atoms from precondition and eﬀects but also web service inputs and outputs.
Outputs of Web services are added into the state as well as positive eﬀects. Notethat inputs of Web services are taken from atoms in the state and/or outputs ofother services. The data stream from an input to an output via services is called
dataﬂow, and we call a datum that streams in and out via services IO ﬂuent.
Deﬁnition 4. An atomic service is an expansion of the operator, and deﬁned
as a 5-tuple such thatas = ⟨name(as), inputs(as), outputs(as), precond(as), effects(as)⟩.
– name(as) is a name of service. As well as operator name name(o), it has asyntactic expression of the form n(x1 , ..., xk ), but variable symbol xi comesfrom not only precondition(as) and effects(as) but also inputs(as) andoutputs(as).
– inputs(as) denotes inputs to the web service as, and outputs(as) denotes
outputs returned by the web service. precond(as) represents preserving or
causal condition of as for the web service execution. effects(as) is the side effects or causal eﬀects onto the state s by the web service execution. inputs(as)and outputs(as) is an sequence of variables respectively, while precond(as)and effects(as) is a set of literals, as same as in operators.
Deﬁnition 5. A composite service is an expansion of the method in HTN task
network, and deﬁned as a 7-tuple, that is,
cs = ⟨name(cs), task(cs), inputs(cs), outputs(cs), subtasks(cs),precond(cs), controlConstruct(cs)⟩.
Where the deﬁnition of name(cs), inputs(cs), outputs(cs), and precond(cs) aresame as the deﬁnition of that in atomic service, but the notation of task(cs),subtasks(cs), and controlConstruct(cs) ﬁrstly appear here in a composite service.
A task in Web services is deﬁned as same way in HTN task planning. If thetask symbol t is a name symbol of name(as) of atomic service as and its terms
r1 , ..., rn can be identical to variables of the atomic service, the task is calledprimitive.
A task network in Web service is a pair of a set of subtasks(cs), and a set ofcontrolConstruct(cs).
Deﬁnition 6. A task network in Web service composition and decomposition isexpressed as
w = ⟨U, CC⟩.

5

Where U is a set of all of task nodes in the network, and CC is a set of allcontrol construct included in the network. Note that the constraint of CC includes control ﬂows, dataﬂows, and preconditions of task-corresponding composite services and atomic services. The controlConstruct(cs) contains task ﬂows
(abstract control ﬂows) and dataﬂows. A composite service can contain only one
control construct in deﬁnition, but a control construct can contain other tasks
and control constructs in the speciﬁc form of various kind of control constructs,
such as sequence, if T henElse, loopW hile, etc.
We can consider various controlConstruct, but in this paper we deﬁne only
three as follows.
Deﬁnition 7. A sequence is a tuple of any number of subtasks.
seq = ⟨elt1 (seq), elt2 (seq), ..., eltk (seq)⟩
Where elti (seq), i ≤ k is a subtask in the cs. In the execution of sequence,elti (seq) is performed in the order of the sequence.
In HTN task planning, constraint constr(m) represents partially orders ofsubtasks. Therefore, a predecessor and the successor of tasks can be interleaved
by another task. However, no service can part the task sequence in sequential
performance of Web services.
Deﬁnition 8. An if T henElse is a 3-tuple as follows.
ite = ⟨if (ite), then(ite), else(ite)⟩
Where if (ite) is a condition that does not cause any side eﬀect in evaluation,and then(ite) is a subtask or a control construct that is performed when if (ite)is true in the state. Optional else(ite) is a subtask or a control construct thatis performed when if (ite) is not true. This if T henElse has two possibility of
branching of control in the execution process.
Note that then(ite) is performed if and only if the condition of if (ite) istrue in the state, but else(ite) is performed not only in case of negation of thecondition of if (ite) but also in the case of unknown condition for if (ite), withthe premise of the open world assumption of Web Semantics.
Deﬁnition 9. loopW hile is a 2-tuple such aslw = ⟨while(lw), seq(lw)⟩
Where while(lw) is a condition during which is true seq(lw) is performed repeatedly. seq(lw) is a sequence. Note that performance of sequence is terminatedeven if while(ls) becomes unknown in the execution process.
2.3

Web Service Composition and Decomposition by HTN

On one hand, the objective of task planning is to obtain totally ordered sequences of actions that achieve a goal, where a goal g in task planning is a set ofground literals. On the other hand, the objective of Web service composition and6decomposition is to obtain a set of executable task ﬂows or programs that are an
instantiated network of procedure in the environment. We have two categories
of goals in essence in Web service composition, i.e., the alteration of world by
Web services and the information retrieval that is provided by performance of
Web services. The former is the same as classical task planning but the latteris diﬀerent from goals in classical task planning. We give ground literals (say,instances of classes in OWL) as goals in task planning, but we cannot designate
values of service outputs as goals in Web service composition. The values of output variables are the very thing we want to know. We are able to only designate
typed variables (classes in OWL) as goal. Web service composers must generate
executable instantiated task ﬂow that includes atomic (invokable) services that
achieve world-altering goals and information-retrieval goals. Furthermore, thecoupling of world-altering service performance and information-retrieval service
performance may happen.
In this subsection, we discuss the intepretability and composability of services
from the standpoint of satisﬁability in situation calculus [8].
Satisﬁability of Web Service: In task planning, an operator o is an abstract
one that stands for all instance operators named by an operator symbol n. In the
instance operators of o, variable symbols in name(o), precond(o), and effects(o)are substituted with corresponding constant symbols. If an instance operator
contains ground atoms and does not contain unground atoms, it is called ground,
otherwise unground. A ground operator that includes ground atoms in S is called
action.
To discuss the interpretation of assertions for Web service (de)composition,
we set an state transition machine. Let Σ be an state transition machine [2]. We
consider a mapping from a state s in assertions of the planning problem P toa state in Σ. For a state s described in planning language L, the corresponding
state in Σ is denoted by sI , and I is called interpretation. In case that there area mapping from si−1 to sIi−1 and si to sIi , if there is a mapping from an instance
operator o in P that links from si−1 to si to oI that links from sIi−1 to sIi , it iscalled satisﬁable on the operator o.
We expand this interpretation to Web service composition and decomposition. In case that there is a mapping from si−1 to sIi−1 and si to sIi ，and froman atomic web service as in P that links from si−1 to si to asI that links fromsIi−1 to sIi , it is called satisﬁable on the atomic web service as.
For an atomic service as, if and only if the precondition precond(as, s) is
satisﬁable, namely a condition in precond(as) holds in an interpretation sIi , andinputs inputs(as, s) is satisﬁable, namely we can ﬁnd the uniﬁcation for eachvariable of inputs onto sIi , where the uniﬁcation is identical to that for theprecond(as), then the atomic service as is satisﬁable on s.
s |= as ⇔ (s |= precond(as) ∧ s |= inputs(as))
On the other hand, a composite service cs is satisﬁable, iﬀ precond(cs),inputs(cs), and controlConstruct(cs) is satisﬁable.

7s |= cs ⇔ (s |= precond(cs) ∧ s |= inputs(cs) ∧ s |= controlConstruct(cs))
When the precondition and inputs of a service are satisﬁable, let us callthe service applicable. An applicable atomic service is always satisﬁable but anapplicable composite services are not necessarily satisﬁable. In other words, anapplicable atomic service has a model on s but there is a case that an applicable
composite service has no model on s.
In order to know the satisiﬁability of a composite service, we need to know
the satisﬁability of controlConstruct.
Satisﬁability of Task: If a task t(r1 , ..., rn ) is primitive, then the task t(r1 , ..., rn )is applicable and satisﬁable, iﬀ as is satisﬁable.
s |= t ⇔ ((name(as) = σ(t(r1 , ..., rn ), θ)) ∧ (s |= as))
Where σ(t(r1 , ..., rn ), θ) expresses the substitution of t(r1 , ..., rn ) by uniﬁer θ fors.
If a task is nonprimitive and the corresponding service is composite, then thetask t(r1 , ..., rn ) is satisﬁable, iﬀ cs is satisﬁable.
s |= t ⇔ ((name(cs) = σ(t(r1 , ..., rn ), θ)) ∧ (s |= cs))
Satisﬁability of sequence Control Construct: Let be seq a sequence, andlet s0 the initial state for sequence seq. Let be γ(si−1 , elti (seq)) a progression ofsubtask elti (seq) for state si−1 . It is seemed that the execution of task elti (seq)for state si−1 makes a progression and yields the next state si . However, wecannot really execute the task in service composition processes. Instead we makethe progression by the uniﬁcation that change abstract types of variables to more
special types.
si = γ(si−1 , elti (seq))
This is the same meanings of the following expression on action by Reiter [8],whereas there are only actions, that contain preconditions and eﬀects, and noservices that contain inputs and outputs.
si = do(elti (seq), si−1 )Let us express the execution of elti (seq) by inputs in1i−1 , ..., inki−1 as elti (seq)(in1i−1 , ..., inki−1 ).
If elt1 (seq) is satisﬁable for s0 and inputs in10 , ..., ink0 , then we can make aprogress for s0 and obtain s1 for elt1 (seq)(in10 , ..., ink0 ) by making a progressof uniﬁcation instead of performance of elt1 (seq).
s1 = γ(s0 , elt1 (seq)(in10 , ..., ink0 ))Then, if elt2 (seq) is satisﬁable for s1 and inputs in11 , ..., inl1 , we can obtain thenext state s2 .

8

s2 = γ(s1 , elt2 (seq)(in11 , ..., inl1 ))We cannot say that if all tasks elti (seq)(in1i−1 , ..., inki−1 ) in sequence are independently satisﬁable for each states then the sequence is satisﬁable, because thesatisﬁability of the control construct also depends on the dataﬂow. We represent
this constraint of dataﬂow in control construct dataf low(seq). If the dataﬂow
constraint is held correctly in the progression of control constructs, we call thecontrol constructs has a model. Thus,s0 |= sequence ⇔ (s0 |= dataf low(seq) ∧ {si−1 |= elti (seq) | i = 1, ..., k})Note that each task elti (seq) may be composite and its satisﬁability is decidedwith the satisﬁability of the corresponding composite service. Obviously, thisdeﬁnition for the control construct and the composite service is recursive but
not tautology, because the satisﬁability can be decidable, namely the composite
service is decomposed down to atomic services in an acyclic task network, andevery atomic service is decidable for satisﬁability.
Satisﬁability of if T henElse Control Construct: Let be ite an instanceof if T henElse, and si−1 is the state for ite. Then, we have three possibilities
on the satisﬁability of ite.
– One is for positive condition such ass |= ite ⇐ (s |= if (ite) ∧ s |= then(ite)).
– Another is for negative condition such ass |= ite ⇐ (s |= ¬ if (ite) ∧ s |= else(ite)).
– The last is for unknown condition such ass ̸|= ite ⇐ (s ̸|= if (ite) ∧ s ̸|= ¬ if (ite)).
If if (ite) holds and then(ite) is satisﬁable, then the ite is satisﬁable. If thenegation of if (ite) holds and else(ite) is satisﬁable, then ite is satisﬁable. However, when the condition of if (ite) is unknown, we cannot deduce that ite issatisﬁable. In the execution process, the value of if (ite) is known as a resultof the service execution and progression of states, but it may be unknown incomposition processes. Therefore, the composer cannot proceed the reasoning at
this branch of possibility. In such a case, the agent has a selection according to
two strategy, i.e., speculative strategy and assurance strategy. In the speculative
strategy, the agent takes one of the possibilities of branches. The instantiatedprogram as a result of (de)composition may be not valid in execution. If theexecuter failed the execution of the generated program, the agent repairs thefailure and replans at the point. In the assurance strategy, the agent brings theincomplete programs to an execution phase and executes it. The agent restartplanning when the value of the if (ite) is known. Thus, the functionality of incremental planning and replanning is requisite for the agent in the open world.
Generally speaking, it is useful to positively give rich information of negation,
disjunction, and complementness in ontologies for the open world.

9

Satisﬁability of loopW hile Control Construct: Let be s0 an initial state
for an instance of loopW hile, lw. When while condition while(lw) of lw does
not hold via knowing the negation of while(lw), lw is satisﬁable and the state s0
does not evolve. If while condition while(lw) holds for s0 , then lw is satisﬁable
iﬀ seq(lw) is satisﬁable. However, when it is unknown whether while(lw) holdor not, we treat it in the same way as if T henElse.
As a result of the execution of satisﬁable sequence seq(lw), the state evolves
and this process is repeated again while while(lw) is satisﬁable for the evolving
state in the loop.
s |= lw ⇐ s |= ¬ while(lw)s |= lw ⇐ s |= while(lw) ∧ seq(lw)s ̸|= lw ⇐ s ̸|= while(lw) ∧ ̸|= ¬while(lw)Note that even if the same procedure is executed repeatedly, the states evolve.
Similarly, even if the same procedure is tested repeatedly on the satisﬁability,
the states may evolve because types of variables evolve more precisely step bystep by loop using the typed uniﬁcation, which is described later.
2.4

Algorithm of Web Service Composition and Decomposition

We cannot decompose the control construct of composite services into subtasks
as HTN task planning does. Instead, we collect all of satisﬁable bindings ofvariables that make a control construct in hand satisﬁable, and search all possibilities by substituting all variables in service parameters. Here note that inputs
and outputs are typed in DL or OWL, and variables and constants in precondition and eﬀects also typed. Therefore we need typed uniﬁcation to computesatisﬁability. The typed uniﬁcation algorithm is described in the next section.
Suppose that u is a task node in U {u ∈ U }, cs is a composite service, andtask(cs) = tu . Then cs instantiate u as producing the instantiated task network
w′ . If w = ⟨U, CC⟩ is primitive, and CC is satisﬁable for s, then w is a solution
for s such that the executer can execute CC for s. If w = ⟨U, CC⟩ is nonprimitive(i.e., at least one task in U is nonprimitive), then w is a solution for s if there isa sequence of satisﬁability checking that simulates dataﬂows and control ﬂows
in control constructs, and a primitive task network w′ is obtained as a result.
The algorithm of HTN Web service composition and decomposition is described as follows.
procedure SWHTN(s, w′ , w, AS, CS, D)
if w = Ø then return w′
nondeterministically choose any u ∈ U that has no predecessors in w
if tu is primitive thenactive ← {σ(s) | as = discover(tu , w, AS, D) and as is satisﬁable in s
σ is a substitution with satisﬁable bindings of asif active = Ø then return fail()
nondeterministically choose any σ(s) ∈ active

10

return SWHTN(σ(s), w′ + σ(u), σ(w − {u}), AS, CS, D)
else ; ; tu is nonprimitive.
active ← {σ(s) | cs = discover(tu , w, CS, D) and cs is applicable in s
σ is a substitution with applicable bindings of cs
if active = Ø then return fail()
nondeterministically choose any σ(s) ∈ active
if tu is not satisﬁable for σ(s) then return fail()
return SWHTN(σ(s), w′ + σ(u), σ(w − {u}), AS, CS, D)
Where s is a state in a situation, w is a part of task network that is to beinstantiated. w′ is a part of task network that is instantiated. AS is a set of
atomic services, and CS is a set of composite services. D is a domain knowledge ofthe target ﬁeld. This algorithm contains the loop of SWHTN() via tail recursive
call. f ail() causes automatic backtracking to the point of the last choice ofnondeterministic selection.
The algorithm is very similar to HTN of task planning [2] and SHOP2 [6],because we already have a convenient terminology satisﬁable. We used it insteadof the terminology of ground action in HTN task planning in order to collectactive atomic service. However, there is no decomposition of composite tasks.
Instead we substitute parameters with bindings in the situation.
In the worse case, we cannot obtain complete solutions from this algorithm,
because it is possible that we encounter unknown conditions without the execution of Web services. In such a case, the agent resolves the problem in themanner of the situated planning agent [9].

3Implementation

3.1

State Space and Variables

Generally, an atom can be expressed as form t(r1 , ..., rn−1 , rn ). Then, if t isfunctional such that the combination of predicate t and variables r1 , ..., rn−1 has
a mapping to each diﬀerent rn on each state s, t is called ﬂuent. rn is called statevariable and expressed as rn = t(r1 , ..., rn−1 ). A ﬂuent can be also expressed ast(r1 , ..., rn−1 , rn ) = true or simply t(r1 , ..., rn−1 , rn ). A strong negation of atom
can be expressed as t(r1 , ..., rn−1 , rn ) = f alse. On the close world assumption,
the absence of positive atom means the negation of the assertion. On the open
world assumption, it means unknown on the assertion.
The state is expressed as a list of state variables as atom. The followingshows an example of the state in which an individual Lucy has an appointment,
and HAL has also an appointment in Lisp. Note that Lucy is already deﬁned as
individual of Person, and HAL is already deﬁned as individual of Robot.
(setq *state*(make-state ’((hasAppointment(Lucy) = LucysAppt)(hasAppointment(HAL) = HALsAppt))))11

On the other hand, we can make a typed variable in the following form inour system.
(make-condition ’((hasAppointment((?p - Person)) = ?appt)))

Note that this appointment with variables typed Person is uniﬁed with
Lucy’s appointment but not uniﬁed with HAL appointment.
3.2

Typed Uniﬁcation

The uniﬁcation algorithm by Russel and Norvig [9] is expanded to accept OWL
entities, classes and individuals. A variable is also an individual of a class in thedomain. Consider the followings, where variablep(x) tests whether x is a variable
individual and variable?(x) tests x for the lisp symbol of individual.
function Typed-Unify(x, y, θ)
if θ = failure then return failure
else if x = y in semantics of OWL then return θelse if variablep(x) then return Typed-Unify-Var+(x, y, θ)else if variablep(y) then return Typed-Unify-Var+(y, x, θ)else if variable?(x) then return Typed-Unify-Var(x, y, θ)else if variable?(y) then return Typed-Unify-Var(y, x, θ)else if compound?(x) and compound?(y) thenreturn Typed-Unify(Args(x), Args(y), Typed-Unify(Op(x), Op(y), θ))else if list?(x) and list?(y) thenreturn Typed-Unify(Rest(x), Rest(y), Typed-Unify(First(x), First(y), θ))else return failure
As shown below, the algorithm of Typed-Unify-Var looks like the same asoriginal Unify-Var in [9] at the surface level, but making a new binding {var/x}
diﬀers from the original. In addition to the symbol level binding between var
and x, the class level bindings are taken into account. If two classes of var andx are disjoint each other, then no uniﬁcation is made and failure is returned. If
two classes relates each other in subsumption relation, then a mapping to thespeciﬁc class is made. Otherwise, a mapping to the intersection of both classes
is made.
function Typed-Unify-Var(var, x, θ)
if {var/val} ∈ θthen return Typed-Unify(val, x, θ)else if {x/val} ∈ θthen return Typed-Unify(var, val, θ)else if var occurs anywhere in x
then return failure
else return make {var/x} ∈ θ12Typed-Unify-Var+ is prepared for the binding of OWL individual objects.
In the integration to SWCLOS [4], an variable var in Typed-Unify-Var+ is anobject typed to OWL classes in the domain, while x may be an individual of
domain classes or may be an variable typed to a domain class.

function Typed-Unify-Var+(var, x, θ)
if x is individual thenif disjoint?(class(var),class(x)) then return failure
else if class(var) = class(x) in semantics of OWL
then return make {symbol(var)/symbol(x)} ∈ θelse if subsumed?(class(x),class(var))
then return make {symbol(var)/symbol(x)} ∈ θelse if subsumed?(class(var),class(x))
then return make {symbol(x)/individual(class(var)) } ∈ θmake {symbol(var)/symbol(x)} ∈ θelse returnthen return make {symbol(x)/individual(intersection(class(var),class(x)))} ∈ θmake {symbol(var)/individual(intersection(class(var),class(x)))} ∈ θmake {symbol(var)/symbol(x)} ∈ θelse return failure

Through uniﬁcation, the type of variable is speciﬁed step by step. The valueof variables are bound to abstract concepts to special concepts along with theprogression via uniﬁcation. However, if we have poor ontologies with respect tothe class hierarchy, this uniﬁcation easily leads silly results. For example, if there
is no knowledge that xsd:integer is disjoint with xsd:ﬂoat, the intersection of
xsd:integer and xsd:ﬂoat is resulted. However, if there is an assertion that ship
is disjoint with automobile, the system fails to ﬁnd the route by amphibiousvehicle.

3.3

Nondeterministic Choice by Continuation

The continuation is well known as program control technique in Scheme. In short,
it is a program frozen in action [3]. When the computational object that contains
the state of a frozen computation is evaluated, it is restarted where it left oﬀ.
This machinery can be a great help to implement the exception handler, multiprocessing, and nondeterministic search and choice. In order to integrate the(de)composer with SWCLOS [4], which is an OWL Full reasoner and language
built on top of Common Lisp Object System, we have adopted the technique ofcontinuation in Lisp [3]. The (de)composition algorithm SWHTN in Subsection
3.4 can be straightforwardly implemented with the continuation.

13

4

Related Work and Concluding Remarks

4.1

Reasoning from Action to Service

Reiter [8] enlightened the task planning problem from situation calculus. Berardi
et al. [1] discussed the synthesis of Web services from situation calculus, but thework still stays in the closed world assumption. Sohrabi et al. [13] demonstrated
Web service composition using agent programming language GoLog, which isbased on situation calculus. However, the problem of the interaction between
precondition and inputs/outputs, which is posed by Sirin et al. in service composition using SHOP2 [11], seems to be still open.
All of them including [11] strongly stick the validity and completeness of service composition. However, the authors argue that the openness and uncertaintyof WWW lead us to the incompleteness of composition. The problem must be
solved by the intelligent behavior of agent in the changeable world. In this paper, we formalized Web service composition/decomposition by HTN using theidea of satisﬁability in situation calculus, and addressed the algorithm for service
composition with the directive suggestion of implementation. We also suggested
that we need situated planning agent that adaptively behaves in service composition, decomposition, execution, and monitoring, by introducing the open world
assumption into the formulation.
Sirin and Parsia [12] deeply discussed the integration of OWL and the taskplanner. In a sense, it could be said that this paper is a legitimate argument on
the HTN formalization touched by them. We addressed the typed uniﬁcation to
make a progress about variable bindings. The system is based on SWCLOS [4]for OWL reasoner. Sirin and Parsia pointed out the existentially bound variables
in preconditions may cause the disparity of binding between planning time andexecution time. We have no solution on this problem in this paper. We know that
SWCLOS cannot reason out on the existential quantiﬁer. On the other hand, theproblem on the creation of anonymous individuals is easily solved with SWCLOS,
because SWCLOS is built on top of Common Lisp Object System (CLOS) andevery concept and individual is an object, even if it is anonymous or not.
4.2

Framework of Web Service AgentIn this paper, we often mentioned the composer and executer. Fig. 1 depicts
a framework of a web service agent by HTN service composition. The system
consists of ﬁve modules, a composer, a decomposer, an executer, the memory,and the user interface.
The composer composes an appropriate task ﬂow on user demands, using
the library of workﬂows or business patterns. The decomposer instantiates theabstract task ﬂow to executable programs that include the invocations of Web
services. The executer interprets and executes the instantiated programs withinvoking Web Services. The machinery functions as memory for various internal
data of agent, i.e., plans of tasks, simulating data of states under planning,14

User Interface

Composer

Library ofWorkflow &Business Pattern

Decomposer

MemoryExecuterWeb Service
Repository

Real
World

Fig. 1. Agent Framework

results of execution, etc. Some part in memory reﬂects the variations of outerworld with sensing data and poling queries, etc.
The user interface works for the communication between the agent and a user.
Some ambiguity and nondeterministic choice in task planning may be solved withthe help from the user through this interface.
This agent plays double roles as intelligent agent for invoking Web services
and interface agent for users. In fact, we have almost developed such an agent
in our application of Rocket Launch Operation Support System [5], in which
the interface agents that mediate between support engineers in distance fromthe launch site and various Web services for information providing on rocket
launch process help the engineers to decide the counteraction in the contingencyof rocket launch process. Semantic Web service technology is adopted to realize
the ﬂexible intelligent decision support system.

4.3

Web Service Discovery

Web service subsumption hierarchy (not task-subtask hierarchy) can be utilized
to discover appropriate Web services that are annotated with inputs, outputs,
precondition, and eﬀects. If a Web service subsumption hierarchy is richly andconsistently built with domain ontologies, the discovery of Web services is justsame as the calculation process of subsumption and classiﬁcation in DL or OWL
on an unknown service. If inputs and outputs are annotated just as xsd:integer or
xsd:string like Java program language, it produces no eﬀects on service discovery.
If IOPEs are typed to classes in middle level ontologies and enter prize ontologies,
the agent can understand meanings of services. If the Web service annotationis poor or inconsistent with domain ontologies, agent must nondeterministicallysolve this problem. Sycara, et al. [10], discussed this problem and presented
OWL-S Matchmaker and OWL-S Virtual Machine.
In this paper, we formulated HTN Web service composition and decomposition on the assumption that agent can automatically and appropriately discover

15

a number of Web services in the situation. The function discover in the algorithm
shown above is such a thing.
4.4

Web Service Decomposition

Usually, HTN is conceived as a method for Web service composition. However,the composition process in HTN is strictly coupled with the decomposition process. We consider the agent depicted in Fig. 1, in which the composer composes
Web services from scratch. In this service composition, the partial ordered planner technique like UCPOP [7] will be useful rather than HTN. In this paper, weconcentrated the discussion to HTN task planning process, in which we have a
top task of HTN at ﬁrst, and the top task and related abstract tasks are instantiated by selecting and combining subtasks and reducing the ambiguity of task
parameters step by step. We call this HTN planning process service decomposition.

References
1. Berardi, D., Calvanese,D., Giacomo, D., Mecella, M.: Reasoning about Actions for
e-Service Composition. International Conference on Automated Planning & Scheduling, ICAPS 2003 (2003)
2. Ghallab, M., Nau, D., Traverso P.: Automated Planning Theory and Practice. Morgan Kaufmann (2004)
3. Graham, P.: On Lisp. Prentice Hall, (1993)
4. Koide, S. Takeda, H.: OWL-Full Reasoning from an Object Oriented Perspective.
Asian Semantic Web Conf., ASWC2006 (2006) 263–277
5. Misono, S., S. Koide, N. Shimada, M. Kawamura, and S. Nagano: Distributed Collaborative Decision Support System for Rocket Launch Operation. IEEE/ASME Int.
Conf. Advanced Intelligent Mechatronics, AIM2005, (2005)
6. Nau, D., T.-C. Au, O. Ilghami, U. Kuter, J. W. Murdock, D. Wu, and F. Yaman:
SHOP2: An HTN Planning System. J. Artiﬁcial Intelligence Research, 20-12, (2003)
379–404
7. Penberthy, J. S. and D. Weld: UCPOP: A Sound, Complete, Partial-Order Planner
for ADL. Third International Conference on Knowledge Representation and Reasoning (KR-92), Cambridge, MA, (1992)
8. Reiter, R.: Knowledge in Action. MIT Press (2001)
9. Russell S. Norvig .P: Artiﬁcial Intelligence: A Modern Approach. Prentice Hall,(1995)
10. Sycara, K., M. Paolucci, A. Ankolekar, and N. Srinivasan: Automated discovery,
interaction and composition of Semantic Web services. J. Web Semantics, 1, Elsevier(2003) 27–46
11. Sirin, E., B. Parsia, D. Wu, J. Hendler, and D. Nau: HTN Planning for Web Service
Composition Using SHOP2. J. Web Semantics, 1, Elsevier (2004) 377–396
12. Sirin, E. and B. Parsia: Planning for Semantic Web Services. In Semantic Web
Services Workshop at 3rd International Semantic Web Conference, (2004)
13. Sohrabi, S., Prokoshyna, N., McIlraith, S.A.: Web Service Composition via Generic
Procedures and Customizing User Preferences. Int. Semantic Web Conf., ISWC2006(2006) 597–611