On the Probabilistic Foundations of Probabilistic Roadmap Planning

Why is probabilistic roadmap (PRM) planning probabilistic? How
does the probability measure used for sampling a robot’s configuration space affect the performance of a PRM planner? These questions
have received little attention to date. This paper tries to fill this gap
and identify promising directions to improve future planners. It introduces the probabilistic foundations of PRM planning and examines
previous work in this context. It shows that the success of PRM planning depends mainly and critically on favorable “visibility” properties of a robot’s configuration space. A promising direction for
speeding up PRM planners is to infer partial knowledge of such
properties from both workspace geometry and information gathered
during roadmap construction, and to use this knowledge to adapt
the probability measure for sampling. This paper also shows that the
choice of the sampling source—pseudo-random or deterministic—
has small impact on a PRM planner’s performance, compared with
that of the sampling measure. These conclusions are supported by
both theoretical and empirical results.