Distributed planning and control for modular robots with unit-compressible modules

Self-reconfigurable robots are versatile systems consisting of large numbers of independent modules. Effective use of these systems requires parallel actuation and planning, both for efficiency and independence from a central controller. In this paper we present the PacMan algorithm, a technique for distributed actuation ad planning for systems with two- or three-dimensional unit-compressible modules. We give two versions of the algorithm along with correctness analysis. We also analyze the parallel actuation capability of the algorithm, showing that it will not deadlock and will avoid disconnecting the robot. We have implemented PacMan on the Crystal robot, a hardware system developed in our lab, and we present experiments and discuss the feasibility of large-scale implementation.