Densification Strategies for Anytime Motion Planning over Large Dense Roadmaps

Abstract

We consider the problem of computing shortest paths in a dense motion-planning roadmap $\mathcal{G}$. We assume that~$n$, the number of vertices of $\mathcal{G}$, is very large. Thus, using any path-planning algorithm that directly searches $\mathcal{G}$, running in $O(V\text{log}V+E)\approx 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 $\mathcal{G}$. Our key insight is to provide existing path-planning algorithms with a sequence of increasingly dense subgraphs of $\mathcal{G}$. We study the space of all ($r$-disk) subgraphs of $\mathcal{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 $\mathcal{G}$. Finally we empirically evaluate the performance of our strategies for random scenarios in ${\mathbb{R}}^2$ and ${\mathbb{R}}^4$ and on manipulation planning problems for a 7 DOF robot arm, and validate our analysis.

Submitted to The International Conference on Robotics and Automation (ICRA) 2017

References in corpus (1)

• Informed RRT*: Optimal Sampling-based Path Planning Focused via Direct Sampling of an Admissible Ellipsoidal Heuristic