The sensitivity of HyperNEAT to different geometric representations of a problem

ABSTRACT

HyperNEAT, a generative encoding for evolving artificial neural networks (ANNs), has the unique and powerful ability to exploit the geometry of a problem (e.g., symmetries) by encoding ANNs as a function of a problem's geometry. This paper provides the first extensive analysis of the sensitivity of HyperNEAT to different geometric representations of a problem. Understanding how geometric representations affect the quality of evolved solutions should improve future designs of such representations. HyperNEAT has been shown to produce coordinated gaits for a simulated quadruped robot with a specific two-dimensional geometric representation. Here, the same problem domain is tested, but with different geometric representations of the problem. Overall, experiments show that the quality and kind of solutions produced by HyperNEAT can be substantially affected by the geometric representation. HyperNEAT outperforms a direct encoding control even with randomized geometric representations, but performs even better when a human engineer designs a representation that reflects the actual geometry of the robot. Unfortunately, even choices in geometric layout that seem to be inconsequential a priori can significantly affect fitness. Additionally, a geometric representation can bias the type of solutions generated (e.g., make left-right symmetry more common than front-back symmetry). The results suggest that HyperNEAT practitioners can obtain good results even if they do not know how to geometrically represent a problem, and that further improvements are possible with a well-chosen geometric representation.

REFERENCES

• 1: J. Clune, B. E. Beckmann, C. Ofria, and R. T. Pennock, "Evolving coordinated quadruped gaits with the HyperNEAT generative encoding." Proceedings of the IEEE Congress on Evolutionary Computing Special Section on Evolutionary Robotics, 2009. Trondheim, Norway. To appear.
• 2: Jeff Clune , Charles Ofria , Robert T. Pennock, How a Generative Encoding Fares as Problem-Regularity Decreases, Proceedings of the 10th international conference on Parallel Problem Solving from Nature: PPSN X, September 13-17, 2008, Dortmund, Germany [doi>10.1007/978-3-540-87700-4_36]
• 3: David B. D'Ambrosio , Kenneth O. Stanley, Generative encoding for multiagent learning, Proceedings of the 10th annual conference on Genetic and evolutionary computation, July 12-16, 2008, Atlanta, GA, USA [doi>10.1145/1389095.1389256]
• 4: J. Gauci and K. O. Stanley, "A case study on the critical role of geometric regularity in machine learning," in AAAI (D. Fox and C. P. Gomes, eds.), pp. 628--633, AAAI Press, 2008.
• 5: Frédéric Gruau, Automatic definition of modular neural networks, Adaptive Behavior, v.3 n.2, p.151-183, Fall 1994 [doi>10.1177/105971239400300202]
• 6: G. S. Hornby, H. Lipson, and J. B. Pollack, "Generative representations for the automated design of modular physical robots," IEEE Transactions on Robotics and Automation, vol. 19, pp. 703--719, 2003.
• 7: G. Hornby, S. Takamura, T. Tamamoto, and M. Fujita, "Autonomous evolution of dynamic gaits with two quadruped robots," IEEE Transactions on Robotics, vol. 21, no. 3, pp. 402--410, 2005.
• 8: J. Kodjabachian and J-A Meyer, "Evolution and Development of Neural Controllers for Locomotion, Gradient-Followig, and Obstacle-Avoidance in Artificial Insects." IEEE Transactions on Neural Networks. Vol 9:5, pp. 796--812. Sept. 1998.
• 9: H. Liu and H. Iba, "A hierarchical approach for adaptive humanoid robot control," in Proceedings of the 2004 IEEE Congress on Evolutionary Computation, (Portland, Oregon), pp. 1546--1553, IEEE Press, 20--23 June 2004.
• 10: Stefano Nolfi , Dario Floreano, Evolutionary Robotics: The Biology, Intelligence, and Technology of Self-Organizing Machines, Bradford Book, 2004
• 11: Karl Sims, Evolving 3D morphology and behavior by competition, Artificial Life, v.1 n.4, p.353-372, Summer 1994
• 12: Kenneth O. Stanley , Risto Miikkulainen, Evolving neural networks through augmenting topologies, Evolutionary Computation, v.10 n.2, p.99-127, Summer 2002 [doi>10.1162/106365602320169811]
• 13: Kenneth O. Stanley, Compositional pattern producing networks: A novel abstraction of development, Genetic Programming and Evolvable Machines, v.8 n.2, p.131-162, June 2007 [doi>10.1007/s10710-007-9028-8]
• 14: Kenneth O. Stanley , David B. D'Ambrosio , Jason Gauci, A hypercube-based encoding for evolving large-scale neural networks, Artificial Life, v.15 n.2, p.185-212, Spring 2009 [doi>10.1162/artl.2009.15.2.15202]
• 15: Vinod K. Valsalam , Risto Miikkulainen, Modular neuroevolution for multilegged locomotion, Proceedings of the 10th annual conference on Genetic and evolutionary computation, July 12-16, 2008, Atlanta, GA, USA [doi>10.1145/1389095.1389136]
• 16: K. Wolff and P. Nordin, "An evolutionary based approach for control programming of humanoids," in Proceedings of the 3rd International Conference on Humanoid Robots (Humanoids'03), (Karlsruhe, Germany), IEEE, VDI/VDE-GMA, 1--2 October 2003.
• 17: www.ode.org
• 18: www.picbreeder.org

INDEX TERMS

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

General Terms:
Algorithms, Experimentation

Keywords:
artificial neural networks, developmental encoding, generative encoding, geometry, hyperneat, indirect encoding, neat, neuroevolution