This paper addresses the quality and optimality of solutions returned by sampling-based path planning algorithms, such as Probabilistic RoadMaps (PRM) and Rapidly-exploring Random Trees (RRT). It rigorously analyzes the asymptotic behavior of these algorithms, showing that their solutions converge almost surely to non-optimal values under mild technical conditions. The main contributions include the introduction of new algorithms, PRM* and RRT*, which are provably asymptotically optimal, meaning their solutions converge almost surely to the optimum. These algorithms maintain computational complexity within a constant factor of their probabilistically complete counterparts. The analysis leverages novel connections between sampling-based path planning algorithms and random geometric graphs, providing insights into probabilistic completeness, asymptotic optimality, and technical tools for algorithm analysis. The paper also discusses the extension to systems with differential constraints and the availability of open-source software implementing the new algorithms.This paper addresses the quality and optimality of solutions returned by sampling-based path planning algorithms, such as Probabilistic RoadMaps (PRM) and Rapidly-exploring Random Trees (RRT). It rigorously analyzes the asymptotic behavior of these algorithms, showing that their solutions converge almost surely to non-optimal values under mild technical conditions. The main contributions include the introduction of new algorithms, PRM* and RRT*, which are provably asymptotically optimal, meaning their solutions converge almost surely to the optimum. These algorithms maintain computational complexity within a constant factor of their probabilistically complete counterparts. The analysis leverages novel connections between sampling-based path planning algorithms and random geometric graphs, providing insights into probabilistic completeness, asymptotic optimality, and technical tools for algorithm analysis. The paper also discusses the extension to systems with differential constraints and the availability of open-source software implementing the new algorithms.