Efficient Constant-Velocity Reconfiguration of Crystalline Robots

From National Research Council Canada

Download	View accepted manuscript: Efficient Constant-Velocity Reconfiguration of Crystalline Robots (PDF, 825 KiB)
DOI	Resolve DOI: https://doi.org/10.1017/S026357471000072X
Author	Search for: Aloupis, Greg; Search for: Collette, Sébastien; Search for: Damian, Mirela; Search for: Demaine, Erik D.; Search for: Robin, Flatland; Search for: Langerman, Stefan; Search for: O'Rourke, Joseph; Search for: Pinciu, Val; Search for: Ramaswami, Suneeta; Search for: Sacristán, Vera; Search for: Wuhrer, Stefanie
Format	Text, Article
Subject	Control of robotic systems; Mobile robots; Modular robots; Motion planning; Path planning
Abstract	In this paper we propose novel algorithms for reconfiguring modularrobots 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 2x2x2 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 [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.
Publication date	2011-01-14
In	Robotica 29, no. January 1 (14 January 2011): 59–71.
Language	English
Peer reviewed	Yes
NRC publication	This is a non-NRC publication "Non-NRC publications" are publications authored by NRC employees prior to their employment by NRC.
NPARC number	16335084
Export citation	Export as RIS
Report a correction	Report a correction (opens in a new tab)
Record identifier	a78fd73b-5de6-4a8d-b5b5-4b4b7c11ab31
Record created	2010-11-10
Record modified	2020-04-21

Date modified:: 2024-07-25