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
Last updated June 1, 2023 by