The concept of stigmergy was proposed by the French entomologist Pierre-Paul Grassé (Grassé, 1959) to describe a mechanism of coordination used by insects. The principle is that work performed by an agent leaves a trace in the environment that stimulates the performance of subsequent work—by the same or other agents. This mediation via the environment ensures that tasks are executed in the right order, without any need for planning, control, or direct interaction between the agents. The notion of stigmergy allowed Grassé to solve the “coordination paradox” (Theraulaz and Bonabeau, 1999), i.e. the question of how insects of very limited intelligence, without apparent communication, manage to collaboratively tackle complex projects, such as building a nest.
The insight came from Grassé’s observation of how termites repair their nest. He noted that initially termites wander around more or less randomly, carrying mud and depositing it here or there. However, the deposits that are created in this haphazard way then stimulate the insects to add more mud in the same place. Thus, the small heaps quickly grow into columns that eventually come together to form an intricate cathedral of interlocking arches. The only communication between the termites is indirect: the partially executed work of the ones provides information to the others about where to make their own contribution.
Another classic example of stigmergy can be found in the pheromone trails left by ants that come back from a food source (Sumpter and Beekman, 2003). The pheromone stimulates other ants to follow the same path. When they find food, they too will reinforce the pheromone trail while following the trail back to the nest. This mechanism leads to the emergence of an efficient network of trails connecting the nest via the shortest routes to all the major food sources.
Up to about 1990, the notion of stigmergy appears to have remained limited to a small circle of researchers studying the behavior of social insects. However, one of these insect specialists, Jean-Louis Deneubourg, was also a member of the “Brussels School” of complex systems, headed by the late Nobel Prize in chemistry, Ilya Prigogine. In this interdisciplinary environment, it became clear that stigmergy was a prime example of spontaneous ordering or self-organization (Camazine et al., 2003; Deneubourg, 1977) and as such potentially applicable to complex systems other than insect societies.
With the advent of the agent-based paradigm in computer simulation, insect societies were conceptualized as swarms of simple agents that are able to perform complex tasks using various forms of self-organization and especially stigmergy (Deneubourg, Theraulaz and Beckers, 1992). The general ability to tackle complex problems exhibited by such self-organizing multi-agent collectives became known as swarm intelligence (Bonabeau, Dorigo and Theraulaz, 1999; Kennedy, 2006). One class of stigmergic mechanisms in particular, so-called ant algorithms, turned out to be surprisingly powerful in tackling a variety of computational problems, including the notorious traveling salesman problem (Dorigo, Bonabeau and Theraulaz, 2000) and the optimization of packet routing along communication networks (Kassabalidis et al., 2001).