Building a MultiAgent System from a User Work ow Speci cation

Abstract

— This paper provides a methodology to build a MultiAgent System (MAS) described in terms of interactive components from a domain-speci c User Work ow Speci cation (UWS). We use a Petri nets-based notation to describe work ow speci cations. This, besides using a familiar and well-studied notation, guarantees an highlevel of description and independence with more concrete vendor-speci c process de nition languages. In order to bridge the gap between work ow speci cations and MASs, we exploit other intermediate Petri nets-based notations. Transformation rules are given to translate a notation to another. The generated agent-based application implements the original work ow speci cation. Run-time support is provided by a middleware suitable for the execution of the generated code.

I. INTRODUCTION

Nowadays open distributed systems, characterized by independent components that cooperate to achieve individual and shared goals, are becoming essential in several contexts, from large scienti c collaborations to enterprise information systems. The Grid and agent communities are both developing concepts and mechanisms for open distributed systems, but with different perspectives [ 10 ]. Grid community has focused on the main prominent cyberinfrastructures [ 12 ] for large-scale resource sharing and distributed system integration, providing tools for secure and reliable resource sharing within dynamic and geographically distributed virtual organizations. Grid computing [ 9 ] promises users the ability to harness the power of large numbers of heterogeneous, distributed resources such as computing resources, data sources, instruments and application services. Agent community instead is working on the development of methodologies and algorithms for autonomous problem solvers that can act exibly in uncertain and dynamic environments in order to achieve their goals [ 13 ]. As referred in [ 10 ], Grid and Agents need each other and are respectively considered the “brawn” and the “brain” of open distributed systems. With the advent of Grid and Agentbased technologies, scientists and engineers are building more and more complex applications to manage and process large data sets, and execute scienti c experiments on distributed grid resources. These applications are generally characterized by the execution of a set of distinct, sometimes repetitive, domain-speci c activities. Automating such processes requires a model that describes the coordination of the activities to be executed, the roles involved in the organization and the needed resources. For this reason, during the last decade, the work ow technology has became very important. In fact the Workow Management Coalition (WfMC) de nes a work ow “the automation of a business process, in whole or part, during which documents, information or tasks are passed from one partecipant to another for action, according to a set of procedural rules.” [ 21 ]. In order to provide a proper work ow speci cation language each standard organization -i.e WfMC, BPMI and OMG- has de ned its own process de nition language. Our aim is to provide a methodology to translate a User Work ow Speci cation (UWS) into a MultiAgent System described in terms of Interactive Components [ 8 ] (ICs). We have based our approach to describe a MAS with the help of components on that proposed by Ferber in [ 9 ] for modelling of MAS in BRIC. Figure 1 shows the two steps of the proposed methodology. In the rst step, UWS is translated to a Role-based Work ow Speci cation (RWS). The user, whose primary expertise is in the application domain, can focus on coordinating domain activities rather than being concerned with the resources involved in the distributed environment. The rst translation assigns the resources or roles needed to execute each task. We have chosen Wf-net as high-level speci cation language suitable to represent the main work ow patterns provided by the most used work ow speci cation languages -i.e XPDL [ 22 ], and BPEL [ 2 ]. Wf-net is a well-known extension of classical Petri net [ 16 ] notation and it has been introduced in [ 18 ]. The second step of the proposed methodology translates RWS into Interactive Components. To describe behavioral aspect of each component we have used BRICs [ 8 ] notation; another extension of classical Petri net. We have de ned transformation rules to map Wf-net speci cation patterns into BRICs. This paper is organized as follows. 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 Work ow Management System (WMS), Petri nets, High level Petri nets and their application to Work ow Management [18].

A. Work ow Management System

Work ow Management Systems (WMSs) provide an automated framework for managing intra- and interprise business processes. A WMS is de ned by WfMC as:“A system that de nes, creates and manages the execution of work ows through the use of software, running on one or more work ow engines, which is able to interpret the process de nition, interact with work ow partecipants and, where required, invoke the use of IT tools and applications.” [ 21 ]. The most part of implemented WMS are based on a client/server architectural style. In these systems, the work ow enactment is entrusted to a central component, that acts as a server and is responsible for the correct execution. These systems lack the exibility, scalability and fault tolerance required for a distributed cross-organizational work ow; in fact a monolithic architecture does not allow the execution of work ow or parts of it over distributed and heterogeneous systems. To overcome these limitations, agent-based technology promises to alleviate many of these problems [ 20 ] and hence enable adaptive work ow. Moreover, using agent mobility, instances of a work ow or parts of it can migrate; i.e., it is possible to transfer the code and the whole execution state, including all data gathered during the execution, between sites participating in work ow's execution. Agent mobility provides two main bene ts. First, migrating work ow decreases ef ciently traf c network; usually code implementing work ow speci cation is less heavy to transfer than the amount of data needed during its execution. The second asset concerns the possibility for the work ow to be executed even in mobile and weekly network connected devices. This model requires a suitable middleware to guarantee code mobility support.

B. Petri nets

A Petri net [ 16 ] is a directed bipartite graph with two node types called places and transitions. The nodes are connected via directed arcs. Connections between two nodes of the same type are not allowed. Places are represented by circles and transitions by boxes or bars. According to [ 15 ], an ordinary Petri net can be de ned as a 4-tuple, P N = (P; T ; F; M0) where: 1) P = fp1; p2; ¢ ¢ ¢ ; pmg is a nite set of places, 2) T = ft1; t2; ¢ ¢ ¢ ; tng is a nite set of transitions, 3) F µ (P £ T ) [ (T £ P ) is a set of arcs ( ow relation), 4) M0 : P ! N is the initial marking function, 5) P \ T = ® and P [ T 6= ®.

Ordinary means that all arcs have weight 1.

A place p is called an input place of a transition t if and only if there exists a directed arc from t to p. Place p is called an output place of transition t if and only if there exists a directed arc from p to t. We use ²t, t² to denote respectively the set of input places and the set of output places a transition t. The notation ²p and p² identi es instead the set of transitions sharing p as input place and as output place respectively.

At any time a place contains zero or more tokens, drawn as black dots. A marking function M 2 P ! N is the distribution of tokens over places and represents the state of P N . In this de nition we do not consider any capacity restrictions for places. The number of tokens may change during the execution of the net.

Transitions are the active components in a Petri net: they change the state of the net according to the following ring rule : 1) A transition t is said to be enabled if and only if each input place p is marked with at least one token. 2) An enabled transition may re. If transition t res, then t consumes one token from each input place p of t and produces one token in each output place p of t.

C. High level Petri nets

A High-level Petri Net (HLPN) [ 1 ] is a P N with three main extensions: ² Extension with color - in Coloured Petri Net (CPN) [ 14 ] tokens are typed and each token has a value often referred as color. Transitions determine the values of the produced tokens on the basis of the values of the consumed tokens. Moreover preconditions can be speci ed taking into account the color of tokens. ² Extension with time - using time extension, tokens receive a timestamp value that indicates the time from which the token is available. A token with timestamp 10 is available for the consumption by a transition only from moment 10. A transition is enabled only at the moment when each of the tokens to be consumed has a timestamp equal or subsequent to the current time. ² Extension with hierarchy - hierarchical extension allows to model complex processes more easily by dividing the main process into ever-smaller subprocesses to overcome the complexity. In this paper, we use the notation proposed by Wil van der Aalst [ 23 ], where a subprocess is a transition represented by double-border square as Figure 2 shows.

D. Work ow Nets

Work ow Nets (WF-nets) [ 23 ] are a subclass of HLPN where tasks are represented by transitions and conditions by places. A WF-net satis es two requirements. First of all, it must contain at least two special places: i and o. Place i is a source place with ²i = ®. Place o is a sink place with o² = ®. Secondly, it must hold that if we add a transition t¤ which connect place o with i i.e. ²t¤ = fog and t¤² = fig - then the resulting Petri net is strongly connected -from each node there exists a directed path to every other node-. This requirement avoids dangling tasks and/or conditions. In order to make the WF-net suitable for work ow process modelling a set of notational extensions was applied to the standard Petri net de nition. In particular, as referred [ 23 ], the author of WF-net added to the classical Petri net transition a set of special transitions (AND split, AND join, XOR split, XOR join, AND/OR split), shown in Figure 3 with their translations, to express branching decisions in a more compact and user friendly way.

In the work ow theory [ 19 ], routing primitives are de ned as a set possible basic patterns that determine which tasks need to be performed and in which order. Using the prevoius de ned special transitions as control ow, a set of four basic routing primitives can be obtained as Figure 4 shows: 1) Sequential routing - task A is executed before task

B, 2) Alternative routing - either task A or task B are executed non deterministically, 3) Concurrent routing - task A and task B are executed concurrently, 4) Iterative routing - task B is repeated In order to model dependencies between the work ow process and its operative environment three different 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 speci c 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 will consider interactive components as computational resources able to execute tasks under particular cases. The resource trigger can be assigned to every transition and is represented by a small, self-explaining icon (+) near the associated transition symbol as Figure 5 shows.

III. ADDING ROLES TO WORKFLOW SPECIFICATION A work ow process speci cation de nes which tasks need to be executed and in what order. A set of cases, identi ed by pre- and postcondition, are handled by executing tasks in a speci c order. A task which needs to be executed for a speci c case is called work item [ 18 ]. A work ow speci cation is the composition of both primitive and complex work items. A primitive work item can be directly executed. A complex work item -called subprocess in [ 18 ]- must be speci ed before it can be used; the speci cation of a subprocess is a work ow of complex and primitive work items. By using subprocesses the speci cation of work ows is simpli ed because they enhance both hierarchical speci cation and reuse: we can use an already existing subprocess without having care of its speci cation. Work items are generally executed by a resource that can be either a machine -i.e. printer or a fax-, a computational entity -i.e. an agent- or a person. Resources are allowed to deal with speci c work items. Grouping resources into classes facilitates the allocation of work items to resources. A resource class based on the capabilities of its members is called role. A work item which is being executed by a speci c resource is called an activity. A work ow designer, whose primary expertise is generally in the application domain, should be free to focus on coordinating domain speci c activities rather than being concerned with the complexity of a domain speci c activity or resources involved to execute it. Users in fact may ignore the topological organization of the distributed environment and resource classes available. The rst step of the proposed methodology translates a user work ow speci cation to a role-based work ow speci cation. During this step each work item is assigned to a role able to perform it. This operation could be made manually or automatically. In the rst case an expert user can assign role by itself, while in the second case an activity repository store all informations about complex activities and the user knows only there is an automatic mapping from domain speci c work items and activities. This resource allocation is applied recursively in all work items of each subprocess. Figure 6 shows an example in bioinformatics. In this case a bioscientist has designed an in-silico experiment -shown on the top of the Figure 6to globally align some omologous sequences to a given one. This work ow involves ve main work items: 1) get gene seq - given a gene id, retrieve the gene

DNA sequence, 2) search genbank omologous - given a DNA sequence, retrieve a set of DNA sequence omologous from NCBI Genbank [ 3 ], 3) search PDB omologous - given a DNA sequence, retrieve a set of DNA sequence omologous from the Protein Data Bank (PDB)[ 4 ], 4) merge seqs - merge two or more set of sequences in a set of sequences, 5) global alignment - given a set of DNA sequences calculate the global alignment

In the Role-based Work ow Speci cation 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 speci c role. In this case we have three roles A, B and C. Roles are translated into Interactive Components in the next step.

IV. INTERACTIVE COMPONENTS SPECIFICATION

In the second step the Role-based Speci cation 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 transformation rules to translate Wf-net to BRICs notation.

A. BRICs notation

Block Representation of Interactive Components (BRICs) [ 8 ] is an high-level language for the design of MultiAgent systems based on a modular approach. A 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 describes its internal structure. A structured component is de ned 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 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 formalism normally used in BRIC is coloured Petri nets with inhibitor arcs. Figure 7 (c) represents the general form of a transition. A transition is de ned by entry arcs, exit arcs and pre-condition of activation. Entry arcs are carriers of a condition, in the form of the description of a token including variables. When the place contains a token corresponding to this description, the arc is validated. There are three categories of entry arcs: 1) Standard arcs, denoted a1; ¢ ¢ ¢ ; an, trigger the transition only if they are all validated consuming tokens which act as triggers and deleting them from input places. 2) Inhibitor arcs, denoted i1; ¢ ¢ ¢ ; im, inhibit the triggering of the transition if they are enabled without deleting tokens from the input place. 3) Non-consumer arcs, denoted b1; ¢ ¢ ¢ ; bk, work as standard arcs, but they don't delete the input tokens.

Fig. 7. BRICs notation An exit arc associate a transition with an output place producing in this position new tokens that depend on the tokens used for triggering the transition. The precondition associated with a transition relates to the external conditions. The components communicate by exchanging information along communication links which connect output terminals to the input terminals. Information 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 nite alphabet. Other importart assumptions concerning this notation are: 1) Input terminals are considered as places, thus names of input terminals are taken to be place identi ers. 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 work ow to interactive components speci cation requires the de nition of a structured component skeleton that represents a rolespeci c implementation. As Figure 8 shows, the basic skeleton has two essential capabilities. First, since it must be able to receive messages from the other external components asynchronously, we specify a subcomponent called MessagesQueue that stores messages as coloured tokens following a First In First Out (FIFO) approach. Each message is de ned in the form: <sender>: <address> << <Act, Pre, Pa> where sender is the identi er of the component sending the message, address is the identi er of the compo

Fig. 9. Scheduler component nent to which the message is addressed. Act and Pre are respectively the activity to be chosen and the precondition 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 Scheduler, providing, as Figure 9 shows, a set of places and transitions to receive tokens from MessagesQueue and to schedule the execution of a set of tasks following the order and cases de ned by the role-based work ow speci cation. 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 ring produces a coloured token in SP in the form: <Act, Pre, Pa> Each Scheduler component contains a set of n Act components and 8tBi;ki we de ne an entry arc ei;ki with the description: <i, k, Pa> where 1 < i < n, 1 < ki < mi and mi is number of pre-conditions for Acti. A token in SP matching with a description of an entry arc ei;ki enables the corresponding transition tBi;ki . The entry arc description for the transition tD is de ned as: <null, null, null> 3) Idle Place (IP) - when this place contains a token the Scheduler is waiting for a new message. 4) Dead Place (SP) - the transition tD when is enabled produce a token in SP inhibiting the transition tA. Consequently the Scheduler can't receive any token 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: <me>: <All> << <null, null, null>

C. Mapping activities

An Interactive Component (IC) is an executor of a piece of work ow speci cation. The nal behaviour of an IC is obtained by plugging the activities of the corresponding role into the basic skeleton previously de ned. Each primitive activity de ned in the Role-based speci cation is associated with an Act component in ICs speci cation. Figure 10 shows how the routing constructs in Figure 4 are mapped into Act components. A component Acti contains an input terminal for each pre-condition of the mapped activities, which are labelled pi;1; ¢ ¢ ¢ ; pi;mi where mi is the number of the activity pre-conditions. When the routing transition tRi res the token produced in pRi enable the task transition tTi -representing a task to be execute by an IC- is enabled iff IP is not empty. The coloured token produced by tTi is a message -as previously de ned- for its and/or other ICs MessageQueue.

D. An example

In the previous sections we have de ned a Petri netsbased methodology showing how a user work ow-based application speci cation can be translated into Interactive 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 applications in distributed environment. Hermes is structured as a component-based, agent-oriented system with 3layer -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 work ow compiler architecture implementing the methodology previously de ned. This component, infact, allows to translate a user domain-speci c work ow speci cation into mobile code supported by Hermes middleware.

A. Work ow compilation process

As Figure 12 shows, work ow compilation process in Hermes requires three main components: 1) WebWFlow - allows the user to de ne graphically a work ow of domain-speci c activities. A repository provides a set of complex or primitive activities available for selecting. At this level activity implementation details are hidden to user. 2) XPDLCompiler - translates the Role-based workow speci cation into Interactive Components speci cation and generates the code to be executed on Hermes middleware. In this case another repository provides the implementation of each activity as a code template. 3) Hermes middleware - supports the generated code execution and mobility.

In the follow sections we focus on the rst two components details.

B. WebWFlow

WebWFlow is a web-based work ow editor supporting the work ows speci cation by composing activities in a graphical environment. The graphical notation provided is mapped by WebWFlow into an XML Process De nition

Fig. 12. Work ow compilation process Language (XPDL) [ 22 ] document. WebWFlow allows to import complex activities from the User Activity Repository (UAR). This repository contains the role-based definition of domain-speci c activities. The implementation of each activity in UAR is provided instead by the User Implementation Activity Repository (UAIR) and corresponds to a piece of Java code extended with Velocity Template Language(VTL)[ 11 ]. The XPDL produced by WebWFlow is a Role-based work ow speci cation.

C. XPDLCompiler

XPDLCompiler receives an XPDL document and generates the Java bytecode implementing Interactive Components. A lexical and syntax analyzer performs the validation and the parsing of the XPDL document using the Java Architecture XML Binding [ 17 ]. After this rst phase, the compiler checks if the activities used in the work ow speci cation have a corresponding implementation in UAIR. Each role is translated in an Agent skeleton, an extension of Hermes UserAgent Java class. As Figure 13 shows, a UserAgent provides the needed communication methods to interact with other UserAgents. Then, for each activity, the corresponding implementation code in UAIR is plugged into an Agent skeleton and each internal scheduler is set. The Java code generation is performed using Apache Velocity (http://jakarta.apache.org/velocity/) template engine. Finally, using the Java compiler, the generated bytecode can be loaded into Hermes middleware.

ACKNOWLEDGMENT

This work is supported by the Investment Funds for Basic Research (MIUR-FIRB) project Laboratory of Interdisciplinary Technologies in Bioinformatics (LITBIO). We would also like to thank Luca Tesei for his valuable remarks and suggestions.

VI. CONCLUSION

This paper presents a methodology to build a MultiAgent System described in terms of Interactive Components from a domain-speci c User Work ow Speci cation. The whole approach is described using Petri nets-based notation. This provides many bene ts. Petri nets are wellstudied formalisms and there are many tools available for veri cation. The high-level of description provided by Petri Nets guarantees independence with vendor-speci c process de nition 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 work ow speci cations 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 approach proposed in [ 5 ], [ 6 ] to validate the implementation starting from the model.

References

[1] W. Aalst . Putting Petri nets to work in industry . Computers in Industry, 25 ( 1 ): 45 – 54 , 1994 .

[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. Wild re: distributed, grid-enabled work ow 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 de nition 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 Arti cial Intelligence . Addison-Wesley, 1999 .

[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: Why grid and agents need each other . In AAMAS , pages 8 – 15 . IEEE Computer Society, 2004 .

[11] A. Group . Vtl reference guide . http://jakarta.apache.org/velocity/docs/vtl-reference-guide.html.

[12] T. Hey and A. E. Trefethen . Cyberinfrastructure for e-Science. Science, 308 ( 5723 ): 817 – 821 , 2005 .

[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 .

[15] T. Murata . Petri nets: Properties, analysis and applications . In Proceedings of the IEEE , volume 77 , pages 541 – 580 , April 1989 .

[16] C. A. Petri . Kommunikation mit Automaten. PhD thesis , Institut fu¨r instrumentelle Matematik, Bonn, 1962 .

[17] Sun . Java architecture for xml binding (jaxb) . http://java.sun.com/webservices/jaxb/.

[18] W. van der Aalst. The application of petri nets to work ow management . The Journal of Circuits, Systems and Computers , 8 ( 1 ): 21 – 66 , 1998 .

[19] W. M. P. van der Aalst , A. H. M. ter Hofstede , B. Kiepuszewski , and A. P. Barros . Work ow patterns . Distributed and Parallel Databases , 14 ( 1 ):5– 51 , 2003 .

[20] J. M. Vidal , P. A. Buhler , and C. Stahl. Multiagent systems with work ows . IEEE Internet Computing , 8 ( 1 ): 76 – 82 , 2004 .

[21] WfMC . Work ow management coalition terminology and glossary . Technical Report WFMC-TC-1011, Work ow Management Coalition , 1999 .

[22] WfMC . Xml process de nition language (xpdl) . WfMC standard, W3C , October 2005 .

[23] K. v. H. W.M.P. van der Aalst . Work ow Management - Models, Methods and Systems . MIT Press, Cambridge, 2002 .