This paper analyzes the asymptotic behavior of the cost of solutions returned by sampling-based motion planning algorithms, such as Probabilistic RoadMaps (PRM) and Rapidly-exploring Random Trees (RRT), as the number of samples increases. It shows that, under mild technical conditions, the cost of the solution returned by these algorithms converges almost surely to a non-optimal value. The paper introduces new algorithms, PRM* and RRT*, which are provably asymptotically optimal, meaning that the cost of the returned solution converges almost surely to the optimum. These algorithms are also shown to have computational complexity within a constant factor of their probabilistically complete but not asymptotically optimal counterparts. The analysis is based on novel connections between sampling-based path planning algorithms and the theory of random geometric graphs. The paper also discusses the limitations of existing algorithms and proposes new algorithms that are both asymptotically optimal and computationally efficient. The new algorithms are shown to perform well in both multiple-query and single-query settings. The paper concludes with a summary of the results and their implications for the field of motion planning.This paper analyzes the asymptotic behavior of the cost of solutions returned by sampling-based motion planning algorithms, such as Probabilistic RoadMaps (PRM) and Rapidly-exploring Random Trees (RRT), as the number of samples increases. It shows that, under mild technical conditions, the cost of the solution returned by these algorithms converges almost surely to a non-optimal value. The paper introduces new algorithms, PRM* and RRT*, which are provably asymptotically optimal, meaning that the cost of the returned solution converges almost surely to the optimum. These algorithms are also shown to have computational complexity within a constant factor of their probabilistically complete but not asymptotically optimal counterparts. The analysis is based on novel connections between sampling-based path planning algorithms and the theory of random geometric graphs. The paper also discusses the limitations of existing algorithms and proposes new algorithms that are both asymptotically optimal and computationally efficient. The new algorithms are shown to perform well in both multiple-query and single-query settings. The paper concludes with a summary of the results and their implications for the field of motion planning.