How communication can improve the performance of multi-agent systems

ABSTRACT

We analyze a general model of multi-agent communication in which all agents learn to communicate simultaneously to a message board. We show that the communicating multi-agent system is equivalent to a Mealy finite state machine whose states are determined by the agents' usage of the learned language. Increasing the language size increases the number of possible states in the Mealy machine, and can improve the performance of the multi-agent system. We introduce the term {\em semantic density} to describe the average number of meanings assigned to each word of a language. Using semantic density, a simple rule is presented that provides a pessimistic estimate of the minimum language size that should be used for any multi-agent problem in which the agents communicate simultaneously. Simulations on a version of the predator-prey pursuit problem, a simplified version of problems seen in warfare scenarios, validate these predictions. The communicating predators evolved using a genetic algorithm perform significantly better than all previous work on similar preys.

REFERENCES

• 1: David H. Ackley and Michael L. Littman. Altruism in the evolution of communication. In Proceedings of Artificial Life IV . MIT Press, 1994.
• 2: Tucker Balch , Ronald C. Arkin, Communication in reactive multiagent robotic systems, Autonomous Robots, v.1 n.1, p.27-52, 1994 [doi>10.1007/BF00735341]
• 3: M. Benda, V. Jagannathan, and R. Dodhiawalla. On optimal cooperation of knowledge sources. Technical Report BCS-G2010-28, Boeing AI Center, Boeing Computer Services, Bellevue, WA, August 1985.
• 4: Piotr J. Gmytrasiewicz, Edmund H. Durfee, and Jeffrey Rosenschein. Toward rational communicative behavior. In AAAI Fall Symposium on Embodied Language. AAAI Press, November 1995.
• 5: D.E. Goldberg and K. Deb. A comparative analysis of selection schemes used in genetic algorithms. In Foundations of Genetic Algorithms, pages 69-93. 1991.
• 6: Koiti Hasida, Katashi Nagao, and Takashi Miyata. A game-theoretic account of collaboration in communication. In Proceedings of the First International Conference on Multi-Agent Systems (ICMAS), pages 140-147. MIT Press, 1995.
• 7: Thomas Haynes , Sandip Sen, Evolving Beharioral Strategies in Predators and Prey, Proceedings of the Workshop on Adaption and Learning in Multi-Agent Systems, p.113-126, August 21, 1995
• 8: Kenneth A. De Jong and William M. Spears. A formal analysis of the role of multi-point crossover in genetic algorithms. Annals of Mathematics and Artificial Intelligence Journal, 5(1):1-26, 1992.
• 9: Richard E. Korf. A simple solution to pursuit games. In Working Papers of the 11th International Workshop on Distributed Artificial Intelligence, pages 183-194, February 1992.
• 10: S. Luke and L. Spector. Evolving teamwork and coordination with genetic programming. In J.R. Koza, D.E. Goldberg, David B. Fogel, and Rick L. Riolo, editors, Proceedings of the First Annual Conference on Genetic Programming (GP-96), pages 150-156, Cambridge, MA, 1996. MIT Press.
• 11: Bruce J. MacLennan , Gordon M. Burghardt, Synthetic ethology and the evolution of cooperative communication, Adaptive Behavior, v.2 n.2, p.161-188, Fall 1993 [doi>10.1177/105971239300200203]
• 12: Gregory M. Saunders and Jordan B. Pollack. The evolution of communication schemes over continuous channels. In From Animals to Animats 4: Proceedings of the 4th International Conference on Simulation of Adaptive Behavior. MIT Press, 1996.
• 13: Luc Steels. Self-organizing vocabularies. In Proceedings of Alife V, 1996.
• 14: Larry M. Stephens and Matthias B. Merx. The effect of agent control strategy on the performance of a dai pursuit problem. In Proceedings of the 10th International Workshop on DAI, 1990.
• 15: Ming Tan. Multi-agent reinforcement learning: Independent vs. cooperative agents. In Proc. of 10th ICML, pages 330-337, 1993.
• 16: Adam Walker and Michael Wooldridge. Understanding the emergence of conventions in multi-agent systems. In Proceedings of 1st ICMAS, 1995.

INDEX TERMS

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

Additional Classification:
  H. Information Systems
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING

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

Keywords:
agent communication languages, evolution of agents, multi-agent communication/collaboration, multi-agent simulation