Sampling-based Algorithms for Optimal Motion Planning
TL;DR Proves that standard PRM and RRT do not converge to optimal paths, and introduces PRM*, RRG and RRT*, which connect each sample within a radius shrinking like (log n / n)^(1/d) and converge almost surely to the optimum at a constant-factor extra cost. In a cluttered 2D test, RRT averages about 1.5x the optimal cost while every RRT* run converges to it.
What they do
PRM and RRT find a feasible path with probability approaching one, but little was known about how good that path is as samples grow. This paper proves that PRM, RRT and k-nearest PRM with fixed k do not converge to the optimal cost. It then introduces PRM, RRG and RRT, which provably do (asymptotic optimality), at only a constant-factor increase in complexity.
How it works
- Shrinking connection radius. PRM* connects each sample to all vertices within r(n) = γ(log n / n)^(1/d), with γ above a threshold set by the dimension and the free-space volume, so about log n connections are attempted per vertex. The k-nearest variants connect to k log n neighbours, with k > e(1 + 1/d); k = 2e works for every problem.
- RRG grows like RRT but also connects each new vertex to every vertex in that shrinking ball, building an incremental roadmap with cycles.
- RRT* keeps a tree. A new vertex takes the nearby parent that gives the lowest cost from the root, then rewires nearby vertices through itself when that lowers their cost.
- Analysis uses random geometric graph theory. The thresholds for completeness and optimality match the percolation and connectivity thresholds of such graphs.
Results
- Theory: the new planners make O(log n) collision checks per iteration and run in O(n log n log^d m) time for n samples and m obstacles, against Ω(n log n + n log^d m) for RRT.
- Obstacle-free 2D, 500 trials: RRT ends close to √2 times the optimal cost with variance near 2.5. RRT* converges to the optimum with variance near zero.
- Cluttered 2D, 500 trials: RRT averages about 1.5x optimal and all RRT* runs reach the optimum, which lies in a different homotopy class from RRT’s usual solution.
- k-nearest sPRM with k from 5 to 15 does not converge to the optimum; PRM* does. Over up to one million iterations, the RRT*/RRT running-time ratio settles to a constant.
Limitations
The paper covers path planning only: straight-line connections in Euclidean space with no differential constraints, which are left to future work. The guarantees are asymptotic, holding almost surely as samples go to infinity. The radius constant γ depends on the free-space volume, which the k-nearest variants avoid. All experiments are in simulation, mostly in 2D, plus runs in 5 and 10 dimensions.
Figures
Abstract
During the last decade, sampling-based path planning algorithms, such as Probabilistic RoadMaps (PRM) and Rapidly-exploring Random Trees (RRT), have been shown to work well in practice and possess theoretical guarantees such as probabilistic completeness. However, little effort has been devoted to the formal analysis of the quality of the solution returned by such algorithms, e.g., as a function of the number of samples. The purpose of this paper is to fill this gap, by rigorously analyzing the asymptotic behavior of the cost of the solution returned by stochastic sampling-based algorithms as the number of samples increases. A number of negative results are provided, characterizing existing algorithms, e.g., showing that, under mild technical conditions, the cost of the solution returned by broadly used sampling-based algorithms converges almost surely to a non-optimal value. The main contribution of the paper is the introduction of new algorithms, namely, PRM* and RRT*, which are provably asymptotically optimal, i.e., such that the cost of the returned solution converges almost surely to the optimum. Moreover, it is shown that the computational complexity of the new algorithms is within a constant factor of that of their probabilistically complete (but not asymptotically optimal) counterparts. The analysis in this paper hinges on novel connections between stochastic sampling-based path planning algorithms and the theory of random geometric graphs.
Summaries are written automatically from each paper's text. Figures and videos come from the paper and its project page; all credit goes to the authors.