**Reference**:- Greg Aloupis, Sébastien Collette, Erik D. Demaine, Stefan Langerman, Vera Sacristán, and Stefanie Wuhrer, “Reconfiguration of Cube-Style Modular Robots Using
*O*(log*n*) Parallel Moves”, in*Proceedings of the 19th Annual International Symposium on Algorithms and Computation (ISAAC 2008)*, Gold Coast, Australia, December 15–17, 2008, pages 342–353. **Abstract**:-
We consider a model of reconfigurable robot, introduced and prototyped by the
robotics community. The robot consists of independently manipulable
unit-square atoms that can extend/contract arms on each side and attach/detach
from neighbors. The optimal worst-case number of sequential moves required to
transform one connected configuration to another was shown to be
Θ(
*n*) at ISAAC 2007. However, in principle, atoms can all move simultaneously. We develop a parallel algorithm for reconfiguration that runs in only*O*(log*n*) parallel steps, although the total number of operations increases slightly to Θ(*n*log*n*). The result is the first (theoretically) almost-instantaneous universally reconfigurable robot built from simple units. **Comments**:- This paper is also available from SpringerLink.
**Copyright**:- Copyright held by the authors.
**Length**:- The paper is 12 pages.
**Availability**:- The paper is available in PDF (252k).
- See information on file formats.
- [Google Scholar search]
**Related papers**:- Crystalline_WAFR2008 (Realistic Reconfiguration of Crystalline (and Telecube) Robots)
- Crystalline_CGTA (Linear Reconfiguration of Cube-Style Modular Robots)

See also other papers by Erik Demaine.

Last updated July 7, 2020 by Erik Demaine.