Home/Densification Strategies for Anytime Motion Planning over Large Dense Roadmaps

Densification Strategies for Anytime Motion Planning over Large Dense Roadmaps

Shushman Choudhury, Oren Salzman, Sanjiban Choudhury and Siddhartha Srinivasa
Conference Paper, 2017 IEEE International Conference on Robotics and Automation (ICRA), May, 2017

Download Publication (PDF)

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.


We consider the problem of computing shortest paths in a dense motion-planning roadmap G. We assume that n, the number of vertices of G, is very large. Thus, using any path-planning algorithm that directly searches G, running in O(VlogV + E) ~ O(n^2) time, becomes unacceptably expensive. We are therefore interested in anytime search to obtain successively shorter feasible paths and converge to the shortest path in G. Our key insight is to provide existing path-planning algorithms with a sequence of increasingly dense subgraphs of G. We study the space of all (r-disk) subgraphs of G. 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 G. Finally we empirically evaluate the performance of our strategies for random scenarios in R^2 and R^4 and on manipulation planning problems for a 7 DOF robot arm, and validate our analysis.

BibTeX Reference
title = {Densification Strategies for Anytime Motion Planning over Large Dense Roadmaps},
author = {Shushman Choudhury and Oren Salzman and Sanjiban Choudhury and Siddhartha Srinivasa},
booktitle = {2017 IEEE International Conference on Robotics and Automation (ICRA)},
keyword = {Motion Planning},
sponsor = {National Science Foundation IIS (#1409003), Toyota Motor Engineering & Manufacturing (TEMA), and the Office of Naval Research},
month = {May},
year = {2017},