=Paper=
{{Paper
|id=Vol-494/paper-36
|storemode=property
|title=Executing Agent Plans by Reducing to Workflows
|pdfUrl=https://ceur-ws.org/Vol-494/ladspaper10.pdf
|volume=Vol-494
|dblpUrl=https://dblp.org/rec/conf/mallow/HalacCEED09
}}
==Executing Agent Plans by Reducing to Workflows==
https://ceur-ws.org/Vol-494/ladspaper10.pdf
Executing Agent Plans by Reducing to Workflows
Tayfun Gokmen Halac, Övünç Çetin, Erdem Eser Ekinci
Rıza Cenk Erdur, Oguz Dikenelli
Ege University, Department Of Computer Engineering
35100 Bornova, Izmir, Turkey
Email: {tayfunhalac,ovunccetin,erdemeserekinci}@gmail.com
{cenk.erdur,oguz.dikenelli}@ege.edu.tr
Abstract—In this paper, we introduce an agent planner ar- the meta-level. Second, a common model that will form a com-
chitecture that can reduce the basic artifacts of agent planning mon execution basis for the tasks that have different semantics
paradigms, semantic services and business process languages into is needed. Based on the fact that a plan can be represented as a
a common workflow model. These artifacts are then executed by
means of a workflow component that the architecture includes. directed graph which can be executed as a workflow, defining a
By having a workflow component in an agent infrastructure, var- generic workflow graph model will satisfy the requirement for
ious agent programming paradigms including different planning a common model. Finally, algorithms for the transformations
approaches as well as different workflow definition languages from the meta-models into the common representation model
can be executed on the same agent platform. To illustrate our should be developed.
ideas, we focus on the reduction of plans to the workflow model.
To explicate the reduction mechanism, we have preferred to use In this paper, we introduce a planner architecture that fulfills
HTN which is a widely known planning approach in multi-agent the requirements given above. The introduced architecture
domain. Based on the semantics that we have defined for our includes a generic workflow graph model into which various
workflow and HTN models, we have given an algorithm for task semantics can be transformed. This generic workflow
transformation from HTN to workflow model. graph model has been defined based on the abstract definition
given in [5]. Within the planner architecture, we have also
implemented an executor component which is used to execute
I. I NTRODUCTION
the instances of the generic workflow graph model.
Agents can execute various task structures in order to In literature, there are studies that aim to execute web ser-
achieve their goals. These task structures may be components vices or workflows within a planner or an agent architecture.
of a plan (e.g. actions), services including semantically defined [6] describes how SHOP2 HTN planning system can be used
web services, or workflows which are represented using an to execute OWL-S descriptions. The SHOP2 planner takes the
appropriate formalism such as BPEL[1], XPDL[2]. An agent composite process defined using OWL-S as input and executes
may execute each of these task structures in a way that is this composite process. WADE[7] is a software platform which
independent of others as it is the case for an agent that can is built on top of the well-known agent framework JADE[8].
execute only plans, only OWL-S service definitions or only WADE uses a directly executable simple workflow structure
workflows. based on java class instead semantically described planning
On the other hand, it is usually a desired property for an paradigms. Our study differs from these works, since our
agent to execute several task structures in a combined manner. proposed planner architecture can support combinations of
For example, one or more actions of a hierarchical task various task semantics both at design-time and run-time by
network (HTN)[3], [4] plan may need to call a web service providing a common execution layer for all of them. Neither
or execute a pre-defined workflow. In addition, in open and [6] nor [7] aims to support more than one task execution
collaborative multi-agent organizations where task structures semantics at the same time. Another point that needs attention
can be distributed within the environment, it is required to is that the workflow graph model which constitutes the core of
discover, access, compose (if needed), and execute them at our common execution model is not related with the concept
run-time. To support various task execution semantics both at of executing a workflow within an agent. The workflow graph
design time and run-time, what is needed is a special agent model is a directed graph structure into which various task
planner architecture that should ideally provide a unique and semantics are transformed before execution.
common basis for the execution of different task structures in We have implemented the planner architecture within
a both independent and combined manner. SEAGENT[9], which is a semantic web enabled multi-agent
There are three basic requirements to support various task system framework developed by our research group[10]. The
execution semantics in an agent architecture. First, meta- planner can reduce the plans defined using OWL ontologies
models for the representation of various task semantics are and OWL-S service definitions into the common workflow
needed. OWL-S, which is a standard for defining web services graph model, and then execute them. To illustrate the reduction
semantically, and workflow definition formalisms such as process, we just focus on the transformation of HTN semantics
BPEL are examples for such meta-models. As another exam- into the common workflow graph model in this paper. We have
ple, agent plans can be represented using OWL ontologies at chosen HTN because HTN planning is a well-known approach
that has affected the agent domain most, and has been di- execution. It verifies the syntactical structure of the workflow
rectly used in several agent development frameworks[11], [12]. and data flow over this workflow instance.
SEAGENT also incorporates HTN as its planning paradigm. Reducers, Matchers, and JENA2 form a bridge connecting
Remaining parts are organized as follows: Before giving the execution layer to the Semantic Web layer. The ontological
the details of the reduction mechanism, we introduce current definitions of the agent’s actions from the Semantic Web layer
architecture of SEAGENT planner in Section II. In section are read here, and converted to the corresponding workflows.
III, details of our planner’s internal workflow structure, to The Reducers sub-package contains the graph reducer compo-
which HTN plans and other process definition languages are nents (GoalReducer, HTNReducer, OWLSReducer) that parse
reduced, are given. Soon after, we define our enhanced HTN Goal, HTN and OWL-S definitions and reduce them into the
semantics in section IV. In section V, the algorithm that workflow. The other module, called Matchers, contains three
achieves the reduction from HTN to Workflow model is given, submodules: RoleMatcher, GoalMatcher and ActMatcher. Role
and correctness of the reduction mechanism is discussed. and goal matchers collaborate to find an appropriate goal
Section VI includes a working example and Section VII the description for an objective which the agent must fulfill. If a
conclusion. goal is matched with an objective, the description of the goal
is given to the GoalReducer to reduce it into a goal workflow.
II. T HE A RCHITECTURE O F T HE P LANNER During the execution of the goal workflow, an ActMatcher is
The implementation of the proposed planner architecture is invoked for each sub-goal to find an appropriate act (HTN
presented in Figure-1. As indicated in the figure, two vertical plan or OWLS service) that accomplishes the sub-goal. After
layers compose the overall architecture. The front layer, called the ActMatcher returns the corresponding act description, a
Semantic Web Layer, uses ontological descriptions to represent reducer (HTNReducer, or OWLSReducer) is selected to reduce
the artifacts of the planning process. These ontology descrip- the act description to the workflow.
tions are: Goal, Role, HTN 1 and OWL-S. The goal ontology In this paper, we only focus on the reduction of HTN plans
defines the objectives which the agent intends to reach within to workflows. To specify our reducing process, workflow and
the organization. It specifies abstract definitions for agent HTN semantics are formally defined in the following sections.
behaviors. The role ontology, on the other hand, puts the Next, reducer algorithm is illustrated in the section V.
related goal definitions together within a role description. In
addition, it also defines some constraints about the considered III. S EMANTICS OF SEAGENT W ORKFLOW G RAPH
role. Roles and goals take in charge during planning process,
and then the output plan is reduced to the workflow model. Our As mentioned in the introduction, workflow technology has
main interest is on reduction of plans, not on this plan decision been extensively researched in the academy and as a result of
process. The HTN ontology is used to describe the agent these efforts this technology has reached to a high degree of
plans using HTN planning technique. Finally, OWL-S (Web maturity. Widely acceptance of workflows in industrial settings
Ontology Language for Services) is a part of our proposed and standardization of workflow definition languages such as
architecture to support semantic services. As is seen in the BPEL, XPDL are the signs of this maturity degree. On the
figure, the planner, which composes the Execution Layer, other hand, from the execution perspective, several approaches
consists of four modules: WorkflowElements, WorkflowEngine, have raised up such as executing the workflows on Petri-
Matchers, Reducers. Nets[13] and on conceptual directed graphs[5].
The WorkflowElements module contains building blocks of Sadiq and Orlowska abstractly introduced the basic building
our graph structure which is used to represent the agent acts blocks of a workflow process using the graphical terms such as
as a workflow at execution time. The graph structure is based nodes and flows in [5]. They also defined the basic workflow
on tasks, coordinators and flows, all of which are discussed in constructs such as sequence, choice, concurrency and iteration.
detail in Section III. Besides the modeling workflows, they touch on reliability of
The WorkflowEngine module is responsible for perform- the workflow model in [14], [15]. For this purpose, some struc-
ing a workflow instance and coordinating its execution. It tural conflicts as deadlock, lack of synchronization, live-lock
consists of three submodules: ExecutionToken, LazyBinder, are determined. Our workflow model is built by deriving the
and GraphVerifier. The ExecutionToken is the major com- abstract definitions of Sadiq et al. and extended by constraints
ponent for the execution which traverses the nodes of the to avoid structural conflicts articulated in [14].
workflow instance and executes tasks of workflow instance. In this section, we semantically declare the concepts and
The LazyBinder module was developed to support dynamic their constraints of our workflow implemetation. Before giving
graph binding. It has a special abstract graph node called semantics of our workflow model, we evoke to the reader that a
LazyTask which loads the concrete graph at runtime. This workflow is also a kind of directed graph[16], [17]. So, we start
dynamic binding capability makes our workflow dynamically to explain semantics of our model by giving the formalism of
extendable. Thus, at run-time new goals and tasks can be the directed graph with the following definition.
appended based on the state of the environment and/or agent’s Definition 1: Given directed graph is a tuple of g = hV, Ei,
knowledge. Finally, the GraphVerifier module is responsible V = {v0 , v1 , . . . , vn } and E = {hvs , vt i : vs , vt ∈ V }.
for verification of a workflow instance before it is given to the
2 We use JENA (http://jena.sourceforge.net/) to read and manipulate the
1 http://etmen.ege.edu.tr/etmen/ontologies/HTNOntology-2.1.4.owl ontology documents in the knowledge-base and over the Internet.
Figure 1. SEAGENT Planner Architecture
The directed graph represented with g consists of vertices τi = hnτi , ICτi , OCτi i ∈ T . In detail, nτi is the identifier of
V and directed edges E. A vertex, v ∈ V , specifies a the task, while ICτi and OCτi correspond to input and output
node in the graph. The words, node and vertex, will be used containers respectively.
interchangeably. A directed edge, e ∈ E, shows a directed link • A data container, κ, is the set of data items which are
between two vertices of the graph. In the definition, vertex needed to execute a task or generated by the task, κ
”vs ” represents the source vertex of the edge and vertex ”vt ” = {d1 , d2 , . . . , di }. IC and OC are sub types of data
is for the target. We define a function, path, that helps to gather container, IC, OC ⊂ κ.
the directed ways between two given vertices: • A data item, di = hndi , typedi i, stands for data which is
• path (vi , vk ) = (e0 , . . . , en ) where vi ∈ V and vk ∈ V held by input and output containers. di is identified by
represents the first and the last vertex of the path. path its name (ndi ) within the container and typedi property
defines one of the directed ways between vertices vi specifies the data-type of di .
and vk . The first term of the finite sequence of edges The required coordination of tasks of workflow and data
is e0 where source (e0 ) = vi and the last term is sharing between tasks are provided by special components
en where target (en ) = vk . For all terms of the se- called flows. There are two types of flows in our model: control
quence, target node of an edge equals to source node flows and data flows. The details of the flows are determined
of the next term, (target (e0 ) = source (e1 )) ∧ . . . ∧ with the following definitions.
(target (en−1 ) = source (en )). Definition 4: A data flow, dfi = hτsrc , dsrc , τtrg , dtrg i ∈
• paths (vi , vk ) = {path1 (vi , vk ) , path2 (vi , vk ) , . . .} DF where τsrc , τtrg ∈ T , dsrc ∈ OCτsrc , dtrg ∈ ICτtrg , is
represents all different ways between the given two nodes. a type of flow that is used for data migration between two
This definition uses two functions for each edge e ∈ E: tasks. It transmits the value of the source task(τsrc )’s output
source (e) = vm where vm ∈ V represents the source vertex item (dsrc ) to the target task(τtrg )’s input item (dtrg ) after
of e and target (e) = vn where vn ∈ V represents the target the source task performed.
vertex of e. Data flows are important to supply inputs to the tasks. So,
Semantics of the workflow graph model, which extends the to supply the inputs safely, we define some constraints on
directed graph represented formally above, is defined below data flows. Before declaring these constraints, we define two
by giving details of the model’s building blocks. supportive functions, inData and outData, as below:
Definition 2: wfg, which is a tuple hT,C,CF, DF,ICwf g , outData (dsrc ) = {df : df ∈ DF ∧ sourceItem (df ) =
OCwf g ,T N i, expresses a workflow graph that consists of dsrc } where dsrc is a data item, returns the set of data flows
set of tasks T, set of flows CF and DF which represent whose source data item is dsrc .
control flow and data flow sets respectively, input and output inData (dtrg ) = {df : df ∈ DF ∧ targetItem (df ) = dtrg }
containers ICwf g and OCwf g , set of coordinators C, and set where dtrg is a data item. It returns the set of data flows
of terminal nodes T N . whose target is dtrg .
The workflow graph as mentioned previously is derived from sourceItem and targetItem functions are similar to
the directed graph. So, when looked through the directed graph source and target functions, but they are used to retrieve
perspective, some entities of workflow graph, such as tasks, the data items bound by the specified data flow.
coordinators and terminal nodes, are sub-sets of the vertex set: Now, we can describe the constraints on data flows using
T, C, T N ⊂ V . Also, CF and DF are specialized entities of these functions:
workflow that are sub-sets of directed edge set: CF, DF ⊂ E. • (C) There should not be more than one
data flow between any two data items:
Definition 3: An element of task set is formally defined as ∀dsrc , dtrg (|outData (dsrc ) ∩ inData (dtrg )| ≤ 1)
• (C) Data type of the target task’s input item must be the purpose of implementing these structures. These special
equal or subsume the type of the source task’s output nodes named as coordinator nodes, will be defined next.
item: ∀df ∈ DF typedsrc ⊆ typedtrg Definition 6: Here, we define all sub-sets of coordinators,
As we mentioned above, a data flow expresses the direction C, together. There are four types of coordinator nodes; choice,
of the data item migration. Differently from the data flow, on merge, fork, synchronizer; CH, M R, F R, SY ⊂ C ⊂ V .
the other hand, a control flow is used to specify the execution • A choice node, chi = hnch , dcond i ∈ CH, has more than
sequence of task nodes in a workflow graph. one outgoing flows and contains a condition input dcond
Definition 5: A control flow is a tuple, cfi = hvsrc , vtrg i ∈ to select a branch.
CF , consisting of source vertex (vsrc ) and target vertex (vtrg ). • A merge node, mri ∈ M R, has more than one incoming
Control flows are more decisive than data flows on process branches and it is used to join the mutually exclusive
of workflows. To avoid inconsistencies, control flows must paths which are split by a choice node.
be constructed according to some defined constraints. Before • A fork node, f ri ∈ F R, has more than one outgoing
declaring these constraints on our workflow model, we de- flows and enables all of them at the same time.
scribe two supportive functions, inControl and outControl, • A synchronizer node, syi ∈ SY , has more than one
to make the constraints more understandable: incoming flows, which are activated concurrently by a
inControl(n) = {cf : cf ∈ CF ∧ target (cf ) = n} where n fork node, and waits all to be finished. In other words,
∈ V , acquires the set of control flows whose target node is n. it synchronizes the concurrent execution paths within a
outConrol(n) = {cf : cf ∈ CF ∧ source (cf ) = n} where workflow.
n ∈ V , returns the set of control flows whose source is n. The coordinator nodes are used in pairs to construct exclusive
Now, we can specify the constraints using these functions: choice and parallel split workflow patterns[18]. The exclusive
• (C) All flows must have two different nodes connected choice pattern creates a divergence point into two or more
to their two sides. ∀f ∈ E (source (f ) 6= target (f )) branches such that only one of which is selected for the exe-
• (C) A task have to be source or target of only one control cution. The parallel split pattern, on the other hand, provides
flow. ∀τ ∈ T (|inControl(τ )| = 1 ∧ |outControl(τ )| = concurrent execution paths which are activated simultaneously.
1∧inControl (τ ) 6=outControl (τ )) An exclusive choice is constructed with a hchi , mri i pair,
• (C) There should not be more than one direct con- while a hf ri , syi i pair composes a parallel split.
trol flow between any two nodes. ∀vm ∈ V, ∀vn ∈ As is clearly stated, the coordinator nodes are required to
V (|outControl (vn ) ∩ inControl (vm )| ≯ 1) build workflows including complex patterns. But misusage of
• (C) The source node of a control flow must be the coordinators may result in defected workflows. Therefore,
ahead of the target node in the order of execution. the following constraints should be defined on the coordinator
∀vm , ∀vn ((path(vm , vn ) 6= ∅) → (outControl (vn ) ∩ nodes to provide a consistent workflow.
inControl(vm ) = ∅)). As an exception, in an iteration • (C) Since the aforementioned workflow patterns are con-
structure, one of the outgoing flows of a choice node structed using coordinator pairs, there must exist a merge
goes to the preceding merge node. node for each choice node, and a synchronizer node for
Although the constraints on control and data flows help to each fork node. These two constraints could be expressed
build consistent work flows, they are not enough. Control and by f : CH → M R and g : F R → SY functions, which
data flows also must be compatible with each other in terms are one-to-one and onto, respectively.
of workflow direction. • (C) All choice and fork nodes have one incoming
• (C) Since a data flow transmits the data from the source and more than one outgoing flows. ∀n ∈ F R ∪
node to the target node, the source node must be finished CH ((|inControl(n)| = 1) ∧ (|outControl(n)| > 1))
before the target node starts. Therefore, the source node • (C) All synchronizer and merge nodes have at least two
must always precede the target node within the workflow incoming flows and only one outgoing flow. ∀n ∈ SY ∪
in terms of execution sequence. M R ((|inControl(n)| > 1) ∧(|outControl(n)| = 1))
∀τm , ∀τn ((path (τm , τn ) 6= ∅) → outData (τn ) ∩ (in− The node definitions made so far specify the intermediate
Data (τm ) = ∅)) nodes. In other words, we did not give any definition of
∀τm , ∀τn ((outData (τm ) ∩ inData (τn ) 6= ∅) → (path nodes which represents the end points of the workflow up
(τm , τn ) 6= ∅)) to now. The following definition, on the other hand, explains
inData(τ ) = {df : df ∈ DF ∧ target(df ) = τ } where the terminal nodes, T N = {vi , vf }, used for this purpose.
τ ∈ T , returns the set of data flows whose target is τ . Definition 7: Initial node, vi ∈ V , represents the beginning
outData(τ ) = {df : df ∈ DF ∧ source(df ) = τ } of the workflow, while the final node, vf ∈ V , represents the
where τ ∈ T , returns the set of data flows whose source end, wf gn = (vi , {τ1 , τ2 , . . . , τn } , {c1 , c2 , . . . , cn } , vf ).
is the given task. • (C) vi is the first node of the wf gn , it has
Data migration on the workflow and execution ordering of no incoming but only one outgoing control flow:
the tasks can be provided easily via flows. But they are not ∀vi ((inControl (vi ) = ∅) ∧ (|outControl (vi )| = 1))
sufficient when some complex structures, which come from • (C) vf is the last node of the wf gn , it has
the nature of the workflow, such as concurrency, alternation only one incoming but no outgoing control flow:
and iteration, are considered. We need some special nodes for ∀vf ((inControl (vf ) = 1) ∧ (outControl (vf ) = ∅))
• (C) Each workflow graph contains exactly one initial and Within a workflow, P corresponds an input container and each
one final node. data item in it represents a provision. Therefore, it provides
∀wf g (wf g ∈ W F G → wf g 3 vi ∧ wf g 3 vf ) the data which is required for starting the task’s execution and
whose value can be obtained from an outcome of the preceding
IV. S EMANTICS OF SEAGENT HTN task or from an external resource.
Definition 13: An outcome, oi = hnoi , typeoi , valueoi i ∈
Previously, we gave semantics of our workflow model. Our O, represents the data which is produced during execution.
approach, as mentioned in the introduction, is to design and Some tasks gather information, which is represented by out-
implement a planner architecture that enables to execute dif- comes, during execution. They can be passed to needer tasks.
ferent planning paradigms and workflow definition languages O corresponds the output container, which consists of data
in the same agent architecture. Due to this purpose, we choose items that represents outcomes, of a task within a workflow.
HTN paradigm, mostly used planning paradigm in the agent Definition 14: A state (or outcome state), si ∈ S, is a label
literature. on a link specifying that the branch will be executed in which
Semantics of HTN is firstly articulated by Kutluhan et al. condition.
in [3]. In his model, HTN is closer to AI problem solving. State instances are used to construct branching or concurrency
For the purpose of using HTN in web agent programming, structures within plans. In detail, outgoing links with distinct
Sycara et al. reformed it in [4]. They contributed the link outcome state results in an exclusive choice pattern, while the
concept to provide a unified information and control flow same outcome states form a parallel split.
within plans. Although that contribution makes HTN plans Definition 15: ST = {θ1 , θ2 , . . . , θi } indicates the set of
more tractable, it allows designing error-prone plans. Our HTN subtasks of a behavior.
model is a detailed revision of Sycara et al.’s that is extended A constraint on subtasks is revealed below.
by exhaustive link definitions and constraints that permit to
• (C) A task can be child of exactly one behavior (except
avoid designing erroneous plans. Base concept of our HTN
the root behavior which represents the HTN plan). In
model is task;
other words, a task can be included by only one ST .
Definition 8: An HTN task, θi = hnθi , Pθi , Oθi i ∈ Θ, is
∀θ ∈ Θ (θ ∈ STβm → θ ∈ / STβn )
generalization of the primitive task (action) and the compound
task (behavior), A ⊂ Θ, B ⊂ Θ. Up till now, we have mentioned about the HTN actions,
A task encapsulates the common properties of behaviors and behaviors and relation between a behavior and its subtasks.
actions, such as provisions, outcomes, and name. But they are For the rest of this section, link definitions, which forms
distinguished by other properties explained below. control and information flows between tasks, will be given.
For that purpose, we define the link set, Γ, that is the super
Definition 9: A behavior, βi = hnβi , Pβi , Oβi , STβi , Γβi i
set of provision, order, inheritance and disinheritance links,
∈ B, represents a compound task which encloses other tasks.
P L, OL, IL, DL ⊂ Γ.
A behavior (βi ) corresponds to a workflow graph (wf g)
that has sub nodes which may be primitive actions or other • (C) An important constraint on links: The source and
behaviors. In the definition, a behavior consists of name, the target task of a link must be different: ∀l ∈
provisions, outcomes, subtasks, and subtask links respectively. Γ (source (l) 6= target (l))
nβi is a label that distinguishes the behavior from the others. Here we define two functions that are used in determining the
Since a behavior is a compound task, it cannot be performed details of links: For ∀θ ∈ Θ
directly. It must be decomposed to its primitive actions whose inLink (θ) = {link : (link ∈ Γ) ∧ (target(link) = θ)}
executions contribute toward accomplishment of the behavior. outLink (θ) = {link : (link ∈ Γ) ∧ (source(link) = θ)}
As mentioned, there are four types of link: provision link,
Definition 10: An action, αi = hnαi , Pαi , Oαi , λαi i ∈ A, order link, inheritance link and disinheritance link. While
is a primitive task that is executed directly. It corresponds an provision links coincide with both data and control flows,
indecomposable workflow task node. order links correspond to control flows only. Inheritance and
An action consists of name, provisions, outcomes, and a disinheritance links are data flows between a behavior and
function. nαi is a label that distinguishes the action from the its subtasks. Here, the formal definitions of links and their
others. Because actions are executable entities within a plan, constraints are given with necessary logical functions.
they must implement a function, λαi , which fulfills the actual Definition 16: An order link, oLinki = hθsrc , θtrg , si ∈
work of the action. OL, represents a control flow between two tasks and it
Definition 11: A parameter, πi = hnπi , typeπi i ∈ Π, designates the execution order.
stands for data which is needed or produced by tasks. A Order links consist of source task, target task, and state. By
parameter πi consists of name (nπi ) and type (typeπi ). using order links and states together, we can create plans
The parameter is an abstract concept that cannot be seen in including conditional branching and parallel execution paths.
an HTN plan. Parameter is generalization of provision and • (C) Source and target tasks of an order link must be
outcome, P ⊂ Π , O ⊂ Π. The definitions of these concepts included in the same subtask list. In other words, an order
are given below. link can connect two tasks if both are the subtask of the
Definition 12: A provision, pi = hnpi , typepi , valuepi i ∈ same behavior. ∀link ∈ OL(source(link) ∈ STβn ↔
P , represents the data which is needed for execution of task. target(link) ∈ STβn )
• (C) At most one order link can be con- • (C) Each provision of the root behavior must be
structed between two tasks. ∀θsrc , ∀θtrg bound with at least one inheritance link. ∀p ∈ Pβroot
(|(outLink (θsrc ) ∈ OL) ∩ (inLink (θtrg ) ∈ OL)| ≤ 1) (|(outLink (p) ∩ IL)| > 0) where βroot ∈ B.
We define a generalized concept, parameter link (πL),where Definition 19: A disinheritance link, dLinki = hθsrc , βtrg ,
P L, DL, IL ⊂ ΠL, for the rest of link types: inheri- os , ot i ∈ DL, represents a parameter transfer from a task to
tance, disinheritance and provision links. All these links parent behavior. It corresponds to a data flow from a subtask
constructs data flows between the tasks by mapping the to the final node of a workflow.
source and the target parameter of these tasks. A significant Disinheritance link consists of source task, target behavior,
point about the parameter mapping is compatibility of the an outcome of source sub task, and an outcome of target
parameter types: ∀πL ∈ ΠL (type (sourceP aram (πL)) ⊆ behavior. Source task of a disinheritance is child of the target
type (targetP aram (πL))) where sourceParam and target- task, βtrg ∈ B and θsrc ∈ STβtrg .
Param functions are used to retrieve the source and the target • (C) Source and target parameter of a disinheri-
parameter of the parameter link respectively. tance link must be an outcome. ∀dl ∈ DL
Two definitions below specify two supportive functions that ((sourceP aram(dl) ∈ O) ∧ (targetP aram(dl) ∈ O))
are used to get incoming and outgoing parameter links which • (C) At most one disinheritance link can be con-
are used to bind the given parameter. These functions will help structed between the same outcome pairs. ∀osrc , ∀otrg
to describe the later definitions. (|outLink (osrc ) ∩ inLink (otrg ) ∩ DL| ≤ 1)
inLink (π) = {πL : (πL ∈ ΠL) ∧ (targetP aram(πL) = • (C) A disinheritance link must be provided for each
π)} where ∀π ∈ Π. outcome of a behavior to collect all outcomes from the
outLink (π) = {πL : (πL ∈ ΠL)∧(sourceP aram(πL) = sub-tasks. If there is an exclusive choice structure, a
π)} where ∀π ∈ Π. disinheritance link must be constructed for all exclusive
Definition 17: A provision link, pLinki = hθsrc ,θtrg ,os , paths to fulfill all outcomes of the behavior. ∀βi ∈ B (∀on
pt ,si ∈ P L, represents a data and a control flow between ∈ Oβi (|inLink (on ) ∩ DL| > 1))
two tasks.
A provision link binds an outcome of the source task and a V. T RANSFORMATION OF HTN INTO W ORKFLOW
provision of the target task. If a conditional branching occurs
To implement our approach about executing different plan-
after the source task, the outcome state of the link (s) maps
ning paradigms and workflow definition languages in the same
a particular branching condition to the target task.
agent architecture, HTNReducer, which is a component of the
• (C) Source and target tasks of a provision link must Reducers submodule as mentioned in Section II, is used to
be the child of the same behavior. ∀pLink ∈ P L transform an HTN definition into a workflow before execution.
(source (pLink) ∈ STβn ↔ target (pLink) ∈ STβn ) In this section, this transformation process is introduced within
• (C) Source parameter of a provision link must be an out- the scope of our workflow-based HTN planner.
come and target parameter must be a provision. ∀pl ∈ P L
((sourceP aram(pl) ∈ O) ∧ (targetP aram(pl) ∈ P )) Algorithm 1 Reduction of an HTN behavior to a workflow
• (C) At most one provision link can be constructed
Input: an HTN behavior β.
between the same outcome-provision pair. ∀osrc , ∀ptrg Output: a workflow wf g.
(| (outLink (osrc ) ∩ P L) ∩ (inLink (ptrg ) ∩ P L) | ≤ 1)
1) Initiate a workflow graph wf g corresponding to β.
• (C) Either an order link or a provision link can be
2) Create the nodes corresponding to the subtasks of β.
constructed between two tasks.
a) If subtask is an HTN behavior, then apply the
∀θsrc , ∀θtrg ((outLink (θsrc ) ∩ inLink (θtrg ) ∩ OL 6= ∅) → same process from step 1 and create a complete
(outLink (θsrc ) ∩ inLink (θtrg ) ∩ P L = ∅)) subworkflow for the subbehavior.
∀θsrc , ∀θtrg ((outLink (θsrc ) ∩ inLink (θtrg ) ∩ P L 6= ∅) → b) For an HTN action, otherwise, create a primitive
(outLink (θsrc ) ∩ inLink (θtrg ) ∩ OL = ∅)) workflow task node.
3) Construct flows between workflow tasks in wf g.
Definition 18: An inheritance link, iLinki = hβsrc , θtrg , 4) Put required coordinator nodes to junction points.
ps , pt i ∈ IL, represents a parameter link between a behavior
and one of its subtasks. It corresponds to a data flow from the
initial node of a workflow to a subtask.
Inheritance link consists of source behavior, target task, a A. Reduction Algorithm
provision of source behavior, and a provision of target sub Based on the formal definitions in Section III and Section
task. βsrc ∈ B and θtrg ∈ STbsrc . IV, we have developed an algorithm shown in Algorithm-1 for
• (C) Source and target parameter of an reducing a behavior description to the corresponding workflow.
inheritance link must be a provision. ∀il ∈ IL For this purpose, the HTN reduction algorithm constructs a
((sourceP aram (il) ∈ P ) ∧ (targetP aram (il) ∈ P )) part of the graph in a few steps. It begins the process with
• (C) At most one inheritance link can be con- creating an empty graph, which consists of initial and final
structed between the same provision pairs. ∀psrc , ∀ptrg nodes, and the data containers only, for the behavior. Then, it
(|outLink (psrc ) ∩ inLink (ptrg ) ∩ IL| ≤ 1) creates workflow task nodes for the subtasks of the behavior
and adds them into the empty graph. After the subtask nodes
are added to the graph model, the next step is constructing
the flows between these nodes. Finally, the last step of the
reduction process, which follows the flow construction, is
placing the coordinator nodes to the required locations within
the graph. The steps of the algorithm are elaborated below.
In step 2, a node is created for each subtask of the given
behavior according to its type. If the subtask is an HTN
action, a primitive task node is constructed together its data
containers. Otherwise, for an HTN behavior, the reduction
process is achieved for this behavior and a graph model is
created. The point to take into consideration is recursion while
creating subnodes of workflow. By means of this recursion a
sub-behavior is reduced prior to its parent.
As previously mentioned, the next step following the sub-
task creation is connecting the flows between these nodes. To
do this, appropriate flow(s) for each link that is defined by the
behavior description is constructed. The link type specifies the
flow type and end nodes of the flow. For an inheritance link,
a data flow from the initial node of the graph (iwf g ) to the
target task of the link is constructed. A disinheritance link
corresponds to a data flow between the source task of the link
and the final node of the graph (fwf g ). For order links and
provision links, on the other hand, a control flow is constructed
for each. In addition to the control flow, a data flow is also
constructed for a provision link.
After the flow construction phase, we obtain a raw graph
model that consists of only task nodes and flows between them.
There is no coordination component in this model. The last
step of the algorithm, in line 4, overcomes this lack by placing
the coordinators to the appropriate locations within the graph.
To do this, the divergence and convergence points are marked
with special nodes and then these special nodes are replaced
with suitable coordinator nodes.
As a result, at the end of the reduction process, we obtain Figure 2. Reduction of Primitive HTN Patterns
a complete workflow graph corresponding to the given HTN
behavior. The graph contains task nodes that are connected
with the flow objects, and the coordinator nodes that determine h0 T 20 , {pτ2 } , {oτ2 }i , h0 T 30 , {pτ3 } , {oτ3 }i}
the flow of execution. • The control flow, CFwf1 = {hiwf1 , τ1 i , hτ1 , τ2 i ,
The outputs of our algorithm for primitive HTN patterns hτD1 , τ3 i , hτ2 , fwf1 i , hτ3 , E
fwf1 i}, and data flow DFwf1 =
are represented in Figure-2. These patterns are composed of { iwf1 , dinwf , τ1 , dinτ1 , hτ1 , doutτ1 , τ2 , dinτ2 i, hτ1 ,
1
behaviors which have only primitive subtasks and other build- doutτ1 , τ3 , dinτ3 i, hτ2 , doutτ2 , fwf1 , doutwf1 i, hτ3 , doutτ3 ,
ing blocks of HTN. Since plans, which have only primitive fwf1 , doutwf1 i} sets are filled in line 3.
subtasks, can be defined by assembling these patterns, adding • Finally, a fork-synchronizer node pair is inserted
new actions to them and constructing new links between to required points, in line 4. This operation fills
actions, they can be transformed into workflows. the coordinator node set Cwf2 = {f r1 , sy1 } and
To understand the reduction process better, we explain it by updates the control flow set CFwf1 = {hiwf1 ,
demonstrating one of primitive patterns. (see Figure-2(F)) The τ1 i, hτ1 , f r1 i , hf r1 , τ2 i , hf r1 , τ3 i , hτ2 , mr1 i , hτ3 , mr1 i ,
input behavior can be represented as β1 = h0 BH10 , {pβ1 } , hmr1 , fwf1 i}.
{oβ1 } , {α1 , α2 , α3 } , {pLink1 , pLink2 }i where α1 =
h0 AC10 ,{pα1 } ,{oα1 } ,λα1 i, α2 = h0 AC20 ,{pα2 } ,{oα2 } ,λα2 i,
α3 =h0 AC30 ,{pα3 } ,{oα3 } ,λα3 i and pLink1 =hα1 ,α2 ,oα1 , B. Correctness of Reduction
pα2 ,0 S10 i, pLink2 = hα1 , α3 , oα1 , pα3 ,0 S10 i. Theorem 1: Let β is a behavior defined with HTN seman-
• At the start, an empty workflow wf1 = h∅, ∅, {hiwf1 , tics. REDU CE (β) terminates and returns a workflow wf .
fwf1 i}, ∅, ∅, ∅, {iwf1 , fwf1 }i is created, in line 1. Proof: A behavior represents a tree, and is reduced
• In the next step, in line 2, the actions are con- completely after all subtasks are reduced. So, from the line
verted to primitive workflow tasks and these tasks are 2a of algorithm, the algorithm is executed over again for
inserted to task set: Twf1 = {h0 T 10 , {pτ1 } , {oτ1 }i, subbehaviors until reaching to the leaf actions. Finally, after
the leaves are transformed in line 2b, algorithm proceeds and From our hypothesis we know that we have
bottom-up construction of root behavior is achieved. corresponding workflow tasks τ1 , τ2 , τ3 of the HTN
Theorem 2: Let B = {β1 , β2 , . . . , βn } be a collection of tasks θ1 , θ2 , θ3 . The behavior β is reduced to a
HTN behaviors that conforms our constraints and β be one of workflow wf = hTwf , Cwf , CFwf , ∅, ∅, ∅, T Nwf i where
these. Let wf g = REDU CE (β), then wf g is the workflow Twf = {τ1 , τ2 , τ3 }, Cwf = {f r1 , sy1 } and CFwf =
which corresponds to behavior β. {hiwf , τ1 i , hτ1 , f r1 i , hf r1 , τ2 i , hf r1 , τ3 i , hτ2 , sy1 i , hτ3 , sy1 i ,
Proof: The proof of the theorem is by induction: hsy1 , fwf i}. In line 4, fork and synchronizer nodes are inserted
Hypothesis For an HTN behavior β, there exists a workflow to the beginning and the end of the parallel split structure in
graph wf = hTwf , Cwf , CFwf , DFwf , ICwf , OCwf , T Nwf i the raw workflow.
where Twf contanins the workflow tasks corresponds to sub We proved that our reduction mechanism transforms the HTN
tasks of β, CFwf and DFwf contains the flows corresponds plan into the workflow model correclty. In our proof, we
to links of HTN, and ICwf and OCwf contains inputs and showed the correspondence of the result workflow to the input
outputs which corresponds to provisions and outcomes of β. plan.
Base Case Suppose β is a behavior with only one action
α1 as sub task. The reduction of β ends up with a workflow VI. C ASE S TUDY
wf = hTwf , ∅, CFwf , ∅, ∅, ∅, T Nwf i where Twf = {τ1 } and To illustrate the reduction of plans to workflows, a tourism
CFwf = {hiwf , τ1 i , hτ1 , fwf i}. As is seen in line 2b, after application is implemented as a case study with SEAGENT
workflow is created in line 1, τ1 is constructed for α1 and Framework. In this application an agent which plays tourism
then it is connected with iwf and fwf in line 3. (see Figure- agency role is responsible for making a vacation plan. A plan
2(A)) ontology (BHPlanVacation) which is the implementation of
Inductive Step Besides the sequence structure in HTN, planning a vacation goal (PlanVacation) is provided in the
there exists a few structures such as nesting, conditional knowledgebase of this agent.
branching and parallelism. We will analyze each of the struc- Ontology3 individual of BHPlanVacation is depicted in
tures case by case to show that results of our translation are Figure-5(B). BHPlanVacation behavior has three subtasks, and
correct. it needs location information (location provision) and vacation
Case 1: While HTN plans can only be extended breadth- budget (budget provision) to make plan. After the execution of
wise with primitive subtasks, expansion in depth is provided the behavior is completed, it gathers the remainder of budget
with subbehaviors. (see Figure-3) (remainder outcome). Firstly, a hotel room is booked in spec-
ified holiday resort (ACBookHotelRoom), and remainder from
budget is passed to the next task. After reservation operation,
a travel ticket is bought according to the customer request
(BHBuyTravelTicket). Finally, a car is rented to go to the hotel
from the airport or terminal (ACRentCar), and the remainder
value is passed to the parent behavior. Representation of the
plan which is designed according to our HTN definitions in
Figure 3. Reduction of nested behavior SEAGENT HTN Editor4 is shown in Figure-5(A).
Suppose β is a behavior with a subbehavior βsub . From our
hypothesis we know that there exists a workflow wfsub for
subbehavior βsub . The reduction of β leads to a workflow
wf = hTwf , ∅, CFwf , ∅, ∅, ∅, T Nwf i where Twf = {wfsub }
and CFwf = {hiwf , wfsub i , hτ1 , wfsub i}.
Case 2: Suppose β = h0 BH10 , ∅, ∅, {θ1 , θ2 , θ3 } , Γβ1 i,
where Γβ1 = {hθ1 , θ2 ,0 S10 i , hθ1 , θ3 ,0 S20 i}, is a behavior with
a conditional branching structure. (similar to Figure-2(E))
From our hypothesis we assume that we have valid
workflow tasks τ1 , τ2 , τ3 which correspond to the
HTN tasks θ1 , θ2 , θ3 . The behavior β is reduced to a Figure 4. WFPlanVacation workflow
workflow wf = hTwf , Cwf , CFwf , ∅, ∅, ∅, T Nwf i where
Twf = {τ1 , τ2 , τ3 }, Cwf = {ch1 , mr1 } and CFwf = When agent determines to execute the PlanVacation goal,
{hiwf , τ1 i , hτ1 , ch1 i , hch1 , τ2 i , hch1 , τ3 i , hτ2 , mr1 i , hτ3 , mr1 i , gives the goal description to the planner. After the plan-
it
hmr1 , fwf i}. After raw graph is obtained, choice and merge ner ascertains that the goal is atomic, it searches for the
nodes are inserted to the beginning and the end of the appropriate act in the knowledgebase via the ActMatcher. The
exclusive choice structure in line 4. ActMatcher finds the BHPlanVacation HTN description and
0 0
Case 3: Suppose β = h BH1 , ∅, ∅, {θ1 , θ2 , θ3 } , Γβ1 i, 3 Full version: http://www.seagent.ege.edu.tr/etmen/LADS009CaseStudy.zip
where Γβ1 = {hθ1 , θ2 ,0 S10 i , hθ1 , θ3 ,0 S10 i}, is a behavior with 4 HTN Editor is a part of the SEAGENT Development Environment that is
a parallelism structure. (similar to Figure-2(F)) used to build up HTN ontologies easily.
Figure 5. BHPlanVacation A) HTN Representation B) Ontology Individual
transmits it to the HTNReducer to reduce it to workflow. After R EFERENCES
the HTNReducer completes reduction, the generated workflow [1] T. Andrews, F. Curbera, H. Dholakia, Y. Goland, J. Klein, F. Leymann,
is the executable form of the plan description. The workflow K. Liu, D. Roller, D. Smith, S. Thatte, I. Trickovicand, and S. Weer-
which is constructed by HTNReducer is shown in Figure-4. awarana, “Business process execution language for web services v-1.1,”
W3C, Candidate Recommendation, 2003.
As is seen in the Figure-4, the workflow tasks are created [2] WfMC, “Workflow management coalition workflow standard: Workflow
for all actions of plan and the subbehavior is converted to process definition interface - xml process definition language (xpdl)
subworkflow. After the workflow that corresponds to BHPlan- (wfmc-tc-1025),” Workflow Management Coalition, Lighthouse Point
(FL), Tech. Rep., 2002.
Vacation is constructed, the planner starts to proceed on the [3] K. Erol, J. Hendler, and D. S. Nau, “Semantics for hierarchical task-
workflow via the ExecutionToken. Tasks are performed when network planning,” College Park, MD, USA, Tech. Rep., 1994.
the token visits them. Execution of a task means execution of [4] K. Sycara, M. Williamson, and K. Decker, “Unified information and
control flow in hierarchical task networks,” in Working Notes of the
the java class that is attached to the corresponding HTN action. AAAI-96 workshop ’Theories of Action, Planning, and Control’, 1996.
Java reflection API is used to create and execute action class [5] W. Sadiq and M. Orlowska, “Modeling and verification of workflow
instances. graphs,” in Technical Report No. 386, Department of Computer Science.
The University of Queensland, Australia, 1996.
[6] E. Sirin, B. Parsia, D. Wu, J. A. Hendler, and D. S. Nau, “Htn planning
for web service composition using shop2,” J. Web Sem., vol. 1, no. 4,
VII. C ONCLUSION pp. 377–396, 2004.
This paper briefly depicts the architecture of SEAGENT [7] G. Caire, D. Gotta, and M. Banzi, “Wade: a software platform to
develop mission critical applications exploiting agents and workflows,”
agent development framework’s planner. The main character- in AAMAS (Industry Track), 2008, pp. 29–36.
istic of the proposed architecture is its being based on the [8] A. P. F. Bellifemine and G. Rimassa, “JADE - a FIPA-compliant agent
workflow technology and its ability to process the artifacts of framework,” in Proceedings of the Practical Applications of Intelligent
Agents, 1999.
agent programming paradigms such as plans, services, goals, [9] E. E. Ekinci, A. M. Tiryaki, Ö. Gürcan, and O. Dikenelli, “A planner
and roles by executing these artifacts after reducing them to infrastructure for semantic web enabled agents,” in OTM Workshops,
workflows. 2007, pp. 95–104.
[10] O. Dikenelli, “Seagent mas platform development environment,” in
To implement the ideas behind the proposed architecture, we AAMAS (Demos), 2008, pp. 1671–1672.
described an HTN ontology to define agent plans, developed a [11] J. R. Graham, K. Decker, and M. Mersic, “Decaf - a flexible multi agent
workflow component using Java, and focused on the reduction system architecture.” Autonomous Agents and Multi-Agent Systems,
vol. 7, no. 1-2, pp. 7–27, 2003.
of agent plans to workflows. We used this planner architecture [12] K. P. Sycara, M. Paolucci, M. V. Velsen, and J. A. Giampapa, “The
in industrial and academical projects. The last version of the retsina mas infrastructure,” Autonomous Agents and Multi-Agent Sys-
SEAGENT can be downloaded5 as an open source project. tems, vol. 7, no. 1-2, pp. 29–48, 2003.
[13] W. M. P. van der Aalst, “The application of petri nets to workflow
SEAGENT planner has been designed with the idea that management,” Journal of Circuits, Systems, and Computers, vol. 8, no. 1,
different plan definition languages other than HTN can also pp. 21–66, 1998.
[14] S. W. Sadiq, M. E. Orlowska, W. Sadiq, and C. Foulger, “Data flow and
be reduced to the generic workflow model. In addition, busi- validation in workflow modelling,” in ADC, 2004, pp. 207–214.
ness process definition languages such as BPEL, OWL-S can [15] W. Sadiq and M. E. Orlowska, “Analyzing process models using graph
also be reduced to the generic workflow model. Moreover, reduction techniques,” Inf. Syst., vol. 25, no. 2, pp. 117–134, 2000.
[16] J. Davis, W. Du, and M.-C. Shan, “Openpm: An enterprise process
these business process definition languages can be used in management system,” IEEE Data Eng. Bull., vol. 18, no. 1, pp. 27–
connection with different plan definition languages providing 32, 1995.
the interoperability of them. These features show the way [17] W. Du, J. Davis, and M. C. Shan, “Flexible specification of workflow
compensation scopes,” in GROUP ’97: Proceedings of the international
of incorporating different languages into agent programming ACM SIGGROUP conference on Supporting group work. New York,
paradigms as well as offering a high degree of flexibility in USA: ACM, 1997, pp. 309–316.
developing agent systems. [18] B. K. W.M.P van der Aalst, A.H.M. ter Hofstede and A. Barros,
“Workflow patterns,” in Distributed and Parallel Databases, July 2003,
5 SEAGENT Semantic Web Enabled Framework, http://seagent.ege.edu.tr/ pp. 5–51.