Difference between revisions of "Stigmergy"

Revision as of 19:30, 29 July 2010

Presented by Francis Heylighen

Concept

The work of the agent(s) leaves a trace that is registered in the medium, where it is perceivable by other agents, stimulating them to further improve or extend the work that needs to be done. This is feedback cycle is mostly positive: more work being done leads to more further work being done. The feedback can be negative when an agent corrects or removes a mistake made by previous agent.

Important dimensions of stigmergy

• Lifetime/ Evaporation: how long does the trace last in the absence of further work?

Evaporation rate must be higher if valid information lifetime is short.

• • defined evaporation for ant foraging: food sources get quickly exhausted, and therefore the pheromone trace becomes outdated -> pheromones must evaporate quickly
  • no evaporation for SO encyclopedia: most articles have indefinite lifetime once they are "mature".
  • in-between applications might exist - eg. idea of newssystem where older information evaporates (so as not to overflow the front page). Notion of Frecency - recently and most frequently accessed articles.

• Qualitative versus quantitative stigmergy
  • links in Wikipedia to non-exisiting articles

• Number of agents
  • in principle one agent is enough
  • reactive agents without own memory use stigmergy/medium as memory, eg. wasp nest building

• Medium
  • Local versus global memory
  • transient vs. (semi-)permanent

• Updating of data in the medium
  • Evaporation - runs always; normally time-dependent
  • Changes made by agents - eg. changes made to pheromones by backward ant in ant routing algos

• Evaporation
  • is necessary key element.
  • Soft state - if you don't refresh it will evaporate. Analogous to router timeouts in the internet
  • highly dynamic scenarios need higher evaporation rates

• Shortcomings of stigmergy
  • Delay, timeliness not guaranteed. Can be reduced by increasing number of agents

• Where does Stigmergy work well and where not?
  • Medium: You need a medium that is sufficiently stable (cannot use air as medium)
  • Medium: Medium must be accessible by all agents
  • Asynchronous nature (can also be an advantage) - you don't know when the next agent will come along - delay - timeliness not guaranteed
  • Anonymous communication - you don't know who the next agent is - implies a certain homogeneity of agents (one agent as good as the next eg. as in ants) or self-selection of agents (eg. only a person who thinks they are qualified will edit a Wikipedia article)
  • Reliability
  • Evaporation rate may limit scenarios - highly dynamic scenarios would need extremely high evaporation rate. Maybe for these scenarios another approach (eg. swarming) would be better
  • A list of applications would be needed

• Some examples
  • Firebrigade with answering machine (=stigmergy) = bad idea
  • Police cars traveling around and responding to nearest emergency - can work