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

The problem we address is the distributed reconfiguration of a metamorphic robotic system composed of any number of two dimensional hexagonal modules from specific initial to specific goal configurations. We present a distributed algorithm for reconfiguring a straight chain of hexagonal modules at one location to any intersecting straight chain configuration at some other location in the plane. We prove our algorithm is correct, and show that it is asymptotically optimal in the number of moves and in the time required for parallel reconfiguration. We then consider the distributed reconfiguraion of straight chains of modules to a more general class of goal configurations.