Planning with reachable distances

Xinyu Tang, Shawna Thomas, Nancy M. Amato

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Motion planning for spatially constrained robots is difficult due to additional constraints placed on the robot, such as closure constraints for closed chains or requirements on end effector placement for articulated linkages. It is usually computationally too expensive to apply sampling-based planners to these problems since it is difficult to generate valid configurations. We overcome this challenge by redefining the robot's degrees of freedom and constraints into a new set of parameters, called reachable distance space (RD-space), in which all configurations lie in the set of constraint-satisfying subspaces. This enables us to directly sample the constrained subspaces with complexity linear in the robot's number of degrees of freedom. In addition to supporting efficient sampling, we show that the RD-space formulation naturally supports planning, and in particular, we design a local planner suitable for use by sampling-based planners. We demonstrate the effectiveness and efficiency of our approach for several systems including closed chain planning with multiple loops, restricted end effector sampling, and on-line planning for drawing/sculpting. We can sample single-loop closed chain systems with 1000 links in time comparable to open chain sampling, and we can generate samples for 1000-link multi-loop systems of varying topology in less than a second.

Original languageEnglish (US)
Title of host publicationAlgorithmic Foundations of Robotics VIII - Selected Contributions of the Eighth International Workshop on the Algorithmic Foundations of Robotics
Pages517-531
Number of pages15
DOIs
StatePublished - 2010
Externally publishedYes
Event8th International Workshop on the Algorithmic Foundations of Robotics, WAFR - Guanajuato, Mexico
Duration: Dec 7 2008Dec 9 2008

Publication series

NameSpringer Tracts in Advanced Robotics
Volume57
ISSN (Print)1610-7438
ISSN (Electronic)1610-742X

Other

Other8th International Workshop on the Algorithmic Foundations of Robotics, WAFR
CountryMexico
CityGuanajuato
Period12/7/0812/9/08

ASJC Scopus subject areas

  • Electrical and Electronic Engineering
  • Artificial Intelligence

Fingerprint Dive into the research topics of 'Planning with reachable distances'. Together they form a unique fingerprint.

Cite this