Paper by Erik D. Demaine

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, volume 42, number 6–7, August 2009, pages 652–663.

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(n2) 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.

This paper is also available from ScienceDirect.

The paper is 20 pages.

The paper is available in PDF (3178k).
See information on file formats.
[Google Scholar search]

Related papers:
Crystalline_WAFR2008 (Realistic Reconfiguration of Crystalline (and Telecube) Robots)
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)

See also other papers by Erik Demaine.
These pages are generated automagically from a BibTeX file.
Last updated June 13, 2024 by Erik Demaine.