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
Abstract
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.