Paper Info
Title
The critical radius in sampling-based motion planning
Abstract
AbstractWe develop a new analysis of sampling-based motion planning in Euclidean space with uniform random sampling, which significantly improves upon the celebrated result of Karaman and Frazzoli and subsequent work. In particular, we prove the existence of a critical connection radius proportional to Θ ( n − 1 / d ) for n samples and d dimensions: below this value the planner is guaranteed to fail (similarly shown by Karaman and Frazzoli). More importantly, for larger radius values the planner is asymptotically (near-)optimal. Furthermore, our analysis yields an explicit lower bound of 1 − O ( n − 1 ) on the probability of success. A practical implication of our work is that asymptotic (near-)optimality is achieved when each sample is connected to only Θ ( 1 ) neighbors. This is in stark contrast to previous work that requires Θ ( log n ) connections, which are induced by a radius of order ( log n n ) 1 / d . Our analysis applies to the probabilistic roadmap method (PRM), as well as a variety of “PRM-based” planners, including RRG, FMT*, and BTT. Continuum percolation plays an important role in our proofs. Lastly, we develop similar theory for all the aforementioned planners when constructed with deterministic samples, which are then sparsified in a randomized fashion. We believe that this new model, and its analysis, is interesting in its own right.
Year
DOI
Venue
2020
10.1177/0278364919859627
Periodicals
Keywords
Field
DocType
Motion planning, sampling-based algorithms, probabilistic roadmaps, random geometric graphs, continuum percolation, probabilistic completeness, asymptotic optimality
Motion planning,Control theory,Critical radius,Probabilistic roadmaps,Algorithm,Euclidean space,Sampling (statistics),Mathematics
Journal
Volume
Issue
ISSN
39
2-3
0278-3649
Citations 
PageRank 
References 
2
0.39
0
Authors
2
Name
Order
Citations
PageRank
Kiril Solovey17110.30
Michal Kleinbort272.21