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”, in Proceedings of the 18th Annual International Symposium on Algorithms and Computation (ISAAC 2007), December 17–19, 2007, pages 208–219.

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) atom operations (expand, contract, attach, detach) and is performed in O(n) parallel steps. This improves on previous reconfiguration algorithms [1–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 SpringerLink.

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

Related papers:
Crystalline_CGTA (Linear Reconfiguration of Cube-Style Modular Robots)
Crystalline_ISAAC2008 (Reconfiguration of Cube-Style Modular Robots Using O(log n) Parallel Moves)
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 March 9, 2018 by Erik Demaine.