Optimal kinodynamic motion planning for 2D reconfiguration of self-reconfigurable robots


Conference Paper

A self-reconfigurable (SR) robot is one composed of many small modules that autonomously act to change the shape and structure of the robot. In this paper we consider a general class of SR robot modules that have rectilinear shape that can be adjusted between fixed dimensions, can transmit forces to their neighbors, and can apply additional forces of unit maximum magnitude to their neighbors. We present a kinodynamically optimal algorithm for general reconfiguration between any two distinct, 2D connected configurations of n SR robot modules. The algorithm uses a third dimension as workspace during reconfiguration. This entire movement is achieved within O( √ n) movement time in the worst case, which is the asymptotically optimal time bound. The only prior reconfiguration algorithm achieving this time bound was restricted to linearly arrayed start and finish configurations (known as the "x-axis to y-axis problem"). All other prior work on SR robots assumed a constant velocity bound on module movement and so required at least time linear in n to do the reconfiguration.

Duke Authors

Cited Authors

  • Reif, J; Slee, S

Published Date

  • January 1, 2008

Published In

  • Robotics: Science and Systems

Volume / Issue

  • 3 /

Start / End Page

  • 153 - 160

Electronic International Standard Serial Number (EISSN)

  • 2330-765X

International Standard Serial Number (ISSN)

  • 2330-7668

International Standard Book Number 13 (ISBN-13)

  • 9780262524841

Citation Source

  • Scopus