Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

In this paper, we suggest tree-structure-aware GP operators that heed tree distributions in structure space and their possible structural difficulties. The main idea of the proposed GP operators is to place the generated offspring of crossover and/or mutation in a specified region of tree structure space insofar as possible, taking into account the observation that most solutions are found in that region. To enable that, the proposed operators are designed to utilize information about the region to which the parents belong and node/depth statistics of the subtree selected for modification.

The proposed approach is applied to automatic gait generation of quadruped robot to demonstrate the effectiveness of it. The results show that the results using the proposed tree-structure-aware operators are superior to the results of standard GP for gait problem in both fitness and velocity.

REFERENCES

• 1: Jason M. Daida , Robert R. Bertram , Stephen A. Stanhope , Jonathan C. Khoo , Shahbaz A. Chaudhary , Omer A. Chaudhri , John A. Ii Polito, What Makes a Problem GP-Hard? Analysis of a Tunably Difficult Problem in Genetic Programming, Genetic Programming and Evolvable Machines, v.2 n.2, p.165-191, June 2001 [doi>10.1023/A:1011504414730]
• 2: J.M. Daida, A.M. Hilss, "Identifying Structural Mechanisms in Standard Genetic Programming," Proceedings of the Genetic and Evolutionary Computation Conference (GECCO2003), LNCS 2724, pp.1639--1651, Chicago, IL, USA, July 12-16, 2003.
• 3: J.M. Daida, A.M. Hilss, "What Makes a Problem GP Hard? Validating a Hypothesis of Structural Causes," Proceedings of the Genetic and Evolutionary Computation Conference (GECCO2003), LNCS 2724, pp.1665--1677, Chicago, IL, USA, July 12-16, 2003
• 4: T. Ito, H. Iba, S. Sato, "Depth Dependent Crossover for Genetic Programming," in Proceedings of the World Congress on Computational Intelligence, pp.775--780, Anchorage, AK. USA, May 4-9, 1998
• 5: John R. Koza, Genetic programming: on the programming of computers by means of natural selection, MIT Press, Cambridge, MA, 1992
• 6: John R. Koza, Genetic programming II: automatic discovery of reusable programs, MIT Press, Cambridge, MA, 1994
• 7: S. Luke, Issues in Scaling Genetic Programming Breeding Strategies, Tree Generation and Code Bloat, PhD thesis, University of Maryland, 2000
• 8: Hammad Majeed , Conor Ryan, On the constructiveness of context-aware crossover, Proceedings of the 9th annual conference on Genetic and evolutionary computation, July 07-11, 2007, London, England [doi>10.1145/1276958.1277286]
• 9: N.F. McPhee, A. Jarvis, E.F. Crane, "On the Strength of Size Limits in Linear Genetic Programming," Proceedings of the Genetic and Evolutionary Computation Conference (GECCO2004), LNCS 3103, pp.593--604, Seattle, WA, USA, June 26-30, 2004
• 10: Ngyen, X. Hoai, B. McKay, D. Essam, "Representation and structural Difficulty in Genetic Programming," IEEE Transactions on Evolutionary Computation, 10(2), pp.157--166, April 2006
• 11: J. Page , Riccardo Poli , William B. Langdon, Smooth Uniform Crossover with Smooth Point Mutation in Genetic Programming: A Preliminary Study, Proceedings of the Second European Workshop on Genetic Programming, p.39-48, May 26-27, 1999
• 12: Riccardo Poli , Jonathan Page, Solving High-Order Boolean Parity Problems with Smooth Uniform Crossover, Sub-Machine Code GP and Demes, Genetic Programming and Evolvable Machines, v.1 n.1-2, p.37-56, April 2000 [doi>10.1023/A:1010068314282]
• 13: Sara Silva , Ernesto Costa, Resource-limited genetic programming: the dynamic approach, Proceedings of the 2005 conference on Genetic and evolutionary computation, June 25-29, 2005, Washington DC, USA [doi>10.1145/1068009.1068290]
• 14: Zonker D. and Punch W.F., lil-gp 1.1 User's Manual, GARAGe, College of Engineering, Michigan State University, (1998)
• 15: Hornby, G.S., Takamura, S., Yamamoto, T., Fujita, M. Autonomous evolution of dynamic gaits with two quadruped robots. IEEE Trans. Robotics, Vol. 21, No. 3, 2005, 402--410.
• 16: Sony Corporation, Model information for ERS-7, OPEN-R SDK, (2004) Chen, W. Odometry Calibration and Gait Optimisation. Technical Report, The University of New South Wales, School of Computer Science and Engineering, 2005.
• 17: Dong, H., Zhao, M., Zhang, J., Shi, Z., Zhang, N. Gait planning of quadruped robot based on third-order spline interpolation. In Proceedings of the 2006 IEEE/RSJ International Conference on Intelligent Robots and Systems(IROS'06), Beijing China October 9-15, 2006.
• 18: Mericli, T., Akin, H.L., Mericli, C., Kaplan, K., Celik, B. The Cerberus'05 Team Report.
• 19: Hohl, L., Tellez, R., Michel, O., Ijspeert, A.J. Aibo and Webots: Simulation, wireless remote control and controller transfer. Robotics and Autonomous Systems, 54, 2006, 472--485.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.9 Robotics

General Terms:
Algorithms, Design

Keywords:
automatic gait generation, genetic programming, quadruped robot, tree-structure-aware gp operators