Efficient Constant-Velocity Reconfiguration of Crystalline Robots

Download
  1. (PDF, 543 KB)
  2. Get@NRC: Efficient Constant-Velocity Reconfiguration of Crystalline Robots (Opens in a new window)
DOIResolve DOI: http://doi.org/10.1017/S026357471000072X
AuthorSearch for: ; Search for: ; Search for: ; Search for: ; Search for: ; Search for: ; Search for: ; Search for: ; Search for: ; Search for: ; Search for:
TypeArticle
Journal titleRobotica
Volume29
IssueJanuary 1
Pages5971; # of pages: 13
SubjectControl of robotic systems; Mobile robots; Modular robots; Motion planning; Path planning
AbstractIn 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
LanguageEnglish
Peer reviewedYes
NRC publication
This is a non-NRC publication

"Non-NRC publications" are publications authored by NRC employees prior to their employment by NRC.

NPARC number16335084
Export citationExport as RIS
Report a correctionReport a correction
Record identifiera78fd73b-5de6-4a8d-b5b5-4b4b7c11ab31
Record created2010-11-10
Record modified2016-05-09
Bookmark and share
  • Share this page with Facebook (Opens in a new window)
  • Share this page with Twitter (Opens in a new window)
  • Share this page with Google+ (Opens in a new window)
  • Share this page with Delicious (Opens in a new window)
Date modified: