Sampling-based algorithms for optimal motion planning

Analysis

Why This Paper Matters

Sampling-based motion planning algorithms such as probabilistic roadmaps (PRM) and rapidly exploring random trees (RRT) had become workhorses in robotics due to their practical success and probabilistic completeness. However, the community lacked a rigorous understanding of solution quality—specifically, how the cost of returned paths behaves as the number of samples grows. This paper by Karaman and Frazzoli filled that gap by providing a formal asymptotic analysis, revealing that widely used algorithms converge to suboptimal solutions under mild conditions.

The introduction of PRM* and RRT* marked a paradigm shift: for the first time, sampling-based planners were shown to be provably asymptotically optimal while retaining computational efficiency within a constant factor of their predecessors. This bridged theory and practice, giving practitioners confidence that increasing samples yields arbitrarily good solutions. The paper's use of random geometric graph theory also opened new avenues for analyzing sampling-based algorithms.

With over 5,900 citations, the work has become foundational in robot motion planning and has influenced areas such as autonomous driving, manipulation, and even reinforcement learning where sampling-based optimization is relevant.

Technical Contributions

• Negative results for existing algorithms: Under mild technical conditions, the cost of solutions returned by PRM and RRT converges almost surely to a non-optimal value, characterizing their limitations.
• Asymptotically optimal algorithms: PRM* and RRT* are introduced with proofs that their solution cost converges almost surely to the optimum as samples increase.
• Complexity analysis: The new algorithms are shown to have computational complexity within a constant factor of their probabilistically complete counterparts, ensuring practicality.
• Random geometric graph connections: The analysis leverages novel links between sampling-based planning and random geometric graph theory, providing a rigorous mathematical foundation.

Results

The paper establishes that existing algorithms like PRM and RRT are not asymptotically optimal—their solution costs converge to a non-optimal value almost surely. In contrast, PRM* and RRT* are proven to converge almost surely to the optimal cost. The computational complexity of the new algorithms is within a constant factor of the original algorithms, meaning the asymptotic optimality comes at no significant increase in asymptotic computational cost. These results are derived under mild technical conditions on the configuration space and cost function.

Significance

This work fundamentally changed the theoretical landscape of sampling-based motion planning by introducing asymptotic optimality as a desirable and achievable property. It spurred a wave of research on optimal sampling-based planners, variants (e.g., RRT*-Smart, Informed RRT*), and applications in complex robotic systems. The connections to random geometric graphs have also enriched both fields. Beyond robotics, the paper's rigorous approach to analyzing stochastic algorithms informs the broader AI community, particularly in reinforcement learning and optimization, where sampling-based methods are prevalent. Its high citation count attests to its lasting impact on both theory and practice.