Paper by Erik D. Demaine

Reference:

Greg Aloupis, Sébastien Collette, Mirela Damian, Erik D. Demaine, Robin Flatland, Stefan Langerman, Joseph O'Rourke, Suneeta Ramaswami, Vera Sacristán, and Stefanie Wuhrer, “Linear Reconfiguration of Cube-Style Modular Robots”, Computational Geometry: Theory and Applications, to appear.

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 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 [1, 2, 3], which require O(n²) 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.

Availability:

The paper is available in PDF (3178k).

See information on file formats.

[Google Scholar search]

Related papers:

Crystalline_ISAAC2008 (Reconfiguration of Cube-Style Modular Robots Using $O(\log n)$ Parallel Moves)

Crystalline_ISAAC2007 (Linear Reconfiguration of Cube-Style Modular Robots)

Crystalline_EGC2007 (Linear Reconfiguration of Cube-Style Modular Robots)