Evolving Multiagent Coordination Strategies with Genetic Programming   [GP]

by

Haynes, T., Sen, S., Schoenefeld, D. and Wainwright, R.

Literature search on Evolutionary ComputationBBase ©1999-2013, Rasmus K. Ursem
     Home · Search · Adv. search · Authors · Login · Add entries   Webmaster
Note to authors: Please submit your bibliography and contact information - online papers are more frequently cited.

Info: 1995
Keywords:genetic algorithms, genetic programming
Abstract:
The design and development of behavioral strategies to coordinate the actions of multiple agents is a central issue in multiagent systems research. [MS] We propose a novel approach of evolving, rather than handcrafting, behavioral strategies. The evolution scheme used is a variant of the Genetic Programming (GP) paradigm. [GP] As a proof of principle, we evolve behavioral strategies in the predator-prey domain that has been studied widely in the Distributed Artificial Intelligence [AI] community. We use the GP to evolve behavioral strategies for individual agents, as prior literature claims that communication between predators is not necessary for successfully capturing the prey. The evolved strategy, when used by each predator, performs better than all but one of the handcrafted strategies mentioned in literature. We analyze the shortcomings of each of these strategies. The next set of experiments involve co-evolving predators and prey. To our surprise, a simple prey strategy evolves that consistently evades all of the predator strategies. We analyze the implications of the relative successes of evolution in the two sets of experiments and comment on the nature of domains for which GP based evolution is a viable mechanism for generating coordination strategies. We conclude with our design for concurrent evolution of multiple agent strategies in domains where agents need to communicate with each other to successfully solve a common problem.
Notes:
URL(s):Postscript
(G)zipped postscript

Review item:

Mark as doublet (will be reviewed)

Print entry



BibTex:
@TechReport{Haynes:1995:EMC,
  author =       "Thomas Haynes and Sandip Sen and Dale Schoenefeld and
                 Roger Wainwright",
  title =        "Evolving Multiagent Coordination Strategies with
                 Genetic Programming",
  number =       "UTULSA-MCS-95-04",
  institution =  "The University of Tulsa",
  year =         "1995",
  month =        may # " 31,",
  keywords =     "genetic algorithms, genetic programming",
  abstract =     "The design and development of behavioral strategies to
                 coordinate the actions of multiple agents is a central
                 issue in multiagent systems research. We propose a
                 novel approach of evolving, rather than handcrafting,
                 behavioral strategies. The evolution scheme used is a
                 variant of the Genetic Programming (GP) paradigm. As a
                 proof of principle, we evolve behavioral strategies in
                 the predator-prey domain that has been studied widely
                 in the Distributed Artificial Intelligence community.
                 We use the GP to evolve behavioral strategies for
                 individual agents, as prior literature claims that
                 communication between predators is not necessary for
                 successfully capturing the prey. The evolved strategy,
                 when used by each predator, performs better than all
                 but one of the handcrafted strategies mentioned in
                 literature. We analyze the shortcomings of each of
                 these strategies. The next set of experiments involve
                 co-evolving predators and prey. To our surprise, a
                 simple prey strategy evolves that consistently evades
                 all of the predator strategies. We analyze the
                 implications of the relative successes of evolution in
                 the two sets of experiments and comment on the nature
                 of domains for which GP based evolution is a viable
                 mechanism for generating coordination strategies. We
                 conclude with our design for concurrent evolution of
                 multiple agent strategies in domains where agents need
                 to communicate with each other to successfully solve a
                 common problem.",
  URL =          "http://euler.mcs.utulsa.edu/~haynes/jp.ps",
  notes =        "

                 ",
}