Paper by Erik D. Demaine

Reference:

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”, in Proceedings of the 18th Annual International Symposium on Algorithms and Computation (ISAAC 2007), December 17–19, 2007, pages 208–219.

BibTeX

@InProceedings{Crystalline_ISAAC2007,
  AUTHOR        = {Greg Aloupis and S{\'e}bastien Collette and Mirela Damian
                   and Erik D. Demaine and Robin Flatland and Stefan Langerman
                   and Joseph O'Rourke and Suneeta Ramaswami and
                   Vera Sacrist{\'a}n and Stefanie Wuhrer},
  TITLE         = {Linear Reconfiguration of Cube-Style Modular Robots},
  BOOKTITLE     = {Proceedings of the 18th Annual International Symposium on
                   Algorithms and Computation (ISAAC 2007)},
  bookurl       = {http://www.nishizeki.ecei.tohoku.ac.jp/isaac07/},
  MONTH         = {December 17--19},
  YEAR          = 2007,
  PAGES         = {208--219},

  doi           = {https://dx.doi.org/10.1007/978-3-540-77120-3_20},
  dblp          = {https://dblp.org/rec/conf/isaac/AloupisCDDFLORAW07},
  comments      = {This paper is also available from <A HREF="https://doi.org/10.1007/978-3-540-77120-3_20">SpringerLink</A>.},
  replaces      = {Crystalline_EGC2007},
  papers        = {Crystalline_CGTA; Crystalline_ISAAC2008; Crystalline_EGC2007},
}

Abstract:

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) atom operations (expand, contract, attach, detach) and is performed in O(n) parallel steps. This improves on previous reconfiguration algorithms [1–3], which require O(n²) 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.

Comments:

This paper is also available from SpringerLink.

Availability:

The paper is available in PDF (2652k).

See information on file formats.

[Google Scholar search]

Related papers:

Crystalline_CGTA (Linear Reconfiguration of Cube-Style Modular Robots)

Crystalline_ISAAC2008 (Reconfiguration of Cube-Style Modular Robots Using O(log n) Parallel Moves)

Crystalline_EGC2007 (Linear Reconfiguration of Cube-Style Modular Robots)