Geometric Probability Results for Bounding Path Quality in Sampling-based Roadmaps after Finite Computation

TitleGeometric Probability Results for Bounding Path Quality in Sampling-based Roadmaps after Finite Computation
Publication TypeConference Paper
Year of Publication2015
AuthorsDobson, A, Moustakides, GV, Bekris, KE
Conference NameIEEE International Conference on Robotics and Automation (ICRA)
Date Published05/2015
Conference LocationSeattle, WA
Abstract

Sampling-based algorithms provide efficient solutions to high-dimensional, geometrically complex motion planning problems. For these methods asymptotic results are known in terms of completeness and optimality. Previous work by the authors argued that such methods also provide probabilistic near-optimality after finite computation time using indications from Monte Carlo experiments. This work
formalizes these guarantees and provides a bound on the probability of finding a near-optimal solution with PRM* after a finite number of iterations. This bound is proven for general-dimension Euclidean spaces and evaluated through simulation. These results are leveraged to create automated stopping criteria for PRM* and sparser
near-optimal roadmaps, which have reduced running time and storage requirements.

URLhttp://www.cs.rutgers.edu/~kb572/pubs/finite_prm.pdf