On the Probabilistic Foundations of Probabilistic Roadmap Planning

TLDR

Probabilistic roadmap planning’s probabilistic nature and the influence of the sampling probability measure on performance have received little attention. The paper aims to fill this gap by identifying promising directions to improve future PRM planners, notably by inferring partial visibility properties from workspace geometry and roadmap data to adapt the sampling probability measure. The authors introduce the probabilistic foundations of PRM planning, examine prior work, and propose inferring partial visibility properties from workspace geometry and roadmap data to adapt the sampling measure. The study finds that PRM success hinges on favorable visibility properties of the configuration space, that the sampling source has little effect compared to the sampling measure, and that these conclusions are supported by theory and experiments.

Abstract

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.