Agents can execute various task structures in order to achieve their goals. These task structures may be components of a plan (e.g. actions), services including semantically defined web services, or workflows which are represented using an appropriate formalism such as BPEL [1], XPDL [2]. An agent may execute each of these task structures in a way that is independent of others as it is the case for an agent that can execute only plans, only OWL-S service definitions or only workflows.
On the other hand, it is usually a desired property for an agent to execute several task structures in a combined manner. For example, one or more actions of a hierarchical task network (HTN) [3], [4] plan may need to call a web service or execute a pre-defined workflow. In addition, in open and collaborative multi-agent organizations where task structures can be distributed within the environment, it is required to discover, access, compose (if needed), and execute them at run-time. To support various task execution semantics both at design time and run-time, what is needed is a special agent planner architecture that should ideally provide a unique and common basis for the execution of different task structures in a both independent and combined manner.
There are three basic requirements to support various task execution semantics in an agent architecture. First, metamodels for the representation of various task semantics are needed. OWL-S, which is a standard for defining web services semantically, and workflow definition formalisms such as BPEL are examples for such meta-models. As another example, agent plans can be represented using OWL ontologies at the meta-level. Second, a common model that will form a common execution basis for the tasks that have different semantics is needed. Based on the fact that a plan can be represented as a directed graph which can be executed as a workflow, defining a generic workflow graph model will satisfy the requirement for a common model. Finally, algorithms for the transformations from the meta-models into the common representation model should be developed.
In this paper, we introduce a planner architecture that fulfills the requirements given above. The introduced architecture includes a generic workflow graph model into which various task semantics can be transformed. This generic workflow 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 the instances of the generic workflow graph model.
In literature, there are studies that aim to execute web services or workflows within a planner or an agent architecture. [6] describes how SHOP2 HTN planning system can be used to execute OWL-S descriptions. The SHOP2 planner takes the composite process defined using OWL-S as input and executes this composite process. WADE [7] is a software platform which is built on top of the well-known agent framework JADE [8]. WADE uses a directly executable simple workflow structure based on java class instead semantically described planning paradigms. Our study differs from these works, since our proposed planner architecture can support combinations of various task semantics both at design-time and run-time by providing a common execution layer for all of them. Neither [6] nor [7] aims to support more than one task execution semantics at the same time. Another point that needs attention is that the workflow graph model which constitutes the core of our common execution model is not related with the concept of executing a workflow within an agent. The workflow graph model is a directed graph structure into which various task semantics are transformed before execution.
We have implemented the planner architecture within SEAGENT [9], which is a semantic web enabled multi-agent system framework developed by our research group [10]. The planner can reduce the plans defined using OWL ontologies and OWL-S service definitions into the common workflow graph model, and then execute them. To illustrate the reduction process, we just focus on the transformation of HTN semantics into the common workflow graph model in this paper. We have 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 [11], [12]. SEAGENT also incorporates HTN as its planning paradigm.
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.
The implementation of the proposed planner architecture is 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, HTN 1 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 1 http://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.
As mentioned in the introduction, workflow technology has 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 Petri-Nets [13] and on conceptual directed graphs [5].
Sadiq and Orlowska abstractly introduced the basic building blocks of a workflow process using the graphical terms such as nodes and flows in [5]. They also defined the basic workflow constructs such as sequence, choice, concurrency and iteration. Besides the modeling workflows, they touch on reliability of the workflow model in [14], [15]. For this purpose, some structural conflicts as deadlock, lack of synchronization, live-lock are determined. Our workflow model is built by deriving the abstract definitions of Sadiq et al. and extended by constraints to avoid structural conflicts articulated in [14].
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 [16], [17]. So, we start to explain semantics of our model by giving the formalism of the directed graph with the following definition.
Definition 1: The directed graph represented with g consists of vertices V and directed edges E. A vertex, v ∈ V , specifies a node in the graph. The words, node and vertex, will be used interchangeably. A directed edge, e ∈ E, shows a directed link between two vertices of the graph. In the definition, vertex "v s " represents the source vertex of the edge and vertex "v t " is for the target. We define a function, path, that helps to gather the directed ways between two given vertices:
represents the first and the last vertex of the path. path defines one of the directed ways between vertices v i and v k . The first term of the finite sequence of edges is e 0 where source (e 0 ) = v i and the last term is e n where target (e n ) = v k . For all terms of the sequence, target node of an edge equals to source node of the next term, (target (e 0 ) = source (e 1 ))
represents all different ways between the given two nodes. This definition uses two functions for each edge e ∈ E: source (e) = v m where v m ∈ V represents the source vertex of e and target (e) = v n where v n ∈ V represents the target vertex of e.
Semantics of the workflow graph model, which extends the directed graph represented formally above, is defined below by giving details of the model's building blocks.
Definition 2: wfg, which is a tuple T,C,CF, DF,IC wf g , OC wf g ,T N , expresses a workflow graph that consists of set of tasks T, set of flows CF and DF which represent control flow and data flow sets respectively, input and output containers IC wf g and OC wf g , set of coordinators C, and set of terminal nodes T N . The workflow graph as mentioned previously is derived from the directed graph. So, when looked through the directed graph perspective, some entities of workflow graph, such as tasks, coordinators and terminal nodes, are sub-sets of the vertex set: T, C, T N ⊂ V . Also, CF and DF are specialized entities of workflow that are sub-sets of directed edge set: CF, DF ⊂ E. Definition 3: An element of task set is formally defined as
In detail, n τi is the identifier of the task, while IC τi and OC τi correspond to input and output containers respectively. sourceItem and targetItem functions are similar to source and target functions, but they are used to retrieve the data items bound by the specified data flow. Now, we can describe the constraints on data flows using these functions:
• (C) There should not be more than one data flow between any two data items:
• (C) Data type of the target task's input item must be equal or subsume the type of the source task's output item: ∀df ∈ DF type dsrc ⊆ type dtrg 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, cf i = v src , v trg ∈ CF , consisting of source vertex (v src ) and target vertex (v trg ). 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:
returns the set of control flows whose source is n. Now, we can specify the constraints using these functions:
There should not be more than one direct control flow between any two nodes.
The source node of a control flow must be ahead of the target node in the order of execution.
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.
where τ ∈ T , returns the set of data flows whose target is τ . outData(τ ) = {df : df ∈ DF ∧ source(df ) = τ } where τ ∈ 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, ch i = n ch , d cond ∈ CH, has more than one outgoing flows and contains a condition input d cond to select a branch. • A merge node, mr i ∈ 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 r i ∈ F R, has more than one outgoing flows and enables all of them at the same time. • A synchronizer node, sy i ∈ 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 [18]. The exclusive choice pattern creates a divergence point into two or more branches such that only one of which is selected for the execution. The parallel split pattern, on the other hand, provides concurrent execution paths which are activated simultaneously. An exclusive choice is constructed with a ch i , mr i pair, while a f r i , sy i 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.
)) 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 = {v i , v f }, used for this purpose.
Definition 7: Initial node, v i ∈ V , represents the beginning of the workflow, while the final node, v f ∈ V , represents the end, wf g n = (v i , {τ 1 , τ 2 , . . . , τ n } , {c 1 , c 2 , . . . , c n } , v f ).
• (C) v i is the first node of the wf g n , it has no incoming but only one outgoing control flow:
is the last node of the wf g n , it has only one incoming but no outgoing control flow:
• (C) Each workflow graph contains exactly one initial and one final node.
IV. SEMANTICS OF SEAGENT HTN Previously, we gave semantics of our workflow model. Our 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 [3]. In his model, HTN is closer to AI problem solving. For the purpose of using HTN in web agent programming, Sycara et al. reformed it in [4]. They contributed the link concept to provide a unified information and control flow within plans. Although that contribution makes HTN plans more tractable, it allows designing error-prone plans. Our HTN model is a detailed revision of Sycara et al.'s that is extended by exhaustive link definitions and constraints that permit to avoid designing erroneous plans. Base concept of our HTN model is task; Definition 8: An HTN task, θ i = n θi , P θi , O θi ∈ Θ, 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 = n βi , P βi , O βi , ST βi , Γ βi ∈ 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 = n αi , P αi , O αi , λ αi ∈ 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 = n πi , type πi ∈ Π, 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, p i = n pi , type pi , value pi ∈ 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, o i = n oi , type oi , value oi ∈ 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), s i ∈ 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 = {θ 1 , θ 2 , . . . , θ i } 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 . ∀θ ∈ Θ (θ ∈ ST βm → θ / ∈ 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: ∀l ∈ Γ (source (l) = target (l)) Here we define two functions that are used in determining the details of links:
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, oLink i = θ src , θ trg , s ∈ 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. ∀link ∈ OL(source(link) ∈ ST βn ↔ target(link) ∈ ST βn )
• (C) At most one order link can be constructed between two tasks.
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: ∀πL ∈ ΠL (type (sourceP aram (πL)) ⊆ type (targetP aram (πL))) where sourceParam and target-Param 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 (π) = {πL : (πL ∈ ΠL) ∧ (targetP aram(πL) = π)} where ∀π ∈ Π.
outLink (π) = {πL : (πL ∈ ΠL)∧(sourceP aram(πL) = π)} where ∀π ∈ Π.
Definition 17: A provision link, pLink i = θ src ,θ trg ,o s , p t ,s ∈ 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.
Definition 18: An inheritance link, iLink i = β src , θ trg , p s , p t ∈ 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 ∈ B and θ trg ∈ ST bsrc .
Source and target parameter of an inheritance link must be a provision. ∀il ∈ IL ((sourceP aram (il) ∈ P ) ∧ (targetP aram (il) ∈ P )) • (C) At most one inheritance link can be constructed between the same provision pairs. ∀p src , ∀p trg (|outLink (p src ) ∩ inLink (p trg ) ∩ IL| ≤ 1)
• (C) Each provision of the root behavior must be bound with at least one inheritance link. ∀p ∈ P βroot (|(outLink (p) ∩ IL)| > 0) where β root ∈ B. Definition 19: A disinheritance link, dLink i = θ src , β trg , o s , o t ∈ 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 ∈ B and θ src ∈ ST βtrg .
• (C) Source and target parameter of a disinheritance link must be an outcome. ∀dl ∈ DL ((sourceP aram(dl) ∈ O) ∧ (targetP aram(dl) ∈ O)) • (C) At most one disinheritance link can be constructed between the same outcome pairs. ∀o src , ∀o trg (|outLink (o src ) ∩ inLink (o trg ) ∩ DL| ≤ 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.
To implement our approach about executing different planning 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.
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.
Based on the formal definitions in Section III and Section 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 (i wf 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 (f wf 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 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 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 the flow of execution.
The outputs of our algorithm for primitive HTN patterns are represented in Figure -2. These patterns are composed of behaviors which have only primitive subtasks and other building blocks of HTN. Since plans, which have only primitive subtasks, can be defined by assembling these patterns, adding new actions to them and constructing new links between actions, they can be transformed into workflows.
To understand the reduction process better, we explain it by demonstrating one of primitive patterns. (see Figure -2(F)) The input behavior can be represented as
where α 1 = AC1 ,{p α1 } ,{o α1 } ,λ α1 , α 2 = AC2 ,{p α2 } ,{o α2 } ,λ α2 , α 3 = AC3 ,{p α3 } ,{o α3 } ,λ α3 and pLink 1 = α 1 ,α 2 ,o α1 , p α2 , S 1 , pLink 2 = α 1 , α 3 , o α1 , p α3 , S 1 .
• At the start, an empty workflow wf 1 = ∅, ∅, { i wf1 , f wf1 }, ∅, ∅, ∅, {i wf1 , f wf1 } is created, in line 1. • In the next step, in line 2, the actions are converted to primitive workflow tasks and these tasks are inserted to task set:
Theorem 1: Let β is a behavior defined with HTN semantics. REDU CE (β) terminates and returns a workflow wf .
Proof: A behavior represents a tree, and is reduced completely after all subtasks are reduced. So, from the line 2a of algorithm, the algorithm is executed over again for 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 = {β 1 , β 2 , . . . , β n } 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 = T wf , C wf , CF wf , DF wf , IC wf , OC wf , T N wf where T wf contanins the workflow tasks corresponds to sub tasks of β, CF wf and DF wf contains the flows corresponds to links of HTN, and IC wf and OC wf 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 = T wf , ∅, CF wf , ∅, ∅, ∅, T N wf where T wf = {τ 1 } and CF wf = { i wf , τ 1 , τ 1 , f wf }. As is seen in line 2b, after workflow is created in line 1, τ 1 is constructed for α 1 and then it is connected with i wf and f wf in line 3. (see Figure -2(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 = T wf , C wf , CF wf , ∅, ∅, ∅, T N wf where T wf = {τ 1 , τ 2 , τ 3 }, C wf = {f r 1 , sy 1 } and CF wf = { i wf , τ 1 , τ 1 , f r 1 , f r 1 , τ 2 , f r 1 , τ 3 , τ 2 , sy 1 , τ 3 , sy 1 , sy 1 , f wf }. 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.
To illustrate the reduction of plans to workflows, a tourism 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 Editor 4 When agent determines to execute the PlanVacation goal, it gives the goal description to the planner. After the planner ascertains that the goal is atomic, it searches for the appropriate act in the knowledgebase via the ActMatcher. The ActMatcher finds the BHPlanVacation HTN description and As is seen in the Figure -4, the workflow tasks are created for all actions of plan and the subbehavior is converted to subworkflow. After the workflow that corresponds to BHPlan-Vacation 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.
To implement the ideas behind the proposed architecture, we 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 downloaded 5 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.