Skip to main content

Asymptotically optimal kinodynamic motion planning for self-reconfigurable robots

Publication ,  Journal Article
Reif, JH; Slee, S
Published in: Springer Tracts in Advanced Robotics
October 20, 2008

Self-reconfigurable robots are composed of many individual modules that can autonomously move to transform the shape and structure of the robot. In this paper we present a kinodynamically optimal algorithm for the following "x-axis to y-axis" reconfiguration problem: given a horizontal row of n modules, reconfigure that collection into a vertical column of n modules. The goal is to determine the sequence of movements of the modules that minimizes the movement time needed to achieve the desired reconfiguration of the modules. Prior work on self-reconfigurable (SR) robots assumed a constant velocity bound on module movement and so required time linear in n to solve this problem. In this paper we define an abstract model that assumes unit bounds on various physical properties of modules such as shape, aspect ratio, mass, and the maximum magnitude of force that an individual module can exert. We also define concrete instances of our abstract model similar to those found in the prior literature on reconfigurable robots, including various examples where the modules are cubes that are attached and can apply forces to neighboring cubes. In one of these concrete models, the cube's sides can contract and expand with controllable force, and in another the cubes can apply rotational torque to their neighbors. Our main result is a proof of tight Θ(√n) upper and lower bounds on the movement time for the above reconguration problem for concrete instances of our abstract model. This paper's analysis characterizes optimal reconfiguration movements in terms of basic laws of physics relating force, mass, acceleration, distance traveled, and movement time. A key property resulting from this is that through the simultaneous application of constant-bounded forces by a system of modules, certain modules in the system can achieve velocities exceeding any constant bounds. This delays modules with the least distance to travel when reconfiguring in order to accelerate modules that have the farthest to travel. We utilize this tradeoff in our algorithm for the x-axis to y-axis problem to achieve an O(√n) movement time. © 2008 Springer-Verlag Berlin Heidelberg.

Duke Scholars

Published In

Springer Tracts in Advanced Robotics

DOI

EISSN

1610-742X

ISSN

1610-7438

Publication Date

October 20, 2008

Volume

47

Start / End Page

457 / 472

Related Subject Headings

  • Industrial Engineering & Automation
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Reif, J. H., & Slee, S. (2008). Asymptotically optimal kinodynamic motion planning for self-reconfigurable robots. Springer Tracts in Advanced Robotics, 47, 457–472. https://doi.org/10.1007/978-3-540-68405-3_29
Reif, J. H., and S. Slee. “Asymptotically optimal kinodynamic motion planning for self-reconfigurable robots.” Springer Tracts in Advanced Robotics 47 (October 20, 2008): 457–72. https://doi.org/10.1007/978-3-540-68405-3_29.
Reif JH, Slee S. Asymptotically optimal kinodynamic motion planning for self-reconfigurable robots. Springer Tracts in Advanced Robotics. 2008 Oct 20;47:457–72.
Reif, J. H., and S. Slee. “Asymptotically optimal kinodynamic motion planning for self-reconfigurable robots.” Springer Tracts in Advanced Robotics, vol. 47, Oct. 2008, pp. 457–72. Scopus, doi:10.1007/978-3-540-68405-3_29.
Reif JH, Slee S. Asymptotically optimal kinodynamic motion planning for self-reconfigurable robots. Springer Tracts in Advanced Robotics. 2008 Oct 20;47:457–472.

Published In

Springer Tracts in Advanced Robotics

DOI

EISSN

1610-742X

ISSN

1610-7438

Publication Date

October 20, 2008

Volume

47

Start / End Page

457 / 472

Related Subject Headings

  • Industrial Engineering & Automation