Paper by Erik D. Demaine

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.

BibTeX

@Article{Crystalline_Robotica,
  AUTHOR        = {Greg Aloupis and S\'ebastien Collette and Mirela Damian and
                   Erik D. Demaine and Robin Flatland and Stefan Langerman
                   and Joseph O'Rourke and Val Pinciu and Suneeta Ramaswami and
                   Vera Sacrist\'an and Stefanie Wuhrer},
  TITLE         = {Efficient constant-velocity reconfiguration of crystalline robots},
  JOURNAL       = {Robotica},
  VOLUME        = 29,
  NUMBER        = 1,
  YEAR          = 2011,
  PAGES         = {59--71},
  NOTE          = {Special issue on Robotic Self-X Systems.},

  doi           = {https://dx.doi.org/10.1017/S026357471000072X},
  dblp          = {https://dblp.org/rec/journals/robotica/AloupisCDDFLOPRSW11},
  comments      = {This paper is also available from <A HREF="http://dx.doi.org/10.1017/S026357471000072X">Cambridge Journals Online</A>.},
}

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