Abstract. 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 2 × 2 × 2 metamodules. The reconfiguration involves a total of O(n) atom operations (expand, contract, attach, detach) and is performed in O(n) parallel steps. This improves on previous reconfiguration algorithms [1] [2] [3] , 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.
A linear-time parallel algorithm for reconfiguring within the bounding box of source and target is given in REF .
Linear Reconfiguration of Cube-Style Modular Robots
ISAAC
Computer Science