Analysis of an evolutionary reinforcement learning method in a multiagent domain

ABSTRACT

Many multiagent problems comprise subtasks which can be considered as reinforcement learning (RL) problems. In addition to classical temporal difference methods, evolutionary algorithms are among the most promising approaches for such RL problems. The relative performance of these approaches in certain subdomains (e. g. multiagent learning) of the general RL problem remains an open question at this time. In addition to theoretical analysis, benchmarks are one of the most important tools for comparing different RL methods in certain problem domains. A recently proposed multiagent RL benchmark problem is the RoboCup Keepaway benchmark. This benchmark is one of the most challenging multiagent learning problems because its state-space is continuous and high dimensional, and both the sensors and the actuators are noisy. In this paper we analyze the performance of the neuroevolutionary approach called Evolutionary Acquisition of Neural Topologies (EANT) in the Keepaway benchmark, and compare the results obtained using EANT with the results of other algorithms tested on the same benchmark.

REFERENCES

• 1: P. J. Angeline, G. M. Saunders, and J. B. Pollack. An evolutionary algorithm that constructs recurrent neural networks. IEEE Transactions on Neural Networks, 5:54--65, 1994.
• 2: James E. Baker, Adaptive Selection Methods for Genetic Algorithms, Proceedings of the 1st International Conference on Genetic Algorithms, p.101-111, July 01, 1985
• 3: P. Bentley and S. Kumar. Three ways to grow designs: A comparison of embryogenies for an evolutionary design problem. In Proceedings of the Genetic and Evolutionary Computation Conference, volume 1, pages 35--43, Orlando, Florida, USA, 13--17 July 1999. Morgan Kaufmann.
• 4: J. C. Bongard and R. Pfeifer. Repeated structure and dissociation of genotypic and phenotypic complexity in artificial ontogeny. In Proceedings of the Genetic and Evolutionary Computation Conference, pages 829--836, 2001.
• 5: F. Gomez, J. Schmidhuber, and R. Miikkulainen. Efficient non-linear control through neuroevolution. In Proceedings of the European Conference on Machine Learning, 2006.
• 6: F. Gruau. Neural Network Synthesis Using Cellular Encoding and the Genetic Algorithm. PhD thesis, Ecole Normale Superieure de Lyon, Laboratoire de l'Informatique du Parallelisme, France, January 1994.
• 7: Y. Kassahun. Towards a Unified Approach to Learning and Adaptation. PhD thesis, Technical Report 0602, Institute of Computer Science and Applied Mathematics, Christian-Albrechts University, Kiel, Germany, Feb 2006.
• 8: Yohannes Kassahun , Mark Edgington , Jan Hendrik Metzen , Gerald Sommer , Frank Kirchner, A common genetic encoding for both direct and indirect encodings of networks, Proceedings of the 9th annual conference on Genetic and evolutionary computation, July 07-11, 2007, London, England [doi>10.1145/1276958.1277162]
• 9: Yohannes Kassahun , Jan Hendrik Metzen , Jose Gea , Mark Edgington , Frank Kirchner, A General Framework for Encoding and Evolving Neural Networks, Proceedings of the 30th annual German conference on Advances in Artificial Intelligence, September 10-13, 2007, Osnabrück, Germany [doi>10.1007/978-3-540-74565-5_17]
• 10: H. Kitano. Designing neural networks using genetic algorithms with graph generation system. Complex Systems, 4:461--476, 1990.
• 11: A. Lindenmayer. Mathematical models for cellular interactions in development, parts I and II. Journal of Theoretical Biology, 18:280--315, 1968.
• 12: Stefano Nolfi , Dario Floreano, Evolutionary Robotics: The Biology,Intelligence,and Technology, MIT Press, Cambridge, MA, 2000
• 13: S. Nolfi and D. Parisi. Growing neural networks. Technical Report PCIA-91-15, Institute of Psychology, Rome, 1991.
• 14: Joseph Reisinger , Risto Miikkulainen, Acquiring evolvability through adaptive representations, Proceedings of the 9th annual conference on Genetic and evolutionary computation, July 07-11, 2007, London, England [doi>10.1145/1276958.1277164]
• 15: Hans-Paul Paul Schwefel, Evolution and Optimum Seeking: The Sixth Generation, John Wiley & Sons, Inc., New York, NY, 1993
• 16: B. Sendhoff and M. Kreutz. Variable encoding of modular neural networks for time series prediction. In Congress on Evolutionary Computation, pages 259--266, 1999.
• 17: N. Siebel, J. Krause, and G. Sommer. Efficient learning of neural networks with evolutionary algorithms. In Proceedings of the 29th German Symposium for Pattern Recognition, pages 466--475, 2007.
• 18: Kenneth Owen Stanley , Risto P. Miikkulainen, Efficient evolution of neural networks through complexification, The University of Texas at Austin, 2004
• 19: Peter Stone , Richard S. Sutton, Keepaway Soccer: A Machine Learning Testbed, RoboCup 2001: Robot Soccer World Cup V, p.214-223, January 2002
• 20: P. Stone, R. S. Sutton, and G. Kuhlmann. Reinforcement learning for RoboCup-soccer Keepaway. Adaptive Behavior, 13(3):165--188, 2005.
• 21: Richard S. Sutton , Andrew G. Barto, Introduction to Reinforcement Learning, MIT Press, Cambridge, MA, 1998
• 22: Matthew E. Taylor , Shimon Whiteson , Peter Stone, Comparing evolutionary and temporal difference methods in a reinforcement learning domain, Proceedings of the 8th annual conference on Genetic and evolutionary computation, July 08-12, 2006, Seattle, Washington, USA [doi>10.1145/1143997.1144202]
• 23: J. Vaario, A. Onitsuka, and K. Shimohara. Formation of neural structures. In Proceedings of the Fourth European Conference on Articial Life, pages 214--223, 1997.
• 24: Shimon Whiteson , Peter Stone, Evolutionary Function Approximation for Reinforcement Learning, The Journal of Machine Learning Research, 7, p.877-917, 12/1/2006
• 25: Shimon Whiteson , Matthew E. Taylor , Peter Stone, Empirical Studies in Action Selection with Reinforcement Learning, Adaptive Behavior - Animals, Animats, Software Agents, Robots, Adaptive Systems, v.15 n.1, p.33-50, March 2007 [doi>10.1177/1059712306076253]
• 26: Darrell Whitley , Stephen Dominic , Rajarshi Das , Charles W. Anderson, Genetic Reinforcement Learning for Neurocontrol Problems, Machine Learning, v.13 n.2-3, p.259-284, Nov./Dec. 1993 [doi>10.1007/BF00993045]
• 27: X. Yao. Evolving artificial neural networks. Proceedings of the IEEE, 87(9):1423--1447, 1999.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
          Subjects: Connectionism and neural nets

General Terms:
Algorithms

Keywords:
neuroevolution, reinforcement learning