Measure theoretic analysis of probabilistic path planning

This paper presents a novel analysis of the probabilistic roadmap method (PRM) for path planning. We formulate the problem in terms of computing the transitive closure of a relation over a probability space, and give a bound on the expected number iterations of PRM required to find a path, in terms of the number of intermediate points and the probability of choosing a point from a certain set. Explicit geometric assumptions are not necessary to complete this analysis. As a result, the analysis provides some unification of previous work. We provide an upper bound which could be refined using details specific to a given problem. This bound is of the same form as that proved in previous analyses, but has simpler prerequisites and is proved on a more general class of problems. Using our framework, we analyze some new path-planning problems, 2k-degree-of-freedom kinodynamic point robots, polygonal robots with contact, and deformable robots with force field control. These examples make explicit use of generality in our approach that did not exist in previous frameworks.