Topological evolution for embodied cellular automata

In this work we introduce a novel method for creating behaviors in cellular automata: optimizing the topology of the cellular substrate while maintaining a single simple update rule. We study the effect of altering the shape of a 3D cellular automaton and local signaling ability of each of its cells on the ability of that automaton as a whole to give rise to emergent locomotion behavior. This system optimizes for the physically embodied interactions between a cellular automaton with an external physically simulated world, rather than optimizing directly for a computational ability internal to the automaton itself. We give each cell in the automaton the ability to have an internal "excited" state, and also the ability to perform a physical action (volumetric contraction and expansion) as a result of that state. We then employ an evolutionary algorithm to optimize for the locomotion ability of the "robot" resulting from the behavior of this embodied automaton. We demonstrate a number of diverse topologies which lead to effective locomotion behaviors in this paradigm. We believe that creating complex behavior from simple rules in a complex substrate not only opens up questions about cellular automata, but also provides insights towards the study of morphological computation and embodied cognition. (C) 2015 Elsevier B.V. All rights reserved.