Analysis of probabilistic roadmaps for path planning

We pro,ide an analysis of a recent 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; 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 gamma; 2) the distance function of gamma from the obstacles; 3) the number of nodes N of the probabilistic roadmap constructed. Importantly, our results do not depend strongly an 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 hounds, We also compare, through this example. the different approaches to the analysis of the planning method.