Paper by Erik D. Demaine

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.

BibTeX

@InProceedings{Crystalline_WAFR2008,
  AUTHOR        = {Greg Aloupis and S{\'e}bastien Collette and Mirela Damian
                   and Erik D. Demaine and Dania El-Khechen and Robin Flatland
                   and Stefan Langerman and Joseph O'Rourke and Val Pinciu and
                   Suneeta Ramaswami and Vera Sacrist{\'a}n and Stefanie Wuhrer},
  TITLE         = {Realistic Reconfiguration of Crystalline (and Telecube) Robots},
  BOOKTITLE     = {Proceedings of the 8th International Workshop on the
                   Algorithmic Foundations of Robotics (WAFR 2008)},
  bookurl       = {http://www.wafr.org/},
  SERIES        = {Springer Tracts in Advanced Robotics},
  VOLUME        = 57,
  ADDRESS       = {Guanajuato, M\'exico},
  MONTH         = {December 7--9},
  YEAR          = 2008,
  PAGES         = {433--447},

  doi           = {https://dx.doi.org/10.1007/978-3-642-00312-7_27},
  dblp          = {https://dblp.org/rec/conf/wafr/AloupisCDDEFLOPRAW08},
  comments      = {This paper is also available from <A HREF="http://dx.doi.org/10.1007/978-3-642-00312-7_27">SpringerLink</A>.},
  length        = {16 pages},
  papers        = {Crystalline_ISAAC2008; Crystalline_CGTA},
}

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²) such atom operations, which are performed in O(n) parallel steps. This improves on previous reconfiguration algorithms, which either use O(n²) 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)