Addressing Cost-Space Chasms in Manipulation Planning

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.