Volume 23 Issue 7/8- Publication Date: 1 July-August 2004
State Complexes for Metamorphic Robots
A. Abrams Department of Mathematics, University of Georgia, Athens, GA 30602, USA and R. Ghrist Department of Mathematics, University of Illinois, Urbana, IL 61801, USA

A metamorphic robotic system is an aggregate of homogeneous robot units which can individually and selectively locomote in such a way as to change the global shape of the system. We introduce a mathematical framework for defining and analyzing general metamorphic robots. With this formal structure, combined with ideas from geometric group theory, we define a new type of configuration space for metamorphic robots—the state complex—which is especially adapted to parallelization. We present an algorithm for optimizing an input reconfiguration sequence with respect to elapsed time. A universal geometric property of state complexes—non-positive curvature—is the key to proving convergence to the globally timeoptimal solution obtainable from the initial path

Return to Contents