Analysis of the difficulty of learning goal-scoring behaviour for robot soccer

ABSTRACT

Learning goal-scoring behaviour from scratch for simulated robot soccer is considered to be a very difficult problem, and is often achieved by endowing players with an innate set of hand-coded skills, or by decomposing the problem into learning a set of simpler behaviours which are then aggregated into goal-scoring behaviour. When only basic skills are available to the player the fitness landscape is very flat, containing only a few thin peaks. As more human expertise is injected via hand-coded skills or a composite fitness function, more gradient information becomes apparent on the landscape and the genetic search is more successful. The work presented in this paper uses autocorrelation and information content measures to examine features of the fitness landscape to explain how the difficulty of the problem is changed by injecting human expertise.

REFERENCES

• 1: Frauenfelder, H., et al., eds. Landscape Concepts in Physics and Biology. Special Issue of Physica D. Vol. 107, p. 2--4. 1997. Elsevier Science: Amsterdam, Holland.
• 2: Goldberg, D., B. Korb, and K. Deb, Messy Genetic Algorithms : Motivation, Analysis, and First Results. Complex Systems 3, 1989.
• 3: Hordijk, W., A Measure of Landscapes. Evolutionary Computation, 4(4): p.335--360. 1996.
• 4: Jyh-Shing Roger Jang , Chuen-Tsai Sun, Neuro-fuzzy and soft computing: a computational approach to learning and machine intelligence, Prentice-Hall, Inc., Upper Saddle River, NJ, 1996
• 5: Jones, T., One Operator, One Landscape, in Technical Report 95-02-025. 1995. Santa Fe Institute: Santa Fe, NM.
• 6: Kauffman, S.A., Adaptation on Rugged Fitness Landscapes, in Lectures in the Sciences of Complexity, D. Stein, Ed. p.527--618. 1989. Addison Wesley.
• 7: Kitano, H., et al. The Robot World Cup Initiative in Working Notes of the 1995 IJCAI Workshop on Entertainment and AI/Alife, p.19--24. 1995. Montreal, Canada.
• 8: Lima, P., et al., RoboCup 2004 Competitions and Symposium: A Small Kick for Robots, a Giant Score for Science, in AI Magazine 6(2). 2005.
• 9: Luke, S. Genetic Programming Produced Competitive Soccer Softbot Teams for RoboCup97 in J. Koza et al., eds, Proceedings of the Third Annual Genetic Programming Conference, p.204-222. 1998. Morgan Kaufmann, San Francisco.
• 10: Riedmiller, M., et al. Brainstormers 2D - Team Description 2005 in Team Description Papers, Proceedings of RoboCup 2005 (CD) (to appear). 2005.
• 11: Riley, J. The SimpleSoccer Machine Learning Environment in S.-B. Cho et al., eds, Proceedings of the First Asia-Pacific Workshop on Genetic Programming, p.24-30. 2003. Canberra, Australia.
• 12: Vesselin K. Vassilev , Terence C. Fogarty , Julian F. Miller, Information Characteristics and the Structure of Landscapes, Evolutionary Computation, v.8 n.1, p.31-60, March 2000 [doi>10.1162/106365600568095]
• 13: Vassilev, V.K. Information Analysis of Fitness Landscapes in P. Husbands and I. Harvey, eds, Proceedings of the Fourth European Conference on Artificial Life. 1997. Brighton, England: The MIT Press.
• 14: Weinberger, E., Correlated and Uncorrelated Fitness Landscapes and How to Tell the Difference. Biological Cybernetics, 63: p. 325--336. 1990.
• 15: Wright, S. The Roles of Mutation, Inbreeding, Crossbreeding and Selection in Evolution in D.F. Jones, ed., Proceedings of the Sixth International Congress on Genetics, p.356--366. 1932. Brooklyn NY: Brooklyn Botanic Garden.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.0 General

General Terms:
Algorithms, Performance, Theory

Keywords:
fitness landscapes, fuzzy systems, genetic algorithm