Formal Specification of Multi-Agent System Architecture

Abstract

- Multi-Agent Systems (MAS) are an emerging paradigm that has high potentials for developing distributed, open and concurrent complex systems. These systems often need to operate in dynamic environments and face the challenges of handling continuously changing requirements. These aspects increase the complexity of designing MAS. To handle the complexity and facilitate reasoning, software architecture is now recognized as the best way to meet these expectations. In this paper, we try to handle these issues by proposing a new approach for modeling and analyzing MAS architectures by using a formal specification of the Bigraphical Reactive System (BRS). The feasibility and the advantage of the proposed approach are shown thru a case study.

Keywords

• - Multi-Agent Systems
• software architecture description language
• Bigraphical Reactive System
• formal specification

1. INTRODUCTION

In the recent years software systems tend to be more distributed, open and concurrent. This evolution of computing has changed the way of thinking but also the design of such systems. Multi-Agent Systems (MAS) are particularly suitable for developing these kinds of systems. MAS can be defined as a set of autonomous loosely coupled entities called agents, which communicate in an asynchronous way to achieve a personal or a global goal. An agent represents the first order entity in a MAS. It is considered as an autonomous computing system that offers a high level of abstraction and mechanisms which address issues such as knowledge representation and reasoning, communication, perception, commitments, goals, beliefs and intentions. Therefore such systems often need to operate in dynamic environments and face the challenges of handling continuously changing requirements; therefore they must be flexible, robust and capable of adapting to their environments [1]. So the development of multiagent systems is a complex engineering task. To meet this challenge, it is necessary to raise the level of abstraction of systems far beyond the code and break them down into modules (i.e., sub-problems) [ 2 ] to manage the complexity and facilitate reasoning. The software architecture is now a recognized way to meet these expectations. It aims to provide high-level descriptions of systems, representing not only their logical structure, but also many other functional and non-functional aspects (e.g., behavior, security). It also shows a set of properties and constraints that the system must meet. Offering a global vision and a high level structure and organization of a system, the software architecture plays a key role as a pivot point between the requirements of a system and its implementation. For that purpose Architecture description languages (ADLs) were adopted as formal tools for describing software architecture at a high level of abstraction, so far many ADLs such as Darwin, Rapide, Dynamic-Wright [ 3 ] and π-ADL [ 4 ] have been proposed for representing and analyzing software architectures. However these ADLs are not suited to full representing MAS architecture characteristics such as reasoning, communication, perception and dynamic reconfiguration. In this work, Bigraphical Reactive Systems (BRS) [ 5 ] are adopted as a semantic framework to formalize MAS architectures that are based on the Belief-Desire-Intention (BDI) agent model. In addition to their graphical aspect and rigorous basis, Milners BRS are capable of representing both locality and connectivity constituting main concepts of MAS architecture. A bigraphical reactive system consists of a category of bigraphs and a set of reaction rules providing them the ability to reconfigure themselves. Therefore, BRS are very suitable to formalize MAS fundamental architectural aspects and their reconfiguration.

In this paper, we use bigraphical reactive systems (BRSs) as a formal method to propose a BDI-MAS model for specifying static and dynamic aspects, at the individual (agent) level and social level (MAS), including relationships and constraints of BDI-MAS architectures. The rest of the paper is organized as follows. In section II, we introduce Bigraphical Reaction Systems (BRS) and we recall fundamental elements of MAS. Section III presents our bigraphical specification of BDI-MAS architecture. The given formalization approach is illustrated thru an example in section IV. Finally, some concluding remarks and ongoing work finishes the paper.

2. BIGRAPHS AND MAS 2.1. MAS

An agent is a computer system situated in an environment, which is capable of autonomous action and flexible in order to meet its design objectives [ 6 ].

This definition is based on the following three keywords:   

Situatedness: means that the agent

receives sensory data directly from the environment and can perform actions that are intended to modify it.

Autonomy: means that the agent can act

by itself without external direct intervention.

Flexibility: is related to the notion of

objective and intelligence.

Agents are considered granule system components responsible for part of the overall task, and communicating with the others. According to their properties and capabilities agents can be classified into one of the three main categories: reactive, cognitive, hybrids. A Multi-Agent system is defined by K. Sycara [ 7 ] as the emergence of a global behavior generated by a set of interactions between agents to solve problems that are beyond their individual reasoning capabilities. MAS can be classified according to several criteria: size and number of agents, interaction mechanisms, etc... However, two main features emerge from MAS. - The cognitive abilities : of agents to specify their ability to plan their actions, to reason about actions and plans of other agents and to evaluate the environment. - The organization of MAS defines the relationship between each agent, the structure of communications between agents and the degree of cooperation. These "intelligent" agents have the following characteristics: (1) An explicit representation of knowledge, (2) The structuring of their mental states, and (3)The cognitive abilities: updating knowledge, planning and autonomy.

The BDI (Belief, Desire, and Intention) model [ 8 ] is the most commonly used approach for representing agent internal state. It is based on a widely known theory of human behavior developed by the philosopher Michael Bratman. It does not prescribe a specific implementation. The model can described in different ways, and in fact a number of different implementations have been developed. Besides, the BDI model has been used to build a number of significant real-world applications. Mental attitudes of agents according to the BDI model are:   

Beliefs: What the environment, agent knows its

Desires: The states to which the agent may want to get involved;

The intentions projects it intends to carry

out.

A BDI agent should update his beliefs with the information from its environment, decide which options are offered to him, determine new intentions and realize his actions according to his intentions. The concept of intention is the main part of this approach because it allows linking the goals, beliefs and commitments with a theory of action.

2.2. R BIGRAPHS

Bigraphical reactive systems were initially introduced by R.Milner [ 5 ] to provide a completely graphical intuitive formal model capable of representing at the same time connectivity and locality of distributed entities which is very close to MAS concepts. The proposal of BRS provides a model for information systems with mobile placing and mobile linking, in which real-world pervasive and distributed systems can be described and analyzed. Further it provides the unification of existing process calculi for concurrency and mobility (such as π-calculus, Petri nets, λ calculus, and so on) in a simpler way [ 9 ].

Structural Aspects: A bigraph is the combination of two independent structures place and link graphs. The place graph represents system entities geographical distribution. The link graph is a hypergraph representing interconnections between these entities. Within a BRS, system entities are represented by nodes and interactions between them are represented by edges (see Fig. 1). A node can be dotted with ports representing connexion points to edges or inner/outer names.

Each node has a control, which is an identifier belonging to a set that is called a signature (usually denoted as S). Each control indicates how many ports the node has, which controls are atomic (node empty), and which of the nonatomic controls are active (node permitting reaction inside) or passive. The inner names and outers names of a bigraph indicate connecters to which other bigraphs or roots (i.e. regions) can be connected. Such interconnection is possible only if the outer name of a bigraph or root is equal to the inner name of another bigraph. Sites represent holes into which a root or node can be nested. They are considered as an abstraction indicating the presence of other elements. Definition [ 5 ]: a bigraph is formally defined by G= (V, E, ctrl, GP,GL) ∶ I → J, I = <m, x>, J = <n, y>, where: - V and E represent finite sets of nodes and edges respectively. - ctrl ∶ V → K a control map that assigns a control to each node. The signature K is a set of controls. - GP and GL are respectively.

Place and Link graphs

- I and J represent inner and outer names (interfaces) respectively of the bigraph G.

Bigraph can also be expressed by term language, in [ 9 ] Milner axiomatises the structure of bigraphs, to prove that the theory is complete, the algebra of bigraphs structure is surprisingly simple, the primary operations and elements used in this paper are summarized in Table 1.

Dynamical aspects: Bigraphs structural dynamics is expressed through A BRS (Bigraphical Reactive System) consisting of a category of bigraphs and a set of reaction rules; each one defines a redex bigraph to be transformed to a reactum bigraph.

Formally, a reaction rule takes the form(R,R’,n) where R : m → J is a redex, R’ : m’ → J is a reactum and n : m’ → m is a map of ordinals [ 5 ]. The category of all bigraphs and their reaction rules constitute a BRS.

3. Related work

Actualy there are two ADLs that have been dedicated to the description of MAS architecture, first SKwyRL-ADL [ 10 ]. Which is based on the first-order logic and presents a set of architectural concepts based primarily on the BDI agent model and the conventional ADL. MAS modeling can be processed on two levels: internal or global. The Internal model captures the states and potential behavior of the agent. In turn, the global model is used to describe the interaction between the agents that compose the MAS architecture. The second is ADLMAS [ 11 ] an architectural description language of SMA, which is based on Object Oriented Petri Nets as a theory and formal basis. ADLMAS is used to represent the concurrency, synchronization and distribution aspects of MAS at the individual (agent) and the social (MAS) level. However, these approaches handle the static check; the use of predicates does raise the issue that checking for the satisfaction of predicates is not decidable. Also they lack of intuitive graphical representation and mechanisms to describe constraints, hierarchies and it’s difficult to express dynamic aspects of architectural evolution.

4. A bigraphical model for system architecture multiagent

From futures of the BDI model and the bigraphical reactive systems literature proposed in the section 2, the objective of our work is to come up with a formal model able to specify BDI-MAS architecture. Therefore this section proposes a formal approach based on bigraphs devoted to the conceptualization of BDI-MAS architecture.

Bigraphs represent a sophisticated tool to formalize BDI-MAS architecture elements, providing graphics and languages based terms elements to model both static and dynamic architectural aspects. The underlying model only consider element relative to architecture modeling of BDI-MAS (components and the relationships among them) and do not consider the functional semantic or heuristics on which for example a plan is chosen among others. At a high level of abstraction, multiagent system is considered as a set of computing entities (a set of agents) that are distributed across multiple sites, and are often referred to as nodes. In Table 2 we summarize fundamental elements intervening in a BDI-MAS architecture.

4.1. Structural description of the BDI-MAS model:

BDI-MAS, models the architecture at two levels of abstraction the agent level and the social level. The former describes the internal structure and state of the agent (i.e. the basic construct elements of the MAS) and the second describes the assembly and interaction among agents that compose the MAS architecture.

Agent level: Figure 2 describes a BDI agent and its internal structure, generally an agent is situated in a root representing the agent physical/logical location. Each agent (denoted by AG) is composed of three principal nodes which in turn contains other nodes that structure them. In what follows we will take a closer look on the nodes that compose the agent AG1:

The beliefs (the B node) represent the vision that the agent has of the world. They correspond to the information that the agent has on the environment and on the other agents. They can be incorrect, incomplete or uncertain. Beliefs change as and when the agent, (1) by his ability of perception or interaction with other agents through the input and output interface respectively x and y, whose aim is gathering information. (2) Following the execution of a plan, the updating of beliefs in this case is achieved through the e1 link that connects the respective ports of the nodes B and I. Node B is composite type it contains atomic nodes that represent knowledge which constitute the beliefs of the agent AG (denoted by K).

The desires (node G) or goals of the agent represent the states of the environment, and itself, that the agent would like to see realized. These goals can be internal or external to the agent (as part of collaboration between agents, MAS level). An agent may have conflicting desires. In this case, he has to choose among his desires a subset which is consistent. This consistent subset of its desires is identified with the goals of the agent. They are represented as plans not yet instantiated to allow the agent to achieve its goals. A desire is represented as a node (denoted by D1, D2) which contains a Port through which it can choose the plan to be instantiated and therefore to execute in order to satisfy the desire in question.

Intentions (node I) of an agent are the desires that the agent has decided to perform or actions he decided to do to accomplish its desires. Even if all the desires of an agent are consistent, the agent may not be able to accomplish all his desires at once. There are stacks of instantiated plans where each plan (denoted by P) is dedicated to satisfy one and only desire. Furthermore, AG is dotted of two ports attached to an inner interface x and an outer interface y that allow an agent to interact with other agents and the environment, and is used to send and receive messages between agents. The presence of the site 0, site 1, site 2, site3, site 4 means that the model take into account the dynamic deploying of new agents, knowledge, plans and goals and also in our MAS architecture. The signature associated to a BDI-MAS bigraph is as follows: K = { L: (2, active), M: (1, active), N :( 0, active), O :( 1, atomic), P :( 0, atomic)}, L, M, N, O and P represents controls associated to different nodes. The different nodes types used in the model and their associated controls are summarized in Table 3. Social level: MAS architecture is presented in term of an interconnected set of Agents that interact. The model presented provides notations for describing the structure of MAS in terms of hierarchical configurations of interacting components. It provides an explicit and common basis for describing MAS architectural configurations (see figure 3).

Each agent carries out some part of the total computation and interacts to combine their behaviors, resulting in a behavior for the system as a whole. Interactions can be quite complex where each agent can initiate communication, generate messages, and respond to other agents’ messages, in order for agents participating in these interactions to achieve overall system goals[1], The interaction is the means for setting dynamic relationship more agents in the system and how this relationship is made. We distinguish several ways to achieve this coupling:  

By not managed indirect interaction mediated by the environment; By direct, managed, punctual and instantaneous interaction;

4.2. Modeling BDI-MAS

Reconfiguration

Architectural

Albeit, bigraphs are enough to formally specify BDI-MAS architectural components and their interaction scheme. Therefore, BDI-MAS architecture dynamics is formalized using reaction rules expressing changes of form in terms of shape shifting while preserving architectural constraints. In this subsection, we give some reaction rules samples defined to model BDI-MAS internal and external behavior and reconfiguration.

 Resolution of an external goal SMA level: The reaction rule figure 4 describes how an agent through its interfaces (input and output) communicates with other agents to satisfy its goals. At the level of the node G there is a desire D1 waiting to be satisfied, except that the current agent does not have enough knowledge to come to solve this goal, so the construction of a plan is not possible. Therefore the agent AG initiates a connection with the AG1 agent in the form of request (a correspondence between the input and output interfaces of the two agents results in the creation of the link e4). The agent AG1 receives this request and processes it within the limits of its skills. At this point there are two cases either: (1) the agent refuses / does not understand the request. In this case nothing happens internally; only the requesting agent will receive an informational message of refusal or not understanding for the request which he has emitted. (2) The agent accepts and thus the desire D1 of the agent AG is added to the desires of the agent AG1.At this stage, it becomes a resolution of an internal goal (Reaction rule defined above) when the desire D1 is satisfied at the agent AG1 which updates its beliefs (node B). The internal process finished, the agent AG receives through its input interface (e5 link), the knowledge he needs, so now he has the opportunity to build its own plan to satisfy the desire D1.

The algebric specification of the rule is:

AGxy .(Be1.(K|K1|d2) |G.(D1|d4)|I.(d3)|d1)| AG1xy.(B1e2.(K2|d7)|G1.(D3|d9)|I1e2.(d8) |d6) → AGxy .(Be1.(K |K1 |K3 |d2) |G.(D1e6 |d4) |I.(P2e6 |d3) |d1) | AG1xy.(B1e2.(K2 |K3 |d7) |G1.(D3 |d9)|I1e2.(d8) |d6) The resolution of an external goal can be expressed in a single reaction rule named rlcollaboration which is none other than the execution of a sequence of reaction rules.

Due to the lake of space algebric specification of the resolution of internal goal and adding of a new agent rules are given without graphical representation: 

Resolution of an internal goal (agent level):

AGx y .(Be1.(K |d2) |G.(D1 |d4) |Ie1 .(P |d3) |d1) |d0 → AGx y .(Be1.(K |K1 |d2) |G.(D1e2 |d4)| Ie1 .(Pe2 |d3) |d1) |d0 The reaction rule algebraic specification describes how our BDI agent is able to solve an internal goal, 

Adding a new agent:

AGxy.(Be1.(K |K1|d2)|G.(D1e2|d4)|Ie1 ).(Pe2 |d3) |d1) |d0 → AGxy.(Be1.(K |K1|d2) |G.( D1e2 |d4)| Ie1 .(Pe2 |d3)|d1) | AG1xy.(B1e4.(K1|K2|d7)|G1.(D2e5|d9)| I1e4.(P1e5|d8)|d6) The reaction rule algebraic specification describes the reconfiguration of a MAS at the architectural level. That’s to say the addition of a new agent into a given configuration (here the adding of the agent AG1).

5. Case study

In what follows we present a case study that was borrowed from [ 11 ]. This case study represents a BDI (Belief, Desire and Intention) multi-agent system to model an electronic commerce system. The system includes three agents: a customer (buyer) and two sellers. The customer negotiates with the two sellers to decide which one to choose on the basis of the price (see figure 5).

The customer (buyer) is denoted by agent CL. Agents BY1 and BY2 represent the sellers. These agents have the same standard architecture defined in our BDI-MAS model. In what follows we show through reactions rules how the client interacts with the two vendors to fulfill its transaction. - First, the buyer must show the desire to buy a product (the desire to know the price of a given product): the desire is noted by D1. - Then, a negotiation protocol ( FIPA contract net protocol [ 12 ]) is followed. - The agent CL sends a Call For Proposal (CFP) to all the sellers thru its output interface y. - A connection is established between the output interface of the agent CL and the input interfaces of the agents BY1, BY2. - The agents BY1 and BY2 get the CFP as a desire (denoted by D1).

Agents BY1 and BY2 formulate their proposals by conducting an internal goal resolution of the desire D1. This results in the emergence of the knowledge K3, K4 in the beliefs modules of the seller’s agents B1 and B2. - The agent CL through its input interface creates links e5 and e6 to receive the proposals of both sellers. - Finally, agent CL chooses the best proposal with respect to knowledge of the agent (e.g. the client's budget). The knowledge K4 is added to the beliefs module B of the agent CL.

Thus the desire D1 (to know the price of a product) is solved. Therefore, an update of the desires (module G) is performed. As a result a new desire D2 (desire to acquire a product) appears at the node G.

Algebric specification Make and send proposal rule: CLxye5e6 .(Be1.(K |d2) |G.(D1|d4)|Ie1.(d3)|d1)|d0|| BY1xye5.(B1e2.(K1|K3|d6)|G1.(D1e7|D3|d8) |I1e2.(P2e7 |d7) |d5)| BY2xye6.(B2e4.(K2|K4|d9)|G2.(D1e8 |d11) | I2e4.(P3e8 |d10)|d12)|d13 → CLxy .(Be1.(K|K4|K5|d2) |G.(D4|d4)|Ie1.(d3)|d1)|d0|| BY1xy.(B1e2.(K1|K3|d6)|G1.(D3|d8)|I1e2.(d7) |d5)| BY2xy.(B2e4.(K2|K4|d9)|G2.(d11) | I2e4.(d10)|d12)|d13

6. Conclusion

In this paper, we have proposed a formal modeling approach of the BDI-MAS architecture. The system has been specified at both individual (agent) and social (MAS) levels. The BDI-MAS bigraph simplifies considerably the MAS architectures readability. The model emphasizes on both locality and connectivity that can be used to represent the location and interconnection of MAS architectures. On the other hand reaction rules allow developers to correctly analyze the BDI-MAS architecture features, including modeling the behavior of the BDI agents and describing reconfigurations that could be added to the architecture.

In the perspectives of this work, we plan to:

Formally analyze and verify some BDI-MAS architectures properties such as deadlock. Provide a tool that generate executable implementation from our BDI-MAS architecture model,

Develop the model to address issues such as Mobility, and dynamic reconfiguration of agents.

7. REFERENCES

[1] R.J. Allen, “A Formal Approach to Software Architecture,” PhD thesis, CMU Technical Report CMU-CS-97-144, Carnegie Mellon Univ., May 1997.

References

[2] D.L. Parnas , “ On the Criteria to Be Used in Decomposing Systems into Modules,” Comm. ACM , vol. 15 , pp. 1053 - 1058 , 1972 .

[3] R.J. Allen , R. Douence , and D. Garlan , “ Specifying and Analyzing Dynamic Software Architectures” , In Proc. of FASE'98 , Lisbon, Portugal, 1998 .

[4] F. Oquendo , “ π-ADL: An architecture description language based on the higher-order typed - calculus for specifying dynamic and mobile software architectures” , ACM SIGSOFT , 2004 (3), pp. 1 - 14 .

[5] R. Milner , ” Bigraphs and their algebra” , In Proceedings of the LIX Colloquium on Emerging Trends in Concurrency Theory (LIX 2006 ),Electronic Notes in Theoretical Computer Science, Volume 209 , Elsevier , 2008 , pp. 5 - 19 .

[6] N.R. Jennings , “ An Agent-Based Approach for Building Complex Software Systems , ” Comm. ACM , vol. 44 , no. 4 , pp. 35 - 41 , 2001 .

[7] K.P. Sycara . The many faces of agents . AI Magazine , 19 ( 2 ) : 11 - 12 , 1998 .

[8] A.S. Rao and M.P. Georgeff , “ Modeling Rational Agents within a BDI-Architecture,” Proc. Second Int'l Conf . Principles of Knowledge Representation and Reasoning (KR '91) , pp. 473 - 484 , 1991 .

[9] R. Milner “ Axioms for bigraphical structure” , University of Cambridge, The Computer Laboratory, Cambridge CB3 0FD, UK, Tech. Rep , UCAM-CL- TR- 581 , February 2004 .

[10] S. Faulkner , and M. Kolp . "Towards an Agent Architectural Description Language for Information Systems." ICEIS (3) . 2003 .

[11] Z. Yu , Y. Cai , Yu , Z. , & Cai , Y. “ Object-oriented Petri nets based architecture description language for multi-agent systems” . IJCSNS , vol. 6 , no 1, 2006 .

[12] R.G. Smith, "The Contract Net Protocol: HighLevel Communication and Control in a Distributed Problem Solver," IEEE Trans. Computers , vol. 29 , no. 12 , pp. 1104 - 1113 , Dec. 1980 .