Geometric probability results for bounding path quality in sampling-based roadmaps after finite computation

Sampling-based algorithms provide efficient solutions to high-dimensional, geometrically complex motion planning problems. For these methods asymptotic results are known in terms of completeness and optimality. Previous work by the authors argued that such methods also provide probabilistic near-optimality after finite computation time using indications from Monte Carlo experiments. This work formalizes these guarantees and provides a bound on the probability of finding a near-optimal solution with PRM* after a finite number of iterations. This bound is proven for general-dimension Euclidean spaces and evaluated through simulation. These results are leveraged to create automated stopping criteria for PRM* and sparser near-optimal roadmaps, which have reduced running time and storage requirements.

I. Introduction and Related Work

While motion planning is PSPACE-hard [1], [2], sampling-based approaches can frequently provide efficient solutions in practice, even for high-dimensional, geometrically complex problems [3], [4]. Two families of methods have emerged. Approaches, such as the Probabilistic Roadmap Method (PRM), preprocess a configuration space -space) to create a structure useful for answering multiple queries [5]. Tree-based planners, such as the Rapidly-exploring Random Tree (RRT), are suited for single-query planning and kinodynamic systems [6], [7]. Many variants focus on quickly finding solutions and dealing with narrow passages [8]. Some approaches are tailored to returning high-clearance paths [9], or low cost solutions [10].