-In this paper, we introduce an agent planner ar- the meta-level. Second, a common model that will form a comchitecture 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 amceoamnsmoofnawwoorkrkflfloowwmcoodmepl.oTnhenestetahrattiftahcetsaarrcehittheecntuerxeeicnuctleuddebsy. 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. iTdoeaesx,pwliecaftoecuthseornedthuectrieodnumcteiocnhaonfispmla,nwsetohtahvee wporerfkeflrorewdmtooduesle. 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. INTRODUCTION 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 serachieve 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
directly used in several agent development frameworks[
Remaining parts are organized as follows: Before giving the details of the reduction mechanism, we introduce current architecture of SEAGENT planner in Section II. In section III, details of our planner’s internal workflow structure, to which HTN plans and other process definition languages are reduced, are given. Soon after, we define our enhanced HTN semantics in section IV. In section V, the algorithm that achieves the reduction from HTN to Workflow model is given, and correctness of the reduction mechanism is discussed. Section VI includes a working example and Section VII the conclusion.
presented in Figure-1. As indicated in the figure, two vertical layers compose the overall architecture. The front layer, called Semantic Web Layer, uses ontological descriptions to represent the artifacts of the planning process. These ontology descriptions are: Goal, Role, HTN1 and OWL-S. The goal ontology defines the objectives which the agent intends to reach within the organization. It specifies abstract definitions for agent behaviors. The role ontology, on the other hand, puts the related goal definitions together within a role description. In addition, it also defines some constraints about the considered role. Roles and goals take in charge during planning process, and then the output plan is reduced to the workflow model. Our main interest is on reduction of plans, not on this plan decision process. The HTN ontology is used to describe the agent plans using HTN planning technique. Finally, OWL-S (Web Ontology Language for Services) is a part of our proposed architecture to support semantic services. As is seen in the figure, the planner, which composes the Execution Layer, consists of four modules: WorkflowElements, WorkflowEngine, Matchers, Reducers.
The WorkflowElements module contains building blocks of our graph structure which is used to represent the agent acts as a workflow at execution time. The graph structure is based on tasks, coordinators and flows, all of which are discussed in detail in Section III.
The WorkflowEngine module is responsible for performing a workflow instance and coordinating its execution. It consists of three submodules: ExecutionToken, LazyBinder, and GraphVerifier. The ExecutionToken is the major component for the execution which traverses the nodes of the workflow instance and executes tasks of workflow instance. The LazyBinder module was developed to support dynamic graph binding. It has a special abstract graph node called LazyTask which loads the concrete graph at runtime. This dynamic binding capability makes our workflow dynamically extendable. Thus, at run-time new goals and tasks can be appended based on the state of the environment and/or agent’s knowledge. Finally, the GraphVerifier module is responsible for verification of a workflow instance before it is given to the 1http://etmen.ege.edu.tr/etmen/ontologies/HTNOntology-2.1.4.owl execution. It verifies the syntactical structure of the workflow and data flow over this workflow instance.
Reducers, Matchers, and JENA2 form a bridge connecting the execution layer to the Semantic Web layer. The ontological definitions of the agent’s actions from the Semantic Web layer are read here, and converted to the corresponding workflows. The Reducers sub-package contains the graph reducer components (GoalReducer, HTNReducer, OWLSReducer) that parse Goal, HTN and OWL-S definitions and reduce them into the workflow. The other module, called Matchers, contains three submodules: RoleMatcher, GoalMatcher and ActMatcher. Role and goal matchers collaborate to find an appropriate goal description for an objective which the agent must fulfill. If a goal is matched with an objective, the description of the goal is given to the GoalReducer to reduce it into a goal workflow. During the execution of the goal workflow, an ActMatcher is invoked for each sub-goal to find an appropriate act (HTN plan or OWLS service) that accomplishes the sub-goal. After the ActMatcher returns the corresponding act description, a reducer (HTNReducer, or OWLSReducer) is selected to reduce the act description to the workflow.
In this paper, we only focus on the reduction of HTN plans to workflows. To specify our reducing process, workflow and HTN semantics are formally defined in the following sections. Next, reducer algorithm is illustrated in the section V.
been extensively researched in the academy and as a result of
these efforts this technology has reached to a high degree of
maturity. Widely acceptance of workflows in industrial settings
and standardization of workflow definition languages such as
BPEL, XPDL are the signs of this maturity degree. On the
other hand, from the execution perspective, several approaches
have raised up such as executing the workflows on
PetriNets[
Sadiq and Orlowska abstractly introduced the basic building
blocks of a workflow process using the graphical terms such as
nodes and flows in [
Besides the modeling workflows, they touch on reliability of
the workflow model in [
In this section, we semantically declare the concepts and
their constraints of our workflow implemetation. Before giving
semantics of our workflow model, we evoke to the reader that a
workflow is also a kind of directed graph[
Definition 1: Given directed graph is a tuple of g = hV; Ei, V = fv0; v1; : : : ; vng and E = fhvs; vti : vs; vt 2 V g.
2We use JENA (http://jena.sourceforge.net/) to read and manipulate the ontology documents in the knowledge-base and over the Internet. The directed graph represented with g consists of vertices i = hn i ; IC i ; OC i i 2 T . In detail, n i is the identifier of V and directed edges E. A vertex, v 2 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 2 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" = fd1; d2; : : : ; dig. 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 2 V and vk 2 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; dtrgi 2 paths (vi; vk) = fpath1 (vi; vk) ; path2 (vi; vk) ; : : :g DF where src; trg 2 T , dsrc 2 OC src , dtrg 2 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 2 E: tasks. It transmits the value of the source task( src)’s output source (e) = vm where vm 2 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 2 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;ICwfg; outData (dsrc) = fdf : df 2 DF ^ sourceItem (df ) = OCwfg;T N i, expresses a workflow graph that consists of dsrcg 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) = fdf : df 2 DF ^ targetItem (df ) = dtrgg containers ICwfg and OCwfg, 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 data flow Definition 3: An element of task set is formally defined as should not be more than between any two data 8dsrc; dtrg (joutData (dsrc) \ inData (dtrg)j (C) Data type of the target task’s input item must be equal or subsume the type of the source task’s output item: 8df 2 DF typedsrc typedtrg As we mentioned above, a data flow expresses the direction of the data item migration. Differently from the data flow, on the other hand, a control flow is used to specify the execution sequence of task nodes in a workflow graph.
Definition 5: A control flow is a tuple, cfi = hvsrc; vtrgi 2 CF , consisting of source vertex (vsrc) and target vertex (vtrg).
Control flows are more decisive than data flows on process of workflows. To avoid inconsistencies, control flows must be constructed according to some defined constraints. Before declaring these constraints on our workflow model, we describe two supportive functions, inControl and outControl, to make the constraints more understandable: inControl(n) = fcf : cf 2 CF ^ target (cf ) = ng where n 2 V , acquires the set of control flows whose target node is n. outConrol(n) = fcf : cf 2 CF ^ source (cf ) = ng where n 2 V , returns the set of control flows whose source is n.
Now, we can specify the constraints using these functions: (C) All flows must have two different nodes connected to their two sides. 8f 2 E (source (f ) 6= target (f )) (C) A task have to be source or target of only one control flow. 8 2 T (jinControl( )j = 1 ^ joutControl( )j = 1^inControl ( ) 6=outControl ( )) (C) There should not be more than one direct control flow between any two nodes. 8vm 2 V; 8vn 2 V (joutControl (vn) \ inControl (vm)j 1) (C) The source node of a control flow must be ahead of the target node in the order of execution. 8vm; 8vn ((path(vm; vn) 6= ;) ! (outControl (vn) \ inControl(vm) = ;)). As an exception, in an iteration structure, one of the outgoing flows of a choice node goes to the preceding merge node.
Although the constraints on control and data flows help to build consistent work flows, they are not enough. Control and data flows also must be compatible with each other in terms of workflow direction.
(C) Since a data flow transmits the data from the source node to the target node, the source node must be finished before the target node starts. Therefore, the source node must always precede the target node within the workflow in terms of execution sequence. 8 m; 8 n ((path ( m; n) 6= ;) ! outData ( n) \ (in Data ( m) = ;)) 8 m; 8 n ((outData ( m) \ inData ( n) 6= ;) ! (path ( m; n) 6= ;)) inData( ) = fdf : df 2 DF ^ target(df ) = g where
2 T , returns the set of data flows whose target is . outData( ) = fdf : df 2 DF ^ source(df ) = g where 2 T , returns the set of data flows whose source is the given task.
Data migration on the workflow and execution ordering of the tasks can be provided easily via flows. But they are not sufficient when some complex structures, which come from the nature of the workflow, such as concurrency, alternation and iteration, are considered. We need some special nodes for the purpose of implementing these structures. These special nodes named as coordinator nodes, will be defined next.
Definition 6: Here, we define all sub-sets of coordinators, C, together. There are four types of coordinator nodes; choice, merge, fork, synchronizer; CH; M R; F R; SY C V .
A choice node, chi = hnch; dcondi 2 CH, has more than one outgoing flows and contains a condition input dcond to select a branch.
A merge node, mri 2 M R, has more than one incoming branches and it is used to join the mutually exclusive paths which are split by a choice node.
A fork node, f ri 2 F R, has more than one outgoing flows and enables all of them at the same time.
A synchronizer node, syi 2 SY , has more than one incoming flows, which are activated concurrently by a fork node, and waits all to be finished. In other words, it synchronizes the concurrent execution paths within a workflow.
The coordinator nodes are used in pairs to construct exclusive
choice and parallel split workflow patterns[
An exclusive choice is constructed with a hchi; mrii pair, while a hf ri; syii pair composes a parallel split.
As is clearly stated, the coordinator nodes are required to build workflows including complex patterns. But misusage of the coordinators may result in defected workflows. Therefore, the following constraints should be defined on the coordinator nodes to provide a consistent workflow.
(C) Since the aforementioned workflow patterns are constructed using coordinator pairs, there must exist a merge node for each choice node, and a synchronizer node for each fork node. These two constraints could be expressed by f : CH ! M R and g : F R ! SY functions, which are one-to-one and onto, respectively. (C) All choice and fork nodes have one incoming and more than one outgoing flows. 8n 2 F R [ CH ((jinControl(n)j = 1) ^ (joutControl(n)j > 1)) (C) All synchronizer and merge nodes have at least two incoming flows and only one outgoing flow. 8n 2 SY [
M R ((jinControl(n)j > 1) ^(joutControl(n)j = 1)) The node definitions made so far specify the intermediate nodes. In other words, we did not give any definition of nodes which represents the end points of the workflow up to now. The following definition, on the other hand, explains the terminal nodes, T N = fvi; vf g, used for this purpose.
Definition 7: Initial node, vi 2 V , represents the beginning of the workflow, while the final node, vf 2 V , represents the end, wf gn = (vi; f 1; 2; : : : ; ng ; fc1; c2; : : : ; cng ; vf ).
(C) vi is the first node of the wf gn, it has no incoming but only one outgoing control flow: 8vi ((inControl (vi) = ;) ^ (joutControl (vi)j = 1)) (C) vf is the last node of the wf gn, it has only one incoming but no outgoing control flow: 8vf ((inControl (vf ) = 1) ^ (outControl (vf ) = ;)) (C) Each workflow graph contains exactly one initial and one final node. 8wf g (wf g 2 W F G ! wf g 3 vi ^ wf g 3 vf )
approach, as mentioned in the introduction, is to design and implement a planner architecture that enables to execute different planning paradigms and workflow definition languages in the same agent architecture. Due to this purpose, we choose HTN paradigm, mostly used planning paradigm in the agent literature.
Semantics of HTN is firstly articulated by Kutluhan et al.
in [
Definition 8: An HTN task, i = hn i ; P i ; O i i 2 , is generalization of the primitive task (action) and the compound task (behavior), A , B .
A task encapsulates the common properties of behaviors and actions, such as provisions, outcomes, and name. But they are distinguished by other properties explained below.
Definition 9: A behavior, i = hn i ; P i ; O i ; ST i ; i i 2 B, represents a compound task which encloses other tasks. A behavior ( i) corresponds to a workflow graph (wf g) that has sub nodes which may be primitive actions or other behaviors. In the definition, a behavior consists of name, provisions, outcomes, subtasks, and subtask links respectively. n i is a label that distinguishes the behavior from the others. Since a behavior is a compound task, it cannot be performed directly. It must be decomposed to its primitive actions whose executions contribute toward accomplishment of the behavior.
Definition 10: An action, i = hn i ; P i ; O i ; i i 2 A, is a primitive task that is executed directly. It corresponds an indecomposable workflow task node.
An action consists of name, provisions, outcomes, and a function. n i is a label that distinguishes the action from the others. Because actions are executable entities within a plan, they must implement a function, i , which fulfills the actual work of the action.
Definition 11: A parameter, i = hn i ; type i i 2 , stands for data which is needed or produced by tasks. A parameter i consists of name (n i ) and type (type i ). The parameter is an abstract concept that cannot be seen in an HTN plan. Parameter is generalization of provision and outcome, P , O . The definitions of these concepts are given below.
Definition 12: A provision, pi = hnpi ; typepi ; valuepi i 2 P , represents the data which is needed for execution of task. Within a workflow, P corresponds an input container and each data item in it represents a provision. Therefore, it provides the data which is required for starting the task’s execution and whose value can be obtained from an outcome of the preceding task or from an external resource.
Definition 13: An outcome, oi = hnoi ; typeoi ; valueoi i 2 O, represents the data which is produced during execution. Some tasks gather information, which is represented by outcomes, during execution. They can be passed to needer tasks. O corresponds the output container, which consists of data items that represents outcomes, of a task within a workflow.
Definition 14: A state (or outcome state), si 2 S, is a label on a link specifying that the branch will be executed in which condition.
State instances are used to construct branching or concurrency structures within plans. In detail, outgoing links with distinct outcome state results in an exclusive choice pattern, while the same outcome states form a parallel split.
Definition 15: ST = f 1; 2; : : : ; ig indicates the set of subtasks of a behavior.
A constraint on subtasks is revealed below.
(C) A task can be child of exactly one behavior (except the root behavior which represents the HTN plan). In other words, a task can be included by only one ST . 8 2 ( 2 ST m ! 2= ST n ) Up till now, we have mentioned about the HTN actions, behaviors and relation between a behavior and its subtasks. For the rest of this section, link definitions, which forms control and information flows between tasks, will be given. For that purpose, we define the link set, , that is the super set of provision, order, inheritance and disinheritance links, P L; OL; IL; DL .
(C) An important constraint on links: The source and the target task of a link must be different: 8l 2 (source (l) 6= target (l)) Here we define two functions that are used in determining the details of links: For 8 2 inLink ( ) = flink : (link 2 ) ^ (target(link) = )g outLink ( ) = flink : (link 2 ) ^ (source(link) = )g As mentioned, there are four types of link: provision link, order link, inheritance link and disinheritance link. While provision links coincide with both data and control flows, order links correspond to control flows only. Inheritance and disinheritance links are data flows between a behavior and its subtasks. Here, the formal definitions of links and their constraints are given with necessary logical functions.
Definition 16: An order link, oLinki = h src; trg; si 2 OL, represents a control flow between two tasks and it designates the execution order.
Order links consist of source task, target task, and state. By using order links and states together, we can create plans including conditional branching and parallel execution paths. (C) Source and target tasks of an order link must be included in the same subtask list. In other words, an order link can connect two tasks if both are the subtask of the same behavior. 8link 2 OL(source(link) 2 ST n $ target(link) 2 ST n ) (C) At most one order link can be constructed between two tasks. 8 src; 8 trg (j(outLink ( src) 2 OL) \ (inLink ( trg) 2 OL)j 1) We define a generalized concept, parameter link ( L),where P L; DL; IL L, for the rest of link types: inheritance, disinheritance and provision links. All these links constructs data flows between the tasks by mapping the source and the target parameter of these tasks. A significant point about the parameter mapping is compatibility of the parameter types: 8 L 2 L (type (sourceP aram ( L)) type (targetP aram ( L))) where sourceParam and targetParam functions are used to retrieve the source and the target parameter of the parameter link respectively.
Two definitions below specify two supportive functions that are used to get incoming and outgoing parameter links which are used to bind the given parameter. These functions will help to describe the later definitions.
inLink ( ) = f L : ( L 2 L) ^ (targetP aram( L) = )g where 8 2 . outLink ( ) = f L : ( L 2 L)^(sourceP aram( L) = )g where 8 2 .
Definition 17: A provision link, pLinki = h src; trg;os; pt;si 2 P L, represents a data and a control flow between two tasks.
A provision link binds an outcome of the source task and a provision of the target task. If a conditional branching occurs after the source task, the outcome state of the link (s) maps a particular branching condition to the target task. (C) Source and target tasks of a provision link must be the child of the same behavior. 8pLink 2 P L (source (pLink) 2 ST n $ target (pLink) 2 ST n ) (C) Source parameter of a provision link must be an outcome and target parameter must be a provision. 8pl 2 P L ((sourceP aram(pl) 2 O) ^ (targetP aram(pl) 2 P )) (C) At most one provision link can be constructed between the same outcome-provision pair. 8osrc; 8ptrg (j (outLink (osrc) \ P L) \ (inLink (ptrg) \ P L) j 1) (C) Either an order link or a provision link can be constructed between two tasks. 8 src; 8 trg ((outLink ( src) \ inLink ( trg) \ OL 6= ;) ! (outLink ( src) \ inLink ( trg) \ P L = ;)) 8 src; 8 trg ((outLink ( src) \ inLink ( trg) \ P L 6= ;) ! (outLink ( src) \ inLink ( trg) \ OL = ;))
Definition 18: An inheritance link, iLinki = h src; trg; ps; pti 2 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 provision of source behavior, and a provision of target sub task. src 2 B and trg 2 STbsrc .
(C) Source and target parameter of an inheritance link must be a provision. 8il 2 IL ((sourceP aram (il) 2 P ) ^ (targetP aram (il) 2 P )) (C) At most one inheritance link can be constructed between the same provision pairs. 8psrc; 8ptrg (joutLink (psrc) \ inLink (ptrg) \ ILj 1) (C) Each provision of the root behavior must be bound with at least one inheritance link. 8p 2 P root (j(outLink (p) \ IL)j > 0) where root 2 B.
Definition 19: A disinheritance link, dLinki = h src; trg; os; oti 2 DL, represents a parameter transfer from a task to parent behavior. It corresponds to a data flow from a subtask to the final node of a workflow.
Disinheritance link consists of source task, target behavior, an outcome of source sub task, and an outcome of target behavior. Source task of a disinheritance is child of the target task, trg 2 B and src 2 ST trg .
(C) Source and target parameter of a disinheritance link must be an outcome. 8dl 2 DL ((sourceP aram(dl) 2 O) ^ (targetP aram(dl) 2 O)) (C) At most one disinheritance link can be constructed between the same outcome pairs. 8osrc; 8otrg (joutLink (osrc) \ inLink (otrg) \ DLj 1) (C) A disinheritance link must be provided for each outcome of a behavior to collect all outcomes from the sub-tasks. If there is an exclusive choice structure, a disinheritance link must be constructed for all exclusive paths to fulfill all outcomes of the behavior. 8 i 2 B (8on 2 O i (jinLink (on) \ DLj > 1))
ning paradigms and workflow definition languages in the same agent architecture, HTNReducer, which is a component of the Reducers submodule as mentioned in Section II, is used to transform an HTN definition into a workflow before execution. In this section, this transformation process is introduced within the scope of our workflow-based HTN planner.
Algorithm 1 Reduction of an HTN behavior to a workflow Input: an HTN behavior .
Output: a workflow wf g.
1) Initiate a workflow graph wf g corresponding to . 2) Create the nodes corresponding to the subtasks of . a) If subtask is an HTN behavior, then apply the same process from step 1 and create a complete subworkflow for the subbehavior. b) For an HTN action, otherwise, create a primitive workflow task node. 3) Construct flows between workflow tasks in wf g. 4) Put required coordinator nodes to junction points. A. Reduction Algorithm
IV, we have developed an algorithm shown in Algorithm-1 for reducing a behavior description to the corresponding workflow.
For this purpose, the HTN reduction algorithm constructs a part of the graph in a few steps. It begins the process with creating an empty graph, which consists of initial and final nodes, and the data containers only, for the behavior. Then, it 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 subtask 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 (iwfg) 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 (fwfg). 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 h0T 20; fp 2 g ; fo 2 gi ; h0T 30; fp 3 g ; fo 3 gig the flow of execution. The control flow, CFwf1 = fhiwf1 ; 1i ; h 1; 2i ;
The outputs of our algorithm for primitive HTN patterns h 1; 3i ; h 2; fwf1 i ; h 3; fwf1 ig, and data flow DFwf1 = are represented in Figure-2. These patterns are composed of fDiwf1 ; dinwf1 ; 1; din 1 E ; h 1; dout 1 ; 2; din 2 i; h 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 ig 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 = ff r1; sy1g and
To understand the reduction process better, we explain it by updates the control flow set CFwf1 = fhiwf1 ; demonstrating one of primitive patterns. (see Figure-2(F)) The 1i; h 1; f r1i ; hf r1; 2i ; hf r1; 3i ; h 2; mr1i ; h 3; mr1i ; input behavior can be represented as 1 = h0BH10; fp 1 g ; hmr1; fwf1 ig. fo 1 g ; f 1; 2; 3g ; fpLink1; pLink2gi where 1 = h0AC10;fp 1 g ;fo 1 g ; 1 i, 2 = h0AC20;fp 2 g ;fo 2 g ; 2 i,
3 =h0AC30;fp 3 g ;fo 3 g ; 3 i and pLink1 =h 1; 2;o 1 ; B. Correctness of Reduction p 2 ;0S10i, pLink2 = h 1; 3; o 1 ; p 3 ;0 S10i. Theorem 1: Let is a behavior defined with HTN semanAt the start, an empty workflow wf1 = h;; ;; fhiwf1 ; tics. REDU CE ( ) terminates and returns a workflow wf . fwf1 ig; ;; ;; ;; fiwf1 ; fwf1 gi 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 = fh0T 10; fp 1 g ; fo 1 gi; subbehaviors until reaching to the leaf actions. Finally, after the leaves are transformed in line 2b, algorithm proceeds and bottom-up construction of root behavior is achieved.
Theorem 2: Let B = f 1; 2; : : : ; ng be a collection of HTN behaviors that conforms our constraints and be one of these. Let wf g = REDU CE ( ), then wf g is the workflow which corresponds to behavior .
Proof: The proof of the theorem is by induction:
Hypothesis For an HTN behavior , there exists a workflow graph wf = hTwf ; Cwf ; CFwf ; DFwf ; ICwf ; OCwf ; T Nwf i where Twf contanins the workflow tasks corresponds to sub tasks of , CFwf and DFwf contains the flows corresponds to links of HTN, and ICwf and OCwf contains inputs and outputs which corresponds to provisions and outcomes of .
Base Case Suppose is a behavior with only one action 1 as sub task. The reduction of ends up with a workflow wf = hTwf ; ;; CFwf ; ;; ;; ;; T Nwf i where Twf = f 1g and CFwf = fhiwf ; 1i ; h 1; fwf ig. As is seen in line 2b, after workflow is created in line 1, 1 is constructed for 1 and then it is connected with iwf and fwf in line 3. (see Figure2(A))
Inductive Step Besides the sequence structure in HTN, there exists a few structures such as nesting, conditional branching and parallelism. We will analyze each of the structures case by case to show that results of our translation are correct.
Case 1: While HTN plans can only be extended breadthwise with primitive subtasks, expansion in depth is provided with subbehaviors. (see Figure-3) From our hypothesis we know that we have corresponding workflow tasks 1; 2; 3 of the HTN tasks 1; 2; 3. The behavior is reduced to a workflow wf = hTwf ; Cwf ; CFwf ; ;; ;; ;; T Nwf i where Twf = f 1; 2; 3g, Cwf = ff r1; sy1g and CFwf = fhiwf ; 1i ; h 1; f r1i ; hf r1; 2i ; hf r1; 3i ; h 2; sy1i ; h 3; sy1i ; hsy1; fwf ig. In line 4, fork and synchronizer nodes are inserted to the beginning and the end of the parallel split structure in the raw workflow.
We proved that our reduction mechanism transforms the HTN plan into the workflow model correclty. In our proof, we showed the correspondence of the result workflow to the input plan.
application is implemented as a case study with SEAGENT Framework. In this application an agent which plays tourism agency role is responsible for making a vacation plan. A plan ontology (BHPlanVacation) which is the implementation of planning a vacation goal (PlanVacation) is provided in the knowledgebase of this agent.
Ontology3 individual of BHPlanVacation is depicted in Figure-5(B). BHPlanVacation behavior has three subtasks, and it needs location information (location provision) and vacation budget (budget provision) to make plan. After the execution of the behavior is completed, it gathers the remainder of budget (remainder outcome). Firstly, a hotel room is booked in specified 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 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 = fwfsubg and CFwf = fhiwf ; wfsubi ; h 1; wfsubig.
Case 2: Suppose = h0BH10; ;; ;; f 1; 2; 3g ; 1 i, where 1 = fh 1; 2;0 S10i ; h 1; 3;0 S20ig, 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 = f 1; 2; 3g, Cwf = fch1; mr1g and CFwf = When agent determines to execute the PlanVacation goal, fhiwf ; 1i ; h 1; ch1i ; hch1; 2i ; hch1; 3i ; h 2; mr1i ; h 3; mr1i ; it gives the goal description to the planner. After the planhmr1; fwf ig. 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
Case 3: Suppose = h0BH10; ;; ;; f 1; 2; 3g ; 1 i, 3Full version: http://www.seagent.ege.edu.tr/etmen/LADS009CaseStudy.zip where 1 = fh 1; 2;0 S10i ; h 1; 3;0 S10ig, is a behavior with 4HTN 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. transmits it to the HTNReducer to reduce it to workflow. After the HTNReducer completes reduction, the generated workflow is the executable form of the plan description. The workflow which is constructed by HTNReducer is shown in Figure-4.
for all actions of plan and the subbehavior is converted to subworkflow. After the workflow that corresponds to BHPlanVacation is constructed, the planner starts to proceed on the workflow via the ExecutionToken. Tasks are performed when the token visits them. Execution of a task means execution of the java class that is attached to the corresponding HTN action. Java reflection API is used to create and execute action class instances.
This paper briefly depicts the architecture of SEAGENT agent development framework’s planner. The main characteristic of the proposed architecture is its being based on the workflow technology and its ability to process the artifacts of agent programming paradigms such as plans, services, goals, and roles by executing these artifacts after reducing them to workflows.
described an HTN ontology to define agent plans, developed a workflow component using Java, and focused on the reduction of agent plans to workflows. We used this planner architecture in industrial and academical projects. The last version of the SEAGENT can be downloaded5 as an open source project.
SEAGENT planner has been designed with the idea that different plan definition languages other than HTN can also be reduced to the generic workflow model. In addition, business process definition languages such as BPEL, OWL-S can also be reduced to the generic workflow model. Moreover, these business process definition languages can be used in connection with different plan definition languages providing the interoperability of them. These features show the way of incorporating different languages into agent programming paradigms as well as offering a high degree of flexibility in developing agent systems.
5SEAGENT Semantic Web Enabled Framework, http://seagent.ege.edu.tr/