**Reference**:- Greg Aloupis, Sébastien Collette, Mirela Damian, Erik D. Demaine, Robin Flatland, Stefan Langerman, Joseph O'Rourke, Val Pinciu, Suneeta Ramaswami, Vera Sacristán, and Stefanie Wuhrer, “Efficient constant-velocity reconfiguration of crystalline robots”,
*Robotica*, volume 29, number 1, 2011, pages 59–71. Special issue on Robotic Self-X Systems. **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 constant velocity and can displace at most a constant number of other atoms. We assume that one of the atoms has access to the coordinates of atoms in the target configuration.Our algorithms involve a total of

*O*(*n*^{2}) atom operations, which are performed in*O*(*n*) parallel steps. This improves on previous reconfiguration algorithms, which either use*O*(*n*^{2}) parallel steps [Rus and Vona, 2001, Vassilvitskii et al., 2002, Butler and Rus, 2003] or do not respect the constraints mentioned above [Aloupis et al., 2009b]. In fact, in the setting considered, our algorithms are optimal. A further advantage of our algorithms is that reconfiguration can take place within the union of the source and target configuration space, and only requires local communication **Comments**:- This paper is also available from Cambridge Journals Online.
**Availability**:- The paper is available in PDF (415k).
- See information on file formats.
- [Google Scholar search]

See also other papers by Erik Demaine.

Last updated December 1, 2021 by Erik Demaine.