stigmergy

Stigmergy is one method of self-organization in a system. It is defined as a method whereby one member of the system changes their local environment, and then another member visits the environment, identifies the changes, and then changes their local environment in response. Eventually, the entire environment is changed by these series of changes in the local environment.

Coined by French biologist Pierre-Paul Grasse in the 1950s, stigmergy is an extension of swarm theory and finds its roots in the customs of eusocial colony insects such as ants and termites.

The primary example of stigmergy is the ant march:

1. A portion of food is dropped.
2. An ant finds the food. Upon returning with the food to the nest, it leaves a pheromone trail from the food to home.
3. Other ants detect the pheromones and follow the trail.
4. Some ants don't detect the trail, but find alternate paths to the food. If this trail is faster, they will create more pheromone trails in the same amount of time; thus their trail will be stronger, and ants will be more attracted to this shorter, faster trail.
5. Eventually, the shortest trail is discovered, and all future ants rely on this trail to the food. Thus, though the ants do not act communally, they respond to the collective results of their individual brethren. Pure stigmergy.

Other examples of this include ant corpse-piling (they prefer larger piles to smaller piles, and thus all small corpse piles eventually are combined into one large corpse pile through stigmergy) and termite nest construction practices (where individual termites attach pheromones to bits of mud to encourage similar placement of arches, chambers, and tunnels.)

The Internet is a major source of human stigmergy through the spread of memes, blog trackbacks, and an ever-increasing information/news cycle. Everything2 has elements of stigmergy within it, such as voting (through which better writeups are identified and receive more votes) and the ability for writers to use a single node title to write multiple varying pieces (feeding off each other's individual efforts to create a collectively holistic work at a given node.)

How do they do it?

Have you ever watched ants going about their busy lives and wondered how they managed to accomplish really smart tasks like locating food, finding the shortest path from the food to the nest, cooperating to carry objects that are too large for one ant to handle, or working together to collect their scattered dead comrades and pile them onto a few large heaps? Or have you ever looked at a wasp nest and wondered how a bunch of really dumb wasps can cooperate to build such a complex and intricate structure without any direct communication with their fellows and without any architect or boss wasp telling them what to do according to some master plan? Could people even do that?

Stigmergy is a concept that helps demystify these and other such wonders of nature. Simply put, it means that an agent, an ant for example, does something to change its environment, and that change in turn alters the behavior of other agents (ants) and even the subsequent behavior of the agent itself. Recently, this concept has been rediscovered and extended as a potentially useful technique for routing in communication networks, artificial intelligence, robotics, and various problems in the social sciences. In particular, it is fundamental to the concept of swarm intelligence.

Stigmergy was first proposed by zoologist Pierre-Paul Grasse in 1959 to explain how termites are able build their nests. He showed how the changes that the termites make in their environment as they construct their nests trigger different building behaviors in the termites themselves. Thus, the actions of the individual termites are actually determined by the physical thing that they are making as it takes shape over time. This concept can be generalized to mean the various mechanisms by which active agents can affect the actions of other agents within a system indirectly by changing the environment that the agents share, rather than by direct, intelligent communication between agents. In this generalized concept, the agents might be mobile software agents or software 'bots operating within a network, nanobots, construction or exploration robots operating on a distant moon or planet, or even writers operating in an collaborative environment.

Example

OK, that's maybe a little too abstract to grasp clearly, so let's see how it actually works by looking at one of the simplest examples: ant foraging. The problem for the ant colony is to search the area around the nest for a food source, determine the path of shortest distance between nest and food, and get all the workers to follow that path and bring the food back to the nest.

Now, the ants cannot talk it over and agree on a strategy in advance. Nor can they communicate with each other directly during the mission, and say, for example, "Hey, girls! I've found this 12-ounce tub of Haagen Daz that one of those two-legged giant things dropped in the grass!" and then proceed to give directions to find the treat. The only thing they can do is to leave a pheromone trail where they walk. An ant that comes across a pheromene trail is likely to follow it. The stronger the trail, the more likely it will be followed. (A trail is stronger if it is more recent or if it has been traveled by more ants.)

The workers all start out from the nest at different times and explore the area independently and randomly. Some of them will end up back at the nest before finding anything, and then start out again. Sooner or later, some of the ants will find a food source. (Let's say that there is only one in our example.) Thereupon, they will return to the nest, following their own pheromone trail. The ant that happened to find the shortest path to the food will return to the nest soonest, leaving a trail that has a double dose of pheromone. Her trail will then be the most likely followed by the ants that leave the nest after her return, while the longer paths of the other ants will be less likely followed. We can see that very soon, with more and more ants reinforcing the pheromone trail along the shortest path, nearly all of the ants will be following the shortest path and bringing back the food.

Problem solved. The individual ants haven't a clue; they are non-intelligent robots. Together as a colony, however, they exhibit a kind of intelligent behavior by simply following a few very elementary rules. What is sometimes called swarm intelligence is an effect of stigmergy.

---

Note: Concerning the ant's ability to return to its nest, more recent research has shown that ants are equipped with sophisticated mechanisms, such as for sensing sun position and measuring distance traveled, that allow them to return to the nest by the most direct route without having to follow trails. An ant picked up from a place distant from the nest and placed elsewhere will return to a place that is the same distance and in the same direction away from the new location as is the nest from the original location. The example given here still works to illustrate the idea of stigmergy, though.