Generic Distributed Self-Reconfiguration Algorithms (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:

An extension to the locomotion algorithm is the ability to move into confined spaces, such as tunnels:

We are developing  algorithms for non-locomotion tasks such as self-assembly and self-repair: