Introduction to stigmergy

A very good introduction to stigmergy is provided by Owen Holland and Chris Melhuish in an article entitled "Stigmergy, self-organisation, and sorting in collective robotics" submitted to the magazine "Artificial Life".

This is shown below, but it is interesting to read the full article because it expands upon the concept of stigmergy and goes on to describe the design of a robot system that demonstrates stigmergy in action.

Owen Holland and Chris Melhuish

Introduction: Stigmergy - by Owen Holland and Chris Melhuish

Stigmergy is a concept occasionally used in biology to describe the influence on behaviour of the persisting environmental effects of previous behaviour. It was originally proposed by Grasse [12] to explain some of his observations on termite building behaviour. Grasse had observed that worker termites in the presence of particular configurations of a construction (and of other workers) would be stimulated to a high degree of activity, and would tend to add building material to specific parts of the construction. As the construction was changed by these additions, the site of addition of further material would be modified, leading to the progressive growth and completion of the feature; the termites would then switch to constructing another such feature, or would begin a new task apparently triggered by the presence of the completed feature. The phrasing of his introduction of the term is worth noting:

"La coordination des taches, la regulation des constructions ne dependent pas directement des oeuvriers, mais des constructions elles-memes. L'ouvrier ne dirige pas son travail, il est guide par lui. C'est ˆ cette stimulation d'un type particulier que nous donnons le nom du STIGMERGIE ( stigma , piqure; ergon , travail, oeuvre = oeuvre stimulante)."

Translation:

["The coordination of tasks and the regulation of constructions does not depend directly on the workers, but on the constructions themselves. The worker does not direct his work, but is guided by it . It is to this special form of stimulation that we give the name STIGMERGY ( stigma , goad; ergon , work, product of labour = stimulating product of labour)."]

In the English summary, the concept is expressed more directly: "The stimulation of the workers by the very performances they have achieved is a significant one inducing accurate and adaptable response, and has been named stigmergy ."

2.

If stigmergy is indeed at the root of the building behaviour of termites, ants, bees, wasps, and other social insects, then it is certainly a powerful principle, as social insect constructions are remarkable for their complexity, size, and adaptive value. However, it is possible to extend the idea easily to other domains; it can then be seen as an even more impressive and general account of how simple systems can produce a wide range of apparently highly organised and coordinated behaviours and behavioural outcomes, simply by exploiting the influence of the environment. In Grasse's vision, a worker deposits a piece of building material (does 'work') in a particular location; this changes the sensory input subsequently obtained at that location, and hence may change the behaviour produced (and the work done) at that location in the future. If a drop of pheromone was deposited instead, it could also change the behaviour at that location in the future, at least until such time as it had completely evaporated. The laying and sensing of pheromones, especially in the form of chemical trails, underlies many of the spectacular abilities of ants, especially in the control of foraging, and is clearly an instance of Grasse's concept; the modern practice is to extend the definition of stigmergy by replacing the sense of 'work' with the sense of 'any environmental change produced by the animal'. (In fact the regulation of termite building behaviour is now understood to involve pheromones as well as constructional features.)

Although there have been several modern treatments of stigmergy as a general phenomenon, there is still room for more precision in its definition. For instance, Grasse's original sense of 'stimulation' should formally be refined. All that is necessary for stigmergy to occur is for the outcome of the behaviour of the relevant agent to be appropriately affected by previous environmental changes, and this can happen in a number of distinct ways:

(i) the agent's choice of action may be affected (a qualitative effect)

(ii) the selected action may be unchanged, but the exact position, strength, frequency, latency, duration, or any other parameter of the action may be affected (a quantitative effect)

(i) captures Grasse's sense of action being guided, and (ii) also includes the element of intensity of activity. The qualitative effect in (i) may of course be internally controlled by some threshold mechanism acting on a quantitatively varying input. However, there is also a third possibility which is not included in Grasse's formulation:

(iii) a previous action at a location might affect neither the choice nor the parameters of a subsequent action, but only the outcome (a qualitative and/or quantitative effect)

This requires some explanation. Consider a car being driven along a muddy track. Although the driver might try to steer a particular course, the wheels may settle into deep ruts which take the car along another course. The actions taken by previous drivers have affected the outcome of the actions taken by the present driver. (Incidentally, he will have further deepened the ruts, and will have a still harder time of it the next time.) This influence may be thought of as passive stigmergy [13] whereas (i) and (ii) may be thought of as active [13] in that they affect the agent itself. Passive stigmergy is very close to purely physical situations where some constantly acting force - often a fluid - changes the environment in such a way as to change its future effect on the environment; for example, the formation of sand dunes, river deltas, and meandering rivers are all instances of this.

We are now in a position to ask how stigmergy can actually produce complex patterns, whether of material or behaviours. Stigmergy is essentially a mechanism which allows an environment to structure itself through the activities of agents within the environment: the state of the environment, and the current distribution of agents within it, determine how the environment and the distribution of agents will change in the future. As has been made clear by Bonabeau et al [3], any structure emerging from this repeated interraction develops by a process of self-organisation (SO). (See also [7, 16]).

Bonabeau and his colleagues have provided a useful brief summary of the nature and properties of SO. They define and describe SO as "...a set of dynamical mechanisms where by structures appear at the global level of a system from interactions among its lower-level components. The rules specifying the interactions among the system's constituent units are executed on the basis of purely local information, without reference to the global pattern, which is an emergent property of the system rather than a property imposed upon the system by an external ordering influence."

They go on to identify four basic ingredients of SO, and three characteristic signatures. The ingredients are positive feedback, negative feedback, the amplification of fluctuations, and the presence of multiple interactions; the signatures are the creation of spatiotemporal structures in an initially homogeneous medium, the possible attainability of different stable states (multistability), and the existence of parametrically-determined bifurcations.

The mechanism of stigmergy, combined with environmental physics, provides the basic ingredients in social insects; the resultant SO produces outcomes which display the characteristic signatures. Stigmergic SO is distinguished from the purely physical SO mentioned in the last paragraph because it involves mobile agents. Agents can sense the local environment, and act on it, in ways determined by their physical and computational constituents. The possibilities for producing spatiotemporal structures both in the environment and in the distribution of agents within the environment are therefore infinitely greater than those arising directly from the environmental physics. It is this potential richness of behaviour-mediated changes which has been exploited by evolution to produce the striking phenomena found in social insect colonies; Bonabeau et al [3] have pointed out some of the possible ways in which evolution may favour the emergence of some aspects of self-organisation.

There are several other comments which may usefully be made about stigmergy, and which can increase our understanding. One approach to stigmergy is simply to consider the minimal qualities of agent and environment which are necessary to support it. An agent has two key abilities: it can move through the environment, and it can act on the environment. The environment must be able to be changed locally by agents; and such changes must persist long enough to affect the choice, parameters, or consequences of agents' behaviour. (This effectively rules out stigmergy in empty or highly dynamic environments, such as space, air, and water.) Change can be reduced to a small number of categories: material can be taken from the environment, or added to it, or some local quality of the environment can be altered. The scope of stigmergy is thus defined: the three types of environmental change may produce the three types of stigmergic action on the two agent abilities. It should be clear that some form of stigmergy must inevitably be in operation in many biological systems, and can be expected to occur in many artificial systems when they are widely deployed in the real world. However, only those instances of stigmergy which give rise to SO will produce noticeable or useful effects.

Some additional clues to the origins and underlying principles of stigmergy can be gathered from the observation that, as Grasse pointed out in his original paper [12], there are two ways of structuring the generation of behavioural sequences in insects (and, by extension, in simple agents of any type). In the first, found in solitary species such as the digger wasp, the execution of the first movement in a sequence sets some internal state which then, often in conjunction with some appropriate external cue, initiates the second movement, and so on. In the second, found in both solitary and social insects, there is no such internal state; the external cue alone is sufficient. The second method often requires that the external cue is correlated with the successful completion of the first movement.

This second strategy is more appropriate for social insects, for many reasons; more importantly, it sets the scene for stigmergy. Because there are many identical agents available, there is no longer any requirement that a connected sequence of movements (or sub-tasks making up a task) must be carried out by a single agent. The presence of the cues alone will ensure that a complete sequence is executed, even if each movement is performed by a different agent. (Where there is no suitable cue available from the end- state of the sub-task itself, it may be necessary to augment the sub-task to provide some additional external cue, or sign.) In particular, where there are many similar cues for a certain sub-task at a given location, the rate of performance of the sub-task will be a function of the number of agents at that location. (This would not necessarily be the case if an agent had to be in a particular internal state in order to be able to respond to the cue.) If there are many locations with such cues, the sub-task will be performed fastest at the locations which have the greatest numbers of agents present. Stigmergy can thus control the morphogenetic development of a construction or other spatial pattern by controlling the distribution of agents within the environment rather than just by controlling the elicitation of building actions at particular sites.