Analysis of probabilistic roadmaps for path planning

TLDR

Probabilistic roadmaps are widely used for path planning, yet their theoretical performance remains poorly understood. The paper analyzes the probabilistic roadmap method for path planning. The authors study how the failure probability of connecting two configurations depends on path length, clearance from obstacles, and roadmap size, and provide estimates for the required number of nodes to achieve a target failure probability while comparing different analytical approaches. The analysis demonstrates that the failure probability is largely insensitive to local irregularities, and the authors illustrate this with an example that estimates the necessary roadmap size and compares analytical approaches.

Abstract

We provide an analysis of a path planning method which uses probabilistic roadmaps. This method has proven very successful in practice, but the theoretical understanding of its performance is still limited. Assuming that a path /spl gamma/ exists between two configurations a and b of the robot, we study the dependence of the failure probability to connect a and b, on: 1) the length of /spl gamma/; 2) the distance function of /spl gamma/ from the obstacles; 3) the number of nodes N of the probabilistic roadmap constructed. Importantly, our results do not depend strongly on local irregularities of the configuration space, as was the case with previous analysis. These results are illustrated with a simple but illuminating example. In this example, we provide estimates for N, the principal parameter of the method, in order to achieve failure probability within prescribed bounds. We also compare, through this example, the different approaches to the analysis of the planning method.