Abstract

Provides an analysis of a 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 /spl gamma/ exists between two configurations a and b of the robot, we study the dependence of the failure probability to connect a and b on (i) the length of /spl gamma/, (ii) the distance function of /spl gamma/ from the obstacles, and (iii) the number of nodes N of the probabilistic roadmap constructed. Importantly, our results do not depend strongly on 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 bounds. We also compare, through this example, the different approaches to the analysis of the planning method.

Keywords

Probabilistic roadmapProbabilistic logicMotion planningPath (computing)Computer scienceFunction (biology)Probabilistic analysis of algorithmsMathematical optimizationSimple (philosophy)Probability density functionAlgorithmRobotMathematicsArtificial intelligenceStatistics

Affiliated Institutions

Related Publications

Swarm Intelligence

Eric Bonabeau , Marco Dorigo , Guy Théraulaz

Social insects--ants, bees, termites, and wasps--can be viewed as powerful problem-solving systems with sophisticated collective intelligence. Composed of simple interacting age...

1999 Oxford University Press eBooks 6323 citations

De-noising by soft-thresholding

David L. Donoho

Donoho and Johnstone (1994) proposed a method for reconstructing an unknown function f on [0,1] from noisy data d/sub i/=f(t/sub i/)+/spl sigma/z/sub i/, i=0, ..., n-1,t/sub i/=...

1995 IEEE Transactions on Information Theory 9389 citations

Publication Info

Year
2002
Type
article
Volume
4
Pages
3020-3025
Citations
415
Access
Closed

External Links

Download PDF (Free) View on DOI.org Semantic Scholar

Social Impact

Altmetric
PlumX Metrics

Social media, news, blog, policy document mentions

Citation Metrics

415
OpenAlex
41
Influential
109
CrossRef

Cite This

Lydia E. Kavraki, Mihail N. Kolountzakis, J.-C. Latombe (2002). Analysis of probabilistic roadmaps for path planning. Proceedings of IEEE International Conference on Robotics and Automation , 4 , 3020-3025. https://doi.org/10.1109/robot.1996.509171

Identifiers

DOI
10.1109/robot.1996.509171

Data Quality

Data completeness: 81%