Building a MultiAgent System from a User Workflow Specification Ezio Bartocci∗ , Flavio Corradini∗ , Emanuela Merelli∗ ∗ Dipartimento di Matematica e Informatica, Università di Camerino, Via Madonna delle Carceri, 62032 Camerino, Italy {name.surname}@unicam.it Abstract— This paper provides a methodology to build a MultiAgent System (MAS) described in terms of inter- active components from a domain-specific User Workflow Specification (UWS). We use a Petri nets-based notation to describe workflow specifications. This, besides using a familiar and well-studied notation, guarantees an high- level of description and independence with more concrete vendor-specific process definition languages. In order to bridge the gap between workflow specifications and MASs, we exploit other intermediate Petri nets-based notations. Fig. 1. A two steps methodology Transformation rules are given to translate a notation to another. The generated agent-based application implements the original workflow specification. Run-time support is provided by a middleware suitable for the execution of the involved in the organization and the needed resources. generated code. For this reason, during the last decade, the workflow technology has became very important. In fact the Work- I. I NTRODUCTION flow Management Coalition (WfMC) defines a workflow Nowadays open distributed systems, characterized by “the automation of a business process, in whole or part, independent components that cooperate to achieve indi- during which documents, information or tasks are passed vidual and shared goals, are becoming essential in several from one partecipant to another for action, according contexts, from large scientific collaborations to enterprise to a set of procedural rules.” [21]. In order to provide information systems. The Grid and agent communities a proper workflow specification language each standard are both developing concepts and mechanisms for open organization -i.e WfMC, BPMI and OMG- has defined its distributed systems, but with different perspectives [10]. own process definition language. Our aim is to provide a Grid community has focused on the main prominent methodology to translate a User Workflow Specification cyberinfrastructures [12] for large-scale resource shar- (UWS) into a MultiAgent System described in terms of ing and distributed system integration, providing tools Interactive Components [8] (ICs). We have based our for secure and reliable resource sharing within dynamic approach to describe a MAS with the help of components and geographically distributed virtual organizations. Grid on that proposed by Ferber in [9] for modelling of MAS computing [9] promises users the ability to harness the in BRIC. Figure 1 shows the two steps of the proposed power of large numbers of heterogeneous, distributed methodology. In the first step, UWS is translated to resources such as computing resources, data sources, a Role-based Workflow Specification (RWS). The user, instruments and application services. Agent community whose primary expertise is in the application domain, can instead is working on the development of methodologies focus on coordinating domain activities rather than being and algorithms for autonomous problem solvers that can concerned with the resources involved in the distributed act flexibly in uncertain and dynamic environments in environment. The first translation assigns the resources or order to achieve their goals [13]. As referred in [10], roles needed to execute each task. We have chosen Wf-net Grid and Agents need each other and are respectively as high-level specification language suitable to represent considered the “brawn” and the “brain” of open dis- the main workflow patterns provided by the most used tributed systems. With the advent of Grid and Agent- workflow specification languages -i.e XPDL [22], and based technologies, scientists and engineers are building BPEL [2]. Wf-net is a well-known extension of classical more and more complex applications to manage and Petri net [16] notation and it has been introduced in [18]. process large data sets, and execute scientific experiments The second step of the proposed methodology translates on distributed grid resources. These applications are gen- RWS into Interactive Components. To describe behavioral erally characterized by the execution of a set of distinct, aspect of each component we have used BRICs [8] sometimes repetitive, domain-specific activities. Automat- notation; another extension of classical Petri net. We have ing such processes requires a model that describes the defined transformation rules to map Wf-net specification coordination of the activities to be executed, the roles patterns into BRICs. This paper is organized as follows. 96 Section 2 describes the background of the work. Section 3 and 4 explain the two steps of our methodology. In Section 5, we present a case study that applies this methodology in Hermes [7] middleware. We conclude in Section 6. II. BACKGROUND This section provides some background on Workflow Management System (WMS), Petri nets, High level Petri nets and their application to Workflow Management [18]. Fig. 2. A subprocess A. Workflow Management System Workflow Management Systems (WMSs) provide an 4) M0 : P → N is the initial marking function, automated framework for managing intra- and interprise 5) P ∩ T = ® and P ∪ T 6= ®. business processes. A WMS is defined by WfMC Ordinary means that all arcs have weight 1. as:“A system that defines, creates and manages the execution of workflows through the use of software, A place p is called an input place of a transition t running on one or more workflow engines, which is if and only if there exists a directed arc from t to p. able to interpret the process definition, interact with Place p is called an output place of transition t if and workflow partecipants and, where required, invoke the only if there exists a directed arc from p to t. We use •t, use of IT tools and applications.” [21]. The most part t• to denote respectively the set of input places and the of implemented WMS are based on a client/server set of output places a transition t. The notation •p and architectural style. In these systems, the workflow p• identifies instead the set of transitions sharing p as enactment is entrusted to a central component, that acts input place and as output place respectively. as a server and is responsible for the correct execution. These systems lack the flexibility, scalability and fault At any time a place contains zero or more tokens, tolerance required for a distributed cross-organizational drawn as black dots. A marking function M ∈ P → N is workflow; in fact a monolithic architecture does not the distribution of tokens over places and represents the allow the execution of workflow or parts of it over state of P N . In this definition we do not consider any distributed and heterogeneous systems. To overcome capacity restrictions for places. The number of tokens these limitations, agent-based technology promises to may change during the execution of the net. alleviate many of these problems [20] and hence enable adaptive workflow. Moreover, using agent mobility, Transitions are the active components in a Petri instances of a workflow or parts of it can migrate; i.e., it net: they change the state of the net according to the is possible to transfer the code and the whole execution following firing rule : state, including all data gathered during the execution, 1) A transition t is said to be enabled if and only if between sites participating in workflow’s execution. each input place p is marked with at least one token. Agent mobility provides two main benefits. First, 2) An enabled transition may fire. If transition t fires, migrating workflow decreases efficiently traffic network; then t consumes one token from each input place usually code implementing workflow specification is less p of t and produces one token in each output place heavy to transfer than the amount of data needed during p of t. its execution. The second asset concerns the possibility for the workflow to be executed even in mobile and weekly network connected devices. This model requires C. High level Petri nets a suitable middleware to guarantee code mobility support. A High-level Petri Net (HLPN) [1] is a P N with three main extensions: • Extension with color - in Coloured Petri Net B. Petri nets (CPN) [14] tokens are typed and each token has a A Petri net [16] is a directed bipartite graph with value often referred as color. Transitions determine two node types called places and transitions. The nodes the values of the produced tokens on the basis are connected via directed arcs. Connections between of the values of the consumed tokens. Moreover two nodes of the same type are not allowed. Places are preconditions can be specified taking into account represented by circles and transitions by boxes or bars. the color of tokens. According to [15], an ordinary Petri net can be defined • Extension with time - using time extension, tokens as a 4-tuple, P N = (P, T, F, M0 ) where: receive a timestamp value that indicates the time 1) P = {p1 , p2 , · · · , pm } is a finite set of places, from which the token is available. A token with 2) T = {t1 , t2 , · · · , tn } is a finite set of transitions, timestamp 10 is available for the consumption by 3) F ⊆ (P × T ) ∪ (T × P ) is a set of arcs (flow a transition only from moment 10. A transition is relation), enabled only at the moment when each of the tokens 97 constructs named “triggers” were added to the standard Petri net -resource, message and time trigger. In this paper we will consider only the resource trigger. In this particular case, a trigger is associated to a specific resource needed to execute a task. As Figure 5 we can consider a trigger as special place linked with the transition representing a task. When the needed resource is not available this place is empty and the transition is not enabled, while if it contains a token it means that the resource is available and the task related to the linked transition could be executed. In the following sections we Fig. 3. Special transitions and their translation will consider interactive components as computational resources able to execute tasks under particular cases. The resource trigger can be assigned to every transition to be consumed has a timestamp equal or subsequent and is represented by a small, self-explaining icon (⇓) to the current time. near the associated transition symbol as Figure 5 shows. • Extension with hierarchy - hierarchical extension allows to model complex processes more easily by dividing the main process into ever-smaller subpro- III. A DDING ROLES TO W ORKFLOW S PECIFICATION cesses to overcome the complexity. In this paper, we A workflow process specification defines which tasks use the notation proposed by Wil van der Aalst [23], need to be executed and in what order. A set of cases, where a subprocess is a transition represented by identified by pre- and postcondition, are handled by double-border square as Figure 2 shows. executing tasks in a specific order. A task which needs to be executed for a specific case is called work item [18]. D. Workflow Nets A workflow specification is the composition of both Workflow Nets (WF-nets) [23] are a subclass of HLPN primitive and complex work items. A primitive work item where tasks are represented by transitions and conditions can be directly executed. A complex work item -called by places. A WF-net satisfies two requirements. First of subprocess in [18]- must be specified before it can be all, it must contain at least two special places: i and o. used; the specification of a subprocess is a workflow of Place i is a source place with •i = ®. Place o is a complex and primitive work items. By using subprocesses sink place with o• = ®. Secondly, it must hold that if the specification of workflows is simplified because they we add a transition t∗ which connect place o with i - enhance both hierarchical specification and reuse: we can i.e. •t∗ = {o} and t∗ • = {i} - then the resulting Petri use an already existing subprocess without having care net is strongly connected -from each node there exists of its specification. Work items are generally executed by a directed path to every other node-. This requirement a resource that can be either a machine -i.e. printer or a avoids dangling tasks and/or conditions. In order to make fax-, a computational entity -i.e. an agent- or a person. the WF-net suitable for workflow process modelling a set Resources are allowed to deal with specific work items. of notational extensions was applied to the standard Petri Grouping resources into classes facilitates the allocation net definition. In particular, as referred [23], the author of work items to resources. A resource class based on of WF-net added to the classical Petri net transition a the capabilities of its members is called role. A work set of special transitions (AND split, AND join, XOR item which is being executed by a specific resource is split, XOR join, AND/OR split), shown in Figure 3 with called an activity. A workflow designer, whose primary their translations, to express branching decisions in a more expertise is generally in the application domain, should be compact and user friendly way. free to focus on coordinating domain specific activities In the workflow theory [19], routing primitives are defined rather than being concerned with the complexity of a as a set possible basic patterns that determine which tasks domain specific activity or resources involved to execute need to be performed and in which order. Using the it. Users in fact may ignore the topological organization of prevoius defined special transitions as control flow, a set the distributed environment and resource classes available. of four basic routing primitives can be obtained as Figure The first step of the proposed methodology translates 4 shows: a user workflow specification to a role-based workflow 1) Sequential routing - task A is executed before task specification. During this step each work item is assigned B, to a role able to perform it. This operation could be made 2) Alternative routing - either task A or task B are manually or automatically. In the first case an expert user executed non deterministically, can assign role by itself, while in the second case an 3) Concurrent routing - task A and task B are executed activity repository store all informations about complex concurrently, activities and the user knows only there is an automatic 4) Iterative routing - task B is repeated mapping from domain specific work items and activities. In order to model dependencies between the workflow This resource allocation is applied recursively in all work process and its operative environment three different items of each subprocess. Figure 6 shows an example in 98 BRIC component -see Figure 7 (a)- is a software structure characterized externally by a certain number of input and output terminals and internally by a set of components. Every component is an instance of a class, which de- scribes its internal structure. A structured component is defined by the assembly of the its subcomponents. The input terminals of the structured components are linked to the input terminals of the the sub-components and is also possible to combine terminals of the composite Fig. 4. Routing primitives components with sub-components as showed in Figure 7 (b). The behaviour of elementary components is described in terms of a Petri net based formalism. The default net bioinformatics. In this case a bioscientist has designed an formalism normally used in BRIC is coloured Petri nets in-silico experiment -shown on the top of the Figure 6- with inhibitor arcs. Figure 7 (c) represents the general to globally align some omologous sequences to a given form of a transition. A transition is defined by entry arcs, one. This workflow involves five main work items: exit arcs and pre-condition of activation. Entry arcs are 1) get gene seq - given a gene id, retrieve the gene carriers of a condition, in the form of the description DNA sequence, of a token including variables. When the place contains 2) search genbank omologous - given a DNA se- a token corresponding to this description, the arc is quence, retrieve a set of DNA sequence omologous validated. There are three categories of entry arcs: from NCBI Genbank [3], 1) Standard arcs, denoted a1 , · · · , an , trigger the tran- 3) search PDB omologous - given a DNA sequence, sition only if they are all validated consuming retrieve a set of DNA sequence omologous from tokens which act as triggers and deleting them from the Protein Data Bank (PDB)[4], input places. 4) merge seqs - merge two or more set of sequences 2) Inhibitor arcs, denoted i1 , · · · , im , inhibit the trig- in a set of sequences, gering of the transition if they are enabled without 5) global alignment - given a set of DNA sequences deleting tokens from the input place. calculate the global alignment 3) Non-consumer arcs, denoted b1 , · · · , bk , work as In the Role-based Workflow Specification - standard arcs, but they don’t delete the input tokens. shown on the bottom of Figure 6- subprocesses search genbank omologous, search PDB omologous and merge seqs are substituted with the corresponding set of primitive work items. Each primitive work item is assigned to a specific role. In this case we have three roles A, B and C. Roles are translated into Interactive Components in the next step. IV. I NTERACTIVE C OMPONENTS S PECIFICATION In the second step the Role-based Specification is translated into Interactive Components. In order to specify the behaviour of each component indipendently from the corresponding generated code, we use BRICs [8], another Petri nets-based notation. In this section we provide trans- formation rules to translate Wf-net to BRICs notation. Fig. 7. BRICs notation A. BRICs notation An exit arc associate a transition with an output place Block Representation of Interactive Components producing in this position new tokens that depend on (BRICs) [8] is an high-level language for the design of the tokens used for triggering the transition. The pre- MultiAgent systems based on a modular approach. A condition associated with a transition relates to the ex- ternal conditions. The components communicate by ex- changing information along communication links which connect output terminals to the input terminals. Informa- tion is transported through the net in the form of tokens. A token is either an elementary piece of information whose value is a mere presence or absence, or a predicate in the form p(l1 , · · · , ln ), where each li represents a number or a symbol in a finite alphabet. Other importart assumptions Fig. 5. Resource trigger concerning this notation are: 99 Fig. 6. From User to Role-Based Workflow Specification 1) Input terminals are considered as places, thus names of input terminals are taken to be place identifiers. 2) Any direct link between an input terminal of an incorporating component and an input terminal of incorporated component is assumed to comprise a transition, in accordance with Petri net design rules. B. Mapping roles with structured components The translation from a role-based workflow to inter- active components specification requires the definition of a structured component skeleton that represents a role- specific implementation. As Figure 8 shows, the basic skeleton has two essential capabilities. First, since it Fig. 9. Scheduler component must be able to receive messages from the other external components asynchronously, we specify a subcomponent called MessagesQueue that stores messages as coloured nent to which the message is addressed. Act and Pre tokens following a First In First Out (FIFO) approach. are respectively the activity to be chosen and the pre- Each message is defined in the form: condition to be set, Pa is a possible input parameter :
<< for the activity -null value means no parameters. In the basic skeleton we specify a second subcomponent, called where sender is the identifier of the component sending Scheduler, providing, as Figure 9 shows, a set of places the message, address is the identifier of the compo- and transitions to receive tokens from MessagesQueue and to schedule the execution of a set of tasks following the order and cases defined by the role-based workflow specification. Scheduler component has four main places: 1) Scheduler Input (SI) - a token in this place means a new message for the scheduler. 2) Schedule Place (SP) - after tA firing produces a coloured token in SP in the form: Each Scheduler component contains a set of n Act components and ∀tBi,ki we define an entry arc ei,ki with the description: Fig. 8. Basic skeleton component where 1 < i < n, 1 < ki < mi and mi is number 100 Fig. 11. From Role-Based Workflow to Interactive Components Specification in SP place. This place is called dead, because a token here stops the behaviour of this component. When this happens tD can produce also a token for the external components to stop their behaviour too: : << C. Mapping activities An Interactive Component (IC) is an executor of a piece of workflow specification. The final behaviour of an IC is obtained by plugging the activities of the corresponding role into the basic skeleton previously defined. Each primitive activity defined in the Role-based Fig. 10. Mapping activities specification is associated with an Act component in ICs specification. Figure 10 shows how the routing constructs in Figure 4 are mapped into Act components. of pre-conditions for Acti . A token in SP matching A component Acti contains an input terminal for each with a description of an entry arc ei,ki enables pre-condition of the mapped activities, which are labelled the corresponding transition tBi,ki . The entry arc pi,1 , · · · , pi,mi where mi is the number of the activity description for the transition tD is defined as: pre-conditions. When the routing transition tRi fires the token produced in pRi enable the task transition tTi -representing a task to be execute by an IC- is enabled 3) Idle Place (IP) - when this place contains a token iff IP is not empty. The coloured token produced by tTi the Scheduler is waiting for a new message. is a message -as previously defined- for its and/or other 4) Dead Place (SP) - the transition tD when is enabled ICs MessageQueue. produce a token in SP inhibiting the transition tA . Consequently the Scheduler can’t receive any token 101 D. An example Figure 11 shows, on the top a Role-based specification using all possibile routing primitives and on the bottom the translation in ICs specification. For each role in the first corresponds to an IC in the second. All pre-conditions and activities are mapped into Act components adding the right routing transitions and are plugged in the Scheduler of the IC basic skeleton. An Act component produce at least a message describing which are the next IC, Act component and input terminal to be reach and an optional parameter for the task transition. The field address in the message specifies which are the receiver IC and an entry arc is assumed from this output teminal and the external input terminal of the IC specified. V. A CASE STUDY In the previous sections we have defined a Petri nets- based methodology showing how a user workflow-based application specification can be translated into Interac- tive Components. As a case study we have applied this methodology in Hermes [7], an agent-based middleware, for the design and the execution of activity-based appli- cations in distributed environment. Hermes is structured as a component-based, agent-oriented system with 3- layer -user, system and run-time- software architecture. Due to the lack of space, middleware architecture is not discussed here and we refer to [7] for further details. In this section, we focus instead on its workflow compiler architecture implementing the methodology previously defined. This component, infact, allows to translate a user domain-specific workflow specification into mobile code supported by Hermes middleware. A. Workflow compilation process Fig. 12. Workflow compilation process As Figure 12 shows, workflow compilation process in Hermes requires three main components: 1) WebWFlow - allows the user to define graphically a Language (XPDL) [22] document. WebWFlow allows to workflow of domain-specific activities. A repository import complex activities from the User Activity Repos- provides a set of complex or primitive activities itory (UAR). This repository contains the role-based def- available for selecting. At this level activity imple- inition of domain-specific activities. The implementation mentation details are hidden to user. of each activity in UAR is provided instead by the User 2) XPDLCompiler - translates the Role-based work- Implementation Activity Repository (UAIR) and corre- flow specification into Interactive Components sponds to a piece of Java code extended with Velocity specification and generates the code to be executed Template Language(VTL)[11]. The XPDL produced by on Hermes middleware. In this case another repos- WebWFlow is a Role-based workflow specification. itory provides the implementation of each activity as a code template. C. XPDLCompiler 3) Hermes middleware - supports the generated code XPDLCompiler receives an XPDL document and execution and mobility. generates the Java bytecode implementing Interactive In the follow sections we focus on the first two Components. A lexical and syntax analyzer performs components details. the validation and the parsing of the XPDL document using the Java Architecture XML Binding [17]. After this first phase, the compiler checks if the activities used in the workflow specification have a corresponding B. WebWFlow implementation in UAIR. Each role is translated in an WebWFlow is a web-based workflow editor supporting Agent skeleton, an extension of Hermes UserAgent Java the workflows specification by composing activities in a class. As Figure 13 shows, a UserAgent provides the graphical environment. The graphical notation provided is needed communication methods to interact with other mapped by WebWFlow into an XML Process Definition UserAgents. Then, for each activity, the corresponding 102 [2] T. Andrew, F. Curbera, H. Dholakia, Y. Goland, and et al. Business process execution language (bpel) for web services version 1.1. Technical report, IBM, 2003. [3] D. Benson, I. Karsch-Mizrachi, D. Lipman, J. Ostell, and D. Wheeler. Genbank. Nucleic Acids Res., 34:D16–20, 2006. [4] H. Berman, J. Westbrook, Z. Feng, G. Gilliland, T. Bhat, W. H., S. I.N., and B. P.E. Wildfire: distributed, grid-enabled workflow construction and execution. Nucleic Acids Res., 28(1):235–42, 2000. [5] A. Bertolino, F. Corradini, P. Inverardi, and H. Muccini. Deriving test plans from architectural descriptions. In ICSE, pages 220–229, 2000. [6] A. Bertolino, P. Inverardi, and H. Muccini. An explorative journey from architectural tests definition downto code tests execution. In ICSE, pages 211–220. IEEE Computer Society, 2001. [7] F. Corradini and E. Merelli. Hermes: agent-based middleware for mobile computing. In Mobile Computing, volume 3465, pages 234–270. LNCS, 2005. [8] J. Ferber. Multi-Agent System: An Introduction to Distributed Artificial Intelligence. Addison-Wesley, 1999. Fig. 13. UserAgent and Agent main methods [9] I. Foster and C. Kesselman. The Grid: Blueprint for a Future Computing Infrastructure. Morgan Kaufmann Publishers, San Francisco, CA, 1998. [10] I. T. Foster, N. R. Jennings, and C. Kesselman. Brain meets brawn: implementation code in UAIR is plugged into an Agent Why grid and agents need each other. In AAMAS, pages 8–15. skeleton and each internal scheduler is set. The Java IEEE Computer Society, 2004. code generation is performed using Apache Velocity [11] A. Group. Vtl reference guide. http://jakarta.apache.org/velocity/docs/vtl-reference-guide.html. (http://jakarta.apache.org/velocity/) template engine. [12] T. Hey and A. E. Trefethen. Cyberinfrastructure for e-Science. Finally, using the Java compiler, the generated bytecode Science, 308(5723):817–821, 2005. can be loaded into Hermes middleware. [13] N. R. Jennings. An agent-based approach for building complex software systems. Commun. ACM, 44(4):35–41, 2001. [14] K. Jensen. Coloured Petri Nets. Basic concept, analysis methods and practical use. EATCS monographs on Theoretical Computer Science. Springer-Verlag, Berlin, 1996. ACKNOWLEDGMENT [15] T. Murata. Petri nets: Properties, analysis and applications. In Proceedings of the IEEE, volume 77, pages 541–580, April 1989. This work is supported by the Investment Funds for [16] C. A. Petri. Kommunikation mit Automaten. PhD thesis, Institut für instrumentelle Matematik, Bonn, 1962. Basic Research (MIUR-FIRB) project Laboratory of In- [17] Sun. Java architecture for xml binding (jaxb). terdisciplinary Technologies in Bioinformatics (LITBIO). http://java.sun.com/webservices/jaxb/. We would also like to thank Luca Tesei for his valuable [18] W. van der Aalst. The application of petri nets to workflow management. The Journal of Circuits, Systems and Computers, remarks and suggestions. 8(1):21–66, 1998. [19] W. M. P. van der Aalst, A. H. M. ter Hofstede, B. Kiepuszewski, VI. C ONCLUSION and A. P. Barros. Workflow patterns. Distributed and Parallel Databases, 14(1):5–51, 2003. This paper presents a methodology to build a MultiA- [20] J. M. Vidal, P. A. Buhler, and C. Stahl. Multiagent systems with gent System described in terms of Interactive Components workflows. IEEE Internet Computing, 8(1):76–82, 2004. [21] WfMC. Workflow management coalition terminology and glos- from a domain-specific User Workflow Specification. The sary. Technical Report WFMC-TC-1011, Workflow Management whole approach is described using Petri nets-based nota- Coalition, 1999. tion. This provides many benefits. Petri nets are well- [22] WfMC. Xml process definition language (xpdl). WfMC standard, W3C, October 2005. studied formalisms and there are many tools available [23] K. v. H. W.M.P. van der Aalst. Workflow Management - Models, for verification. The high-level of description provided by Methods and Systems. MIT Press, Cambridge, 2002. Petri Nets guarantees independence with vendor-specific process definition languages. Behaviour of agents can also be described using BRICs, another Petri nets-based notation. In this case it is possible to describe components independently from the their implementing code. Using transformation rules from a notation to another we reduce the gap between workflow specifications and MultiAgent System. Our approach currently supports the building of a MAS based on message passing communication, its extension towards uncoupled communication will be next considered. As future work we also aim to use the ap- proach proposed in [5], [6] to validate the implementation starting from the model. R EFERENCES [1] W. Aalst. Putting Petri nets to work in industry. Computers in Industry, 25(1):45–54, 1994. 103