TY - GEN
T1 - Planning with reachable distances
AU - Tang, Xinyu
AU - Thomas, Shawna
AU - Amato, Nancy M.
PY - 2010
Y1 - 2010
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=77949867987&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=77949867987&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-00312-7_32
DO - 10.1007/978-3-642-00312-7_32
M3 - Conference contribution
AN - SCOPUS:77949867987
SN - 9783642003110
T3 - Springer Tracts in Advanced Robotics
SP - 517
EP - 531
BT - Algorithmic Foundations of Robotics VIII - Selected Contributions of the Eighth International Workshop on the Algorithmic Foundations of Robotics
T2 - 8th International Workshop on the Algorithmic Foundations of Robotics, WAFR
Y2 - 7 December 2008 through 9 December 2008
ER -