Evolving symmetric and modular neural networks for distributed control

ABSTRACT

Problems such as the design of distributed controllers are characterized by modularity and symmetry. However, the symmetries useful for solving them are often difficult to determine analytically. This paper presents a nature-inspired approach called Evolution of Network Symmetry and mOdularity (ENSO) to solve such problems. It abstracts properties of generative and developmental systems, and utilizes group theory to represent symmetry and search for it systematically, making it more evolvable than randomly mutating symmetry. This approach is evaluated by evolving controllers for a quadruped robot in physically realistic simulations. On flat ground, the resulting controllers are as effective as those having hand-designed symmetries. However, they are significantly faster when evolved on inclined ground, where the appropriate symmetries are difficult to determine manually. The group-theoretic symmetry mutations of ENSO were also significantly more effective at evolving such controllers than random symmetry mutations. Thus, ENSO is a promising approach for evolving modular and symmetric solutions to distributed control problems, as well as multiagent systems in general.

REFERENCES

• 1: O. Bastert. Stabilization Procedures and Applications. PhD thesis, Technische Universität Müchen, 2001.
• 2: Randall D. Beer , Hillel J. Chiel , Leon S. Sterling, Heterogeneous neural networks for adaptive behavior in dynamic environments, Advances in neural information processing systems 1, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1989
• 3: J. C. Bongard and R. Pfeifer. Repeated structure and dissociation of genotypic and phenotypic complexity in artificial ontogeny. In Proceedings of GECCO, pages 829--836, 2001.
• 4: J. J. Collins and I. N. Stewart. Coupled nonlinear oscillators and the symmetries of animal gaits. Journal of Nonlinear Science, 3(1):349--392, 1993.
• 5: GAP -- groups, algorithms, and programming, 2007. http://www.gap-system.org.
• 6: A. Garcia-Bellido. Symmetries throughout organic evolution. PNAS, 93(25):14229--14232, December 1996.
• 7: F. Gruau. Neural Network Synthesis Using Cellular Encoding and the Genetic Algorithm. PhD thesis, Ecole Normale Superieure de Lyon, France, 1994.
• 8: M. Herzog and O. Manz. On the number of subgroups in finite solvable groups. Journal of the Australian Mathematical Society (Series A), 58:134--141, 1995.
• 9: F. Heylighen. The growth of structural and functional complexity during evolution. In The Evolution of Complexity: The Violet Book of 'Einstein Meets Magritte', chapter 2, pages 17--44. Springer, 1999.
• 10: Gregory S. Hornby , Jordan B. Pollack, Creating high-level components with a generative representation for body-brain evolution, Artificial Life, v.8 n.3, p.223-246, 2002 [doi>10.1162/106454602320991837]
• 11: H. Kitano. Designing neural networks using genetic algorithms with graph generation system. Complex Systems, 4:461--476, 1990.
• 12: S. Luke and L. Spector. Evolving graphs and networks with edge encoding: Preliminary report. In Late-Breaking Papers of Genetic Programming, 1996.
• 13: J. F. Miller. Evolving a self-repairing, self-regulating, French flag organism. In Proceedings of GECCO, 2004.
• 14: ODE: Open dynamics engine, 2007. http://www.ode.org/.
• 15: OGRE: Object-oriented graphics rendering engine, 2007. http://www.ogre3d.org/.
• 16: OPAL: Open physics abstraction layer, 2007. http://opal.sourceforge.net/.
• 17: Open BEAGLE, 2007. http://beagle.gel.ulaval.ca/.
• 18: A. R. Palmer. Symmetry breaking and the evolution of development. Science, 306:828--833, 2004.
• 19: K. Sims. Evolving 3D morphology and behavior by competition. In Proceedings of Artificial Life IV, pages 28--39, 1994.
• 20: 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]
• 21: 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]
• 22: Kenneth O. Stanley , Risto Miikkulainen, A Taxonomy for artificial embryogeny, Artificial Life, v.9 n.2, p.93-130, Spring 2003 [doi>10.1162/106454603322221487]
• 23: K. O. Stanley and R. Miikkulainen. Competitive coevolution through evolutionary complexification. Journal of Artificial Intelligence Research, 21:63--100, 2004.
• 24: 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]

INDEX TERMS

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

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.9 Robotics
          Subjects: Propelling mechanisms

General Terms:
Design, Experimentation, Performance

Keywords:
controllers, group theory, indirect encoding, modularity, multilegged robots, symmetry