# Multi-agent Systems Design and Prototyping with Bigraphical Reactive Systems

Alessio Mansutti, Marino Miculan, Marco Peressotti

► To cite this version:

Alessio Mansutti, Marino Miculan, Marco Peressotti. Multi-agent Systems Design and Prototyping with Bigraphical Reactive Systems. 4th International Conference on Distributed Applications and Interoperable Systems (DAIS), Jun 2014, Berlin, Germany. pp.201-208, 10.1007/978-3-662-43352-2_16. hal-01287744

HAL Id: hal-01287744

https://inria.hal.science/hal-01287744

Submitted on 14 Mar 2016

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Multi-agent systems design and prototyping with bigraphical reactive systems*

Alessio Mansutti

Marino Miculan

Marco Peressotti

Laboratory of Models and Applications of Distributed Systems,
Department of Mathematics and Computer Science, University of Udine, Italy
alessio.mansutti@gmail.com, mm@uniud.it, marco.peressotti@uniud.it

**Abstract.** Several frameworks and methodologies have been proposed to ease the design of Multi Agent Systems (MAS), but the vast majority of them is tightly tied to specific implementation platforms. In this paper, we outline a methodology for MAS design and prototyping in the more abstract framework of *Bigraphical Reactive Systems* (BRS). In our approach, components and elements of the application domain are modelled as *bigraphs*, and their dynamics as graph rewriting rules. Desiderata can be encoded by means of type systems or logical formulae. Then, the BDI agents (i.e., their beliefs, desires and intentions) are identified and extracted from the BRS. This yield a prototype which can be run as *distributed bigraphical system*, evolving by means of distributed transactional rewrites triggered by cooperating agents depending on their internal intentions and beliefs.

This methodology allows the designer to benefit from the results and tools from the theory of BRS, especially in the requirement analysis and validation phases. Among other results, we mention behavioural equiva-
lences, temporal/spatial logics, visual tools for editing, for simulation and for model checking, etc. Moreover, bigraphs can be naturally composed, thus allowing for *modular design* of MAS.

## 1 Bigraphical reactive systems

*Bigraphical Reactive Systems* (BRSs) [12] are a flexible and expressive meta-model for ubiquitous computation. System states are represented by *bigraphs*, which are compositional data structures describing at once both the locations and the logical connections of (possibly nested) components of a system (see Figure 1). Like graph rewriting, the dynamic behaviour of a system is defined by a set of (*parametric*) *reaction rules*, which can modify a bigraph by replacing a *redex* with a *reactum*, possibly changing agents’ positions and connections.

BRSs have been successfully applied to the formalization of a broad variety of domain-specific calculi and models, from traditional programming languages to process calculi for concurrency and mobility, from context-aware systems to web-service orchestration languages; a non exhaustive list is [2, 4, 9, 17]. Very recently bigraphs have been used in structure-aware agent-based computing for modelling

<footnote>* Work partially supported by MIUR PRIN project 2010LHT4KM, CINA.</footnote>
<figure><img src="image_2.png" /><figcaption>Fig. 1. Forming a bigraph from a place graph and a link graph.</figcaption></figure>

the structure of the (physical) world where the agents operates (e.g., drones, robots, etc.) [13]. Another inspiring recent development is a formal connection between ontologies and a particular class of BRS recovering inference and (non-monotone) reasoning as graphs rewrites and reachability tests.

Beside their normative and expressive power, BRSs are appealing because they provide a range of interesting general results and tools, which can be readily instantiated with the specific model under scrutiny: simulation tools, systematic construction of compositional bisimulations [12], graphical editors [8], general model checkers [15], modular composition [14], stochastic extensions [10], etc.

The key point of BRSs is that “the model should consist in some sort of reconfigurable space”. Agents may interact in this space, even if they are spatially separated. This means that two agents may be adjacent in two ways: they may be at the same (abstract) *place*, or they may be connected by a *link*. This leads to the definition of *bigraphs* as an enriched hyper-graph combining two independent graphical structures over the same set of *nodes*: a hierarchy of places called *place graph*, and a hyper-graph of connections called *link graph* [12, Def. 2.3]. Each node in a bigraph is decorated with a type called *control* specifying additional properties such as the number of available link endpoints (*ports*). The set of available controls is called *signature* and is often denoted as $\Sigma$. We refer the reader to [12] for a precise and extensive presentation of BRS.

Figure 1 shows how a place graph and a link graph are merged yielding a bigraph. In particular, it portrays the state of a system composed by interconnected cars. These cars can move across an abstract topology described by a graph of locations; each location is presented as a (rectangle-shaped) node whose sub-nodes represent the cars at each location (car-shaped), the antenna coverage (triangle-shaped), and location interconnections (circle-shaped). Finally, a cross-shaped node is used to mark the destination of cars linked to it.

<figure><img src="image_3.png" /><figcaption>Fig. 2. Applying a parametric rewriting rule.</figcaption></figure>
The dynamic behaviour of a system is described in terms of *reactions* of the form $a \to a'$ where *a*, *a'* are bigraphs of the given BRS. Reactions are defined by parametric rewriting rules i.e. pairs of bigraphs ($R_L, R_R$) equipped with a function from the sites (parameters) of $R_R$ to those of $R_L$ called *instantiation rule*. An example is provided in Figure 2 where the rewriting rule *R* (on the left) is applied to the bigraph in Figure 1 (yielding the bigraph on the right); the instantiation map is denoted by red arrows, keeping track of which nodes are created or deleted in the process (this extra information is functional to the results presented in this paper and is not required by the bigraphical framework).

BRS usually include a *sorting discipline* for ruling out spurious (i.e. non well-formed) states. In their general form, sortings are judgements over bigraph and reactions and can be used to model additional properties such as desiderata for the systems e.g. "a car reaches its destination" as will be discussed later.

## 2 From BRS to MAS

The first step for translating a specification given as a BRS (optionally enriched with properties and desiderata) to a MAS is to distinguish between *subjects* and *objects* in the domain model, i.e. which entities can perform actions and which cannot. This distinction is not necessarily unique and is intrinsically part of the specification; in fact, many approaches found in literature assume similar distinctions, although usually tailored to specific implementations (e.g. by means of specific classes in the ontology modelling the problem domain [3, 16]).

Subjects and objects may be defined as specific configurations of portions of the bigraph, but a simpler characterization can be done in the signatures, i.e. by partitioning $\Sigma$ into the set of subject ($\Sigma_s$) and the set of object ($\Sigma_o$) controls. This solution prevents ambiguities (e.g. arising from overlapping configurations) and simplifies the mapping between agents and their BRS specification. Controls can be either *active* or *passive*: reactions can take place only within an active context (i.e. a context obtained by nesting only active controls). A subject can be temporary inhibited by a passive context, like, for instance, a virtualized machine that is halted by its supervisor in response to some suspicious behaviour.

A bigraph in the BRS is a model of the global state of the system and hence it is natural to read nodes decorated with subject controls as BDI agents in the prototype MAS. Then, bigraphical reactions model agent reconfigurations where node creation/destruction translates in agent creation/termination accordingly to the instantiation map. An example of reconfiguration induced by a bigraphical rewrite is illustrated in Figure 3 where the signature $\Sigma$ is defined as the union of $\Sigma_s = \{\Box:0, \Delta:2\}$ and $\Sigma_o = \{\Box:1\}$. Each bigraph is mapped into a family of agents hierarchically organised mirroring the place graph structure (which represents strong relations e.g. spatial or administrative ones); hence agents are aware of their parent and children along this hierarchy. Object nodes are collapsed in the internal state of the agent associated to their nearest ancestor. This mapping is consistent with the forest structure of place graphs, the idea that ancestors represent the environment and object the passive entities carrying data. From
<figure><img src="image_4.png" /><figcaption>**Fig. 3.** The MAS induced by a BRS over $\Sigma_s = \{\Box:0, \Delta:2\}$ and $\Sigma_o = \{\Box:1\}$.</figcaption></figure>

this perspective, circular nodes in Figure 3 can be read as sandboxes used by square agents to wrap and host foreign (triangular) ones.

The mapping induced by $\Sigma_s$ and $\Sigma_o$ defines a partition of the place graph assigning to each agent a portion of the global state. This portion corresponds to the public image of the agent’s internal state (*public state*) and strong consistency is assumed only for this information (whereas other approaches assume a shared consistent state [13], as in the case of blackboard systems). A similar approach is adopted for the link graph however, hyper-edges are intrinsically “less-local” than place dependencies and it is very common for an hyper-edge to span over several nodes, e.g. in the case of a shared communication medium like a network. Therefore, assuming that agents sharing a hyper-edge are consistently aware of each other may be very demanding. To mitigate this shortcoming, consistency (and hence agent public states) is limited to the hyper-edge handles (i.e. the name associated to a hyper-edge). This solution can be read as if agents were linked only through some mediating proxy (middleware). However, the use of handles does not preclude the presence of (full) hyper-edges in agent beliefs since these are not required to be consistent (differently from public states). Links and handles are pictured in Figure 3 as green thick lines and diamonds.

Agent beliefs are the view that an agent has of the system i.e. a bigraph which is not guaranteed to be consistent with the global state. The only part of it that can be safely assumed to be consistent is the agent *public state*, i.e., the portion of the global bigraph mapped into the agent and its neighbouring agents. Note that a system-wide snapshot of public states always yields a consistent view of the global state represented by means of a bigraph (from the specification BRS). Inconsistencies may appear only between agents beliefs but are readily addressed by means of logical timestamps thanks to the mapping between BRS and MAS states. In practice, each agent will maintain an internal counter that is incremented at every update of its public state and attaches this value to its public state, hence effectively implementing logical timestamps – since bigraphs are uniquely partitioned and assigned to agents by the aforemen-
tioned mapping. This simple mechanism offers a way to locally resolve conflicts between cooperating agents and their beliefs. (Terminated agents are handled by death certificates as usual.)

A cornerstone in the theory of bigraphs is the concept of *idempotent pushouts*<fnref n="1" /> (IPO) [12, Def. 4.4]. IPOs characterize the *minimal contexts* enabling a given reaction. The advantages of IPOs for our purposes are twofold: first, these minimal contexts can be used as minimal hypothesis during *planning* tasks; secondly the bound on the context simplifies distributed rewritings. In fact, an agent interested in performing some action can check its beliefs or actual context against those obtained from the IPO construction and negotiate the rewrite with the agents involved. The operation can be refined by locks or push/pull notification with the agent neighbourhood. Moreover, IPOs guarantee that reconfiguration operations will involve only the minimal number of agents.

In general, reactions of BRS are non-deterministic, but can be easily restricted by suitable sortings (over states and executions), e.g. by requiring or forbidding specific occurrences [1], type systems [7] and modal logics [5]. The same tools and techniques are used to decorate a BRS MAS specification with (global) properties and desiderata. The presence of deadlocks highlights conflicts between desires/goals and (non-confluent) non-determinism may be the symptom of an incomplete specification. However, in some cases, non-determinism may be desirable (e.g. to express events from outside the system) and therefore has to be supported by the model.

## 3 Structural properties and desiderata

In this Section we describe how properties and desiderata for a given BRS specification can be expressed by means of spatial and temporal logics. In particular, “spatiality” and “temporality” are used to characterize the states and transitions of the given BRS respectively. This is achieved by combining a temporal logic such as CTL (computational tree logic) on top of BiLog, a spatial logic for bigraphs [5]: BiLog formulae are seen as the atomic predicates of CTL. Although more complex combinations are possible (even spatial-temporal logics precisely designed for BRS), this rather simple stratification already yields a great expressive power. Moreover, this stratification allows us to readily adapt model checking algorithms for CTL by extending them with BiLog ones. In the following, we elaborate the BRS of “interconnected cars” introduced in the previous Sections and present how structural properties and desiderata are modelled in this spatial-temporal logic for bigraphs.

The first structural property we discuss requires that “cars always reach their destination”. This requirement is captured by the formula:

$$ \mathbf{AF}[\mathit{Car}_{c,x} | \mathit{Target}_x] \qquad (1) $$

<footnote n="1">¹ IPO are connected to the concept of borrowed context extensively used in the theory of graph rewriting systems; actually both are instance of GRPO.</footnote>
where BiLog sub-formula enclosed by the square brackets is satisfied only by those states where the car node is next to the target it is connected with. The AF operator is the CTL “all-future” temporal operator and states that, for every path starting from the current state, the BiLog predicate eventually holds. For instance, (1) holds for the bigraph in Figure 1 but not for any state where the car is spatially disconnected from its target (hence (1) effectively rules out “bad initial states”). Likewise, we can model the requirement “cars are always connected to some antenna wherever there is one” as follows:

$$ \mathbf{AG}([\mathit{id}_{\langle 1,x \rangle} | /_y] \otimes \mathit{Zone}(\mathbf{Car}_{y,x})) \lor [\mathbf{Car}_{a,x} | \mathit{Connection}_{a,c}] \quad (2) $$

In other words, a car is disconnected only if it is in a zone covered by no antenna.

Predicates (1) and (2) can be thought as temporal-structural requirements about the system; on the other hand, we can use the same logic to express desires, e.g., the desire “there exists a route such that the car is never disconnected” (at least until the target is reached) is expressed by:

$$ \mathbf{E}([\mathbf{Car}_{c,x} | \mathit{Connection}_{a,c}] \mathbf{U} [\mathbf{Car}_{c,x} | \mathit{Target}_x]) \quad (3) $$

which combines (1) with a stronger version of (2). A predicate expressing a desire, like (3), may not be valid for a whole BRS, but this does not means that unsafe states are reached. In fact, agents will try to find suitable paths (i.e., by careful planning) accordingly to their desires and chosen goals.

# 4 Discussions and future work

In this paper we have outlined a methodology for modelling and simulating MAS as distributed BRS. The idea follows the direction of recent and interesting results where information is presented as suitable BRSs or used as a shared topological abstraction for agents [13]. Building upon the solid theory of bigraphs, this methodology offers a rapid prototyping tool aiding the designer in the requirement analysis and validation phases. Among the several theoretical results and practical tools offered by the BRS framework, we mention behavioural equivalences, temporal/spatial logics, visual tools for editing, for simulation and for model checking, etc. Moreover, bigraphs can be naturally composed, thus allowing for modular design of MAS. Overall, this methodology paves the way for cross-fertilizing transfer of results between MAS and BRS.

The use of bigraphs is eased by the support to *attached properties* offered by recent tools like BigRED and LibBig<fnref n="2" />. This feature allows bigraph components to be decorated with additional informations in the form of (typed) properties. In particular, LibBig supports property-aware matchings/rewritings, whose solutions are optimal w.r.t. property-based costs; this allows the designer to easily model and test in a declarative style cost-based policies (e.g. picking up the antennas with the strongest signal, or finding a shortest path).

<footnote n="2">² A Java library for extensible BRSs is available at http://mads.dimi.uniud.it/.</footnote>
The development of a distributed runtime for BRS is in its early stages and would surely benefit from tools and results developed for MAS. For instance, protocols and techniques like *speculative reasoning* [11] could be applied to compute distributed bigraphical reactions more efficiently and possibly ported to other bigraphical tools (in particular, model checkers).

We plan to investigate the connection between distributed matchings and the attribute-based agent-communication at the core of the language for automatic systems SCEL [6]. In both cases interactions are based on the public state (the *interface* in SCEL lingo). Another topic to be investigated is the extraction of a MAS from an (enriched) BRS; this construction resembles bigraphical refinements [14], suggesting the possibility to apply results from the field of (bi-graphical) language engineering to the approach presented in this paper.

## References

1. G. Bacci and D. Grohmann. On the decidability of bigraphical sorting. In *Proc. CALCO*, pages 1–14, 2009.

2. G. Bacci, D. Grohmann, and M. Miculan. Bigraphical models for protein and membrane interactions. In *Proc. MeCBIC'09*, pages 3–18, 2009.

3. C. Bernon, M. Cossentino, M.-P. Gleizes, P. Turci, and F. Zambonelli. A study of some multi-agent meta-models. In *AOSE*, pages 62–77, 2005.

4. L. Birkedal, S. Debois, E. Elsborg, T. Hildebrandt, and H. Niss. Bigraphical models of context-aware systems. In *Proc. FoSSaCS*, pages 187–201, 2006.

5. G. Conforti, D. Macedonio, and V. Sassone. Spatial logics for bigraphs. In *Proc. ICALP*, pages 766–778, 2005.

6. R. De Nicola, M. Loreti, R. Pugliese, and F. Tiezzi. A formal approach to automatic systems programming: the SCEL language. *ACM TAAS*, pages 1–29, 2014.

7. E. Elsborg, T. T. Hildebrandt, and D. Sangiorgi. Type systems for bigraphs. In *TGC*, pages 126–140, 2009.

8. A. J. Faithfull, G. Perrone, and T. T. Hildebrandt. Big Red: A development environment for bigraphs. In *Proc. GCM*, 2012.

9. T. T. Hildebrandt, H. Niss, and M. Olsen. Formalising business process execution with bigraphs and reactive xml. In *Proc. COORDINATION*, pages 113–129, 2006.

10. J. Krivine, R. Milner, and A. Troina. Stochastic bigraphs. In *Proc. MFPS*, pages 73–96, 2008.

11. J. Ma, K. Broda, R. Goebel, H. Hosobe, A. Russo, and K. Satoh. Speculative abductive reasoning for hierarchical agent systems. In *CLMAS*, pages 49–64, 2010.

12. R. Milner. *The Space and Motion of Communicating Agents*. CUP, 2009.

13. E. Pereira, C. M. Kirsch, R. Sengupta, and J. Borges de Sousa. Bigactors—a model for structure-aware computation. In *Proc. ICCPS*, 2013.

14. G. Perrone, S. Debois, and T. T. Hildebrandt. Bigraphical refinement. In *Proc. Re-fine*, pages 20–36, 2011.

15. G. Perrone, S. Debois, and T. T. Hildebrandt. A model checker for bigraphs. In *Proc. SAC*, pages 1320–1325, 2012.

16. P. Ribino, M. Cossentino, C. Lodato, S. Lopes, L. Sabatucci, and V. Seidita. Ontology and goal model in designing BDI multi-agent systems. In *WOA@AI*\*\*IA, pages 66–72, 2013.

17. M. Zhang, L. Shi, L. Zhu, Y. Wang, L. Feng, and G. Pu. A bigraphical model of WSBPEL. In *TASE'08*, pages 117–120, 2008.