Paper Info
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.
Year
DOI
Venue
2011
10.1017/S026357471000072X
Robotica
Keywords
DocType
Volume
universal reconfiguration,neighboring atom,crystalline robot,target configuration space,target configuration,constant velocity,constant number,n atom,efficient constant-velocity reconfiguration,parallel step,atom operation,previous reconfiguration algorithm
Journal
29
Issue
ISSN
Citations 
1
0263-5747
2
PageRank 
References 
Authors
0.36
23
11
Name
Order
Citations
PageRank
Greg Aloupis120026.50
S??bastien Collette220.36
Mirela Damian321228.18
Erik D. Demaine44624388.59
Robin Y. Flatland5695.89
Stefan Langerman6831101.66
Joseph O'Rourke71636439.71
Val Pinciu8346.21
Suneeta Ramaswami922823.87
Vera Sacrist??n1020.36
Stefanie Wuhrer1140534.51