Name
Abstract | ||
|---|---|---|
AbstractRoadmaps constructed by many sampling-based motion planners coincide, in the absence of obstacles, with standard models of random geometric graphs RGGs. Those models have been studied for several decades and by now a rich body of literature exists analyzing various properties and types of RGGs. In their seminal work on optimal motion planning, Karaman and Frazzoli conjectured that a sampling-based planner has a certain property if the underlying RGG has this property as well. In this paper, we settle this conjecture and leverage it for the development of a general framework for the analysis of sampling-based planners. Our framework, which we call localization-tessellation, allows for easy transfer of arguments on RGGs from the free unit hypercube to spaces punctured by obstacles, which are geometrically and topologically much more complex. We demonstrate its power by providing alternative and arguably simple proofs for probabilistic completeness and asymptotic near-optimality of probabilistic roadmaps PRMs in Euclidean spaces. Furthermore, we introduce three variants of PRMs, analyze them using our framework, and discuss the implications of the analysis. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1177/0278364918802957 | Periodicals |
Keywords | DocType | Volume |
motion planning, sampling-based algorithms, probabilistic roadmaps, random geometric graphs, probabilistic completeness, asymptotic optimality | Conference | 37 |
Issue | ISSN | Citations |
10 | 0278-3649 | 4 |
PageRank | References | Authors |
0.41 | 38 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Kiril Solovey | 1 | 71 | 10.30 |
| Oren Salzman | 2 | 61 | 15.27 |
| Dan Halperin | 3 | 1291 | 105.20 |