Self-reconfiguration planning for a class of modular robots

Modular self-reconfigurable robots consist of large numbers (hundreds or thousands) of identical modules that possess the ability to reconfigure into different shapes as required by the task at hand. For example, such a robot could start out as a snake to traverse a narrow pipe, then re-assemble itself into a six-legged spider to move over uneven terrain. growing a pair of arms to pick up and manipulate an object at the same time. This paper examines the self-reconfiguration problem and presents a divide-and-conquer strategy to solve reconfiguration for a class of problems referred to as closed-chain reconfiguration. This class includes reconfigurable robots whose topologies are described by one-dimensional combinatorial topology. A robot topology is first decomposed into a hierarchy of small "substructures" (subgraphs of modules) belonging to a finite set. Basic reconfiguration operations between the substructures in the set are precomputed, optimized and stored in a lookup table. The entire reconfiguration then consists of an ordered series of simple, precomputed sub-reconfigurations happening locally among the substructures.