Lab Info
Journal Club
In The News
Upcoming Meetings
Distributed Robotics

Up Cellular Automata Adaptive Controllers Inverse Kinematics

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:

1-Layer Linear Motion Sequence
(2.6 MB AVI, Cinepak codec)

5-Layer Linear Motion Sequence
(5.5 MB AVI, Cinepak codec)

5-Layer Linear Motion Sequence with Obstacles
(8.3 MB AVI, Cinepak codec)

5-Layer Turning Motion Sequence
(6.9 MB AVI, Cinepak codec)

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:

Recursive Splitting
(14.6 MB Quicktime)

3D Splitting
(4.4 MB Quicktime)

Mars Exploration Simulation
(40.7 MB AVI, RLE codec)



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

Locomotion Through a Tunnel
(1.3 MB AVI, Cinepak codec)


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

Pyramid Self-Assembly
(5.2 MB AVI, RLE codec)

Hole Repair
(29.6 MB AVI, RLE codec)