Cogprints

Talking Helps: Evolving Communicating Agents for the Predator-Prey Pursuit Problem

Jim, Kam-Chuen and Giles, Lee (2000) Talking Helps: Evolving Communicating Agents for the Predator-Prey Pursuit Problem. [Journal (On-line/Unpaginated)]

Full text available as:

[img]
Preview
PDF
1494Kb

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.

Item Type:Journal (On-line/Unpaginated)
Keywords:multi-agent systems predator prey communication
Subjects:Computer Science > Language
Computer Science > Machine Learning
Computer Science > Artificial Intelligence
ID Code:2686
Deposited By:Jim, Kam-Chuen
Deposited On:03 Jan 2003
Last Modified:11 Mar 2011 08:55

References in Article

Select the SEEK icon to attempt to find the referenced article. If it does not appear to be in cogprints you will be forwarded to the paracite service. Poorly formated references will probably not work.

[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.

Metadata

Repository Staff Only: item control page