We consider the theoretical model of Crystalline robots, which have been introduced and prototyped by the robotics community. These robots consist of independently manipulable unit-square atoms that can extend contract arms on each side and attach detach from neighbors. These operations suffice to reconfigure between any two given (connected) shapes. The worstcase number of sequential moves required to transform one connected configuration to another is known to be ( n). However, in principle, atoms can all move simultaneously. We develop a parallel algorithm for reconfiguration that runs in only O(logn) parallel steps, although the total number of operations increases slightly to ( n logn). The result is the first (theoretically) almost-instantaneous universally reconfigurable robot built from simple units.
In this paper we propose a novel algorithm that, given a source robot S and a target robot T, reconfigures S into T. Both S and T are robots composed of n atoms arranged in 2x2x2 meta-modules. The reconfiguration involves a total of O(n) atomic operations (expand, contract, attach, detach) and is performed in O(n) parallel steps. This improves on previous reconfiguration algorithms [D. Rus, M. Vona, Crystalline robots: Self-reconfiguration with compressible unit modules, Autonomous Robots 10 (1) (2001) 107-124; S. Vassilvitskii, M. Yim, J. Suh, A complete, local and parallel reconfiguration algorithm for cube style modular robots, in: Proc. of the IEEE Intl. Conf. on Robotics and Automation, 2002, pp. 117-122; Z. Butler, D. Rus, Distributed planning and control for modular robots with unit-compressible modules, Intl. J. Robotics Res. 22 (9) (2003) 699-715, doi:10.1177 02783649030229002], which require O(n^2) parallel steps. Our algorithm is in-place; that is, the reconfiguration takes place within the union of the bounding boxes of the source and target robots. We show that the algorithm can also be implemented in a synchronous, distributed fashion.