On the probabilistic foundations of probabilistic roadmap planning

Hsu, David, Latombe, Jean-Claude and Kurniawati, Hanna (2006) On the probabilistic foundations of probabilistic roadmap planning. International Journal of Robotics Research, 25 7: 627-643. doi:10.1177/0278364906067174

Author Hsu, David
Latombe, Jean-Claude
Kurniawati, Hanna
Title On the probabilistic foundations of probabilistic roadmap planning
Journal name International Journal of Robotics Research   Check publisher's open access policy
ISSN 0278-3649
Publication date 2006-07-01
Sub-type Article (original research)
DOI 10.1177/0278364906067174
Open Access Status Not yet assessed
Volume 25
Issue 7
Start page 627
End page 643
Total pages 17
Place of publication London, United Kingdom
Publisher Sage
Language eng
Formatted 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 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.
Keyword Robotics
Motion planning
Randomized algorithms
Random sampling
Q-Index Code C1
Q-Index Status Provisional Code
Institutional Status Non-UQ

Document type: Journal Article
Sub-type: Article (original research)
Collection: School of Information Technology and Electrical Engineering Publications
Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 82 times in Thomson Reuters Web of Science Article | Citations
Scopus Citation Count Cited 107 times in Scopus Article | Citations
Google Scholar Search Google Scholar
Created: Tue, 15 Apr 2014, 06:53:35 EST by Ms Kimberley Nunes on behalf of Centre for Medical Diagnostic Technologies in Qld