Back to Search
Start Over
Sampling-based Roadmap Planners are Probably Near-Optimal after Finite Computation
- Publication Year :
- 2014
-
Abstract
- Sampling-based motion planners have proven to be efficient solutions to a variety of high-dimensional, geometrically complex motion planning problems with applications in several domains. The traditional view of these approaches is that they solve challenges efficiently by giving up formal guarantees and instead attain asymptotic properties in terms of completeness and optimality. Recent work has argued based on Monte Carlo experiments that these approaches also exhibit desirable probabilistic properties in terms of completeness and optimality after finite computation. The current paper formalizes these guarantees. It proves a formal bound on the probability that solutions returned by asymptotically optimal roadmap-based methods (e.g., PRM*) are within a bound of the optimal path length I* with clearance {\epsilon} after a finite iteration n. This bound has the form P(|In - I* | {\leq} {\delta}I*) {\leq} Psuccess, where {\delta} is an error term for the length a path in the PRM* graph, In. This bound is proven for general dimension Euclidean spaces and evaluated in simulation. A discussion on how this bound can be used in practice, as well as bounds for sparse roadmaps are also provided.<br />Comment: 17 pages, 5 figures, 3 tables. Submitted to the Eleventh International Workshop on the Algorithmic Foundations of Robotics (WAFR 2014)
- Subjects :
- Computer Science - Robotics
Subjects
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.1404.2166
- Document Type :
- Working Paper