The Robotics Institute

Carnegie Mellon Robotics Institute

Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

Abstract

Finding paths in high-dimensional spaces becomes difficult when we wish to optimize the cost of a path in addition to obeying feasibility constraints. Recently the T-RRT algorithm was presented as a method to plan in high-dimensional cost-spaces and it was shown to perform well across a variety of problems. However, since the T-RRT relies solely on sampling to explore the space, it has difficulty navigating cost-space chasms--narrow low-cost regions surrounded by increasing cost. Such chasms are particularly common in planning for manipulators because many useful cost functions induce narrow or lower-dimensional low-cost areas. This paper presents the GradienT-RRT algorithm, which combines the T-RRT with a local gradient method to bias the search toward lower-cost regions. GradienT-RRT is effective at navigating chasms because it explores low-cost regions that are too narrow to explore by sampling alone. We compare the performance of T-RRT and GradienT-RRT on planning problems involving cost functions defined in workspace, task space, and C-space. We find that GradienT-RRT outperforms T-RRT in terms of the cost of the final path while maintaining better or comparable computation time. We also find that the cost of paths generated by GradienT-RRT is far less sensitive to changes in a key parameter, making it easier to tune the algorithm. Finally, we conclude with a demonstration of GradienT-RRT on a planning-with-uncertainty task on the physical HERB robot.

Keywords

manipulation planning, planning with cost, planning with uncertainty, motion planning

Notes

Sponsor: LAAS-CNRS, NSF

Associated Center(s) / Consortia: Quality of Life Technology Center, National Robotics Engineering Center, and Center for the Foundations of Robotics

Associated Lab(s) / Group(s): Personal Robotics

Note: Differences from version published in ICRA 2011. Note: These changes have already been made to the PDF available on this site. 1. In algorithm 3, line 2: "c_j < c_i" is not the correct notation, it should be: "C(q_s) < C(q^{old}_s)" (Thanks to Konstantin Seiler for catching this one)

Text Reference

Dmitry Berenson, Thierry Simeon, and Siddhartha Srinivasa, "Addressing Cost-Space Chasms in Manipulation Planning," IEEE International Conference on Robotics and Automation (ICRA '11), May, 2011.

BibTeX Reference

@inproceedings{Berenson_2011_6798,
   author = "Dmitry Berenson and Thierry Simeon and Siddhartha Srinivasa",
   title = "Addressing Cost-Space Chasms in Manipulation Planning",
   booktitle = "IEEE International Conference on Robotics and Automation (ICRA '11)",
   month = "May",
   year = "2011",
   Notes = "Differences from version published in ICRA 2011. Note: These changes have already been made to the PDF available on this site. 1. In algorithm 3, line 2: "c_j < c_i" is not the correct notation, it should be: "C(q_s) < C(q^{old}_s)" (Thanks to Konstantin Seiler for catching this one)"
}

The Robotics Institute

Menu