creators_name: Jim, Kam-Chuen creators_name: Giles, Lee type: journale datestamp: 2003-01-03 lastmod: 2011-03-11 08:55:07 metadata_visibility: show title: Talking Helps: Evolving Communicating Agents for the Predator-Prey Pursuit Problem ispublished: pub subjects: comp-sci-lang subjects: comp-sci-mach-learn subjects: comp-sci-art-intel full_text_status: public keywords: multi-agent systems predator prey communication abstract: We analyze a general model of multi-agent communication in which all agents communicate simultaneously to a message board. A genetic algorithm is used to evolve multi-agent languages for the predator agents in a version of the predator-prey pursuit problem. We show that the resulting behavior of the communicating multi-agent system is equivalent to that of a Mealy finite state machine whose states are determined by the agents’ usage of the evolved language. Simulations show that the evolution of a communication language improves the performance of the predators. Increasing the language size (and thus increasing the number of possible states in the Mealy machine) improves the performance even further. Furthermore, the evolved communicating predators perform significantly better than all previous work on similar preys. We introduce a method for incrementally increasing the language size which results in an effective coarse-to-fine search that significantly reduces the evolution time required to find a solution. We present some observations on the effects of language size, experimental setup, and prey difficulty on the evolved Mealy machines. In particular, we observe that the start state is often revisited, and incrementally increasing the language size results in smaller Mealy machines. Finally, a simple rule is derived that provides a pessimistic estimate on the minimum language size that should be used for any multi-agent problem. date: 2000 date_type: published publication: Artificial Life volume: 6 number: 3 publisher: MIT Press refereed: TRUE referencetext: [1] David H. Ackley and Michael L. Littman. Altruism in the evolution of communication. In Rodney A. Brooks and Pattie Maes, editors, Artifi- cial Life IV: Proceedings of the International Workshop on the Synthesis and Simulation of Living Systems. MIT Press, November 1994. [2] Tucker Balch and Ronald C. Arkin. Communication in reactive multiagent robotic systems. Autonomous Robots, 1(1):27–52, 1994. [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] R.A. Brooks. Challenges for complete creature architectures. In J.A. Meyer and S.W. Wilson, editors, From Animals to Animats: Proceedings of the First International Conference on Simulation of Adaptive Behavior, pages 434–443. MIT Press, 1991. [5] www.dictionary.com. [6] Piotr J. Gmytrasiewicz and Edmund H. Durfee. A rigorous, operational formalization of recursive modeling. In Victor Lesser, editor, Proceedings of the First International Conference on Multi–Agent Systems (ICMAS), pages 125–132, San Francisco, CA, 1995. MIT Press. [7] Piotr J. Gmytrasiewicz, Edmund H. Durfee, and Jeffrey Rosenschein. Toward rational communicative behavior. In AAAI Fall Symposium on Embodied Language. AAAI Press, November 1995. [8] 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. [9] Kˆ oiti Hasida, Katashi Nagao, and Takashi Miyata. A game-theoretic account of collaboration in communication. In Victor Lesser, editor, Proceedings of the First International Conference on Multi–Agent Systems (ICMAS), pages 140–147, San Francisco, CA, 1995. MIT Press. [10] Thomas Haynes and Sandip Sen. Evolving behavioral strategies in predator and prey. IJCAI-95 Workshop on Adaptation and Learning in Multiagent Systems, August 1995. 25 [11] 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. [12] Richard E. Korf. A simple solution to pursuit games. InWorking Papers of the 11th InternationalWorkshop on Distributed Artificial Intelligence, pages 183–194, February 1992. [13] Yannis Labrou and Tim Finin. A semantics approach for kqml - a general purpose communication language for software agents. In Proc. Int. Conf on Information and Knowledge Management, 1994. [14] Bruce J. MacLennan and Gordon M. Burghardt. Synthetic ethology and the evolution of cooperative communication. Adaptive Behavior, 2(2):161–188, 1993. [15] Shin I. Nishimura and Takashi Ikegami. Emergence of collective strategies in a prey-predator game model. Artificial Life, 3(4):243–260, 1997. [16] Stefano Nolfi and Dario Floreano. Coevolving predator and prey robots: Do ”arms races” arise in artificial evolution? Artificial Life, 4(4):337–357, 1998. [17] Gregory M. Saunders and Jordan B. Pollack. The evolution of communication schemes over continuous channels. In P. Maes, M. Mataric, J.A. Meyer, and J.B. Pollack, editors, From Animals to Animats 4: Proceedings of the 4th International Conference on Simulation of Adaptive Behavior. MIT Press, 1996. [18] Nicholas J. Savill and Paulien Hogeweg. Evolutionary stagnation due to pattern-pattern interactions in a coevolutionary predator-prey model. Artificial Life, 3(2):81–100, 1997. [19] John R. Searle. Speech Acts: An Essay in the Philosophy of Language. Cambridge U. Press, 1970. [20] Luc Steels. Self-organizing vocabularies. In Proceedings of Alife V, 1996. [21] 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. 26 [22] Ming Tan. Multi-agent reinforcement learning: Independent vs. cooperative agents. In Proc. of 10th ICML, pages 330–337, 1993. [23] AdamWalker and MichaelWooldridge. Understanding the emergence of conventions in multi-agent systems. In Proceedings of the First International Conference on Multi-Agent Systems, San Francisco, CA, June 1995. citation: Jim, Kam-Chuen and Giles, Lee (2000) Talking Helps: Evolving Communicating Agents for the Predator-Prey Pursuit Problem. [Journal (On-line/Unpaginated)] document_url: http://cogprints.org/2686/1/evolveCommALife2000.pdf