Generic Distributed Self-Reconfiguration Algorithms with Cellular Automata

We are investigating the use of algorithms inspired by the cellular automata paradigm to perform various reconfiguration and locomotion tasks on generic modular systems. In these algorithms, geometry-based rules are specified and evaluated independently by each module (cell) in the group. The idea is that simple algorithms that work for an idealized system can then be instantiated on to a variety of actual systems while retaining the (easily shown) correctness of the generic algorithms.

We have developed several locomotion algorithms which implement caterpillar tread-like motion of a group of modules. Another set of algorithms (primarily by Zack Butler) is on division of groups into smaller groups, an idea originally suggested by Satoshi Murata (a colleague at the Tokyo Institute of Technology). These algorithms are interesting both for their own sake and to show how the locomotion rules work independent of group size.