Multiagent Coordination by Stochastic Cellular Automata

1 Introduction

The term multiagent system encompasses large bodies of work from engineering, computer science, and mathematics. Examples include networks of mobile robots [Matari´c, 1992], software agents [Bonabeau et al., 1994], and cellular automata [Wolfram, 1984]. A common thread in all multiagent systems is the issue of coordination. How are a large number of sparsely coupled agents able to produce a coherent global behaviour using simple rules? Answering this question will not only permit the construction of interesting and useful artificial systems but may allow us to understand more about the natural world. Ants and the other social insects are perfect examples of local interaction producing a coherent global behaviour. It is possible for millions of ants to act as a superorganism through local pheromone communication. We seek to reproduce this ability on a fundamental level in order to coordinate artificial systems.

It can be argued that cellular automata (CA) are the simplest example of a multiagent system. Originally studied by [von Neumann, 1966], the term CA is used to describe systems of sparsely coupled difference equations. Despite their simple mechanics, some extremely interesting behaviours have been catalogued (e.g., Conway's Game of Life). The word self-organization is used in many contexts when discussing multiagent systems which can lead to confusion. Here we use it to mean multiagent coordination in the face of more than one alternative. We will be describing a stochastic version of cellular automata. The goal will be to have all cells choose the same symbol from a number of possibilities using only sparse communication. We maintain that rules able to succeed at this task are self-organizing because the cells are not told which symbol to choose, yet they must all coordinate their choices to produce a globally coherent decision. If we told the cells which symbol to choose, the task would be very easy and no communication between cells would be necessary. This can be dubbed centralized organization and is in stark contrast to self- or decentralized organization. We believe that coordination in the face of more than one alternative is at the very heart of all multiagent systems.

This paper is organized as follows. Related work is described, followed by a description of the model under consideration. Results of its performance on the multiagent coordination task are presented. Statistical analysis of the rule are provided followed by discussions and conclusions.

2 RelatedWork

In the following note that typically cellular automata do not operate in a stochastic but rather a deterministic manner. Unless explicitly stated (e.g., stochastic cellular automata (SCA)), the term cellular automata will imply determinism.

[von Neumann, 1966] originally studied cellular automata in the context of self-reproducing mechanisms. The goal was to devise local rules which would reproduce and thus spread an initial pattern over a large area of cells, in a tiled fashion. The current work can be thought of as a simple case of this where the tile size is only a single cell but there are multiple possibilities for that tile. Futhermore, we wish our rules to work starting from any random initial condition of the system.

Cellular automata were categorized by the work of [Wolfram, 1984] in which four universality classes were identified. All rules were shown to belong to one of class I (fixed point), class II (oscillatory), class III (chaotic), or class IV (long transient). These universality classes can also be identified in SCA and we will show that in our particular model, choosing a parameter such that the system displays long transient behaviour (e.g., class IV) results in the best performance on our multiagent coordination task.

[Langton, 1990] has argued that natural computation may be linked to the universality classes. It was shown that by tuning a parameter to produce different CA rules, a phase transition was exhibited. The relation between the phase transition and the universality classes was explored. It was found that class IV behaviour appeared in the vicinity of the phase transition. The current work is very comparable to this study in that we also have a parameter which can be tuned to produce different CA rules. However, our parameter tunes the amount of randomness that is incorporated into the system. At one end of the spectrum, completely random behaviour ensues while at the other completely deterministic behaviour ensues. We also relate the universality classes to particular ranges of our parameter and find a correlation between performance on our multiagent coordination task and class IV behaviour. We attempt to use similar statistical measures to [Langton, 1990] to quantify our findings.

[Mitchell et al., 1993], [Das et al., 1995] study the same coordination task as will be examined here in the case of deterministic CA. However, their approach is to use a genetic algorithm to evolve rules successful at the task whereas here hand-coded rules are described. They found that the best solutions were able to send long range particles (similar to those in the Game of Life) [Andre et al., 1997] in order to achieve coordination. These particles rely on the underlying structure of the connections between cells, specifically that each cell is connected to its neighbours in an identical manner. The current work assumes that no such underlying structure may be exploited and that the same mechanism should work for different connective architectures. The cost for this increased versatility is that the resulting rules are less efficient (in terms of time to coordinate) than their particle-based counterparts.

[Tanaka-Yamawaki et al., 1996] studies the same problem to that considered here. They use totalistic [Wolfram, 1984] rules which do not permit exploitation of the underlying structure of the connections between cells but rather rely on the intensity of each incoming symbol. They also vary a parameter to produce different rules and find that above a certain threshold, "global consensus" occurs but below it does not. However, they consider large clusters of symbols to be a successful global consensus. We do not and thus turn to a stochastic version of their totalistic rules to destroy these clusters and complete the job of global coordination.

3 The Model

In deterministic cellular automata there is an alphabet of a0 symbols, one of which may be adopted by each cell. Incoming connections each provide a cell with one of these symbols. The combination of all incoming symbols uniquely determines which symbol the cell will display as output. Stochastic cellular automata (SCA) work in the very same way except at the output level. Instead of there being a single unique symbol which is adopted with probability ✁ , there can be multiple symbols adopted with probability less than ✁ . Based on this outgoing probability distribution over the a0 symbols, a single unique symbol is drawn to be the output of the cell. This is done for all cells simultaneously. It should be noted that deterministic CA are a special case of SCA.

We consider a specific sub-case of SCA in this paper which corresponds to the totalistic rules of CA. Assume that cells cannot tell which symbols came fromwhich connections. In this case, it is only the intensity of each incoming symbol which becomes important. Furthermore, we desire that our rules work with any number of incoming connections thus rather than using the number of each of the incoming a0 symbols, we use this number normalized by the number of connections which can be thought of as an incoming probability distribution. In summary the model we consider is as follows.

Totalistic SCA. Consider a system of ✂ cells, each of which is connected to a number of other cells. Let ✄ represent an alphabet of a0 symbols. The state of Cell ☎ at time-step ✆ is ✝ ✞ ✠ ✆ ☛ ✌ ✄ . The input probability distribution, pin, for Cell ☎ is given by

where ✒ ✞ accounts for the connections of Cell ☎ to the other cells. The output probability distribution pout is given by the map, ✣ ,

The probability distributions pin and pout are stochastic columns. The new state of Cell ☎ at time-step ✆ ✤ ✁ is randomly drawn according to the distribution pout ✠ ✆ ✤ ✁ ☛ and is represented by ✝ ✞ ✠ ✆ ✤ ✁ ☛ .

It should be noted that in (1) if the connections between the cells are not changing over time then the functions, ✒ ✞ ✯ ✰ ✲ , will not be functions of time. However, we could allow these connections to change which would make them functions of time.

Once the connections are described through the ✒ ✞ ✯ ✰ ✲ functions, the only thing that remains to be defined is the ✣ -map. We assume that each cell has the same ✣ -map but this need not be the case. The possibilities for this map are infinite and thus for the remainder of this paper we discuss a parameterized subset of these possibilities. This subset will be called piecewise-✣ and is defined as follows.

Piecewise-✣ . Let

The (unnormalized) output probabilities are given by

where ❀ is derived from the tunable parameter ❇ as follows:

The (normalized) output probability column is

where ✵ ❑ ✶ out ✏ ▲ ✸ ✻ ▼ ✗ ✵ ✻ ✶ out.

Note that in (5), the tunable parameter, ❇ acts in a similar manner to a temperature parameter. When ❇ ✏ ✁ we have a completely deterministic rule while when ❇ ✏ ❅ we have a completely random rule. Figure 1 shows what the rule looks like for different ❇ when a0 ✏ ❋ .

An equilibrium point, p✞ , in a ✣ -map is one for which the following is true

The idea behind the piecewise-✣ rule was to create an instability in the probability map at the uniform distribution equilibrium point

such that a small perturbation from this point would drive the probability towards one of the stable equilibria

It turns out that when ❅ ❆ ❇ ❏ ✗ ❍ , the equilibrium point, p ✞ uni , is the only stable equilibrium. However when ✗ ❍ ❏ ❇ ❆ ✁ , p ✞ uni becomes unstable and the other equilibria, p ✞ ✗ ✘ ✙ ✙ ✙ ✘ p ✞ ✸ , become stable. This is similar to the classic pitchfork bifurcation as depicted in figure 2 for a0 ✏ ❋ . However, with a0 symbols in the alphabet the pitchfork will have a0 tines.

It is important to stress that we have designed the stability of our system at a local level. The question of global stability and success on the multiagent coordination problem does not follow directly from the local stability of each cell. It might be possible to study the global stability of a system of cells with the piecewise-✣ rule analytically. The approach in this paper has been to study it through simulation and statistical measures.

4 Simulation

We now present simulations of cells running the piecewise- ✣ rule. In order to ensure that the connections between cells are not regular, we consider each cell to exist in a Cartesian box (of size ✁ by ✁ ). The ✂ cells are randomly positioned in this box and symmetrical connections are formed between two cells if they are closer than a threshold Euclidean distance, ✌ , from one another. Figure 4 shows example connections between ✂ ✏ ✁ ❅ ❅ cells with ✌ ✏ ❅ ✙ ❋ . Figure 3 shows example time series for different values of ❇ . When ❇ ❏ ❅ ✙ ✍ , chaotic global behaviour arises, with ❅ ✙ ✍ ❏ ❇ ❏ ✁ fairly successful behaviour results but with ❇ ✏ ✁ clusters form. The formation of clusters means that the global system has stable equilibria which we did not predict from the local rule. However, as ❇ is decreased towards ❅ ✙ ✍ , these equilibria are no longer stable and the system continues to coordinate.

It would seem that there is a good correlation between the stability on the local level and the behaviour type of the global system. As ❇ moves frombelow ❅ ✙ ✍ to above, it appears there is a dramatic phase transition in the behaviour of the system (totally chaotic to fixed point). In the neighbourhood of ❅ ✙ ✍ there is long transient behaviour. It turns out that the best value for ❇ , from the point of view of multiagent coordination, is approximately ❇ ✏ ❅ ✙ ✎ .

5 Statistics

In an attempt to quantify the qualitative observations of the previous section a number of statistical measures were employed in the analysis of the SCA time series. These were used also by [Langton, 1990]. The first measure is taken from [Shannon, 1948] and will be referred to as entropy (✏ ). It is defined as follows.

Entropy Given a sequence of ☛ symbols

from an alphabet of size a0 , the entropy of the sequence may be computed as follows. First compute the frequency, ✓ ✻ , of each of the a0 symbols ✔ ✕ ✌ ✁ ✙ ✙ ✙ a0 which is simply the number of occurrences of symbol ✕ in the sequence, ☞ . From the frequencies, compute the probability, ✵ ✻ , of each of the a0 symbols ✔ ✕ ✌ ✁ ✙ ✙ ✙ a0 as

where ✓ ❑ ✏ ▲ ✸ ✞ ▼ ✗ ✓ ✞ . Finally, the entropy of sequence, ✏ ✯ ☞ ✲ , is defined as

where the ✘ ✚ ✯ a0 ✲ denominator is a normalization constant to make ✏ ✯ ☞ ✲ ✌ ✠ ❅ ✘ ✁ ☛ .

This entropy function produces a value of ❅ when all the symbols in ☞ are identical and a value of ✁ when all a0 symbols are equally common. The second measure is based on the first and will be referred to as mutual information (✛ ). It is defined as Mutual Information Given two sequences of ☛ symbols

from an alphabet of size a0 , the mutual information of the sequence, ✛ ✯ ☞ ✗ ✘ ☞ ❍ ✲ , may be defined as

where ✏ ✯ ☞ ✗ ✘ ☞ ❍ ✲ is the entropy of the two sequences considered as a joint process (i.e., with an alphabet of size a0 ✢ a0 ).

These two measures may be computed on any sequence of symbols. We tested them on spatial sequences (e.g., time series columns from figure 3) and temporal sequences (e.g., time series rows from figure 3). The most interesting measures were average spatial entropy (average of entropies computed from all columns in a time series) and average temporal mutual information (average of all ✛ s computed from all rows in a time series. ✛ was computed between a row and itself shifted by one time-step).

Figure 5 show various measures for ✁ ❅ ❅ ❅ values of ❇ . At each value of ❇ , ✁ ❅ ❅ simulations were done on different random connections between cells and initial conditions. Thus, all displayed measures are actually averaged over ✁ ❅ ❅ simulations. Each simulation was run for ✤ ❅ ❅ time-steps with ✂ ✏ ✁ ❅ ❅ , a0 ✏ ❋ , and ✌ ✏ ❅ ✙ ❋ .

Figure 5 (left) shows the average number of clusters 1 at the final time-step for different values of ❇ . Clearly there is an optimal value of ❇ near ❅ ✙ ✎ . Figure 5 (middle) shows average spatial entropy for different values of ❇ . This measure has a good correlation with average number of clusters. Again, there is a minimum occurring at approximately ❇ ✏ ❅ ✙ ✎ which corresponds to the best performance at multiagent coordination.

Figure 5 (right) displays average temporal mutual information for different values of ❇ . This is a very interesting plot.

1 Number of clusters was computed by considering the SCA as a Markov chain with connections deleted between cells displaying different symbols. The number of clusters is then the number of eigenvalues equal to ✁ from the Markov transition matrix.

Temporal mutual information seems to capture the length of the global transient behaviour of the system. As discussed in [Langton, 1990], the random pattern in the chaotic region is not considered transient but rather the steady state behaviour. The peak in temporal mutual information occurs at ❇ ✏ ❅ ✙ ✍ , the phase transition, and drops away on either side. [Langton, 1990] has a similar plot. Figure 6 shows how the number of clusters at the final time-step ( ✤ ❅ ❅ time-steps) changes as the problem scales up to more cells; it appears to be a linear relationship. Figure 7 shows how the number of clusters at the final time-step changes for different message sizes.

6 Discussion

The strong correlation between the local stability of the piecewise- ✣ rule and the type of global behaviour is quite interesting. It appears that ❇ a0 ❅ ✙ ✍ corresponds to fixed point behaviour (class I), ❇ ✁ ❅ ✙ ✍ corresponds to chaotic behaviour (class III), and ❇ near ❅ ✙ ✍ corresponds to long transient behaviour (class IV). The correlation most likely has something to do with the way in which the incoming probability distribution is computed in (1). This step delivers information averaged from all connected cells. This averaging serves to smooth out differences between connected cells. However, if this smoothing occurs too quickly (i.e., ❇ ✏ ✁ ) the system does not have time to smooth globally resulting in the formation of clusters. The addition of noise in the particular formof the piecewise- ✣ rule aids in slowing the smoothing process thus destroying the clusters. This has been called critical slowing down [Haken, 1983] in other systems. As we approach the critical point ( ❇ ✏ ❅ ✙ ✍ or ❀ ✏ ✁ ) from above, the strength of the instability decreases which slows down the decision-making process. It is a balance of these two effects which seems to be the most effective at multiagent coordination. The optimal operating value of ❇ is not right at the phase transition but a little bit towards the deterministic end of the ❇ spectrum (approximately ❇ ✏ ❅ ✙ ✎ ).

Note that we did not find any oscillatory behaviour (class II) which is likely because the connections between the cells are symmetrical. However, if the piecewise- ✣ rule in figure 1 is reflected (left-right) then the system 'blinks' and global coordination corresponds to all cells blinking in phase with one another.

In this model of multiagent coordination, the boundaries between clusters have purposely been made unstable. This forces them to move randomly until they contact one another and annihilate, leaving a single cluster. The results presented here used ✂ ✏ ✁ ❅ ❅ cells and required on average ✁ ✍ ❅ timesteps to get to a single cluster with ✌ ✏ ❅ ✙ ❋ , a0 ✏ ❋ and ❇ ✏ ❅ ✙ ✎ . Clearly the time required to form a single cluster will increase with the number of cells in the system. Figure 6 confirms this by showing that at the end of ✤ ❅ ❅ time-steps, increasing the number of cells, ✂ , results inmore clusters. The linear relationship suggests that scaling-up may be possible but more in depth studies are required. Figure 7 shows how the systemscales to differentmessage sizes, a0 . Here the relationship between number of clusters (after ✤ ❅ ❅ time-steps) to message size is a bit surprising, first dropping then increasing as a0 increases. It levels off again as the number of symbols exceeds the number of cells (since at most ✂ symbols can be represented in the random initial condition). Again, the nature of this scaling should be studied more closely.

The piecewise- ✣ rule is not the only map that can be used to achieve multiagent coordination in SCA. Replacing it with other monotonically increasing functions (i.e., in figure 1) with the same equilibria also works. We had comparable success to the piecewise- ✣ map using

with the outgoing probability column normalized as in (6).

The model considered here does not require knowledge of the underlying structure of the connections between cells. This was a design requirement as it was originally motivated by a network of communicating mobile robots whose connections might be changing over time and thus difficult to exploit. It is thus natural to question whether the model still works as the connections are varied over time. To this end, a small amount of Gaussian noise was added to the positions of the cells in the Cartesian box of figure 4 at each time-step. As the cells moved, the connections between them changed (since they are limited by the range, ✌ ). The SCA model was still able to form single clusters. This was possible even when ❇ ✏ ✁ which does make sense since there is still some noise being added. However, the nature of the noise is at the connection level rather than the signal level. This aspect is currently under further investigation.

7 Conclusion

A mechanism for multiagent coordination has been presented based on stochastic cellular automata. We consider this to be an example of self-organizing behaviour in that global coordination occurs in the face of more than one alternative. It was shown that by using stochastic rules, sparsely communicating agents could come to a global consensus. A parameter in the coordination mechanism was tuned and it was found that coordination occurred best when the system was near a phase transition between chaotic and ordered behaviour (the optimumwas a little bit towards the ordered side).

It is hoped that this model will shed light on selforganization as a general concept while at the same time providing a simple algorithm to be used in practice.

Acknowledgements

We would like to acknowledge support of this work by NSERC (Natural Science and Engineering Research Council) and CSA (Canadian Space Agency).