Reachable Distance Space: Efficient Sampling-Based Planning for Spatially Constrained Systems

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 plann...

Full description

Saved in:
Bibliographic Details
Published in:The International journal of robotics research 2010-06, Vol.29 (7), p.916-934
Main Authors: Xinyu Tang, Thomas, Shawna, Coleman, Phillip, Amato, Nancy M.
Format: Article
Language:English
Subjects:
Articulated
Computing time
Constraints
Degrees of freedom
Mathematical analysis
Robotics
Robots
Sampling
Subspaces
Topology
Vision systems
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 number of the robot’s degrees of freedom. In addition to supporting efficient sampling of configurations, 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 1,000 links in time comparable to open chain sampling, and we can generate samples for 1,000-link multi-loop systems of varying topologies in less than a second.
ISSN:0278-3649
1741-3176
DOI:10.1177/0278364909357643