Developmental graph cellular automata

During biological morphogenesis, complex and highly specific forms emerge through a developmental process. This often starts with a single cell and can end up creating organisms with trillions of cells. There is no global top-down control of this process but rather it is distributed amongst all the cells, each acting autonomously but coordinating their behaviour through signalling. Abstracting away from biology, this kind of distributed and coordinated development could have many applications, from the self-assembly of physical structures, to the creation of complex computational objects such as neural networks.

Cellular Automata (CA) can be used to explore the capabilities of distributed computation. CA consist of a number of discrete cells connected in some configuration, each with a state and implementing the same update rule, which is applied in parallel at each timestep. This can give rise to complex emergent global behaviour even when the local update rule is comparatively simple. Traditionally, CA are configured on a grid, but it is also possible to structure them as arbitrary graphs. In either case, the cells all exist from the start, in a fixed relationship to each other.

This thesis seeks to adapt CA for constructing graphs via a developmental process. This involves adding, removing and reconfiguring the connections of cells as the system is running. This allows complex graph structures to be created deterministically from the repeated application of a simple rule to a small ‘seed graph’. This can be thought of as an abstract model of biological development and has implications in the field of Artificial Life.

The thesis discusses the design of the model, aiming to strike a balance between simplicity and expressive power. We find that Developmental Graph CA can give rise to rich dynamics and complex patterns of growth. The evolvability of growth rules is investigated. It is found that both the dynamical behaviour and the graph structures produced by the developmental process are amenable to evolution. The organisation of the attractor cycles produced by the model is investigated and used as an analogy of self-reproduction or cell differentiation. Finally, a method of harnessing the computational abilities of the system using the Reservoir Computing paradigm is introduced.