| Abstract: | The problem we address is the distributed reconfiguration of a planar metamorphic robotic system composed of any number of hexagonal modules. After presenting a framework for classifying motion planning algorithms for metamorphic robotic systems, we describe distributed algorithms for reconfiguring a straight chain of hexagonal modules to any intersecting straight chain configuration. We prove our algorithms are correct, and show that they are either optimal or asymptotically optimal in the number of moves and asymptotically optimal in the time required for parallel reconfiguration.Received: 28 October 2002, Accepted: 31 October 2003, Published online: 1 March 2004 Corresdpondence to: Jennifer E. WalterNancy M. Amato: amato]@cs.tamu.edu A preliminary version of this paper appeared in the Proc. of the 19th ACM Symposium on Principles of Distributed Computing, July 2000, pages 171-180. The work of N. Amato and J. Walter was supported in part by NSF CAREER Award CCR-9624315, NSF Grants IIS-9619850, ACI-9872126, EIA-9975018, EIA-0103742, EIA-9805823, ACR-0081510, ACR-0113971, CCR-0113974, EIA-9810937, EIA-0079874, by the Texas Higher Education Coordinating Board grant ARP-036327-017, and by the DOE ASCI ASAP program grant B347886. The work of J. Walter was supported in part by Department of Education GAANN and GE Faculty of the Future fellowships. |
