Needle in a Haystack: Densification in Planning


We consider the problem of computing shortest paths in a dense motion-planning roadmap. We are interested in anytime search to obtain successively shorter feasible paths and converge to the shortest path in the roadmap. Our key insight is to provide existing path-planning algorithms with a sequence of increasingly dense subgraphs of the roadmap. We study the space of all (r-disk) subgraphs of the roadmap. We then formulate and present two densification strategies for traversing this space which exhibit complementary properties with respect to problem difficulty. This inspires a third, hybrid strategy which has favourable properties regardless of problem difficulty. This general approach is then demonstrated and analyzed using the specific case where a low-dispersion deterministic sequence is used to generate the samples used for the roadmap. Finally we empirically evaluate the performance of our strategies for random scenarios in R2 and R4 and on manipulation planning problems for a 7 DOF robot arm, and validate our analysis.

Related Publications

Densification Strategies for Anytime Motion Planning over Large Dense Roadmaps
Shushman Choudhury, Oren Salzman, Sanjiban Choudhury, Siddhartha Srinivasa
IEEE International Conference on Robotics and Automation May, 2017