Environments of multiagent systems typically feature the application of techniques coming from the research context of complex systems: adaptivity and self-organisation are exploited in order to tackle recurrent issues in multiagent systems applications like openness, dynamism and unpredictability. By adopting the “agents and artifacts” meta-model, we conceived the environment as populated by artifacts: as a specific case, we consider them as information repositories storing relevant facts about the external world and agent interaction/coordination. We focus on the coordination problem called collective sort, where autonomous agents in charge of managing such artifacts have the goal of moving information across different artifacts according to local criteria, resulting in the emergence of the complete clustering property. Using a library we developed for the Maude term rewriting system, we simulate the behaviour of this system and evaluate a full solution to this problem.
Systems that should self-organise to face unpredictable changes in the surrounding conditions often
need to achieve adaptivity as an emergent property. As this observation was first made in the
context of natural systems, it was shortly recognised as an inspiring metaphor for artificial systems
as well [3]. However, a main problem with emergent properties is that, by their very definition,
they cannot be achieved through a systematic design: their dynamics and outcomes cannot be
fully predicted. Nonetheless, providing some design support in this context is still possible. The
whole system of interest—that is, the system application and the environment it is immersed in—
can be partially modelled, e.g. as a stochastic system (whose dynamics and duration aspects are
probabilistic). In this scenario, simulations can be run and used as a fruitful tool to predict certain
aspects of the system behaviour, and to support a correct design before actually implementing the
application at hand [
This scenario is particularly interesting for the design of MAS environments [
We consider the “agent and artifacts” meta-model for MAS as a reference [
In particular, when developing an environment built upon tuple spaces, we recognise tuples
distribution among tuple spaces as a main concern: indeed, having tuples sorted out may improve
overall system efficiency. Hence, we get inspiration from the brood sorting problem [3] to evaluate
a solution for sorting tuples in a distributed tuple space scenario: we call this problem collective
sort —as we originally suggested in [
We show a first solution to this problem considering a simplified scenario: environmental agents, each associated to a particular tuple space S and a particular tuple type T , have the private goal of ensuring that S is not wrongly collecting tuples of the type T . This goal is achieved by moving away tuples which are apparently not contributing to perfect clustering. Despite the locality of this criterion, complete sorting emerges from initial chaotic tuple configurations. In order to obtain full convergence from any initial state, we refine the model introducing the concept of space vacuum, leading to the full solution of the collective sort problem.
To devise design choices, and provide evidence of correctness and appropriateness of our
approach, we relied on simulations throughout. Many simulation tools can be exploited to this end,
though they all necessarily force the designer to exploit a given specification language, and
therefore better apply to certain scenarios and not to others—examples are SPiM [
The remainder of this paper is as follows: Section 2 provides some background on coordination techniques featuring adaptivity, Section 3 briefly introduces our simulation framework, Section 4 describes the collective sort scenario, and finally Section 5 presents the full solution we conceived for this problem. 2
Environment models and technologies for multiagent systems are moving towards the application of self-organising techniques, most of which are inspired by natural phenomena.
A first example is the TOTA (Tuples On The Air) middleware [
Another example is the AGV (automatic guided vehicles) application described in [
A similar mechanism is generalised and adopted in the Digital Pheromone Infrastructure [
In the effort to handle the design of this kind of environments, bridging the gap between abstract
model and implementation, it has become very common practice to take into account quantitative
aspects like temporal and probabilistic ones, which are necessary in order to tackle systems that
should feature emergent properties—see e.g. [
In [
Maude is a high-performance reflective language supporting both equational and rewriting logic,
for specifying a wide range of applications [
Inspired by the work of Priami on the stochastic π-Calculus [
Given a transition system of this kind and an initial state, a simulation is simply executed by: (i) checking each time the available actions and their rate; (ii) picking one of them probabilistically (the higher the rate, the more likely the action should occur); (iii) accordingly changing the system state; and finally (iv) advancing the time counter according to an exponential distribution, so that the average frequency is the sum of the action rates.
As an example, we consider the N a − Cl chemical reaction dynamics, provided e.g. in SPiM documentation1. Syntax and semantics of this system is expressed in our Maude library as follows: op <_,_,_,_> : Nat Nat Nat Nat -> State . vars Na Na+ Cl Cl- : Nat . eq < Na,Na+,Cl,Cl- > ==> = ( ion # (float(Na * Cl) * 1.0) ->
[< p Na,s Na+,p Cl,s Cl- >] ); ( deion # (float(Na+ * Cl-) * 2.0) ->
[< s Na,p Na+,s Cl,p Cl- >] ) .
This system is characterised by a state of the kind <Na,Na+,Cl,Cl->, where Na is the number of
sodium atoms, Na+ the number of sodium ions, Cl is the number of chlorine atoms, Cl- the number
1http://www.doc.ic.ac.uk/~anp/spim/Chemical.pdf
of chlorine ions. Two kinds of constant actions are then defined: ion stands for ionization and
deion for deionization. Finally, the transition system is expressed by a single equation, associating
to any state two possible effects: one in which ionization decrements Na and Cl (by prefix predecessor
function p) and increments Na+ and Cl- (by prefix successor function s), and the other that behaves
in the opposite way. Note that, according e.g. to the Gillespie selection algorithm in [
We consider a case inspired by the Swarm Intelligence problem known as brood sorting [3]. It features a multiagent system where the environment is distributed and populated with items of different kinds: the goal of agents is to collect and move items across the environment so as to collect and order them according to an arbitrary shared criterion. This problem basically amounts to clustering: homogeneous items should be grouped together and should be separated from others. Moving to a typical context of MAS software environments, we consider the case of a fixed number of artifacts resembling tuple spaces, hosting tuples of a known set of tuple types. The goal of agents is to move tuples from one tuple space to the other until they are clustered in different tuple spaces according to their type: we call this problem collective sort. Note that the agents are not aware of their cooperative attitude since it is implicit in their goal, and they do not have to interact nor need to perceive other agents.
In several scenarios, sorting tuples may increase the overall system efficiency. For instance, it can make it easier for an agent to find an information of interest based on its previous experience: the probability of finding information where a previous and related one was found is high. Moreover, when tuple spaces contain tuples of one kind only, it is possible to apply aggregation techniques to improve their performance, and it is generally easier to manage and achieve load-balancing.
Increasing system order however comes at a computational price. Achieving ordering is a task that should be generally performed online and in background, i.e. while the system is running and without adding a significant overhead to the main system functionalities. Indeed, it might be interesting to look for suboptimum algorithms, which are able to guarantee a certain degree of ordering in time.
Nature is a rich source of simple but robust strategies; the behaviour we are looking for has
already been explored in the domain of social insects—the aforementioned brood sorting. Ants
perform similar tasks when organising broods and larvae: although their actual behaviour is still
not fully understood, there are several models that are able to mimic the dynamics of the system.
Ants wander randomly and their behaviour is modelled by two probabilities, respectively, the
,
(1)
where k1 and k2 are constant parameters and f is the number of items perceived by an ant in its
neighborhood: f may be evaluated with respect to the recently encountered items. To evaluate the
system dynamics it can be useful to provide a measure of the system order. Such an estimation
can be obtained by measuring the spatial entropy, as done e.g. in [
We conceive a multiagent system where a collection of agents are users of some tuple spaces, forming their environment, and interact with/via them to achieve social goals: in particular, agents are allowed to read, insert and remove tuples in the tuple spaces. Additionally, and transparently to these agents, some further infrastructural support exists that provides tuple spaces with a sorting service, in order to maintain a certain degree of order of tuples in tuple spaces. This service is realised by a class of collector agents, spread in the nodes of the distributed environment along with tuple spaces, and which will be responsible for the sorting task.
We suppose that tuples belong to a well defined and globally shared set of tuple kinds. Each collector agent is implicitly associated to the tuple space S of the node where it is situated. For a specific single tuple kind K, the individual agent’s goal is to make sure that S is not wrongly collecting tuples of the kind K. Since we look for collecting a tuple kind in only one tuple space, this means that the agent should check that there is seemingly no other tuple space R collecting tuples K more than what S is currently doing, in which case some tuple K has to be moved to R. This scenario is depicted in Figure 1: an agent is moving a tuple of kind C from the left tuple space to the top one, since the latter is collecting tuples C more—and similarly for D. Since we want to perform this task online and in background, and with a fully-distributed, swarm-like algorithm, agents cannot compute the probabilities in Equation 1 to decide whether to move or not a tuple: the approach would not be scalable since it requires to count all the tuples for each tuple space, which might not be practical.
In general, a new primitive to access tuple spaces is needed which (i) can feature the locality
character, (ii) can take into account the different quantities of tuples occurring in the space at a
given time, and (iii) can possibly fit the semantics of some existing tuple space primitive—so as
not to impose a too severe semantic change. A reading primitive urd called uniform read is hence
introduced. This is a variant of the standard rd primitive that takes a tuple template and yields
any tuple matching the template: primitive urd instead chooses the tuple in a probabilistic way
[5000 : < 0 @ (’a[100]) | (’b[100]) | (’c[
Going back to our collective sort scenario, each agent has now the ability of performing a uniform read over all tuple kinds of a tuple space: in general, if a tuple of kind K is (uniformly) read, the agent can locally assume that, probabilistically, the tuple kind K is aggregating there more than others. 4.3
Given this general architecture for modelling the collective sort problem, providing a self-organising solution here means to identify the agents’ agenda—sequence of tasks—that could lead each agent to achieve its individual goal. For one such solution to be adequate, complete sorting has to be achieved as an emergent property of the overall system, form possibly any initial configuration of tuples.
Each agent is associated to its source tuple space S, seeks for moving tuples of kind K, and works at a given rate r—the frequency at which each agent schedules the execution of the agenda. The agent agenda we consider is as follows: 1. a destination tuple space D 6= S is drawn randomly; (a) Dynamics of the winning tuple in each tuple space (b) Dynamics of tuple space 0 (c) Entropy of tuple spaces 4. if K = KD 6= KS, then a tuple of kind K is moved from S to D.
At the time the first task is executed, the agent is focussing on whether one tuple of kind K has to be moved from S to D. At the third task, the agent perceives kind KS as the one aggregating most in S, and KD as the one aggregating most in D. Then, the point of last task is that a tuple of kind K is to be moved if and only if K is aggregating in D but not in S.
The success of this distributed algorithm is clearly affected by both probability and timing aspects. Will complete ordering be reached starting from a completely chaotic situation? Will complete ordering be reached starting from the case where all tuples occur in just one tuple space? And if ordering is reached, how many moving attempts are globally necessary? These are the sort of questions that a designer would like to address at the early stages of design without actually resorting to implementation, and that simulation can help addressing. 4.4
We represent the distributed state of a system in Maude using a syntax of the kind:
[ ’a , ’b , ’c , ’d ] | { 0 , 1 , 2 , 3 } |
< 0 @ (’a[100])| (’b[100]) | (’c[
< 0 @ (’a[100])|(’b[100])|(’c[
We simulated traces of execution starting from the above state, obtaining e.g. the behaviour shown in Figure 2. After some steps, some tuple starts moving from one space to the others. After 2024 time units, for instance, tuple kind ’c is already completely collected in tuple space 2. After 4600 time units, the system converged to complete sorting, as we expected. The chart in Figure 3 (a) reports the dynamics of the winning tuple in each tuple space, showing that complete sorting is reached at different times in each space. The chart in Figure 3 (b) displays instead the evolution of the tuple space 0: notice that only the tuple kind ’a aggregates here despite its initial concentration was the same of tuple kind ’b.
Although it would be possible to make some prediction, we do not know in general which tuple space will host a specific tuple kind at the end of sorting: this is an emergent property of the system and is the very result of the interaction of the tuple spaces through the agents! Indeed, the final result is not completely random and the concentration of tuples will evolve in the same direction most of the times. It is interesting to analyse the trend of the entropy of each tuple space as a way to estimate the degree of order in the system through a single value: since the strategy we simulate is trying to increase the inner order of the system we expect the entropy to decrease, as actually shown in Figure 3 (c). If we denote with qij the amount of tuples of the kind i within the tuple space j, nj the total number of tuples within the tuple space j, and k the number of tuple kinds, then, the entropy associated with the tuple kind i within the tuple space j is
Hij = qij log2 qij
nj nj Hj =
Pk i=1 Hij log2 k and it is easy to notice that 0 ≤ Hij ≤ k1 log2 k. The entropy associated with a single tuple space is then computed as where the division by log2 k is introduced in order to obtain 0 ≤ Hj ≤ 1.
2All the specifications cited in this article, charts and instructions for running simulations are available online at
http://www.alice.unibo.it
(2)
(3)
Considering the reference configuration of four tuple spaces and four tuple types, we made
several simulations varying the initial condition, i.e. tuples distribution among tuple spaces: different
configurations, i.e. consisting of a different numbers of tuple spaces and tuple types, will be
investigated in future works. Although, it initially seemed that the solution adopted always converged to
complete sorting, we later identified certain configurations that do not evolve properly. In
particular, there are certain states attracting the system trajectory and having positive entropy, that is,
characterised by a non-complete degree of sorting: we call such states local minima. In particular,
local minima seem not to be related to tuples distribution rather to the absence of tuples: an
example of such minimum is the following state
< 0 @ (’a[
The attempt of solving this problem is what lead us to the solution proposed in this article. 5 5.1
There are two main reasons why the local minimum analysed above cannot be escaped: (i) in spite tuple spaces 0 and 1 host a different number of tuples of kind ’a they are perceived in the same way by agents, for they both have 100% of tuples ’a—instead, it would be desirable to consider space 1 as a stronger aggregator—; (ii) there is no chance of moving a tuple ’c or ’d away from space 3, for no other space aggregates them at all.
These two issues can actually find a common solution by more carefully analysing the brood sorting problem for social insects. There, an ant takes some brood and releases it where a new place is found where brood has a greater concentration. Such a concentration is expressed as quantity of brood over a unit of space. That is, implicitly the ant compares the amount of brood with that of “vacuum” in the unit of space.
If a similar notion of vacuum would be defined in our collective sort example, and e.g. the same amount of vacuum would exist in each space, that could in principle allow to solve the two issues above. On the one hand, space 0 could be recognised as having “less” tuples ’a than space 1—since space 1 occupies less space for vacuum, relatively—and hence movements from space 0 to 1 could be promoted most. On the other hand, some tuples ’c or ’d could be moved from space 3 to another one following the reasonable idea that “tuples that are not aggregating much should fill the vacuum elsewhere”.
To evaluate this solution, we add to tuple spaces another kind of tuple called vacuum, and suppose the quantity of vacuum tuples in each space is the same and is fixed statically since the beginning. The uniform read operation can now possibly yield a vacuum tuple: the more such tuples exist with respect to those to be sorted, the more this event is likely. Then, following the above discussion, we change the agent agenda as follows: 1. a destination tuple space D 6= S is drawn randomly;
4. if K = KD 6= KS a tuple of kind K is moved from S to D.
5. if K 6= KS and KD = vacuum a tuple of kind K is moved from S to D.
Now both KS and KD could be vacuum. Our last task says that if the kind K is not aggregating locally (K 6= KS) and we find significant vacuum in D (KD = vacuum), then we move a tuple of kind K.
We considered the following as starting state: < 0 @ (’a[50])| (’b[0]) | (’c[0]) | (’d[0]) > | < 1 @ (’a[50])| (’b[0]) | (’c[0]) | (’d[0]) > | < 2 @ (’a[0]) | (’b[100])| (’c[0]) | (’d[0]) > | < 3 @ (’a[0]) | (’b[0]) | (’c[100])| (’d[100]) > By simulation we noticed that, independently from the number of vacuum tuples, the system escapes the local minimum reaching complete ordering; But of course such a number can potentially influence effectiveness and efficiency of the solution. Hence, in Figures 4 (a) and (b) we display how the sorting time and the number of tuples moved varies with the number of vacuum tuples in each tuple space. We note the following: (i) performance is actually dependent on the number of vacuum tuples; (ii) as vacuum tuples tend to be the same as the final number of tuples in a tuple space, i.e. 100%, performance degrades dramatically; (iii) sorting time has minima values around 20 and 75 vacuum tuples; (iv) the number of tuples moved increases with the vacuum. What we learn from these charts is that on the one hand, this technique brings anyway to convergence, but on the other, good performance is achieved if the number of vacuum tuples is around 20% of the final number of tuples expected in each tuple space. There in fact, we have a good combination of convergence time and resources allocated to sorting (i.e., number of tuples moved). 5.2
If we require a truly self-organising solution, we must devise a solution which works without knowing a priori any information about tuple distribution. Hence, we cannot statically design the number of vacuum tuples to be used in each tuple space: an adaptive technique has to be used to make this number dynamic, namely, to make vacuum adapting to the situation at hand. In principle, here we seek for a solution where vacuum is initially very low—guaranteeing to move tuples in a proper way—and then, when/if we are about to reach a local minimum, agents make vacuum locally increase guaranteeing to leave perilous states.
Informally, the idea is to increase vacuum each time an agent discovers two spaces aggregating the same tuple, and decrease vacuum when a tuple successfully moves towards an aggregator. That is, we add to the above agent agenda the following tasks: 6. if K = KD 6= KS drop one vacuum tuple from S 7. if K = KD = KS add one vacuum tuple to S In particular, we start from one vacuum tuple, and make sure that this level is never decreased. The charts in Figure 4 (a) and (b) show how this new technique (horizontal line) compares with the one with fixed vacuum. Namely, the behaviour we obtain has average values of convergence time and tuples moved, staying sufficiently far from divergence and bad performance.
Moreover, further simulations we performed on systems that converge with requiring the vacuum management (as in Section 4), show that our adaptive vacuum management does not significantly impact their performance, namely, it is a mechanism exploited on a by-need basis. 6
In this article we focussed on stochastic aspects in the designing of emergent coordination
mechanisms, an emergent issue in the research on MAS environments and in related research contexts.
The collective sort problem discussed is a paradigmatic one: indeed, it emphasises the typical
unpredictability of environment in coordination, e.g. in tuple space scenario, tuples distribution
in space. Any attempt to find general mechanisms to achieve global properties about such
configurations, will likely issue the same problems we identified in collective sort: complete/partial
convergence, performance vs. resource usage, need for adaptive mechanisms. Starting from the
work in [
Several interesting future works can be pursued: • In the context of collective sort, we plan to evaluate other load-balancing approaches, optimising the convergence to complete order, the vacuum mechanism, and studying the performance of our solution as tuple configurations change dynamically. • The library itself is currently a very simple prototype, but we believe it could be improved in several ways and become a very practical simulation tool. • Another interesting idea would be to apply our library to some existing coordination models like TOTA, and provide the necessary tests for the proposed algorithms.
[1] Recursive porous agent simulation toolkit (repast),
http://repast.sourceforge.net/. 2006.
Available online at [3] E. Bonabeau, M. Dorigo, and G. Theraulaz. Swarm Intelligence: From Natural to Artificial Systems. Santa Fe Institute Studies in the Sciences of Complexity. Oxford University Press, Inc., 1999.
Au[13] V. D. Parunak. ’Go To The Ant’: Engineering principles from natural agent systems. Annals of Operations Research, 75:69–101, 1997.