A novel generative encoding for exploiting neural network sensor and output geometry

ABSTRACT

A significant problem for evolving artificial neural networks is that the physical arrangement of sensors and effectors is invisible to the evolutionary algorithm. For example, in this paper, directional sensors and effectors are placed around the circumference of a robot in analogous arrangements. This configuration ensures that there is a useful geometric correspondence between sensors and effectors. However, if sensors are mapped to a single input layer and the effectors to a single output layer (as is typical), evolution has no means to exploit this fortuitous arrangement. To address this problem, this paper presents a novel generative encoding called connective Compositional Pattern Producing Networks (connective CPPNs) that can effectively detect and capitalize on geometric relationships among sensors and effectors. The key insight is that sensors and effectors with consistent geometric relationships can be exploited by a repeating motif in the neural architecture. Thus, by employing an encoding that can discover such motifs as a function of network geometry, it becomes possible to exploit it. In this paper, a method for evolving connective CPPNs called Hypercube-based Neuroevolution of Augmenting Topologies (HyperNEAT) discovers sensible repeating motifs that take advantage of two different placement schemes, demonstrating the utility of such an approach.

REFERENCES

• 1: P. J. Angeline. Morphogenic evolutionary computations: Introduction, issues and examples. In J. R. McDonnell, R. G. Reynolds, and D. B. Fogel, editors, Evolutionary Programming IV: The Fourth Annual Conference on Evolutionary Programming, pages 387--401. MIT Press, 1995.
• 2: P. J. Bentley and S. Kumar. The ways to grow designs: A comparison of embryogenies for an evolutionary design problem. In Proc. of the Genetic and Evol. Comp. Conf. (GECCO-1999), pages 35--43, San Francisco, 1999. Kaufmann.
• 3: J. Bongard, Evolving modular genetic regulatory networks, Proceedings of the Evolutionary Computation on 2002. CEC '02. Proceedings of the 2002 Congress, p.1872-1877, May 12-17, 2002
• 4: D. B. Chklovskii and A. A. Koulakov. MAPS IN THE BRAIN: What can we learn from them? Annual Review of Neuroscience, 27:369--392, 2004.
• 5: D. Federici. Using embryonic stages to increase the evolvability of development. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2004) Workshop Program, Berlin, 2004. Springer Verlag.
• 6: G. J. Goodhill and M. A. Carreira-Perpinn. Cortical columns. In L. Nadel, editor, Encyc. of Cognitive Science, volume 1, pages 845--851. MacMillan Publishers Ltd., London, 2002.
• 7: C. Green. SharpNEAT homepage. http://sharpneat.sourceforge.net/, 2003--2006.
• 8: 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]
• 9: Aristid Lindenmayer, Adding Continuous Components to L-Systems, L Systems, Most of the papers were presented at a conference in Aarhus, Denmark, p.53-68, January 14-25, 1974
• 10: A. P. Martin. Increasing genomic complexity by gene duplication and the origin of vertebrates. The American Naturalist, 154(2):111--128, 1999.
• 11: J. F. Miller. Evolving a self-repairing, self-regulating, French flag organism. In Proc. of the Genetic and Evol. Comp. Conf. (GECCO-2004), Berlin, 2004. Springer Verlag.
• 12: E. Mjolsness, D. H. Sharp, and J. Reinitz. A connectionist model of development. Journal of Theoretical Biology, 152:429--453, 1991.
• 13: Olaf Sporns, Networks analysis, complexity, and brain function, Complexity, v.8 n.1, p.56-60, September 2002 [doi>10.1002/cplx.10047]
• 14: K. O. Stanley. Comparing artificial phenotypes with natural biological patterns. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO) Workshop Program, New York, NY, 2006. ACM Press.
• 15: K. O. Stanley. Exploiting regularity without development. In Proceedings of the AAAI Fall Symposium on Developmental Systems, Menlo Park, CA, 2006. AAAI Press.
• 16: 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]
• 17: K. O. Stanley, B. D. Bryant, and R. Miikkulainen. Real-time neuroevolution in the NERO video game. IEEE Transactions on Evolutionary Computation Special Issue on Evolutionary Computation and Games, 9(6):653--668, 2005.
• 18: 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]
• 19: 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]
• 20: K. O. Stanley and R. Miikkulainen. Competitive coevolution through evolutionary complexification. Journal of Artificial Intelligence Research, 21:63--100, 2004.
• 21: A. Turing. The chemical basis of morphogenesis. Philosophical Transactions of the Royal Society B, 237:37--72, 1952.
• 22: X. Yao. Evolving artificial neural networks. Proceedings of the IEEE, 87(9):1423--1447, 1999.
• 23: M. J. Zigmond, F. E. Bloom, S. C. Landis, J. L. Roberts, and L. R. Squire, editors. Fundamental Neuroscience. Academic Press, London, 1999.

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.6 Learning
          Subjects: Concept learning

General Terms:
Algorithms, Experimentation

Keywords:
HyperNEAT, NEAT, compositional pattern producing networks, large-scale artifical neural networks