Distributed Chain-To-Chain Reconfiguration of Metamorphic Robots

Jennifer E. Walter, Jennifer L. Welch, Nancy M. Amato

To appear at Nineteenth Annual ACM SIGACT-SIGOPS Symposium on PRINCIPLES OF DISTRIBUTED COMPUTING (PODC 2000), Portland, Oregon, 16-19 July 2000


We introduce a new problem in distributed computing, that of motion planning for reconfiguring a metamorphic robotic system from a specific initial to a specific goal configuration. We present a distributed algorithm for reconfiguring a straight chain of modules at one location in the plane to any intersecting straight chain configuration. We prove our algorithm is correct, and show that it is either optimal or asymptotically optimal in the number of moves and asymptotically optimal in the time required for this reconfiguration.