**Reference**:- Greg Aloupis, Sébastien Collette, Mirela Damian, Erik D. Demaine, Dania El-Khechen, Robin Flatland, Stefan Langerman, Joseph O'Rourke, Val Pinciu, Suneeta Ramaswami, Vera Sacristán, and Stefanie Wuhrer, “Realistic Reconfiguration of Crystalline (and Telecube) Robots”, in
*Proceedings of the 8th International Workshop on the Algorithmic Foundations of Robotics (WAFR 2008)*, Springer Tracts in Advanced Robotics, volume 57, Guanajuato, México, December 7–9, 2008, pages 433–447. **Abstract**:-
In this paper we propose novel algorithms for reconfiguring modular robots
that are composed of
*n*atoms. Each atom has the shape of a unit cube and can expand/contract each face by half a unit, as well as attach to or detach from faces of neighboring atoms. For universal reconfiguration, atoms must be arranged in 2 × 2 × 2 modules. We respect certain physical constraints: each atom reaches at most unit velocity and (via expansion) can displace at most one other atom. We require that one of the atoms can store a map of the target configuration.Our algorithms involve a total of

*O*(*n*^{2}) such atom operations, which are performed in*O*(*n*) parallel steps. This improves on previous reconfiguration algorithms, which either use*O*(*n*^{2}) parallel steps [7, 9, 4] or do not respect the constraints mentioned above [1]. In fact, in the setting considered, our algorithms are optimal, in the sense that certain reconfigurations require Ω(*n*) parallel steps. A further advantage of our algorithms is that reconfiguration can take place within the union of the source and target configurations. **Comments**:- This paper is also available from SpringerLink.
**Length**:- The paper is 16 pages.
**Availability**:- The paper is available in PDF (435k).
- 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_CGTA (Linear Reconfiguration of Cube-Style Modular Robots)

See also other papers by Erik Demaine.

Last updated January 18, 2021 by Erik Demaine.