From Classical Models of Morphogenesis to Agent-Based Models of Pattern Formation Eric Bonabeau Santa Fe Institute 1399 Hyde Park Road Santa Fe, NM 87501 bonabeau@santafe.edu Keywords pattern formation, agents Abstract An extremely large body of theoretical work exists on pattern formation, but very few experimental results have confirmed the relevance of theoretical models. It is argued in this article that the notion of agent-based pattern formation, which is introduced and exemplified, can serve as a basis to study pattern formation in nature, especially because pattern-forming systems based on agents are (relatively) more easily amenable to experimental observations. Moreover, understanding agent-based pattern formation is a necessary step if one wishes to design distributed artificial pattern-forming systems. But, to achieve this goal, a theory of agent-based pattern formation is needed. This article suggests that it can certainly be derived from existing theories of pattern formation. 1 Introduction “Morphogenesis is the development of pattern and form in living systems” [36]. Models of morphogenesis are therefore relevant to a variety of fields in biology, including cell biology, embryology, ecology, ethology, and others. Understanding how complex patterns, comparable to those observed in biological systems, unfold in space and time through mostly random processes and interactions among elementary constituent units is also of relevance to the design of distributed problem-solving devices, when finding the solution to a particular problem amounts (or can be shown to be equivalent) to forming a specific pattern. Turing [45] showed in his pioneering paper how patterns could emerge as a result of a diffusive or “Turing” instability: Spatially inhomogeneous perturbations can, under certain conditions, grow exponentially, while spatially constant perturbations die out. Many other models of pattern formation have been developed since Turing’s work (see reviews by Oster [38], Oster and Murray [39], Murray [35], Meinhardt [28], Nijhout [37], Held [22], or Cross and Hohenberg [9] for a “physical” perspective), especially in the context of embryological pattern formation, but it turns out that most of them rely on the same basic principles of short-range activation (or local autocatalysis) and long-range inhibition (or lateral inhibition) [38], as was first understood by Gierer and Meinhardt [20]. A Turing-type (reaction-diffusion) model is of the form [35] ∂t A = F(A, B) + DA 2 A, (1) ∂t B = G(A, B) + DB 2 B, (2) c 1997 Massachusetts Institute of Technology Artificial Life 3: 191–211 (1997) E. Bonabeau Agent-Based Pattern Formation where A(r, t) and B(r, t) are the concentrations of two chemical species, F and G are two nonlinear reaction terms, and DA and DB are the diffusion constants associated with species A and B, respectively. Let us assume that in the absence of diffusion, that is, when DA = DB = 0, the system tends to a spatially homogeneous state that is linearly stable. Then, under certain conditions, diffusion can destabilize this steady state. These conditions must be the implicit (or explicit) implementation by the equations of a combined local activation and long-range inhibition mechanism. For example, it can take the form of two different diffusion constants: DA DB if the action of B is to inhibit the production of A (F(A, B)); in some models, the production of A can enhance that of B, while in other models, the production of B is on the contrary inhibited by that of A. Murray [35] gives two simple examples of Turing-type systems, where B inhibits A; in both cases, one of the conditions of the existence of Turing patterns is DA DB: 1. [20, 42]: F(A, B) = k1 − k2A + k3A2 B, (3) G(A, B) = k4 − k3A2 B. (4) Here, A is produced with the help of B (+k3A2 B in F), but B disappears because of the production of A (−k3A2 B in G). Because DA DB, B disappears from regions around reaction centers (this model is also close to activator-substrate kinetics models, which implement lateral inhibition by depletion [29, 32, 38]). 2. [20]: F(A, B) = k1 − k2A + k3A2 B , (5) G(A, B) = k4A2 − k5B. (6) Here, A enhances (+k4A2 in G) the production of its own inhibitor (+k3A2 /B in F). Because of the separation of the respective diffusion time scales of A and B, this model implements short-range activation (A is self-produced and can maintain itself in regions of low B concentrations) and long-range inhibition (the inhibitor B diffuses faster than A, so that the production of A will be inhibited away from A). Other reaction-diffusion models of morphogenesis rely in fact on the same basic concept of local activation and long-range inhibition (LALI [20, 30, 38]), provided the inhibitor diffuses more rapidly than the activator. Other models of pattern formation rely on the explicit inclusion of LALI. For example, neural models of pattern formation include explicit local autocatalysis and lateral inhibition [17, 43]. Here I will briefly describe the first model of neural pattern formation, suggested by Swindale [43] to account for the formation of ocular dominance stripes in the visual cortex (see also [31] for a parallel approach showing how stripes can be formed when two processes inhibit one another locally but are mutually activating on long range). Let nR(r) and nL(r) be the respective densities of right and left eye synapses in a 2D space. Let us assume that the total number of synapses in the spatial domain is constant: ˜nR(k = 0) + ˜nL(k = 0) = N , where ˜n(k) denotes the spatial Fourier transform at wavevector k. The total stimulus received by a right eye synapse is sR(r) = wRR ∗ nR(r) + wRL ∗ nL(r), where ∗ is the convolution operator over the considered spatial domain, and wRR and wRL are two convolution kernels implementing short-range activation and lateral inhibition. More precisely, wRR represents short-range activation due to the presence 192 Artificial Life Volume 3, Number 3 E. Bonabeau Agent-Based Pattern Formation of right-eye synapses in the immediate neighborhood and long-range inhibition due to the presence of right-eye synapses further away, while wRL represents short-range inhibition due to the presence of left-eye synapses in the immediate neighborhood and long-range activation due to the presence of left-eye synapses further away: Therefore, the LALI mechanism is with respect to synapses of the same type, while it is a LILA mechanism (inverted LALI) with respect to synapses of the other type. In the same way, the total stimulus received by a left-eye synapse located at r is given by sL(r) = wLR ∗ nR(r) + wLL ∗ nL(r), and it is assumed that wRR = wLL = −wRL = −wLR = w. A typical kernel w is of the form w(r) = A exp(−r2 /d2 1 ) − B exp{−r2 /d2 2 }, where r is radial distance, d1 and d2 set the spatial scales over which activation and inhibition are taking place, while A and B define the strengths of activation and inhibition. Swindale [43] suggests that the evolution equations for synapse densities are given by ∂t nR = sR f (nR) (7) ∂t nL = sL f (nL) (8) where f is a function that has zeros at n = 0 and n = N , such as, for example, f (n) = n(N − n). Swindale [43] numerically integrated these equations and found extremely good agreement between the patterns he obtained and pictures of the visual cortex. He was also able to test the response of his system to cortex growth and monocular deprivation. Despite the mathematical interest of analyzing and understanding these models, it must be said that very few theoretical models have been convincingly related to experimental results (with a few exceptions: For example, Ingham and Martinez-Arias [23] and Meinhardt [29] present experimental evidence for the mutual activation of locally exclusive cell states for segmentation in Drosophila, which can be traced back to interactions among genes). In most cases, there is as yet no “proof” that equations really reflect what actually happens: For example, some models have been aimed at describing mammalian coat patterns [1, 34] or patterns on the skin of fishes [26], but very little is known about the actual underlying mechanisms. It is also known that very different processes can lead to the formation of very similar patterns, and it is therefore difficult to say which one is the right one [28, 29, 38]. Moreover, such models may not be the natural type of description for behaviorally implemented pattern forming processes, whereby patterns are created by mobile agents that can take actions depending on their local space-time environment. Most of the models involve diffusing interacting chemical substances, some of them rely on mechanical processes, while others combine diffusing chemicals and moving entities (e.g., chemotactic behavior of bacteria or slime molds [3, 24, 25]. One unifying feature of all these models is that the actors of the patternformation process (chemical substance, bacteria, etc.) are also part of the pattern. Other examples in which agents are part of the pattern include diffusive predator-prey ecological models [33, 41]; in this context, Segel and Jackson [41] have been the first to derive in a simple and elegant way the conditions under which a diffusive instability can occur [16]. It is interesting to refer explicitly to the notion of agent here, because morphogenesis in the context of animal societies—where a large number of impressive architectural patterns can be produced—obviously relies on agents. There are numerous ethologically relevant patterns the constituent units of which are the agents themselves: Such cases include many interesting phenomena, such as aggregation (i.e., when agents aggregate), flocking, collective motion in general, living bridges and chains, and so forth. But there are also many examples of patterns generated by agents who do not directly participate in the shape they produce: This is, for instance, the case of nests in animals Artificial Life Volume 3, Number 3 193 E. Bonabeau Agent-Based Pattern Formation in general, the most complex of those being built by social insects (ants, bees, wasps, and termites). Such nests can be produced through burrowing, sculpting, or through the active aggregation of soil pellets, needles, and so forth. It could therefore be relevant and fruitful to develop models of morphogenesis in nest-building animals, and to take advantage of the existing body of work on embryological pattern formation: For example, it could be interesting to ask whether and how LALI mechanisms can be implemented in a plausible way in pattern-forming agents. But very few works actually deal with the proximate morphogenetic mechanisms underlying nest construction. This program of research would have one major advantage over the classical theoretical embryological pattern-formation program: Agents are well-defined (whereas most of the chemicals present in theoretical embryological pattern-formation models remain hypothetical), and carefully controlled experiments can be devised to study and modify their behaviors. There already exist several biologically motivated models of pattern formation by agents, especially in the context of social insects: For instance, Deneubourg [10] has shown how a simple model relying on chemotaxis [24, 25] can lead to the formation of regularly spaced pillars in termites, Camazine et al. [5, 6] have studied and modeled the formation of concentric patterns of brood, pollen, and honey on the combs of honeybee colonies, Skarka et al. [42] have modeled the initiation of combs in honeybees, Franks et al. [19] have shown how “blind bulldozing” can lead to “sophisticated” building, Theraulaz and Bonabeau [12, 44] have shown that simple deposition behaviors inspired by the observation of wasps [14, 15] can lead to the formation of extremely complex structures, and so on. Most of them rely on the (reasonable) idea that information is processed locally in space and time; that is, agents take actions that depend on their current state and that of their neighborhood. Deneubourg’s [10] model of pillar emergence in termites also involves a diffusing attracting chemical that allows concentration of the building activity at specific building sites. And in fact, this model is close, formally speaking, to many models of chemical pattern formation: The set of equations describing the evolution of the system of soil particles corresponds to a set of reaction-diffusion equations, where the short-range attraction is chemotactic and the long-range inhibition is due to the finite lifetime and the decay of the pheromone. But the spirit of this model is very different from classical embryological models in that agents are in fact the underlying acting processes, and it is, at least in principle, possible to describe the system from their viewpoint: If one wishes to transform Deneubourg’s partial differential equations, which necessarily simplify spatial features and smooth out fluctuations, into a cellular automaton (CA) model, then agents are the essential ingredients, and it is their behavior that has to be coded, although they are not part of the final pattern (see [8] for a simple agent-based CA implementation of this model). In these models, agents act upon their environment and may in turn be influenced by the environment they create. Furthermore, mastering the use of agent-based models to implement pattern-forming processes is a necessary step with a view to designing distributed problem-solving devices. Those who wish to design such devices are usually facing what I would call an “inverse problem,” which can be stated as follows: Given a problem, what should be the specifications of individual agents and the pattern of their interactions so that the dynamical evolution of the collection of agents leads to a reasonably good solution to the problem? In the context of pattern formation, the inverse problem can be formulated as such: How should interacting agents behave (or be programmed) so as to generate a given target pattern? Some problems can easily be mapped onto a spatial representation, so that a solution can be represented by a spatial distribution (of agents or of items they manipulate). For example, a solution of the traveling salesman problem (TSP), a usual benchmark problem in combinatorial optimization, can be represented as a distribution of agents or “pheromone” on the edges that connect the cities [13]. In 194 Artificial Life Volume 3, Number 3 E. Bonabeau Agent-Based Pattern Formation Figure 1. Cut of a termite nest (Apicotermes lamani). Modified from [23]. this case, the relevant spatial structure is a graph, but one may imagine other problems in which space is simply Euclidian space. For example, Lumer and Faieta [27] have proposed a method to structure complex data sets into clusters: The method consists of using ant-like agents to generate a mapping from a high-dimensional attribute space onto a 2D Euclidian space. The problem of data clustering is to find relevant structures in a data set, the method is to map the data set onto a plane, and the “solution” is a particular spatial pattern of items, where items that share essential attributes tend to be clustered together. Lumer and Faieta’s method [27] was inspired by a simple model of clustering in ants, which I shall briefly describe in the next section. The algorithm they proposed made use of results obtained by Deneubourg et al. [11], who studied the behavior and properties of their simple model of pattern formation (clustering of dead bodies in ants). One of the motivations underlying this article is that the study of more complex models of pattern formation by agents (clustering or aggregation being maybe the simplest level of patterning) will facilitate the design of algorithms or devices based on them: It is necessary to understand the behavior and properties of a model of pattern formation before being able to use it for practical purposes. The aim of this article is to start a systematic exploration of what kinds of patterns can be generated by agents that act upon their environment. Because there is an infinite number of possible specifications for such agents, I shall follow a very well-defined but more restricted path, which makes sense if one considers patterns found in nests of social insects, such as termites (Figures 1, 2). This path consists of trying to find biologically plausible or technically reasonable ways of implementing LALI mechanisms in pattern-forming agent systems, without the help of any chemical substance that could direct individual behaviors through chemotaxis or other processes (which excludes Deneubourg’s [10] model of the emergence of pillars in termites, but this is only to concentrate on simpler problems). This may seem a very academic exercise, but it is aimed at clarifying what can be expected from the sole behavior of simple agents. To do so, I shall proceed in three steps: (a) The first is in fact already known because it relies on Young’s [46] CA implementation of a neural model of pattern formation; (b) the second is technically simple but conceptually subtle because it involves a transformation of Young’s formulation into an agent-oriented formulation; (c) finally, the third step consists of modifying Young’s agent-based version to include a mechanism inspired by the memory scheme suggested by Deneubourg et al. [11] in their model of clustering Artificial Life Volume 3, Number 3 195 E. Bonabeau Agent-Based Pattern Formation Figure 2. External wall of a termite nest (Apicotermes lamani). Modified from [22]. Figure 3. Four thousand dead bodies are randomly placed on an experimental 50 × 50 cm arena where Pheidole pallidula workers are present. Modified from [11]. and sorting in ants. The idea is simple: Space is mapped onto time through memory, and LALI in space is replaced by LALI in time, or more precisely, LALI in memory space. Note that I shall not deal explicitly with dynamically varying patterns: The focus of this study is on stable spatial patterns, when they exist, although convergence toward a stable pattern most often occurs after some dynamic transients. Before introducing Young’s model and its variants, it is useful to describe briefly Deneubourg et al.’s model [11], because it sets the stage for the rest of the article. 2 Clustering of Dead Bodies in Ants: Experimental Observation and Model Chr´etien [7] has performed intensive experiments on the ant Lasius niger to study the organization of cemeteries. Other experiments on the ant Pheidole pallidula are also reported in Deneubourg et al. [11], and many species actually organize a cemetery. The phenomenon that is observed in these experiments is the aggregation of dead bodies by workers. If dead bodies, or more precisely, items belonging to dead bodies, are randomly distributed in space at the beginning of the experiment, the workers will form clusters within a few hours. If the experimental arena is not sufficiently large (Figures 3, 4), or if it contains spatial heterogeneities, the clusters will be formed along the borders of the arena or more generally along the heterogeneities. The basic mechanism underlying this type of aggregation phenomenon is an attraction between dead items mediated by the ant workers: Small clusters of items grow by attracting workers to deposit more items. It is this positive feedback that leads to the formation of larger and larger clusters. The exact individual behavior that actually implements 196 Artificial Life Volume 3, Number 3 E. Bonabeau Agent-Based Pattern Formation Figure 4. Experimental arena after 68 hours. Modified from [11]. this positive feedback is, however, still unclear. Another related phenomenon is larval sorting by the ant Leptothorax unifasciatus (this phenomenon is certainly widespread but has been clearly studied in this species [18]): Workers of this species gather the larvae according to their size; that is, all larvae tend to be aggregated with small larvae located in the center and larger larvae in the periphery. Deneubourg et al. [11] have proposed two closely related models relying on biologically plausible assumptions to account for the two above-mentioned phenomena of dead-body clustering and larval sorting in ants. Although the model of clustering is the most biologically “accurate” (i.e., reproduces experimental observations more faithfully), the second model has given rise to more applications. Both models rely on the same principle, and in fact, the clustering model is simply a special case of the sorting model. The general idea is that isolated items should be picked up and dropped at some other location where more items of that type are present. Let us assume that there is only one type of item in the environment. The probability pp for a randomly moving agent (representing an ant in the model), who is not currently carrying an item, to pick up an item is given by pp = k1 k1 + f 2 (9) where f is the perceived fraction of items in the neighborhood of the agent and k1 is a threshold constant: For f k1, pp is close to 1 (i.e., the probability of picking up an item is high when there are not many items in the neighborhood), and pp is close to 0 if f k1 (i.e., items are unlikely to be removed from dense clusters). The probability pd for a randomly moving loaded agent to deposit an item is given by pd = f k2 + f 2 (10) where k2 is another threshold constant: For f k2, pd is close to 0, whereas for f k2, pd is close to 1. As expected, the depositing behavior obeys roughly opposite rules. The question is now to define how f is evaluated. For the sake of robotic implementation, Deneubourg et al. [11] have assumed that f is computed thanks to a short-term memory that each agent possesses: An agent keeps track of the last T time units, and f is simply the number N of items encountered during these last T time units divided by the largest possible number of items that can be encountered during T time units. If one assumes that only 0 or 1 object can be found within a time unit, then f = N /T. As mentioned above, this procedure lends itself more easily to a Artificial Life Volume 3, Number 3 197 E. Bonabeau Agent-Based Pattern Formation Figure 5. Simulation of clustering model with T = 50, k1 = 0.1, k2 = 0.3, 100 agents, 1,500 items, 290 × 200 grid, at t = 1. Figure 6. Same as Figure 5 at t = 5,000,000. robotic implementation, while real ants would use chemical or tactile cues to orient their behaviors, and algorithms inspired by this idea use more direct evaluations of f : This procedure should therefore be taken as an example among many possible procedures, and changing the procedure does not drastically alter the results. Figures 5 and 6 show a simulation of this model with T = 50, k1 = 0.1, k2 = 0.3, 100 agents clustering 1,500 items on a 190 × 200 grid, at t = 1 and t = 5,000,000. Small, evenly spaced clusters emerge within a relatively short time and then merge into fewer larger clusters. Let us now assume that there are two types A and B of items in the environment. The principle is the same as previously, but now f is replaced by fA and fB, the respective fractions of items of types A and B encountered during the last T time units. This process leads to the formation of separate clusters containing either type of objects. This model of clustering is extremely simple, but it is based on agents. And, clearly, clustering or aggregation constitutes a basic level of pattern formation, but more complex models can be designed starting from this basic level. This is why this model seems so important to me: It is now well-understood how to cluster items in a distributed way thanks to this model or its variants (either in a computer [27] or with robots [2]). Can we use more complex versions of this model to design collections of agents that generate more complex patterns? 3 Young’s Version of Neural Pattern Formation Young [46] proposed a simplification of Swindale’s model. First, he used an underlying discrete space and a discrete time dynamics. His model is therefore a two-state cellular 198 Artificial Life Volume 3, Number 3 E. Bonabeau Agent-Based Pattern Formation Figure 7. Example of a run of Young’s [46] model with w1 = 1 and w2 = 0.5; total neighborhood: 9 × 9 around a given cell, with short-range activation only within the 3 × 3 neighborhood surrounding the cell. automaton, where each node can be either a left-eye or a right-eye synapse. Second, he transformed the long-range convolution kernel w(r) = A exp(−r2 /d2 1 )−B exp{−r2 /d2 2 } into a short-range one by making the cutoffs at distances d1 and d2 explicit and by injecting into the new kernel the respective weights of activation and inhibition found in the steady state in Swindale’s model [43]. These transformations result in the following model: Let St i (= 0 or 1) and ri be respectively the state at time t and position of site i, and ri − rj the distance between sites i and j, w1 and w2 two numbers representing the simplified kernel, and Ai = w1 ri −rj ≤d1 St j −w2 d1< ri −rj ≤d2 St j the total stimulus perceived by site i within a distance d2 weighted by the simplified kernel; the dynamics of the system is then given by St+1 i = 0 if Ai < 0, (11) St+1 i = 1 if Ai > 0, (12) and St+1 i = St i if Ai = 0, (13) where the updating is assumed to be performed in parallel. Young found remarkably similar patterns to those obtained with Swindale’s continuous model. Figures 7–9 show a few patterns obtained with Young’s model. 4 Agent-Based Implementation of Young’s Model (1): Space Remains Space A very simple way of transforming Young’s model is to assume that agents perform random walks on the 2D grid and deposit or remove bricks according to the state of their neighborhood. The condition to deposit a brick at an empty site is Ai > 0 (14) while the condition to remove a brick from a site containing a brick is Ai < 0. (15) Artificial Life Volume 3, Number 3 199 E. Bonabeau Agent-Based Pattern Formation Figure 8. Same as Figure 3, but with w1 = 1 and w2 = 0.6. Figure 9. Same as Figure 3, but with w1 = 1 and w2 = 0.9. In all other cases, the site remains unchanged. Figure 10 shows the result of one run of this model. One might wonder what difference there is between Young’s model and this agent-based version, the formulation of which is indeed very close. There are, however, some conceptual differences that open the door to (more) interesting agent-based generalizations: 1. Agents are involved. Although their behavior mimics some kind of spin dynamics (with locality in space and time), it is conceivable that more complicated individual behaviors can be implemented: For instance, memory can be taken into account; one might also want to constrain the spatial behavior of the agents, for instance, to prevent them from walking on bricks or from being able to look through walls. 2. Agents perform random walks. At every time step, each agent walks a distance of one spatial unit toward one of the neighboring sites. This induces strong correlations in the agents’ pathways and therefore in the actions they take. For 200 Artificial Life Volume 3, Number 3 E. Bonabeau Agent-Based Pattern Formation Figure 10. Example of a run of the agent-based version of Young’s [46] model with w1 = 1 and w2 = 0.6. instance, one site may be updated very often within some small time window, whereas another site may not be updated within a large time window, especially if the density of agents is small. Note, however, that ergodicity is insured in the long run (in principle). 3. Finally, the agent-based model is completely asynchronous. It is important to mention this (although synchronicity is not a crucial feature of Young’s model) because it is a necessary condition for implementing more sophisticated agent-based models. One cannot expect natural agents to act in synchrony, except in very specific cases. As regards artificial agents, synchronization can induce high design costs. 5 Agent-Based Implementation of Young’s Model (2): Space Mapped onto Time A more complicated transformation of Young’s model involves a mapping of space onto time and the use of a chronological memory, which may not be biologically unrealistic if this model is to be applied, for instance, to the description of social insects. In this new model, the conditions under which bricks are deposited or removed are essentially expressed in Equations 14 and 15, but now Ai is defined differently. Let us define two time lags t1 and t2 (t1 < t2) which will play in time the roles that d1 and d2 played in space in the previous models. The idea of using time was inspired by Deneubourg et al.’s [11] model of clustering of dead bodies in ants or of larval sorting [18]: Ants move randomly in space and encounter dead bodies; to assess the number of dead bodies present in a given neighborhood, they keep track of the number of dead bodies they have encountered within the last t2 time units; each ant decides whether to pick up or drop a dead body depending on the content of this short-term memory. Because random walks are highly autocorrelated, this procedure allows the agents to have a rough approximation of the density of dead bodies in their neighborhood. Let us now transpose this idea to the case of “neural” pattern formation. Let mt τ (τ = 1, . . . , t1, . . . , t2) be the state of the memory of an agent at time t: mt τ = 1 if the agent Artificial Life Volume 3, Number 3 201 E. Bonabeau Agent-Based Pattern Formation Figure 11. Example of a run of the agent-based version of Young’s [46] model with spatial memory instead of direct perception, memory size = 81 time steps, fixed number of items (5,500), w1 = 1, and w2 = 0.4. Figure 12. Same as Figure 11 with w1 = 1 and w2 = 0.5. has encountered a brick at time t − τ, and mt τ = 0 otherwise. Ai is then given by Ai = w1 τ≤t1 mt τ − w2 t1<τ≤t2 mt τ , (16) where w1 and w2 now represent a simplified kernel in time. Note that Ai is no longer intrinsic to site i but is rather a quantity associated with the agent that reaches site i. Figures 11–13 show various runs of this simple model with different values of the parameters (in particular with t2 = 21 and 81). Although one finds some interesting patterns, they are not exactly similar to those obtained with Young’s model. This problem can be solved to a large extent by resorting to a probabilistic model (i.e., a model in which picking-up and dropping behaviors are probabilistic) rather than a 202 Artificial Life Volume 3, Number 3 E. Bonabeau Agent-Based Pattern Formation Figure 13. Same as Figure 12 with memory size = 21. Figure 14. Example of a run of the agent-based version of Young’s [46] model with spatial memory instead of direct perception, memory size = 81 time steps, fixed number of items (5,500), w1 = 1 and w2 = 0.4, and probabilistic deposit or removal of items with η = 1. deterministic one. The probability for an agent to pick up an item is given by P(pick-up) = 1 1 + eηAi , (17) where η is some (inverse)-temperature-like parameter (set to 1 in the simulations), and the probability of dropping and item is given by P(drop) = 1 1 + e−ηAi . (18) Figure 14 shows a pattern obtained with one run of this model for a given set of parameters. This pattern is now very close to those obtained by Young [46], although Artificial Life Volume 3, Number 3 203 E. Bonabeau Agent-Based Pattern Formation Figure 15. Same as Figure 11 with w1 = 1 and w2 = 0.5. Figure 16. Filtered version of Figure 15: Isolated dots and empty sites have been removed and refilled, respectively. the random motion and behavior of the agents prevent the final pattern from being completely smooth and regular. An additional smoothing procedure is required to “clean” the pattern. Figure 15 shows another run with slightly different values of w1 and w2, and Figure 16 is the corresponding “clean” pattern (i.e., isolated pellets and isolated empty sites have been removed through a one-pass filter). Another idea for implementing short-range activation and long-range inhibition is to combine the preceding scheme with one based on direct perception. In particular, because attraction is short-ranged, it is not absurd to think that it can be based on direct perception. Inhibition, being long-range, can be memory based. An example in which local attraction can be assumed to occur via direct perception is local chemotaxis, that is, cases in which chemotaxis can attract individuals only within a small radius. For instance, Bruinsma [4] showed that the cement pheromone contained in the soil pellets deposited by workers can attract other workers in a zone with a radius of less than 1.5 cm (the size of a worker being about 5 mm): As a first approximation, one might 204 Artificial Life Volume 3, Number 3 E. Bonabeau Agent-Based Pattern Formation Figure 17. Pattern obtained with the combined scheme (Equation (19)), d1 = 2, t1 = 19, t2 = 81, w1 = 1 and w2 = 0.6, 5,000 items on a 100 × 100 grid. therefore consider that chemotaxis can be replaced by direct perception. Now, A reads Ai = w1 ri −rj ≤d1 St j − w2 t1<τ≤t2 mt τ (19) where d1 is the radius of perception of an agent located at site i. Equation (19) means that the tendency of an agent to deposit an item at site i because it perceives a high local density of item is balanced by the content of its memory, or more precisely by the number of items encountered between t1 and t2 time units before t. We now assume that all dropping and picking-up behaviors are deterministic and can be described by Equations (14, 15, 19). Figure 17 shows a pattern obtained with t1 = 19, t2 = 81, w1 = 1 and w2 = 0.6. Although Figure 17 is reminiscent of typical reaction-diffusion patterns, this seems like a complicated scheme, and in fact it can be simplified by setting t1 = 0: in that case, direct perception of items competes with the items encountered within the last t2 time units. Because there may be an overlap between the set of items that are directly perceived and the set of memorized items, it is necessary that the number of memorized items be significantly larger than the number of perceived items. For d1 = 2, and when agents move at each time unit, it seems that the model with t2 = 40 (Figure 18, w1 = 1 and w2 = 0.6) can generate patterns similar to those obtained with t2 = 81 (Figure 19). Figure 20 shows a pattern obtained with the same algorithm but with w1 = 1, w2 = 0.9, and a density of items of 0.15 instead of 0.5 in all previous examples. In this case, attraction based on local perception does almost all the job and leads to the formation of spots; the role of inhibition is to keep the spots separate: In the absence of inhibition, all spots should merge into a single large cluster. Figure 21 shows exactly the opposite situation (w1 = 1, w2 = 0.4), where the high density of items (0.75) leads to the formation of islands of empty sites. Figure 22 shows the effect of reducing the radius of perception: the same parameters as in Figure 18, except that d1 = 1. Figure 18 reproduces the same type of pattern, yet on a smaller scale, and can be compared with Figure 2. Figure 23 shows the effect of anisotropic perception (with the same parameters as in Figure 18): Instead of perceiving its surrounding sites, each agent perceives the sites the x and y coordinates of which are shifted by 1 with respect to the normal neighborhood; this shift along the diagonal produces a pattern that looks Artificial Life Volume 3, Number 3 205 E. Bonabeau Agent-Based Pattern Formation Figure 18. Same as Figure 17, but with t1 = 0 and t2 = 40. Figure 19. Same as Figure 18 with t2 = 81. like the previous ones, but with a clear bias toward the diagonal. This type of situation can occur, for instance, when there is a clear direction of motion, or when the substrate grows, and so forth. Finally, the pattern shown in Figure 24 has been obtained with a slightly different rule for depositing items: Items are still picked up if Ai < 0 (with Ai given by Equation (19)), but the dropping condition is now ri −rj ≤d1 St j ≥ M, where M is the minimal number of items that must be present in the neighborhood to trigger the deposit of a new item. This very simple scheme has been implemented in robots by Beckers et al. [2]: there, the number of items in the neighborhood was assessed by the local resistance of encountered obstacles. In fact, many other mechanisms can be used, either by animals or robots, to roughly compute ri −rj ≤d1 St j . Obviously, there are many ways of implementing LALI mechanisms in agents. I have presented a few possibilities, but many other examples can be found, either to describe pattern formation by natural agents (insects, bacteria, or even mammals), or to design artificial pattern-forming systems based on agents. The constraints in model building 206 Artificial Life Volume 3, Number 3 E. Bonabeau Agent-Based Pattern Formation Figure 20. Same as Figure 18 with w1 = 1, w2 = 0.9, and 1,500 items. Figure 21. Same as Figure 18 with w1 = 1, w2 = 0.4, and 7,500 items. are of course different, but in both cases, a “theory” of agent-based pattern formation is required and can be derived from the existing “classical theories” of morphogenesis. 6 Conclusion It should be clear from the preceding sections that agent-based models allow us to go beyond reaction-diffusion models, which cannot take into account the detailed behaviors of many interacting agents, or even of single agents interacting with themselves in the course of time. The physical constraints that may arise during the pattern-forming process because of the emerging structures can also be taken into account with an agent-based formulation (although it has not been the case in the present work): For example, as agents deposit bricks, more and more constraints may limit the motion of individuals because they cannot walk through walls. Moreover, most classical models Artificial Life Volume 3, Number 3 207 E. Bonabeau Agent-Based Pattern Formation Figure 22. Same as Figure 18 with d1 = 1. Figure 23. Same as Figure 18 with anisotropic perception along the diagonal. rely on deterministic equations that necessarily smooth out most fluctuations. Agentbased models therefore constitute the best description of how interacting agents perform pattern-forming tasks. But a theory of agent-based pattern formation requires the understanding of how to implement basic pattern-forming mechanisms such as LALI mechanisms in terms of the behaviors of agents. The macroscopic description of collective behaviors by means of, for example, Turing-like partial differential equations can still be used as a deterministic mean-field description, certainly more amenable to mathematical treatment. But it is necessary to understand fully how such equations and agent behaviors are related, especially if one wishes (a) to use the body of mathematical work on this topic to make predictions about agent-based models, and (b) to make experiments showing the actual implementation of pattern-forming mechanisms—and I believe this to be one very promising line of research, initiated by Deneubourg’s [10] pioneering article. The present work is a small first step toward connecting classical models of pattern formation with agent-based models. Future work will focus on other 208 Artificial Life Volume 3, Number 3 E. Bonabeau Agent-Based Pattern Formation Figure 24. Same as Figure 18, but deposition occurs if and only if ri−rj ≤d1 St j ≥ M, M = 4, d1 = 1. (once again, biologically plausible or technically reasonable) ways of implementing LALI in agents, especially the inhibitory part of the mechanism, because positive feedback or local attraction is very easy to implement; lateral inhibition, on the other hand, is more subtle, difficult to analyze and evidence in experiments, and can rely on a rich variety of mechanisms. Moreover, while I have presented examples on a twodimensional torus and in which the initial state was homogeneous, the effects of the geometry and the presence of heterogeneities in the environment may influence what patterns are generated, as is the case in classical models. These factors are of special relevance to the study of animals, and particularly social insects, who make use of environmental heterogeneities to build their nests (humidity and temperature gradients, physical obstacles, etc.). Acknowledgments I thank Guy Theraulaz and Jean-Louis Deneubourg for their constant conceptual support. I also wish to thank an anonymous referee for pointing out several references and historical inaccuracies in the first version of the text. My work at the Santa Fe Institute is supported by an Interval Research Postdoctoral Fellowship. References 1. Bard, J. B. L. (1981). A model for generating aspects of zebra and other mammalian coat patterns. Journal of Theoretical Biology, 93, 363–385. 2. Beckers, R., Holland, O. E., & Deneubourg, J.-L. (1994). From local actions to global tasks: Stigmergy and collective robotics. In R. A. Brooks & P. Maes (Eds.), Artificial life IV (pp. 181–189). Cambridge, MA: MIT Press. 3. Bonner, J. T. (1959). The cellular slime molds. Princeton, NJ: Princeton University Press. 4. Bruinsma, O. H. (1979). An analysis of building behavior of the termite Macrotermes subhyalinus (Rambur). Unpublished doctoral dissertation, Landbouwhogeschool, Wageningen. 5. Camazine, S. (1991). Self-organized pattern formation on the combs of honeybee colonies. Behavioral Ecology and Sociobiology, 28, 61–76. Artificial Life Volume 3, Number 3 209 E. Bonabeau Agent-Based Pattern Formation 6. Camazine, S., Sneyd, J., Jenkins, M. J., & Murray, J. D. (1990). A mathematical model of self-organized pattern formation on the combs of honeybee colonies. Journal of Theoretical Biology, 147, 553–571. 7. Chr´etien, L. (1996). Organisation spatiale du materiel provenant de l’excavation du nid chez Messor barbarus et agregation des cadaures d’ouvrieres chez Lasius niger (Hymenoptera: Formicidae). Unpublished doctoral dissertation, Department of Animal Biology, Universite Libre de Bruxelles, Belgium. 8. Courtois, P.-J., & Heymans, F. (1991). A simulation of the construction process of a termite nest. Journal of Theoretical Biology, 153, 469–475. 9. Cross, M. C., & Hohenberg, P. C. (1993). Pattern formation outside of equilibrium. Reviews in Modern Physics, 65, 109–114. 10. Deneubourg, J.-L. (1977). Application de l’ordre par fluctuations `a la description de certaines ´etapes de la construction du nid chez les termites. Insectes Sociaux, 24, 117–130. 11. Deneubourg, J.-L., Goss, S., Franks, N., Sendova-Franks, A., Detrain, C., & Chretien, L. (1991). The dynamics of collective sorting: Robot-like ant and ant-like robot. In J. A. Meyer & S. W. Wilson (Eds.), Simulation of adaptive behavior: From animals to animats (pp. 356–365). Cambridge, MA: MIT Press/Bradford Books. 12. Deneubourg, J.-L., Theraulaz, G., & Beckers, R. (1992). Swarm-made architectures. In (F. J. Varela & P. Bourgine (Eds.), Toward a practice of autonomous systems, Proceedings of the First European Conference on Artificial Life (pp. 123–133). Cambridge, MA: MIT Press/Bradford Books. 13. Dorigo, M., Maniezzo, V., & Colorni, A. (1996). The Ant system: Optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man and Cybernetics B, 26, 1–13. 14. Downing, H. A., & Jeanne, R. L. (1988). Nest construction by the paperwasp Polistes: A test of stigmergy theory. Animal Behavior, 36, 1729–1739. 15. Downing, H. A., & Jeanne, R. L. (1990). The regulation of complex building behavior in the paperwasp Polistes Fuscatus. Animal Behavior, 39, 105–124. 16. Edelstein-Keshet, L. (1988). Mathematical models in biology. New York: Random House. 17. Ermentrout, B., Campbell, J., & Oster, G. (1986). A model for shell patterns based on neural activity. The Veliger, 28, 369–388. 18. Franks, N. R., & Sendova-Franks, A. B. (1992). Brood sorting by ants: Distributing the workload over the work-surface. Behavioral Ecology and Sociobiology, 30, 109–123. 19. Franks, N. R., Wilby, A., Silverman, V. W., & Tofts, C. (1992). Self-organizing nest construction in ants: Sophisticated building by blind bulldozing. Animal Behavior, 44, 357–375. 20. Gierer, A., & Meinhardt, H. (1972). A theory of biological pattern formation. Kybernetik, 12, 30–39. 21. Grass´e, P.-P. (1984). R´eparation, reconstruction et remaniements internes du nid. Coordination des tâches individuelles et comportement stigmergique. Le d´eterminisme du comportement constructeur. In P. P. Grass´e (Ed.), Termitologia, Tome II—Fondation des Soci´et´es—Construction (pp. 490–577). Paris: Masson. 22. Held, L. I. (1992). Models for embryonic periodicity. Basel: Karger. 23. Ingham, P. W., & Martinez-Arias, A. (1992). Boundary and fields in early embryos. Cell, 68, 221–235. 24. Keller, E. F., & Segel, L. A. (1970). The initiation of slime mold aggregation viewed as an instability. Journal of Theoretical Biology, 26, 399–415. 25. Keller, E. F., & Segel, L. A. (1971). Travelling bands of chemotactic bacteria: A theoretical analysis. Journal of Theoretical Biology, 30, 235–248. 26. Kondo, S., & Asai, R. (1995). A reaction-diffusion wave on the skin of the marine angelfish Pomacanthus. Nature, 376, 765–768. 210 Artificial Life Volume 3, Number 3 E. Bonabeau Agent-Based Pattern Formation 27. Lumer, E., & Faieta, B. (1994). Diversity and adaptation in populations of clustering ants. In D. Cliff, P. Husbands, J.-A. Meyer, & S. Wilson (Eds.), Proceedings of Third International Conference on Simulation of Adaptive Behavior (pp. 499–508). Cambridge, MA: MIT Press. 28. Meinhardt, H. (1982). Models of biological pattern formation. London: Academic Press. 29. Meinhardt, H. (1992). Pattern formation in biology: A comparison of models and experiments. Reports on Progress in Physics, 55, 797–849. 30. Meinhardt, H., & Gierer, A. (1974). Applications of a theory of biological pattern formation based on lateral inhibition. Journal of Cell Science, 15, 321–346. 31. Meinhardt, H., & Gierer, A. (1980). Generation and regeneration of sequences during morphogenesis. Journal of Theoretical Biology, 85, 429–450. 32. Meinhardt, H., & Klinger, M. (1987). A model for pattern formation on the shells of molluscs. Journal of Theoretical Biology, 126, 63–89. 33. Mimura, M., & Murray, J. D. (1978). On a diffusive prey-predator model that exhibits patchiness. Journal of Theoretical Biology, 75, 249–262. 34. Murray, J. D. (1981). A pre-pattern formation mechanism for animal coat markings. Journal of Theoretical Biology, 88, 161–199. 35. Murray, J. D. (1989). Mathematical biology. New York: Springer. 36. Murray, J. D. (1990). Discussion: Turing’s theory of morphogenesis—its influence on modelling biological pattern and form. Bulletin of Mathematical Biology, 52, 119–152. 37. Nijhout, H. F. (1992). Pattern formation in biological systems. In L. Nadel and D. Stein (Eds.), 1991 Lectures in complex systems (pp. 159–187). Reading, MA: Addison-Wesley. 38. Oster, G. F. (1988). Lateral inhibition models of developmental processes. Mathematical Biosciences, 90, 265–286. 39. Oster, G. F., & Murray, J. D. (1989). Pattern formation models and developmental constraints. Journal of Experimental Zoology, 251, 186–202. 40. Schnackenberg, J. (1979). Simple chemical reaction systems with limit cycle behavior. Journal of Theoretical Biology, 81, 389–400. 41. Segel, L. A., & Jackson, J. L. (1972). Dissipative structure: An explanation and an ecological example. Journal of Theoretical Biology, 37, 545–559. 42. Skarka, V., Deneubourg, J.-L., & Belic, M.R. (1990). Mathematical model of building behavior of Apis mellifera. Journal of Theoretical Biology, 147, 1–16. 43. Swindale, N. V. (1980). A model for the formation of ocular dominance stripes. Proceedings of the Royal Society of London B, 208, 243–264. 44. Theraulaz, G., & Bonabeau, E. (1996). Modelling the collective building of complex architectures in social insects with lattice swarms. Journal of Theoretical Biology, 177, 381–400. 45. Turing, A. M. (1952). The chemical basis of morphogenesis. Philosophical Transactions of the Royal Society of London, Series B, 237, 37–72. 46. Young, D. A. (1984). A local activator-inhibitor model of vertebrate skin patterns. Mathematical Biosciences, 72, 51–58. Artificial Life Volume 3, Number 3 211