Multi-agent systems proved successful in enacting business processes because of their inner properties (distribution of tasks, collaboration and coordination among agents). MAS adoption in enacting processes becomes even more interesting if they exhibit adaptation capabilities. The proposed approach consists in the automatic generation of a MOISE organisation from the BPMN specification of a business process. This organisation is conceived to support adaptation because of the possibility to adapt its configuration at runtime according to emerging needs. Here, we focus on the tool for processing BPMN specification and generating MOISE organization code.
Traditionally, business processes are designed as static, rigid procedures, but in real production environment there are many events and/or exceptions that can not be foreseen at design time and can lead to the failure of the whole process. For instance, some web service could be not reachable, the network could be extremely busy with heavy delay in response etc. . . However, increasing the agility and the flexibility of business process is not trivial being in contrast to the current trend of over-specifying workflow details with the objective to detail every possible execution branches.
Multi-Agent Systems own many interesting features as autonomy, distribution of tasks, and
collaboration/coordination, that proved successfully in a range of application fields. Historically,
MASs have good records in implementing workflows because all those features perfectly match
with enterprises’ needs [
Most of the agent-based approaches to workflow design are based on services and semantic
web description (i.e. DAML-S [
An important improvement in MAS design and implementation comes out with the JaCaMo
platform [
In this paper we propose a tool able to automatically generate organizations of agents to
implement a given workflow expressed in Business Process Modeling Notation (BPMN) [
The BPMN is a high-level language that allows developer to model all the phases of a planned
business process. It focuses on analysis activity and there is not any bounding between tasks and
services at design time. A recent result has been that a business process, opportunely designed,
may be automatically translated into goals [
Having a BPMN as a set of goals, it is possible to conceive a multi agent system able of
addressing them [
The tool we propose uses a three steps procedure:
2. exploiting a planner for composing available services (stored in a yellow pages service) and obtaining diferent wokflow solutions to the same set of goals, and 3. employment of each diferent solution for generating multi-faceted agent organizations voted to achieve the business goal.
The paper is structured as follows: Section 2 presents the theoretical background, providing a brief description of BPMN, MOISE and JaCaMo. Section 3 describes the automatic generation of MOISE organizations; in particular, Section 3.1 presents a running example; Section 3.2 briefly reports the approach by discussing the mapping between BPMN elements and MOISE metamodel elements; Section 3.3 enters into the details, by explaining the algorithm of conversion. Finally, some conclusion is drawn in Section 4. issue list [ready] issue list [in vote]
issue votes issue list
Determine Issues issue list [initial]
Discussion
Voting annoiusnscueement annouvnocteement
Col ect Votes vote not agree(issue votes)
Vote Results vote results issue votes [final]
In this section we provide a brief description of the main background concepts used along the paper; namely the BPMN notation for the design of business processes and the MOISE framework for multi-agent systems organisations definition.
The Business Process Model and Notation (BPMN) [
MOISE defines a collection of elements for modelling an organization. A MOISE organization is
a specialized group that is devoted to pursue some goal. An organization is not only a collection
of roles. Indeed, defining an organization implies the definition of structural, functional and
normative perspectives [
The Structural Specification describes who (role) operates in the organization, the organization’s hierarchy (groups and subgroups), which role belongs to each group together with its cardinality, and the kind of relationship between roles (authority, communication, acquaintance)
The Functional Specification specifies the scheme of activities associated to each group. A scheme represents the goal decomposition tree. Each scheme is characterized by a goal to attain, and one or more plan. A plan represents the modality (sequence, parallel, choice) to address the inner sub-goals. All the goals are contained into a mission.
The Normative Specification defines obligations and permissions that link roles to missions.
A brief description of the MOISE elements based on definitions proposed by Hubner in [
Structural Specification: Role a role represents a placeholder for an agent that takes in charge to perform some activity.
The number of agents that can play a role is constrained by a minimum and maximum number.
Group a group is composed by roles. A group is well formed when all its roles are played by agents.
Link A link specifies the type of relationship between agents playing two roles. It is possible to describe compatibilities between roles.
Goal semantic description of a result to obtain; MOISE goals may belong to two diferent types: achieve and maintain.
Scheme a Scheme is the decomposition of the organization’s goals as an articulated gol-tree.
It also includes the specification of Missions.
Plan is an operator, used within a Scheme, in order to specify the goal decomposition type (sequence, choice, parallel).
Norm there are two types of norms: obligation and permission. They establish the link between the role and the mission. When an agent plays a role, it should or would commit to missions’ goals.
The MOISE organisation (provided as a XML file) is not operational in itself. A set of
CArtAgO Artifacts allows all necessary constructs and data structures to make a MAS operative,
i.e. allowing agents to adopt ad play a role, to participate to a group, and to commit a mission [
This section discusses the tool for the automatic generation of agent organization, by using a running example to present details of the approach.
In the remaining sections of this paper, we refer to the example workflow reported in Fig. 1.
That is a simplification of a well known BPMN example [
State extractor
BPMN2 GOAL
ID GOAL trigger_cond final_state
Wi Ontology extractor
Ontology
PMR
ID SOLUTION WI items flows
ABSTRACT ID CAPABILITY params pre post effects <agent,service>
GROUNDING
CAPABILITY abstract param_mapping YELLOW PAGES
SOL2
MOISE MOISE-SPEC committee discuss an issue list, and express a vote: if the majority is not reached, a new iteration of discussion/voting is performed.
The process description reports some events (emails) connecting the reported activities with the external voting members, represented as a swimlane shading the behaviour of the voting members that is of low interest for the current example. Data flow in the process is represented by Data Objects (like the Issue_list) that can evolve their refinement during the process, and that is represented by a state (initial, in_vote,. . . ).
This section describes the proposed approach for generating MOISE organizations starting from the BPMN description of a workflow.
The main tools and artifacts of the architecture are depicted in Fig. 2. They contribute to the generation of the organization according to the following sub-steps: Goal Extraction The first step consists in the extraction of goals from the BPMN process that is depicted using some BPMN compliant tool (and exported using the XMI format). This becomes the input of the BPMN2GOAL module1. The tool generates a list of goals by inspecting BPMN elements and their relationships. Indeed, single elements (activities, gateways,. . . ) contribute to the advancement in the world state in a way that is dependent on both endogenous factors (the result provided by the work done inside the element) and exogenous ones (the influence that other process elements have on it by creating its input, and constraining its output for compatibility with the remaining part of the process). In other words, a kind of balance of forces is to be solved in order to represent the mutual influence of each BPMN element on the other,
GOAL: <name of the goal (from BPMN activity>
WHEN: <conditions for goal triggering, from preconditions of the activity and postconditions of predecessor BPMN elements>
THEN: <intended state of the world, from activity postcondition and preconditions of successor BPMN elements> and the single element contribution to what becomes the collective outcome of the process execution.
Details about the goals extraction procedure may be found on [
State of the World Extraction The current state of the world is of paramount importance for the execution of a MAS solution. This is generated by the State Extractor module by processing the input workflow. The method considers the event that is usually sent to the workflow in order to trigger its execution together with any Data Input (an input Data Object for the whole process) as specified in the XMI file.
Ontology Extraction Goal specifications naturally define a vocabulary of terms that may be usefully employed to specify a part of the world where the agents live (predicates in the WHEN/THEN conditions of goals), and the actions that can be done in it (BPMN activities). This generates a primordial ontology that is generated by the Ontology Extractor module. A more accurate processing of some optional details of the BPMN notation greatly contributes to this issue. As an example we could consider Data Objects (that could represent ontology concepts), their states (that could generate predicates), Data type (items) that could contribute to the generation of a IS-A tree. Despite the interesting implications, these features are not relevant to the current work.
Solutions Calculations The possibility to execute the workflow with the available agents
in the MAS depends on the capabilities such agents register in the system’s Yellow Pages. We
suppose each agent, entering the system, registers its own capabilities in such register by using
a tuple <agent, service>. For each service, an Abstract Capability is automatically generated by
considering the service interface specifications like pre and post conditions. Of course, services
with the same specifications are considered as belonging to the same abstract capability thus
creating a redundancy in the capability instantiation that can profitably support some adaptation
degree (see [
Solutions are computed by the Proactive Means-end Reasoning (PMR) algorithm [
The PMR algorithm, in each solution, defines a world transition system (WTS), like the one shown in Fig. ?? from the input workflow of Fig. 1. The initial state corresponds to the initial event of the workflow (the reception of the issue list in this example). The next state corresponds to the availability of an issue list arranged for the discussion. The PMR identifies the capability prepare as the one that could transform the state of the issue list from [received] to [initial]. This capability is the abstraction of a service registered in the Yellow Pages by one or more agents. Actually this likely means the prepare capability proposes the received issue list to the committee chair for editing. Once the chair completes her editing, the list moves to the [initial] state and it is ready for discussion in the committee. Again the PMR algorithm identifies one capability (discussion) for managing the debate and producing the expected output (the issue list in the [ready] refinement state).
Now, if the voting achieves a majority consensus, the final state is reached, otherwise another branch is activated with the possibility to iterate modifications and votes.
This WTS ma be used to deduce the workflow underpinned by the solution. That step is easily done by looking at the capabilities listed in the WTS and reporting them as activities just like it is shown in Fig. 6. Control flows are similarly found in order to complete the design.
It is worth to note that this workflow is equivalent to the input BPMN one in terms of the results it produces but the type and number of services may not (and usually do not) exactly map one-to-one to the initial process activities. This solution is specifically conceived to be executed by the agents in the MAS and it has been designed to only use services that are possessed by those agents. [initial(issue_list)] prepare() discussion() [ready(issue_list)]
voting()_disagree [fnal(issue_list),sent(vote_announcement)] voting()_agree
discussion() voting()_disagree [ready(issue_list),sent(vote_announcement)]
voting()_agree
Of course the proposed example is very simple and solutions could be easily found even by hand but the approach works for large and complex input BPMN processes that would be very hard to solve using a long list of not exactly one-to-one matching services.
Moreover, the PMR algorithm, if the Yellow Pages repository is huge enough, may produce several diferent solutions by diferently composing all the existing capabilities. This generates an even larger number of concrete solutions (the realization of a solution in terms of concrete capabilities).
MOISE Organization Definition The last step in the adopted process consists in the actual definition of the MOISE organization. The main input for that is: 1) the set of goals, 2) the set of solutions generated by the PMR algorithm and 3) the content of the yellow pages. These are processed according to the algorithm detailed in the next subsection. structural-specification group-specification subgroups
APPLY_RULE__ROLE_DEF formation-constraints
APPLY_RULE__GROUP_SPEC
APPLY_RULE__ROLE_COMPATIBILITY functional-specification normative-specification
APPLY_RULE__SCHEME_DEF
APPLY_RULE__NORM_DEF
The automatic definition of the MOISE organization relies upon the XML template represented in Figure 7, in which XML elements and rules interleave. The algorithm has been written in Scala, a language derived by Java but closely integrated with XML. This way a XML rule is defined as a function that receives some parameter and returns the XML element to be used to complete the schema.
For instance, the “role definition rule” is coded as the following Scala function: def apply_rule__role_def(yp:List[ServiceDescr]): Elem = { <role-definitions> {yp.map(service => <role id={service.id + "_role"}>
<extends role="worker"/> </role> )} </role-definitions> } The function receives a list of Capabilities (extracted from the system Yellow Pages) and returns a ‘role-definitions’ tag where children are generated from the list of services (yp parameter). Each service in yp generates (map method) a new ‘role’ xml element extending the ‘worker’ parent role.
The following function contains the rule for generating the group specification corresponding to a Solution as generated by the PMR algorithm. def apply_rule__group_specification(sol: Solution): Elem = { <group-specification id={get_group_id} min="0"> {apply_rule__group_roles(sol) ++ apply_rule__group_links(sol)} </group-specification> } def apply_rule__group_roles(s: Solution): Elem = { <roles> <role id="manager" min="1" max="1"/> {solution.wftasks.map(capability => <role id={capability.id + "_role"} min="1" max="1"/>
)} </roles> } def apply_rule__group_links(s: Solution): Elem = { <links> <link from="manager" to="worker" type="authority" extends-subgroups="false" bi-dir="false" scope="intra-group"/> <link from="worker" to="manager" type="acquaintance" extends-subgroups="false" bi-dir="false" scope="intra-group"/> </links> } Briefly, the rule produces a ‘group-specification’ by applying two sub-rules: the first one is for generating roles of the group; it is done by looking at the specific tasks of the input solution. The PMR solution is an assembly of Capabilities which execution ensures full goal satisfaction. Each of the involved Capabilities produces a new role into the group. Clearly, more agents of the society could own the same Capability, being able of play that role. The second sub-rule is to define structural links among these roles.
An interesting rule is that for generating the scheme, in the functional specification, corresponding to a Solution. def apply_rule__scheme(s: Solution): Elem = { val sol_tree = new SolutionPattern(s) val opt_tree: Option[WorkflowPattern] = sol_tree.get_tree if (opt_tree.isDefined) { val tree : WorkflowPattern = opt_tree.get val capabilities = get_solution_capabilities(s) val scheme_id = get_scheme_id <scheme id={scheme_id}> { apply_rule__plan(tree)++ apply_rule__management_mission(scheme_id)++ capabilities.map(c=>apply_rule__mission(c)) } </scheme> } else { <scheme id={get_scheme_id}> </scheme> }
}
The function uses the SolutionPattern class, responsible of identifying basic workflow patterns[
2 algorithm exploits the control-flow perspective of the solution in order to identify some basic constructs: Sequence patterns, Choice patterns, Loop patterns.
Sequence Pattern. Description: a ‘sequence’ models consecutive steps in a workflow. Activities A,B,C represent a sequence if the execution of B is enabled after the completion of A, and, the execution of C is enabled after the completion of B.
Identification. The translation algorithm supposes the sequence is the default approach for implementing a workflow.
Exclusive Choice Pattern. Description: a point in the workflow where the control may pass to one among several branches, depending on the evaluation of a condition.
Identification. The translation algorithm supposes a split exclusive gateway starts an Exclusive Choice pattern. Branches are identified as possible sequences that terminates either with the same join exclusive gateway (Simple Merge pattern) or an end event.
Structured Cycle Pattern. Description: a point in the workflow where one or more activities can be executed repeatedly.
Identification. The translation algorithm supposes a join exclusive gateway possibly begins a loop, whereas it contains a ’before check’ sequence of activities until a split exclusive gateway that provides at least one exit condition, and a loop condition that begins one or more ’after check’ sequences that rolling back to the first split gateway.
Once the SolutionTree has been built (as in Figure 8), the apply_rule_scheme function easily converts the tree structure into a MOISE ‘scheme’ via goals and plans. This requires the function below: def apply_rule__plan(pattern: WorkflowPattern) : Elem = { pattern match { case SequencePattern(children) => case ActivityPattern(task) => val id = task.grounding.capability.id
<goal id={id}></goal>
It is a recursive rule, that browse the tree structure and incrementally builds the ‘goal/plan’ decomposition. A SequencePattern is translated into a sequence ‘plan’, a ChoicePattern is translated into a choice ‘plan’, whereas the Structured Cycle Pattern is a bit more articulated composition of sequences and choices. The exit condition for the recursion is the Activity (i.e. the leaves of the tree): each activity is translated into a simple ‘goal’ element.
Just to provide and example, the output of the previous rule application is reported below:
The proposed approach consists in the automatic generation of a MOISE organisation from the BPMN specification of a business process with the support of a specific tool. The organisation is conceived to provide system adaptation because it includes several alternative plans (schemes) for pursuing goals. The approach is complemented by a tool for processing BPMN (XMI) code and generating the MOISE organization specification code. The approach is based on a few fundamental steps: 1) the automatic extraction of goals by processing the BPMN activities and their dependencies, 2) the identification of the initial state for agents execution (and solutions computation), 3) the extraction of the ontological vocabulary from goal definitions, 4) the calculation of one or more solutions for the achievement of process objectives by using agents’ capabilities, 5) the generation of a MOISE organization composed of several alternative schemes, one for each computed solution. Alternative schemes in the agent organization can be selected according to performance criteria or to overcome a failure thus achieving some system adaptation. The generation of the organization is supported by a tool that uses well known workflow patterns to process the input BPMN XMI code and to generate the MOISE specification.
The availability of diferent organization’s schemes allows to select the scheme (goal decomposition tree and set of missions) that provide the best performance, according to the quality attributes registered in the yellow pages. The approach also allows to replace the scheme that is in execution with another one, in case of agent/service failures thus obtaining a runtime adaptation feature.
So far, the tool supports the whole BPMN 2.0 specification for defining the process, but the Sub-Process element, that is going to be used to create hierarchical groups. The language for specifying Capabilities is a proprietary format. Very soon, we will move towards open-access action specification languages (PPDL for instance). Currently, the tool has some limitations: 1) parallel gateways are understood by the BPMN2Goal parser but not supported in phase of Goal2MOISE generation; 2) timer/clock events are partially supported because they are translated into first-logic predicates that require the agent society uses a specific internal synchronization mechanism.