In this paper we present a formal model of distributed building inspired by wasp colonies. We characterize a set of distributed stigmergic algorithms that allow a swarm of simple agents to build coherent nest-like structures. The agents that constitute the swarm of builders move randomly on a 3D-lattice and can deposit elementary bricks. The agents do not communicate, have no global representation of the architecture they are building, do not possess any plan or blueprint and they can only perceive the local configuration of matter surrounding them. Only a few of these configurations are stimulating, that is, trigger a building action. The aim of this paper is not to prove that this model is an accurate model of how wasps behave, but rather to show (i) that such behavioral algorithms can produce coherent biological-like architectures, (ii) that these architectures, if they are to be generated with these behavioral algorithms, require algorithms with specific ëcoordinationí properties, and (iii) finally that algorithms possessing these specific properties produce in turn only very specific, coherent architectures. In effect, we found an empirical one-to-one correspondence between biological-like architectures and ëcoordinated algorithmsí. Coordinated algorithms rely on a partition of the shape to be built into modular subshapes: if a swarm of agents is to build a given coherent architecture, the shape has to be decomposed into a finite number of building steps, with the necessary condition that the local stimulating configurations that are created at a given stage differ from those created at a previous or a forthcoming builing stage so as to avoid the deorganization of the whole building activity. Moreover, shapes generated with non-coordinated algorithms, for instance when stimulating configurations corresponding to the subshapes overlap and may subsequently affect the overall building process, are unstable, and the same given rule table will produce very dissimilar architecture in different simulations. Finally, architectures generated under such conditions were found not to resemble any known biological architecture. We believe that our study constitutes a first step towards a deeper understanding of the origins of natural shapes in terms of the logical constraints that may have affected the evolutionary path.

1 Introduction

The tight structural coupling between an insect society and its environment results in a complex collective dynamics whereby coherent functional global patterns emerge from the behaviors of simple agents interacting locally with each other and/or with their environment. While the individual behavior of an insect is very simple (e.g. the workers generally possess a limited behavioral repertoire) and has a strong random component, the nonlinear interactions, either direct or indirect, taking place between individuals, endow the society with a large variety of complex and adaptive collective behaviors (see Theraulaz, 1994 for a complete survey of self-organizing processes in social insects). The behavior of each individual is controlled both by local environmental constraints and by any perceived relevant local information.

In many cases, the structuring of the environment caused by the colonyís activities affects and structures in turn individual behaviors. This phenomenon was coined stigmergy by P.-P. Grassé in his pioneering studies on the reconstruction of the termite nest of Bellicositermes natalensis (Grassé, 1959, 1984). In order to explain the coordination of individualsí tasks, Grassé showed that the regulation of the building activity does not depend on the workers themselves but is mainly achieved by the nest structure. A termite worker does not direct her work; rather, her behavior is controlled and guided by any previously achieved work. Consequently, each time a termite takes a building action, she modifies the shape of the local configuration which had triggered her building action. The new configuration will then automatically trigger other actions from the termite or potentially from any other worker in the colony. This process, also called sematectonic communication (Wilson, 1975) when the only relevant interactions between individuals occur through modifications of the environment, leads to an almost perfectly coherent work and gives the impression that the colony follows a predefined blueprint.

Numerous examples of this decentralized, collective intelligence have been discussed, including the collective choice of a food source in ant and bee colonies (Pasteels et al., 1987; Beckers et al., 1990; Seeley et al., 1991; Camazine & Sneyd, 1991), the formation of trail networks and foraging patterns in ant colonies (Aron et al., 1990; Deneubourg & Goss, 1989; Deneubourg et al., 1989; Franks, 1989; Goss et al., 1990; Franks et al., 1991), the dynamical division of labour in ant and wasp colonies (Deneubourg et al., 1987; Corbara et al., 1991; Theraulaz et al., 1990, 1991), the collective sorting of brood items in ant and bee colonies (Deneubourg et al., 1991; Franks & Sendova-Franks, 1992; Camazine, 1991; Camazine et al., 1990) and some aspects of building behavior in bee, wasp and ant colonies (Belic et al., 1986; Skarka et al., 1990; Deneubourg, Theraulaz & Beckers, 1992; Karsai & Penzes, 1993; Gallais-Hamonno & Chauvin, 1972; Franks et al., 1992).

In this paper, we shall focus on stigmergic building algorithms, i.e. collective building algorithms in which individuals communicate only through the local environment they perceive. The behavioral sequence characterizing the dynamical evolution of a given individual corresponds to a sequence of perceived stimulations. One important problem is to understand the way in which stimuli are organized in space and time so as to ensure a coherent building. In order to study this question, we have used a simplified model of space and simulated simple artificial agents on a lattice, capable of depositing elementary bricks depending on the local configuration of matter. It so happens that the starting point of this work was a set of experimental studies on the building behavior of eusocial wasps, and that some of the simulated algorithms can generate architectures faithfully reproducing wasp architectures encountered in nature. This explains why the rest of the paper will be organized around the building behavior of wasps, although the formal algorithms we present could in principle represent any stigmergic collective building behavior. Our goal is to explore the space of possible architectures that can be generated with a stigmergic algorithm.

After a brief introduction to wasp nest architectures in section 2, we present our model and explain our methodology in section 3. We then give a simple theoretical argument showing how constraints operating at the collective level can act upon individual behavior in the context of stigmergic building in section 4, and compare stigmergic building with building in solitary species in section 5. In section 6, we give some pictorial results of our simulations, and explain what all biological-like architectures have in common: they are all generated by coordinated building algorithms, in which the shape to be built is naturally decomposed into modular subshapes, observed in wasp nest architectures, defining corresponding building stages. In a coordinated algorithm, stimulating configurations belonging to different building stages do not overlap (a stimulating configuration is a local configuration of matter which triggers the deposit of a brick), so that at any time, all individuals cooperate in the building of the current subshape. This is our main result, together with the fact that algorithms with overlapping configurations yield structureless shapes, never found in nature. We also show empirically (1) the topological continuity of the mapping which associates an architecture to a given algorithm, and (2) the relative compactness of the subspace of coordinated algorithms. Point (1) means that two close algorithms in the space of all algorithms (that is, the space of all combinations of elementary rules) generate close architectures. Such a continuity implies in particular the stability of the building (morphogenetic) process with respect to small modifications at the behavioral level. Point (2) is of utmost importance since it implies that ìcoherentî architectures are rare: only highly specific behavioral algorithms can generate them. We end this paper with a discussion on the constraints that may have influenced the evolutionary path towards coordinated algorithms, and make some connections with related models.

2 Nest architectures and building behavior in wasp societies

Social wasps have the ability to build nests whose architectures range from the simplest to more complex, highly organized ones. The great majority of wasps nests are made of plant fibers that are chewed and cemented together with oral secretion. The resulting carton is then shaped by the wasps to build the various parts of the nest (pedicel, walls of cells or external envelope). But one can also find some nests that are made of mud or pure glandular secretion (Wenzel, 1991). Figure 1 shows some examples of nest architectures built by paper wasps. It seems obvious that some of these nests are more complex than others: in particular, nests c and d possess an external envelope and look more organized in the inside. Wenzel (1991) has classified wasp nests architectures, and found more than 60 different types, with many intermediates between extreme forms. A mature nest can have from a few cells up to a million cells packed in stacked combs, the latter being generally built by highly social species.

Since a lot of experimental studies, including ours (Karsai & Theraulaz, 1995), were carried out on primitively eusocial wasps (i.e. with overlapping adult generations, cooperative brood care, presence of a sterile caste), we will focus on these simpler societies of paper wasps. Most of these colonies are usually founded by one or a few individuals, and contain less than 100 individuals at the same time. For instance, in Polistes dominulus, there are about 20 individuals in the colony. What is important to ethologists is the understanding of the underlying behavioral building ëalgorithmsí, and possibly of their phylogeny. Previous studies showed that individual building algorithms consist of a series of ìif-thenî and ìyes-noî decisions (Downing & Jeanne, 1988; Deneubourg, Theraulaz & Beckers, 1992). Such an algorithm includes several types of acts, the first one consisting (with only a few exceptions) in attaching the future nest to a substrate with a ëstalk-like pedicel of wood pulpí (Wenzel, 1991) (see nests a, b and c). It seems that the placement of the first cells of the nest follows always the same rule within one given species. Then wasps initiate the nest by building two cells on either side of a flat extension of the pedicel. Subsequent cells are added to the outer circumference of the combs, each between two previously constructed cells (see figure 2). As more cells are added to the evolving structure, they eventually form closely packed parallel rows of cells and the nest generally has (statistical) radial or bilateral symmetry around these initial cells. One important point is that a wasp will tend to finish a row of cells before initiating a new row and that rows are initiated by the construction of a centrally located cell first. These simple rules ensure that the nest will grow fairly evenly in all directions from the petiole (Downing and Jeanne, 1990). There is therefore an a priori isotropy in space. Other rules ensure the enlargment of the nest by adding new combs with pedicels to the first one. If one looks at wasp nest architectures, one is impressed by the modular nature of the largest nests with the repetition of a basic pattern which represents a simple way to increase the nest size (see figure 2). This modular characteristic results from a cyclic building activity that is imposed by the very structure of the nest and does not result from any internal building cycle. Eggs are laid in the combs which are progressively built. Brood is present in these combs at various stages of maturity, explaining the difference in growth of the different combs, which are extended when needed by the growing larvae.

As long as the construction process goes on, the number of locations capable of receiving new cells increases. Therefore many activities can be performed at the same time and building acts are not performed a priori in a well-defined sequence. This is an extremely important point since the building activity of solitary insects relies on a sequential algorithm (a well-defined sequence of actions), whereas the building behavior of social insects is based on a stigmergic one. The ability of a swarm to build at more than one location on a growing nest is certainly an important evolutionary step for the development of complex nest architectures (Downing & Jeanne, 1990). But this fact has in turn induced new constraints since the local cues regulating the building behavior have to be organized in an appropriate way to ensure a coherent construction. Our numerical experiments have shown that in order to avoid conflicting cues during the building process, configurations that trigger a building action have to be organized in a non overlapping way. This is not a trivial statement indeed: if the wasps follow a strictly stigmergic algorithm, that is if they determine their building behavior on the sole basis of local configurations of matter, what must be the general characteristics of the individual building behavior in order for the group to produce a biological-like, coherent architecture ? In the rest of the paper, we shall examine, in the context of lattice models, what types of algorithms have to be implemented at the individual level in order to generate biological-like nest architectures.

3 Lattice swarms

In our model, we assume that the agents in the swarm move randomly, and independently on a three dimensional cubic lattice. Using a limited number of bricks of different type with the same cubic shape, they deposit these bricks according to a specified set of rules, embodied in a lookup table. The lookup table specifies what type of brick must be deposited at a site from the current configuration of bricks in the local neighborhood of that site. This neighborhood consists of the 26 cells surrounding the central cell occupied by an agent as shown in Figure 9. Agents can modify empty sites only (no unbuilding or brick replacement allowed). Two types of bricks will be considered hereafter. The bricks are the atomic building material, and since we were interested specifically in the spatio-temporal organization of the configurations that trigger a building activity, we will consider that all the agents are able to put down the right brick whenever they meet a stimulating configuration. The space of local configurations that are likely to be encountered by a given agent is rather huge (226 and 326 in 3D with two and three states respectively, which could be 0 (no brick), 1 (type 1 brick) and 2 (type 2 brick) and the space of local rules cannot be explored systematically ( and respectively). Therefore, one has to discover the minimum set of rules necessary to produce a given architecture in a more clever way. We assume that rules are applied in a deterministic, systematic way: each time a stimulating configuration is encountered, the corresponding brick is deposited. See Appendix A, where other ways of applying rules are defined, together with the notion of growth complexity. For obvious reasons, we chose to resort only to very small neighborhoods in space as well as in time: it would neither be biologically plausible nor insightful to use large windows (we seek minimal models), let alone the fact that the corresponding behavioral space would then be too large to be thoroughly explored.

Each agent or insect is able to build alone a complete architecture. In this sense, building is a matter of purely individual behavior. But the individual building behavior (i.e. the types of local configurations that trigger the building activity) has to be organized in such a way that a group of agents can produce the same architecture as well. Note that some natural wasp species face the same problem since nest construction is generally achieved by one female who is then replaced by a group of newly born workers. In particular, the group of agents has to be able to build the architecture without the combined actions of the different agents interfering and possibly destroying the whole activity of the swarm. In other words, individual activities have to be coordinated so as to ensure a well-organized building progress. We know that such a coordination of individual activities can work in termites with pheromone field gradients (Deneubourg, 1977; Kugler & Turvey, 1987; Kugler et al., 1990). One cannot exclude that similar processes could take place in wasp nest construction, but they cannot by themselves ensure the fine regulation of nest construction. With the building behavior in wasps, we come to a new step in the processes that lead to collectively built-up artifacts in social insects. The organization of individual activities need not rely on pheromone gradients but, more fundamentally, can be totally directed by the material patterns encountered on the nest.

4 Collectively induced constraints on individual behavior in a stigmergic building algorithm

When the n agents of a (biological or artificial) swarm join in the construction of an architecture, each time an agent acts on the environment at time t, it can feel at time t+1 the feedback resulting from its own action as well as any other agentís action in the near environment.

Let us now state part of our empirical conclusion, drawn on the basis of many computer simulations presented in section 6: in order to build a biological-like shape (what a biological-like shape may be is somewhat difficult to define formally, although intuitively obvious), the agents of a swarm following the above mentioned simple rules have to coordinate their activities; it is necessary that all agents respond in a uniform manner to the whole set of local configurations they encounter on the architecture. Therefore, at any given time, there must exist an active set of local configurations that all trigger the same qualitative type of brick deposit. Let be the set of all local stimulating configurations, that is the configurations which trigger the building behavior (put down a brick) if they are encountered. In order for the construction to proceed in a coherent way, there must be a succession of a certain number of qualitativeley distinct building states. Let be the set of these building states. Each of these states is characterized by a subset of , , with and . Considering each building state , each time a brick is put down, the result gives rise to one or more configurations , and the construction process may go on either in a sequential manner (a single configuration allows the agents to put down a brick ó not to confuse with a sequential algorithm), or in a parallel manner (in this case, several configurations allowing the deposit of a brick are simultaneously present). The completion of the building state then corresponds to the appearance of new configurations . As we can see, the construction process follows some emergent sketch and it can give rise to recurrent states. Such states are at the root of the modular structures that appear in the architecture. One may have the two following cases (where denotes the set of responses generated in state ):

ï a strictly linear chain of building states :

;

ï a chain of building states that can have recurrent states:

Therefore, if one wants a swarm of agents to build a given architecture, one has to decompose it into a finite number of building steps, with the necessary condition that the local configurations that are created by a given state and which trigger building actions, differ from those created by a previous or a forthcoming building step so as to avoid the deorganization of the building activity. We call such a building algorithm, whose time evolution obeys this nonoverlapping condition, a coordinated algorithm, because all individuals cooperate in the current building state at any time. Although coordination is an intrinsic property of the algorithm, it is not obvious to see it in the rule table, and it is often necessary to run the algorithm to discover the coordination it produces.

The complementary part of these empirical observations will be exposed in section 6: if, as we just explained, the construction of a coherent architecture requires a coordinated algorithm, the set of all coordinated algorithms corresponds in turn to a specific set of architectures, not all biological-like, but all coherent. We shall see indeed that coordinated algorithms produce architectures belonging to a very compact subspace of easily recognizable architectures, namely coherent architectures. Therefore, there is a bidirectional relationship between coherent architectures, including biological-like ones, and coordinated algorithms.

5 Comparison with species of solitary wasps

In solitary species, the building activity relies on a sequence of internal states which specifies the stimulating external local configurations (Theraulaz, Beckers & Deneubourg, 1992; Theraulaz & Deneubourg, 1994). Eventhough the insect may dynamically produce local configurations corresponding to a configuration that is stimulating with respect to a previous or future state, its current internal state makes it (possibly temporarily) insensitive to this type of configuration. Therefore, the building process can rigorously follow the prescribed sequence of states. This explains why the insect may be somewhat ìill at easeî when all stimulating configurations with respect to its current internal state are artificially suppressed: it then has to start the whole building sequence again from the beginning.

Let us consider the situation depicted in figure 3. If the animal is in a state and if = is the set of all local configurations that trigger the bulding activity when the animal is in state , where denotes a stopping configuration produced in the course of construction as the animal is in state , it may happen that one or several configurations are produced. Everything then happens as if the animal were insensitive to these configurations as long as it remains in state .

When it comes to a stigmergic building script involving several individuals that cooperate in the building of a common architecture, the order in which stimulating configurations are produced must be strictly satisfied, and such configurations must not interfere. This ordering constraint further imposes a constraint on the type of architecture that can be collectively generated. Therefore, it is hard to determine whether it is the nature of the coordination of individual building activities through the dynamically varying form that severely restricts the space of possible architectures, or if it is the space of viable architectures (among which those observed in nature) which implies coordination. According to our computer experiments, both viewpoints are equally acceptable.

6 Results

As mentioned earlier, we have tested only purely deterministic rules, with one period and one level of hierarchy. More extensive simulations should be performed in order to explore the whole behavioral space in an exhaustive way, but we believe our results (based on a large sampling of the ensemble of algorithms) to be general enough. The number of agents is kept constant during a simulation. Increasing this number does not affect the final shape of the architecture which will only be achieved faster. According to their neighborhoods and their lookup tables, the agents may put down two types of bricks (type 1 or type 2). Although the rules are quite simple, we obtained very interesting patterns, some of which closely match those found in nature. One must keep in mind that our artificial agents use bricks and not paper to build their nests, and that other artifacts exist, due for instance to the arbitrary discretization of space. Our goal was in fact to test stigmergic algorithms independently of the material used, i.e. artificial wasps in an artificial world.

We present here a few architectures that have been obtained using these simple deterministic rules. Space limitation doesnít allow us to give in extenso all the rules used to grow the architectures presented in figures 4a-4n. As an example we give in the Appendix the whole set of stimulating configurations required to grow architectures 4d,e and 4n. All architectures, except g and h, have been obtained with coordinated algorithms. The difference between (g, h) and all other architectures is striking. One given coordinated algorithm always converges towards architectures that possess similar features, despite the different realizations of the random walks performed by the agents in different simulations. Any uncoordinated algorithm seems to diverge: the same algorithm leads to different global architectures in different simulations. This tendency to diverge comes from the fact that stimulating configurations are not organized in time and space and many of them overlap, so that the architecture grows in space without any coherence. As an illustration of this fact, architectures d and e result from two successive simulations using the same coordinated algorithm, and architectures g and h result from the same non-coordinated algorithm. Moreover, even in shapes built with coordinated algorithms, there may some degree of variation, which is larger in cases where the number of different choices within one given building state is large. But the result may also be deterministic in some cases (that is, all simulations lead to exactly the same architecture despite the random component in individual behavior), through the implicit handshakes and interlocks that are setup at every stage.

Some of the structured architectures of figure 4 are reminiscent of natural wasp nests. Among these nests the presence of plateaus is observed in b, d, e, f, i, and the different levels of the nests are linked together with either a straight axis (b, i) or with a set of pedicels (d, e, f). Some others possess an external envelope: nests k and n are shown with a portion of the front envelope cut away so as to allow for a visualization of the nestís interior, and correspond to nests found in the genera Chartergus. Figures c, g, h, j, l, m, are examples of architectures not found in nature, but only g and h look structureless. As an example of how the particular geometry of the discrete space may influence global patterns, we also present two coherent architectures obtained from coordinated algorithms using hexagonal elementary building blocks, that is, with a 30° rotational invariance around the z-axis (figures 4o and 4p). We see that this particular geometry allows round shapes to be easily created, which is not the case for cubic bricks.

In order to understand what a coordinated algorithm is, we now focus on an example depicted in figure 5. This figure represents the successive steps of the construction of a nest which looks like nests built by Epipona. The transition between two successive building steps is shown to depend on a given number of local configurations stimulating the deposit of a brick. Once all the bricks in the current step have been deposited, the building process goes to the next step. Steps 1 to 5 correspond to the enlargement of the top of the nest, including the first sessile comb of cells (step 3). Step 6 represents the construction and lengthening of the external envelope, from which parallel combs will be built (steps 7 and 8). These steps determine the distinction between this nest, where the entrance and access holes at the different levels lie in the periphery of the comb, from the Chartergus nest represented in figures 4k and 4m, where this hole lies in the middle of the nest. Figure 5.9 represents the final architecture.

Figure 6 illustrates the concept of modularity. Recurrent states may appear, inducing a cyclicity in the groupís behavior. From the architectural viewpoint, this corresponds to a modular pattern, where each module is built during a cycle (all modules are qualitatively identical). This modularity is a simple way for the group to enlarge the architecture. The two figures on the left of figure 6 show how modularity is implemented in a nest with successive plateaus: each cycle corresponds to the addition of a plateau. Figure 6a shows the final architecture (Stelopolybia), with the various stages, while figure 6b explicitly shows the successive steps. Figure 6c shows a complete architecture of Chartergus and figure 6d how modularity takes place.

Let us end with more theoretical considerations about the structures of the behavioral space and of the associated space of architectural patterns. Here, the behavioral space is simply the ensemble of all algorithms, where each algorithm is characterized by a set of stimulating configurations, and the space of architectural patterns is the ensemble of architectures grown by these algorithms. There seems to be a regular relationship between these two spaces, as is shown by a Factorial Correspondence Analysis (figure 7) and a hierarchical cluster analysis (figure 8) (Benzecri, 1973; Lefebvre, 1980). The three axes represented in figure 7 are the leading three eigenvectors of a matrix M whose columns represent 12 architectures (a to n) of figure 4, and whose rows represent the 211 associated stimulating configurations: for instance Mij=0 if architecture j has not been obtained with i as a stimulating configuration, and Mij=1 if i is a stimulating configuration necessary for the generation of architecture j. Figures 7 and 8 show that any two close architectures also have close algorithms: therefore, there seems to be a continuous relationship between architectures and their corresponding algorithms, at least in the coordinated subspace. Note also the relative stability of coordinated algorithms with respect to perturbations in the following sense: if random behavioral rules are added to a coordinated algorithm, they may very well have a relatively small influence or even no influence at all on the corresponding coherent architecture obtained, because such an architecture is partially or fully constrained, so that random rules are unlikely to be ever applied. Goodwin et al. (1993) and Kauffman (1993) have argued along the same lines that morphogenetic processes may be robust because they result from the unfolding in time and space of ìsome richly integrated combinationî of simple mechanisms that mutually constrain one another to produce specific shapes belonging to a small subspace of the space of all possible shapes: ìa few of the conceivable morphologies in the family of forms come to occupy large basins of attractionî (Kauffman, 1993). A very similar idea is also present in the paper by Oster & Alberch (1982), where it is shown that interacting morphogenetic mechanisms mutually impose constraints on one another, so that only large enough mutations, or mutations in the vicinity of bifurcations, can generate substantial modifications of generated forms.

The coordinated subspace seems to be relatively small and compact, since any non-coordinated algorithm lies far away from this subspace. This property is confirmed by a random exploration of rule space: coherent architectures, or, equivalently, coordinated algorithms, are quite rare. We have tested 106 randomly selected algorithms containing up to 40 stimulating configurations (+symmetries around the z-axis), without finding any single coherent architecture. It is only by imposing a bias on our rule space sampling that we eventually came across coherent architectures, whose corresponding algorithms turned out to be coordinated. The coherent architectures we have presented in figure 4 were obtained by working ìbackwardsî, from the shape to be built to the corresponding algorithm.

Finally, a hierarchical cluster analysis was applied to the same table used for FCA except that we removed architectures g and h, that were obtained from a non-coordinated algorithm, because they were too different from all others. This analysis allows to refine the relationships between the architectures, and could be compared to cladograms based on nest architectures. Such a comparison, put in proper perspective, would be an interesting test for our model.

The conclusion of this section is that coordinated algorithms produce relatively stable, coherent shapes belonging to a small, compact subspace of the space of all possible architectures, and that non-coordinated algorithms generate unstable, structureless shapes. We shall now discuss the implications of this conclusion combined with the observation, reported in section 4, that the construction of a coherent architecture requires a coordinated algorithm.

7 Related work and discussion

Related work

The building activity of social insects has been the focus of many studies (Hansell, 1984), in ants (e.g., Gallais-Hammono & Chauvin, 1972; Sudd, 1975; Ceuster, 1980; Franks et al., 1992), bees (e.g., Darchen, 1959; Belic et al., 1986; Skarka et al., 1990), wasps (e.g., Jeanne, 1975; Downing & Jeanne, 1988, 1990; Wenzel, 1991; Karsai & Penzes, 1993; Karsai & Theraulaz, 1995), and termites (Grassé, 1959, 1984; Deneubourg, 1977; Bruinsma, 1979). During the construction of an architecture, social insects are involved in a collective, ìcooperativeî phenomenon usually considered to be of great complexity, that results in the formation of a spatial pattern whose characteristic scale is often far beyond the size of a single animal. Only a few models of collective building behavior are available in the literature, owing to the very complexity of such processes. Some models, that have been insightful by showing how concepts borrowed from self-organization (basically amplifications of small fluctuations) may apply to the description of some aspects of some building behaviors, describe only simple stages or parts of the construction process: initiation of pillars in termites (Deneubourg, 1977), or of parallel combs in bees (Belic et al., 1986; Skarka et al., 1990). In particular, Belic et al. (1986) and Skarka et al. (1990) have introduced and studied a mathematical model for the construction of parallel combs in beehive, where the bee-wax and bee-bee interactions coupled via a nonlinear feedback mechanism constitute the main ingredients: these authors showed the importance of the competition between bees and the bee-wax interactions for the growth of parallel and equidistant combs. But it is not clear to us that such models can go much beyond simple stages unless they become very complicated. For example, would it be possible in practice or even in principle, to organize the building of a wasp nest only in terms of diffusing fields and gradients? We have decided to follow a different path in our approach, by allowing individuals to respond qualitatively, rather than quantitatively, to different stimuli. This choice may correspond to another level of description, that we believe to be more ìtractableî for high level considerations, such as those concerning evolution. Moreover, we decided to focus on purely stigmergic algorithms, that is, distributed building algorithms in which individualsí actions are directed solely by the dynamically evolving shape in construction.

The logic behind our model is very similar to that of other models developped to account for collective brood sorting by ant (Deneubourg et al., 1991) and bee colonies (Camazine, 1991). In these models, individual actions based on local configurations of brood items produce the clustering of eggs, larvae, and pupae in ants and the genesis of a well-organized round shaped pattern, consisting of a succession of three concentric regions of brood, pollen and honey on the comb of honey bees. As regards wasp nests, using a similar approach but a different model, Karsai and Penzes (1993), showed how the construction of the comb structure in Polistes wasp colonies arises from the dynamic interactions between wasps and the previously constructed comb. Finally, for the lattice model described in this paper, since the agents, and hence the bricks, perform random walks on the lattice, it can be considered as a kind of diffusion-limited aggregation, where the ìphysicalî laws governing the aggregation are precisely embodied in the rule table of the algorithm. Similar models have been, and still are, extensively studied in physics, and it may be possible to gain much insight by exploring this analogy. One way of going further along these lines would be to allow the walkers not only to modify the landscape but also to be influenced by the landscape itself, following the Active Walker Model proposed by Freimuth & Lam (1992).

Discussion

Under the condition that the regulation of the buidling behavior operates in a strict stigmergic mode, we have showed that the only way to build a coherent structure is to use a particular class of algorithms, that we named ëcoordinated algorithmsí. In such algorithms, local patterns of matter that result from past construction and that are encountered by individuals moving randomly on the nest structure, provide the exclusive cues necessary to direct and coordinate the building activities of the swarm. We are perfectly aware that such a model oversimplifies the processes we observe in nature. In particular, not to speak of other artifacts, most of the simulated swarms presented here 'live' in an abstract space using cubic bricks to build architectures, while natural wasp nests are built with hexagonal paper cells. Consequently, symmetry properties are not equivalent, as can be seen from architectures 4o and 4n, which have been obtained from a preliminary exploration of algorithms using hexagonal building blocks, and show that round shapes can be readily generated in that case. And once again, our model corresponds to a particular, coarse-grained level of description in which no hypothesis need be made concerning the actual ìmicroscopicî mechanisms governing the behaviors of the agents: it seems that real insects just act as if they were following some rules, and other levels of description may be more relevant to understand the detail of this behavior. It may be for instance that real wasps do not follow discrete, qualitative rules but are rather sensitive to, say, quantitative chemical cues. Such levels of description are not in contradiction but are simply compatible with ours, although they are different and can certainly explain different things.

Nevertheless, and all precautions considered, we believe that the behavioral constraints we studied are still present in real wasps. The basic aim of this paper was to determine what kind of logical path the sequence of stimulating configurations produced by the distributed construction activities along time had to follow, in order for a swarm of agents, be they natural or artificial, to build a coherent architecture about which they have no concept. The conclusion is that this logical path implies coordination, and that coordination can be achieved simply through judiciously chosen stimulating patterns of matter. A classical view would be that coordination leads to some particular architectures, and in this respect, our results could explain to some extent the relatively small number of different nest architectures in nature, if coordination is taken for granted. In effect, we saw that using coordinated algorithms strongly constrains the space of possible coherent architectures (this is illustrated by the smallness and compactness of the subspace of coherent architectures).

But we have also shown that another viewpoint is possible: any such coherent architecture naturally induces coordination, which may then be seen as a by-product of the architecture. As we have seen, the particular features of collective building behavior (or more precisely of the model class of algorithms that we considered here) require that the insectsí building activities be (indirectly) oriented and coordinated by the successive steps of the dynamically evolving architecture, i.e. dynamical patterns of matter, in order to build architectures observed in nature. Thus, following this hypothesis, some types of nest architectures could have been selected in the course of evolution in accordance with their functional and adaptive values, and in turn these architectures (if they are to be generated with the plausible model class of algorithms considered here), may have imposed constraints on the building procedure implemented at the individual level, automatically forcing the agents to coordinate their activities. In other words, cooperation could be in that way a natural, unexpectedly simple, consequence of the architectural forms selected through evolution, provided that, once again, the behavioral algorithms we studied have some biological relevance. The kind of constraints we pointed out through the fact that coordinated algorithms are a logically necessary condition at the individual level in order for a swarm to build coherent nest architectures refers to ahistorical contraints in Resnik's terminology (Resnik, 1995). This is the kind of constraint that will hold no matter what direction evolution takes. Self-organizing properties displayed by complex biological systems belong to that class of constraints and more biological studies have to be undertaken so as to identify the proximal behavioral rules that generate collective constraints on the functional pattern embodied at the level of the colony.

Studies of the mechanisms that allow socials insects to collectively process a great quantity of information about the structure of their environment, or about the organization of their colonies, can give us valuable insight into the constraints these species had to face in the course of evolution in order to reach a perfectly coordinated collective building behavior (Theraulaz & Deneubourg, 1992; Theraulaz & Gervet, 1992; Deneubourg, Theraulaz & Beckers, 1992). The most appropriate viewpoint would certainly be a combination of both the viewpoints that we presented: as pointed out by Jeanne (1975), the evolution of nest architectures has undoubtedly been influenced by a great variety of constraints, including physical factors of the environment and of the material used to build the nest (Hansell, 1984), energetics involved in building the nest, predation by vertebrates and arthropods and social requirements of the colony, as well as behavioral constraints. These latter constraints may act to reduce the space of possible architectures, while natural selection could eventually select those possessing the best functional and adaptive values. The next step would be to study how the physics of the building material (paper, vegetable fibers, mud, …) may act back on the individual behavioral algorithm used by the wasps to shape the architecture. In particular a compared study of the organization of the local cues that control building behavior in different species has to be worked out.

Finally, we believe that our study may also be beneficial to engineers, who, in their own attempt to design distributed artificial multi-agent systems (cellular and reactive robots, mobile automata), are facing the problem of finding simple behavioral algorithms at the individual level so as to produce a collective performance (Bonabeau et al., 1994). The study of collective building processes in social insects seems to be a path to follow in order to discover new kinds of such distributed behavioral algorithms (see in particular Beni, 1988, 1989; Beni & Wang, 1991 for special references concerning swarm intelligence phenomena in cellular robots societies). Let us emphasize the correspondence between a problem-solving trajectory going from an initial state to a desired state, and the coevolution of a swarm and its environment, if properly defined by an external observer (Bonabeau & Theraulaz, 1994). We have shown that coordination may not have to be prewired, but may emerge in some cases from individual behaviors, in such a way that no individual needs to be aware of that coordination. Colonies of simple robots, which already exist (Beckers, Deneubourg & Goss, 1993; Beckers, Holland & Deneubourg, 1994) and are capable of performing spatial clustering of objects, could be designed along these lines, with individuals synchronizing their activities without being explicitly programmed to do so.

References

Aron, S., Deneubourg, J.-L., Goss, S. and Pasteels, J.-M. (1990). Functional self-organisation illustrated by inter-nest traffic in ants: the case of the argentine ant. In: Biological Motion, Lecture Notes in Biomathematics 89 (Alt, W. & Hoffmann, G., eds), pp. 533-547. Springer-Verlag.

Beckers, R., Deneubourg, J.-L., Goss, S. and Pasteels, J.-M. (1990). Collective decision making through food recruitment. Ins. Soc., 37, 258-267.

Beckers, R., Deneubourg, J.-L. & Goss, S. (1993). Self-organized groups of interactive robots. Paper presented at the Second European Conference on Artificial Life, May 24-26 1993, Brussels, Belgium.

Beckers, R., Holland, O.E. & Deneubourg, J.-L. (1994). From local actions to global tasks: Stigmergy and collective robotics. In: Artificial Life IV (Brooks, R. & Maes, P., eds.), 181-189. Cambridge: MIT Press.

Belic, M. R., Skarka, V., Deneubourg, J.-L. & Lax, M. (1986). Mathematical model of honeycomb construction. J. math. Biol. 24, 437-449.

Beni, G. (1988). The concept of cellular robotic system. In: Proceedings of the 1988 IEEE International Symposium on Intelligent Control, Arlington, VA, 57-62. Los Alamitos: IEEE Computer Society Press.

Beni, G. & Wang, J. (1989). Swarm Intelligence. In: Proceedings of the 7th Annual Meeting of the Robotics Society of Japan, Shibaura, Japan, 425-428.

Beni, G. & Wang, J. (1991). Theoretical problems for the realization of distributed robotic systems. In: Proceedings of the 1991 IEEE International Conference on Robotic and Automation, Sacramento, California, 1914-1920. Los Alamitos: IEEE Computer Society Press.

Benzecri, J.P. (1973). Líanalyse des données. II. Líanalyse des correspondances. Paris: Dunod.

Berland, L. & Grassé, P.-P. (1951). Super-famille des Vespoidea Ashmead. In: Traité de Zoologie vol. 10 (Grassé, P.-P., ed), pp. 1127-1174. Paris: Masson.

Bonabeau, E. & Theraulaz, G. (eds.) (1994). Intelligence Collective. Paris: Hermès.

Bonabeau, E., Theraulaz, G., Arpin, E., & Sardet, E. (1994). The building behavior of lattice swarms. In: Artificial Life IV (Brooks, R. & Maes, P., eds.), 307-312. Cambridge: MIT Press.

Bruinsma, O. H. (1979). An analysis of building behaviour of the termite Macrotermes subhyalinus (Rambur). Thesis, Landbouwhogeschool, Wageningen.

Camazine, S. (1991). Self-organizing pattern-formation on the combs of honeybee colonies. Behav. Ecol. Sociobiol. 28, 61-76.

Camazine, S. & Sneyd, J. (1991). A model of collective nectar source selection by honey bees: self-organization through simple rules. J. theor. Biol. 149, 547-571.

Camazine, S., Sneyd, J. Jenkins, M.J. & Murray, J.D. (1990). A mathematical model of self-organizing pattern formation on the combs of honey bee colonies. J. theor. Biol. 147, 553-571.

Ceusters, R. (1980). Etude du degré de couverture du ciel par la végétation au-dessus des nids de Formica polyctena Foerst. Biol. Ecol. Médit. VII (3), 187-188.

Corbara, B., Deneubourg, J.-L., Fresneau, D., Goss, S., Lachaud, J.-P. & Pham-Ngoc, A. (1991). Simulation de la genèse díune division du travail au sein díune société de fourmis Ponerines: un modèle díauto-organisation. Actes Coll. Ins. Soc. 7, 205-206.

Darchen, R. (1959). Les techniques de la construction chez Apis mellifica. Thesis, Université de Paris.

Deneubourg, J.-L. (1977). Application de líordre par fluctuations à la description de certaines étapes de la construction du nid chez les termites. Ins. Soc. 24, 117-130.

Deneubourg, J.-L. & Goss, S. (1989a). Collective patterns and decision making. Ethol.Ecol.& Evol. 1, 295-311.

Deneubourg, J.-L., Theraulaz, G. & Beckers, R. (1992). Swarm-made architectures. In: Toward a Practice of Autonomous Systems, Proceedings of The First European Conference on Artificial Life (Varela, F.J. & Bourgine, P., eds), 123-133. Cambridge, MA: The MIT Press/Bradford Books.

Deneubourg, J.-L., Goss, S., Franks, N. & Pasteels, J.-M. (1989). The blind leading the blind: modeling chemically mediated army ant raid patterns. J. Ins. Behav. 2, 719-725.

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: Simulation of Adaptive Behavior: From Animals to Animats (Meyer, J.A. & Wilson, S.W., eds.), 356-365. Cambridge, MA: The MIT Press/Bradford Books.

Downing, H. A. & Jeanne, R. L. (1988). Nest construction by the paperwasp Polistes: A test of stigmergy theory. Anim. Behav. 36, 1729-1739.

Downing, H. A. & Jeanne, R. L. (1990). The regulation of complex building behavior in the paperwasp Polistes fuscatus . Anim. Behav. 39, 105-124.

Franks, N.R. (1989). Army ants: a collective intelligence. American Scientist, 77, 139-145.

Franks, N.R. & Sendova-Franks, A.B. (1992). Brood sorting by ants: distributing the workload over the work-surface. Behav. Ecol. Sociobiol. 30, 109-123.

Franks, N. R., A. Wilby, V.W. Silverman & C. Tofts. (1992). Self-organizing nest construction in ants: sophisticated building by blind buldozing. Anim. Behav. 44, 357-375.

Freimuth, R. D. & Lam, L. (1990). Active Walker Models for Filamentary Growth Patterns. In: Modeling Complex Phenomena (Lam, L. & Naroditsky, V., eds), 302-313. New-York: Springer Verlag.

Gallais-Hamonno, F.G. & Chauvin, R. (1972). Simulations sur ordinateur de la construction du dôme et du ramassage des brindilles chez une fourmi (Formica polyctena). C. R. Acad. Sc. Paris 275 D, 1275-1278.

Goodwin, B. C., Kauffman, S. & Murray, J. D. (1993). Is morphogenesis an intrinsically robust process? J. theor. Biol. 163, 135-144.

Goss, S., Deneubourg, J.-L., Aron, S., Beckers, R. & Pasteels, J.-M. (1990) How trail laying and trail following can solve foraging problems for ant colonies. In: Behavioural mechanisms of food selection (Hughes, R.N., ed) pp. 661-678. NATO ASI Series, Vol. G20. Springer Verlag.

Grassé, P.-P. (1959). La reconstruction du nid et les coordinations inter-individuelles chez Bellicositermes Natalensis et Cubitermes sp. La théorie de la stigmergie : essai díinterprétation du comportement des termites constructeursî, Ins. Soc. 6, 41-81.

Grassé, P.-P. (1984). Réparation, reconstruction et remaniements internes du nid. Coordination des tâches individuelles et comportement stigmergique. Le déterminisme du comportement constructeur. In: Termitologia, Tome II ñ Fondation des Sociétés ñ Construction ñ (Grassé, P.P. ed.), 490-577. Paris: Masson.

Hansell, M. H. (1984). Animal architecture and building behavior. Longman: London.

Held, L. I. Jr. (1992). Models of embryonic periodicity. Monographs in Developmental Biology, vol. 24 (Sauer, H. W., ed.). Basel: Karger.

Jeanne, R. L. (1975). The adaptativeness of Social wasp nest architecture. The Quart. Rev. Biol. 50, 267-287.

Karsai, I. & Penzes, Z. (1993). Comb building in social wasps: self-organization and stigmergic script. J. theor. Biol. 161, 505-525.

Karsai, I. & Theraulaz, G. (1995). Nest building in a social wasp : postures and constraints (Hymenoptera: Vespidae), Sociobiology 26, 83-114.

Kauffman, S. A. (1993). The origins of order. Oxford: Oxford University Press.

Kugler, P.N. & Turvey, M.T. (1987). Information, natural law, and the self-assembly of rhytmic movements. Hillsdale, NJ: LEA.

Kugler, P.N., Shaw, R.E.,Vincente, K.J. & Kinsella-Shaw, J. (1990). Inquiry into intentional systems I: Issues in ecological physics, Psychol. Res. 52.

Lefebvre, J. (1980). Introduction aux analyses statistiques multi-dimensionnelles. Paris: Masson.

Meinhardt, H. (1982). Models of biological pattern formation. London: Academic Press.

Murray, J. D. (1989). Mathematical biology. Berlin, Heidelberg, New York: Springer.

Oster, G. F. & Alberch, P. (1982). Evolution and bifurcation of developmental programs. Evolution 36, 444-459.

Pasteels, J.M. Deneubourg, J.L. & Goss, S. (1987). Self-organization in ant societies (I): trail recruitment to newly discovered food sources. In: From Individual to Collective Behaviour in Social Insects (Pasteels, J.M. & Deneubourg, J.L., eds.). Experientia Supplementum 54, 155-175. Basel: Birkhauser Verlag.

Resnik, D. (1995). Developmental constraints and patterns: Some pertinent distinctions, J. theor. Biol. 173, 231-240.

Sachs, T. (1994). Variable development as a basis for robust pattern formation. J. theor. Biol. 170, 423-425.

Seeley, T.D., Camazine, S. & Sneyd, J. (1991). Collective decision-making in honey bees: how colonies choose among nectar sources. Behav. Ecol. Sociobiol. 28, 277-290.

Sendova-Franks, A. & Franks, N.R. (1992). Task allocation in ant colonies within variable environments (a study of temporal polyethism). Bull. Math. Biol. 55, 75-96.

Skarka, V., Deneubourg, J.-L. & Belic, M.R. (1990). Mathematical Model of Building Behavior of Apis mellifera. J. theor. Biol. 147, 1-16.

Sudd, J. A. (1975). A model of digging behavior and tunnel production in ants. Ins. Soc. 22, 225.

Theraulaz, G. & Deneubourg , J.L. (1992). On Formal Constraints in Swarm Dynamics. In: Proceedings of the 1992 IEEE International Symposium on Intelligent Control, Glasgow, Scotland. Los Alamitos: IEEE Computer Society Press.

Theraulaz, G. & Deneubourg , J.L. (1994). Swarm Intelligence in Social Insects and the Emergence of Cultural Swarm Patterns. In:The Ethological Roots of Culture (Gardner A., Gardner B., Chiarelli B. & Plooij F., eds.), 107-123. Proc. NATO ASI, Series D: Behavioural and Social Sciences - Vol. 78. Dordrecht: Kluwer Academic Publishers.

Theraulaz, G. & Gervet, J. (1992). Les performances collectives des sociétés díinsectes. Psychologie Française, 37, 7-14.

Theraulaz, G. & Gervet, J. (1993). Principes fonctionnels de líintelligence en essaim et modèles de computation collective chez les insectes sociaux. In: Proceedings of the Second European Congress on Systems Science, Prague, République Tchèque, 3-10 Octobre 1993, Vol. III: 880-889. Paris: AFCET.

Theraulaz, G. (1994). Du Super-Organisme à líIntelligence en Essaim: Modèles et Représentations du Fonctionnement des Sociétés díInsectes. In: Intelligence Collective (Bonabeau E. & Theraulaz G., eds.), 29-109. Paris: Hermès.

Theraulaz, G., Goss, S., Gervet, J. & Deneubourg, J.L. (1990). Swarm Intelligence in wasps colonies : an example of task assignment in multiagents systems. In: Proceedings of the 1990 IEEE International Symposium on Intelligent Control, Philadelphia, PA. (Meystel, A., Herath, J. & Gray, S., eds.), 135-143. Los Alamitos: IEEE Computer Society Press.

Theraulaz, G., Goss, S., Gervet, J. & Deneubourg, J.L. (1991). Task differentiation in Polistes wasp colonies : a model for self-organizing groups of robots. In: Simulation of Adaptive Behavior: From Animals to Animats (Meyer, J.A. & Wilson, S.W., eds.), 346-355. Cambridge, Massachusetts: The MIT Press/Bradford Books.

Wenzel, J. W. (1991). Evolution of nest architecture. In: Social Biology of Wasps (Ross, K. G. & Matthews, R.W., eds.), 480-521. Ithaca: Cornell University Press.

Wilson, E.O. (1971). The Insect Societies. Cambridge, MA: Harvard University Press.

Wilson, E.O. (1975). Sociobiology. Cambridge, Massachusetts: The Belknap Press of Harvard University Press.

Figures captions

Figure 1. a. nest of Ropalidia variegata, b. nest of Mischocyttarus drewsenic. nest of Angiopolybia pallens, d. nest of Epipona morio (modified from Jeanne, 1975 and Berland & Grassé, 1951).

Figure 2. The first steps of nest building in a Polistes dominulus (Christ) wasp society: the three pictures show the initiation of the nest, with the construction of a pedicel (figure a), of the first cell (figure b), and of a few subsequent cells (figure c).

Figure 3. A three-state sequential algorithm. is the transition probability from state i to state j. is the set of stimulating configurations when the animal is in state i and denotes the the set of stopping configurations for state i.

Figure 4. Simulations of collective building with a 3D Lattice Swarm. Simulations were made on a 20x20x20 Lattice with 10 wasps. For those architectures which are reminiscent of natural wasp nests, we give the name of the genera exhibiting a similar design. a. Nest architecture (Parapolybia) obtained after 20000 steps. b. Nest architecture (Parachartergus) obtained after 20000 steps. c. Achitecture obtained after 20000 steps. d, e. Nest Architectures (Stelopolybia) obtained after 20000 steps. f. Nest architecture (Stelopolybia) obtained after 20000 steps. g, h. Architectures obtained after 15000 steps using a non-coordinated algorithm. i Nest architectures (Vespa) obtained after 20000 steps. j Architecture obtained after 80000 steps. k Nest architecture (Chatergus) obtained after 185000 steps. l Architecture obtained after 125000 steps. m Architecture obtained after 85000 steps. n Nest architecture (Chatergus) obtained after 100000 steps. o,p Coherent architectures obtained from coordinated algorithms using hexagonal bulding blocks.

Figure 5. Succesive building steps in the construction of an Epipona nest with a Lattice Swarm. The completion of each step p gives rise to stimulating configurations belonging to the next step. All stimulating configurations are organized so as to ensure a regular building process. In particular, within a given step, the stimulating configurations do not have to be spatially connected and can occur simultaneously at different locations. In steps 7 to 9, the front and right portions of the external envelope have been cut away.

Figure 6. Formation of modular structures as a by-product of recurrent stimulating configurations in the architecture. A Stelopolybia-like nest (a, b) and a Chartergus-like nest (c, d) are depicted.

Figure 7. Factorial Correspondence Analysis (FCA). Projection of the architectures onto the space defined by axes 1, 2 and 3. The subspace occupied by the architectures grown with coordinated algorithms is magnified. The FCA was carried out on the whole set of 211 stimulating configurations necessary to build the 12 architectures selected.

Figure 8. Hierarchical cluster analysis of 11 architectures grown with coordinated algorithms.

Figure 9. Local neighborhood in 3D Lattice Swarm

Appendix A

A1. The rules to deposit bricks have been taken to be very simple in the present paper. But they can be applied in a great number of ways:

(1) rules can be applied deterministically (there are configurations that trigger a deposit and others that donít; each time an agent encounters a stimulating configuration, it will deposit a brick at that location);

(2) rules can be applied stochastically (i.e. a given configuration triggers a rule with a predefined probability);

(3) there is only one set of rules which is always scanned;

(4) there are several sets of rules which are used in a seasonal manner (i.e. set n°1 during t1 times steps, then set n°2 during t2 time steps, etc...)

(5) there is a hierarchy of sets of rules so that lower-level rules are applied when higher-level rules can no longer be applied (i.e. practically, an agent tries to apply the first set of rules; if it does so unsuccessfully for an amount of time T ó this implies some kind of memory ó, it switches to the next set of rules, etc...) and there are many other possible refinements.

A2. These algorithms are extracted from a hierarchy of elementary behaviors developed by Cris Moore (private communication) to describe different levels of growth complexity. Growth complexity is different from recognition complexity, embodied e.g. in Chomskyís grammars, which tell how difficult it is to recognize that a particular pattern belongs to a given set of patterns: growth complexity should be a measure of how difficult it is to grow a pattern. Since we deal with models, such a measure can only exist with respect to a particular model class. The problem is then to find the most appropriate model class to describe a given phenomenon (there are many ways of generating a pattern: see e.g. Meinhardt (1982), Murray (1989), Held (1992), or Sachs (1994)). While it seems rather difficult to evaluate the complexity of continuous growth models, such as reaction-diffusion equations, it becomes possible to do so with formal models relying on discrete automata. Of course, such discrete models may not give a reliable image of how a pattern is actually formed in many cases. Our experience suggests, however, that our model can be applicable, despite all artifacts, to nest building in wasps owing to the apparent ìif-thenî/îyes-noî nature of their behaviors, which can be described, in a rough approximation, by discrete automaton rules. Discrete automata may not describe many other building behaviors, especially if quantitative responses (e.g. to chemical gradients) are intrinsically important.

To grow a pattern on a lattice, one seeks to apply rules depending on the local environment. The way in which the (minimal) rules must be applied in order to generate the desired pattern defines the level of growth complexity (GC) of the pattern. Lower levels are embedded into higher ones. Note that finding the growth complexity of a given pattern is an inverse problem very similar to that of finding the algorithmic complexity of a bit string. Growth complexity has obviously some biological relevance, since it is a measure of the sophistication of the behavioral algorithm needed to effectively grow ëcomplexí architectures. It is also a relevant way of quantifying the sophistication of a man-made system designed to grow these complex architectures. In this paper, only rules of type 1 were examined, and we tried to characterize the class of rules that allow a swarm to build a coherent structure within this restricted context. The growth complexity of a pattern can then be defined here as the minimal number of elementary stimulating configurations required to generate the pattern. For example, the GC of the architectures of figure 4 are the following: a. GC = 13, b. GC= 29, c. GC = 30, d, e. GC = 46, f. GC= 46, g, h. GC = 65, i. GC = 66, j. GC = 78, k. GC = 87, l. GC = 132, m. GC = 141, n. GC = 153. We believe that it may be interesting to compare the evolutionary levels of some species and the GC of their respective nests.

Appendix B

The neighborhood of each agent comprises the 26 first cells surrounding the cell it occupies. We represented this neighborhood with 3 slices along the z direction (see Figure 9).

Below we give the rules (i.e. the whole set of local stimulating configurations) used to produce architectures 4d, 4e and 4n. When the ìwaspî occupies the central position of slice z (marqued ï), i.e. when there is no brick in that cell, it will put down a brick of type 1 in the case of configuration 1.x and a brick of type 2 in the cases 2.x. We give each local configuration without taking into account the symmetries due to rotations and reflections. In the case of architecture 4n (Chartergus) we distinguish the same succession of sub-shapes as in figure 5.

Architecture 4n

Step 1

Step 2

Step 3

Step 4

Step 5

Step 6

Step 7

Step 8

Step 9