Efficient constant-velocity reconfiguration of crystalline robots

Greg Aloupis, Sébastien Collette, Mirela Damian, Erik D. Demaine, Robin Flatland, Stefan Langerman, Joseph O'Rourke, Val Pinciu, Suneeta Ramaswami, Vera Sacristán, Stefanie Wuhrer

Research output: Contribution to journalArticle

6 Citations (Scopus)

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(n2) atom operations, which are performed in O(n) parallel steps. This improves on previous reconfiguration algorithms, which either use O(n2) parallel steps or do not respect the constraints mentioned above. In fact, in the settings 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.

Original languageEnglish (US)
Pages (from-to)59-71
Number of pages13
JournalRobotica
Volume29
Issue number1 SPEC. ISSUE
DOIs
StatePublished - Jan 1 2011

Fingerprint

Reconfiguration
Robot
Robots
Crystalline materials
Atoms
Modular robots
Face
Unit cube
Target
Configuration Space
Expand
Union
Module
Configuration
Unit
Communication

All Science Journal Classification (ASJC) codes

  • Software
  • Control and Systems Engineering
  • Mathematics(all)
  • Computer Science Applications

Keywords

  • Control of robotic systems
  • Mobile robots
  • Modular robots
  • Motion planning
  • Path planning

Cite this

Aloupis, G., Collette, S., Damian, M., Demaine, E. D., Flatland, R., Langerman, S., ... Wuhrer, S. (2011). Efficient constant-velocity reconfiguration of crystalline robots. Robotica, 29(1 SPEC. ISSUE), 59-71. https://doi.org/10.1017/S026357471000072X
Aloupis, Greg ; Collette, Sébastien ; Damian, Mirela ; Demaine, Erik D. ; Flatland, Robin ; Langerman, Stefan ; O'Rourke, Joseph ; Pinciu, Val ; Ramaswami, Suneeta ; Sacristán, Vera ; Wuhrer, Stefanie. / Efficient constant-velocity reconfiguration of crystalline robots. In: Robotica. 2011 ; Vol. 29, No. 1 SPEC. ISSUE. pp. 59-71.
@article{343034059ed64ae3aea7598b6846d7be,
title = "Efficient constant-velocity reconfiguration of crystalline robots",
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(n2) atom operations, which are performed in O(n) parallel steps. This improves on previous reconfiguration algorithms, which either use O(n2) parallel steps or do not respect the constraints mentioned above. In fact, in the settings 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.",
keywords = "Control of robotic systems, Mobile robots, Modular robots, Motion planning, Path planning",
author = "Greg Aloupis and S{\'e}bastien Collette and Mirela Damian and Demaine, {Erik D.} and Robin Flatland and Stefan Langerman and Joseph O'Rourke and Val Pinciu and Suneeta Ramaswami and Vera Sacrist{\'a}n and Stefanie Wuhrer",
year = "2011",
month = "1",
day = "1",
doi = "10.1017/S026357471000072X",
language = "English (US)",
volume = "29",
pages = "59--71",
journal = "Robotica",
issn = "0263-5747",
publisher = "Cambridge University Press",
number = "1 SPEC. ISSUE",

}

Aloupis, G, Collette, S, Damian, M, Demaine, ED, Flatland, R, Langerman, S, O'Rourke, J, Pinciu, V, Ramaswami, S, Sacristán, V & Wuhrer, S 2011, 'Efficient constant-velocity reconfiguration of crystalline robots', Robotica, vol. 29, no. 1 SPEC. ISSUE, pp. 59-71. https://doi.org/10.1017/S026357471000072X

Efficient constant-velocity reconfiguration of crystalline robots. / Aloupis, Greg; Collette, Sébastien; Damian, Mirela; Demaine, Erik D.; Flatland, Robin; Langerman, Stefan; O'Rourke, Joseph; Pinciu, Val; Ramaswami, Suneeta; Sacristán, Vera; Wuhrer, Stefanie.

In: Robotica, Vol. 29, No. 1 SPEC. ISSUE, 01.01.2011, p. 59-71.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Efficient constant-velocity reconfiguration of crystalline robots

AU - Aloupis, Greg

AU - Collette, Sébastien

AU - Damian, Mirela

AU - Demaine, Erik D.

AU - Flatland, Robin

AU - Langerman, Stefan

AU - O'Rourke, Joseph

AU - Pinciu, Val

AU - Ramaswami, Suneeta

AU - Sacristán, Vera

AU - Wuhrer, Stefanie

PY - 2011/1/1

Y1 - 2011/1/1

N2 - 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(n2) atom operations, which are performed in O(n) parallel steps. This improves on previous reconfiguration algorithms, which either use O(n2) parallel steps or do not respect the constraints mentioned above. In fact, in the settings 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.

AB - 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(n2) atom operations, which are performed in O(n) parallel steps. This improves on previous reconfiguration algorithms, which either use O(n2) parallel steps or do not respect the constraints mentioned above. In fact, in the settings 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.

KW - Control of robotic systems

KW - Mobile robots

KW - Modular robots

KW - Motion planning

KW - Path planning

UR - http://www.scopus.com/inward/record.url?scp=79951804818&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=79951804818&partnerID=8YFLogxK

U2 - 10.1017/S026357471000072X

DO - 10.1017/S026357471000072X

M3 - Article

AN - SCOPUS:79951804818

VL - 29

SP - 59

EP - 71

JO - Robotica

JF - Robotica

SN - 0263-5747

IS - 1 SPEC. ISSUE

ER -

Aloupis G, Collette S, Damian M, Demaine ED, Flatland R, Langerman S et al. Efficient constant-velocity reconfiguration of crystalline robots. Robotica. 2011 Jan 1;29(1 SPEC. ISSUE):59-71. https://doi.org/10.1017/S026357471000072X