Global convergence of local agent behaviors

ABSTRACT

Many multi-agent systems seek to reconcile two apparently inconsistent constraints. The system has a global overall objective. However, the agents have only local information to guide their actions. Such systems are presently more art than science. They often exhibit regularities (such as exponential convergence) that we do not understand, and we do not know how to improve their functioning in a disciplined manner. In this paper, we develop a simple statistical model for such systems that can enhance both our intuitions about their functioning and our ability to engineer them, and apply it to three systems that we have constructed.

REFERENCES

• 1: Sven A. Brueckner , H. Van Dyke Parunak, Resource-aware exploration of the emergent dynamics of simulated systems, Proceedings of the second international joint conference on Autonomous agents and multiagent systems, July 14-18, 2003, Melbourne, Australia [doi>10.1145/860575.860701]
• 2: J. L. Deneubourg , S. Goss , N. Franks , A. Sendova-Franks , C. Detrain , L. Chrétien, The dynamics of collective sorting robot-like ants and ant-like robots, Proceedings of the first international conference on simulation of adaptive behavior on From animals to animats, p.356-363, February 1991, Paris, France
• 3: Fitzpatrick, S. and Meertens, L. Soft, Real-Time, Distributed Graph Coloring using Decentralized, Synchronous, Stochastic, Iterative-Repair, Anytime Algorithms: A Framework. KES. U.01.5., Kestrel Institute, 2001.
• 4: Goel, S. Three Approaches to Finite Markov Chains. Cornell University, Ithica, NY, 2004. <u>http://www.cam.cornell.edu/~sharad/papers/FMC.pdf.</u>
• 5: A. K. Jain , M. N. Murty , P. J. Flynn, Data clustering: a review, ACM Computing Surveys (CSUR), v.31 n.3, p.264-323, Sept. 1999 [doi>10.1145/331499.331504]
• 6: Kauffman, S. A. and Levin., S. Toward a general theory of adaptive walks on rugged landscapes. J. Theoret. Biol., 128:1987, 11--45.
• 7: Meertens, L. and Fitzpatrick, S. Peer-to-Peer Coordination of Autonomous Sensors in High-Latency Networks using Distributed Scheduling and Data Fusion. KES. U.01.09, Kestrel Institute, 2001.
• 8: Parunak, H. V. D., Brueckner, S., and Sauter, J. Digital Pheromones for Coordination of Unmanned Vehicles. In Proceedings of Workshop on Environments for Multi-Agent Systems (E4MAS 2004), Springer, 2004, (forthcoming).
• 9: Parunak, H. V. D., Brueckner, S. A., Matthews, R., and Sauter, J. Pheromone Learning for Self-Organizing Agents. IEEE SMC, 35, 3 (May): 2005, 316--326.
• 10: H. Van Dyke ParunaK , Sven Brueckner , John Sauter, Digital pheromone mechanisms for coordination of unmanned vehicles, Proceedings of the first international joint conference on Autonomous agents and multiagent systems: part 1, July 15-19, 2002, Bologna, Italy [doi>10.1145/544741.544843]
• 11: Parunak, H. V. D., Purcell, M., and O'Connell, R. Digital Pheromones for Autonomous Coordination of Swarming UAV's. In Proceedings of First AIAA Unmanned Aerospace Vehicles, Systems, Technologies, and Operations Conference, AIAA, 2002.
• 12: John A. Sauter , Robert Matthews , H. Van Dyke Parunak , Sven A. Brueckner, Performance of digital pheromones for swarming vehicle control, Proceedings of the fourth international joint conference on Autonomous agents and multiagent systems, July 25-29, 2005, The Netherlands [doi>10.1145/1082473.1082610]
• 13: Peter Weinstein , H. Van Parunak , Paul Chiusano , Sven Brueckner, Agents Swarming in Semantic Spaces to Corroborate Hypotheses, Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems, p.1488-189, July 19-23, 2004, New York, New York [doi>10.1109/AAMAS.2004.54]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.0 General

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

General Terms:
Experimentation, Performance, Theory

Keywords:
clustering, convergence, emergent behavior, graph coloring, vehicle routing