Entropy and self-organization in multi-agent systems

ABSTRACT

Emergent self-organization in multi-agent systems appears to contradict the second law of thermodynamics. This paradox has been explained in terms of a coupling between the macro level that hosts self-organization (and an apparent reduction in entropy), and the micro level (where random processes greatly increase entropy). Metaphorically, the micro level serves as an entropy “sink”, permitting overall system entropy to increase while sequestering this increase from the interactions where selforganization is desired. We make this metaphor precise by constructing a simple example of pheromone-based coordination, defining a way to measure the Shannon entropy at the macro (agent) and micro (pheromone) levels, and exhibiting an entropybased view of the coordination.

REFERENCES

• 1: Eric Bonabeau , Marco Dorigo , Guy Theraulaz, Swarm intelligence: from natural to artificial systems, Oxford University Press, Inc., New York, NY, 1999
• 2: S. Brueckner. Return from the Ant: Synthetic Ecosystems for Manufacturing Control. Thesis at Humboldt University Berlin, Department of Computer Science, 2000.
• 3: E. Fredkin. Finite Nature. In Proceedings of The XXVIIth Recontre de Moriond, 1992.
• 4: P.-P. Grasse. La Reconstruction du nid et les Coordinations Inter-Individuelles chez Bellicositermes Natalensis et Cubitermes sp. La theorie de la Stigmergie: Essai d'interpretation du Comportement des Termites Constructeurs. Insectes Sociaux, 6:41-80, 1959.
• 5: H. A. Gutowitz. Complexity-Seeking Ants. In Proceedings of Third European Conference on Artifical Life, 1993.
• 6: B. Hayes. Computational Creationism. American Scientist, 87(5):392-396, 1999.
• 7: P. N. Kugler and M. T. Turvey. Information, Natural Law, and the Self-Assembly of Rhythmic Movement. Lawrence Erlbaum, 1987.
• 8: F. L. Lambert. Shuffled Cards, Messy Desks, and Disorderly Dorm Rooms - Examples of Entropy Increase? Nonsense! Journal of Chemical Education, 76:1385, 1999.
• 9: F. L. Lambert. The Second Law of Thermodynamics. 2000. Web Page, http://www.secondlaw.com/.
• 10: J. Lukkarinen. Re: continuing on Entropy. 2000. Email Archive, http://necsi.org:8100/Lists/complex-science/ Message/2236.html.
• 11: V. D. Parunak. 'Go to the Ant': Engineering Principles from Natural Agent Systems. Annals of Operations Research, 75:69-101, 1997.
• 12: H. Van Dyke Parunak , Sven Brueckner, Ant-like missionaries and cannibals: synthetic pheromones for distributed motion control, Proceedings of the fourth international conference on Autonomous agents, p.467-474, June 03-07, 2000, Barcelona, Spain [doi>10.1145/336595.337572]
• 13: Peeters, P. Valckenaers, J. Wyns, and S. Brueckner. Manufacturing Control Algorithm and Architecture. In Proceedings of Second International Workshop on Intelligent Manufacturing Systems, pages 877-888, K.U. Leuven, 1999.
• 14: Claude E. Shannon , Warren Weaver, A Mathematical Theory of Communication, University of Illinois Press, Champaign, IL, 1963
• 15: ithsonian Institution. Encyclopedia Smithsonian: Pheromones in Insects. 1999. Web Page, http://www.si.edu/resource/faq/nmnh/buginfo/pheromones.ht m.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence
            Subjects: Multiagent systems

Additional Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING

General Terms:
Design, Experimentation, Measurement, Performance, Theory

Keywords:
entropy, pheromones, self-organization