Stigmergy
Encyclopedia
Stigmergy is a mechanism of indirect coordination
between agents or actions. The principle is that the trace left in the environment
by an action stimulates the performance of a next action, by the same or a different agent. In that way, subsequent actions tend to reinforce and build on each other, leading to the spontaneous emergence of coherent, apparently systematic activity.
Stigmergy is a form of self-organization
. It produces complex, seemingly intelligent structures, without need for any planning, control, or even direct communication between the agents. As such it supports efficient collaboration between extremely simple agents, who lack any memory, intelligence or even individual awareness of each other.
s exchange information by laying down pheromone
s (the trace) on their way back to the nest when they have found food. In that way, they collectively develop a complex network of trails, connecting the nest in the most efficient way to the different food sources. When ants come out of the nest searching for food, they are stimulated by the pheromone to follow the trail towards the food source. The network of trails functions as a shared external memory for the ant colony. In computer science, this general method has been applied in a variety of techniques called ant colony optimization
, which search for solutions to complex problems by depositing "virtual pheromones" along paths that appear promising.
Other eusocial creatures, such as termites, use pheromones to build their complex nests by following a simple decentralized rule set. Each insect scoops up a 'mudball' or similar material from its environment, invests the ball with pheromones, and deposits it on the ground, initially in a random spot. However, termites are attracted to their nestmates' pheromones and are therefore more likely to drop their own mudballs on top of their neighbors'. The larger the heap of mud becomes, the more attractive it is, and therefore the more mud will be added to it (positive feedback). Over time this leads to the construction of pillars, arches, tunnels and chambers.
in 1959 to refer to termite behavior. He defined it as: "Stimulation of workers by the performance they have achieved." It is derived from the Greek words στίγμα stigma "mark, sign" and ἔργον ergon "work, action", and captures the notion that an agent’s actions leave signs in the environment, signs that it and other agents sense and that determine and incite their subsequent actions.
Later on, a distinction was made between the stigmergic phenomenon, which is specific to the guidance of additional work, and the more general, non-work specific incitation, for which the term sematectonic communication was coined by E. O. Wilson
, from the Greek words σῆμα sema "sign, token", and τέκτων tecton "craftsman, builder": "There is a need for a more general, somewhat less clumsy expression to denote the evocation of any form of behavior or physiological change by the evidences of work performed by other animals, including the special case of the guidance of additional work."
Stigmergy is now one of the key concepts in the field of swarm intelligence
.
there are many collective projects where users interact only by modifying local parts of their shared virtual environment. Wikipedia
is an example of this. The massive structure of information available in a wiki
, or an open source software project such as the FreeBSD kernel could be compared to a termite
nest; one initial user leaves a seed of an idea (a mudball) which attracts other users who then build upon and modify this initial concept, eventually constructing an elaborate structure of connected thoughts.
The term is also employed in experimental research in robotics
, multi-agent
systems and communication in computer networks.
In these fields there exist two types of stigmergy: active and passive. The first kind occurs when a robotic or otherwise intelligent "agent" alters its environment so as to affect the sensory input of another agent. The second occurs when an agent's action alters its environment such that the environmental changes made by a different agent are also modified. A typical example of active stigmergy is leaving behind artifacts for others to pick up or follow. An example of passive stigmergy is when one agent tries to remove all artifacts from a container, while another agent tries to fill the container completely.
In addition the concept of stigmergy has also been used to describe how cooperative work such as building design may be integrated. Designing a large contemporary building involves a large and diverse network of actors (e.g. architects, building engineers, static engineers, building services engineers and etc.). Their distributed activities may be partly integrated through practices of stigmergy.
Coordination
Coordination is the act of coordinating, making different people or things work together for a goal or effect to fulfill desired goals in an organization.Coordination is a managerial function in which different activities of the business are properly adjusted and interlinked.Coordination may also...
between agents or actions. The principle is that the trace left in the environment
Natural environment
The natural environment encompasses all living and non-living things occurring naturally on Earth or some region thereof. It is an environment that encompasses the interaction of all living species....
by an action stimulates the performance of a next action, by the same or a different agent. In that way, subsequent actions tend to reinforce and build on each other, leading to the spontaneous emergence of coherent, apparently systematic activity.
Stigmergy is a form of self-organization
Self-organization
Self-organization is the process where a structure or pattern appears in a system without a central authority or external element imposing it through planning...
. It produces complex, seemingly intelligent structures, without need for any planning, control, or even direct communication between the agents. As such it supports efficient collaboration between extremely simple agents, who lack any memory, intelligence or even individual awareness of each other.
Stigmergic behavior in insects
Stigmergy was first observed in social insects. For example, antAnt
Ants are social insects of the family Formicidae and, along with the related wasps and bees, belong to the order Hymenoptera. Ants evolved from wasp-like ancestors in the mid-Cretaceous period between 110 and 130 million years ago and diversified after the rise of flowering plants. More than...
s exchange information by laying down pheromone
Pheromone
A pheromone is a secreted or excreted chemical factor that triggers a social response in members of the same species. Pheromones are chemicals capable of acting outside the body of the secreting individual to impact the behavior of the receiving individual...
s (the trace) on their way back to the nest when they have found food. In that way, they collectively develop a complex network of trails, connecting the nest in the most efficient way to the different food sources. When ants come out of the nest searching for food, they are stimulated by the pheromone to follow the trail towards the food source. The network of trails functions as a shared external memory for the ant colony. In computer science, this general method has been applied in a variety of techniques called ant colony optimization
Ant colony optimization
In computer science and operations research, the ant colony optimization algorithm ' is a probabilistic technique for solving computational problems which can be reduced to finding good paths through graphs....
, which search for solutions to complex problems by depositing "virtual pheromones" along paths that appear promising.
Other eusocial creatures, such as termites, use pheromones to build their complex nests by following a simple decentralized rule set. Each insect scoops up a 'mudball' or similar material from its environment, invests the ball with pheromones, and deposits it on the ground, initially in a random spot. However, termites are attracted to their nestmates' pheromones and are therefore more likely to drop their own mudballs on top of their neighbors'. The larger the heap of mud becomes, the more attractive it is, and therefore the more mud will be added to it (positive feedback). Over time this leads to the construction of pillars, arches, tunnels and chambers.
History
The term "stigmergy" was introduced by French biologist Pierre-Paul GrasséPierre-Paul Grassé
Pierre-Paul Grassé, born on November 27, 1895 in Périgueux and died on July 9, 1985, was a French zoologist, author of over 300 publications including the influential 35-volume Traité de Zoologie. He was an expert on termites.- Studies :...
in 1959 to refer to termite behavior. He defined it as: "Stimulation of workers by the performance they have achieved." It is derived from the Greek words στίγμα stigma "mark, sign" and ἔργον ergon "work, action", and captures the notion that an agent’s actions leave signs in the environment, signs that it and other agents sense and that determine and incite their subsequent actions.
Later on, a distinction was made between the stigmergic phenomenon, which is specific to the guidance of additional work, and the more general, non-work specific incitation, for which the term sematectonic communication was coined by E. O. Wilson
E. O. Wilson
Edward Osborne Wilson is an American biologist, researcher , theorist , naturalist and author. His biological specialty is myrmecology, the study of ants....
, from the Greek words σῆμα sema "sign, token", and τέκτων tecton "craftsman, builder": "There is a need for a more general, somewhat less clumsy expression to denote the evocation of any form of behavior or physiological change by the evidences of work performed by other animals, including the special case of the guidance of additional work."
Stigmergy is now one of the key concepts in the field of swarm intelligence
Swarm intelligence
Swarm intelligence is the collective behaviour of decentralized, self-organized systems, natural or artificial. The concept is employed in work on artificial intelligence...
.
Applications
Stigmergy is not restricted to eusocial creatures, or even to physical systems. On the InternetInternet
The Internet is a global system of interconnected computer networks that use the standard Internet protocol suite to serve billions of users worldwide...
there are many collective projects where users interact only by modifying local parts of their shared virtual environment. Wikipedia
Wikipedia
Wikipedia is a free, web-based, collaborative, multilingual encyclopedia project supported by the non-profit Wikimedia Foundation. Its 20 million articles have been written collaboratively by volunteers around the world. Almost all of its articles can be edited by anyone with access to the site,...
is an example of this. The massive structure of information available in a wiki
Wiki
A wiki is a website that allows the creation and editing of any number of interlinked web pages via a web browser using a simplified markup language or a WYSIWYG text editor. Wikis are typically powered by wiki software and are often used collaboratively by multiple users. Examples include...
, or an open source software project such as the FreeBSD kernel could be compared to a termite
Termite
Termites are a group of eusocial insects that, until recently, were classified at the taxonomic rank of order Isoptera , but are now accepted as the epifamily Termitoidae, of the cockroach order Blattodea...
nest; one initial user leaves a seed of an idea (a mudball) which attracts other users who then build upon and modify this initial concept, eventually constructing an elaborate structure of connected thoughts.
The term is also employed in experimental research in robotics
Robotics
Robotics is the branch of technology that deals with the design, construction, operation, structural disposition, manufacture and application of robots...
, multi-agent
Intelligent agent
In artificial intelligence, an intelligent agent is an autonomous entity which observes through sensors and acts upon an environment using actuators and directs its activity towards achieving goals . Intelligent agents may also learn or use knowledge to achieve their goals...
systems and communication in computer networks.
In these fields there exist two types of stigmergy: active and passive. The first kind occurs when a robotic or otherwise intelligent "agent" alters its environment so as to affect the sensory input of another agent. The second occurs when an agent's action alters its environment such that the environmental changes made by a different agent are also modified. A typical example of active stigmergy is leaving behind artifacts for others to pick up or follow. An example of passive stigmergy is when one agent tries to remove all artifacts from a container, while another agent tries to fill the container completely.
In addition the concept of stigmergy has also been used to describe how cooperative work such as building design may be integrated. Designing a large contemporary building involves a large and diverse network of actors (e.g. architects, building engineers, static engineers, building services engineers and etc.). Their distributed activities may be partly integrated through practices of stigmergy.
External links
- Special issue on Stigmergy at Artificial Life Journal, Eric Bonabeau (Eds.), MIT Press, Vol. 5, No. 2, Spring 1999.
- Stigmergic Collaboration: The Evolution of Group Work (peer-reviewed & published article)
- Stigmergy papers published on scientific commons (a growing list of published articles)
- wiki version at MetaCollab.net