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:
|File:icra1s 1xs.avi||File:icra2 5xs.avi|
|File:icra5 5os.avi||File:icra6 5os.avi|
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: File:tunnel2.avi We are developing algorithms for non-locomotion tasks such as self-assembly and self-repair: