Personal tools
You are here: Home Projects In-house Projects The Critical Radius in Sampling-based Motion Planning The Critical Radius in Sampling-based Motion Planning
« July 2018 »
July
SuMoTuWeThFrSa
1234567
891011121314
15161718192021
22232425262728
293031
Log in


Forgot your password?
 

The Critical Radius in Sampling-based Motion Planning

Abstract

prm
PRM-based planners to which our analysis applies. Roughly
speaking, arrow from “A” to “B” indicates that theoretical properties of “A”
extend to “B”, or that the latter maintains “A” as a substructure.

We 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 (2011) and subsequent work. Particularly, we prove the existence of a critical connection radius proportional to Θ(n^{-1/d}) for samples and d dimensions: Below this value the planner is guaranteed to fail (similarly shown by the aforementioned work, ibid.). 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 which requires Θ(log n) connections, that are induced by a radius of order (log n / n)^{1/d}. Our analysis is not restricted to PRM and applies to a variety of “PRM-based” planners, including RRG, FMT* and BTT. Continuum percolation plays an important role in our proofs.

Links

  • Kiril Solovey and Michal Kleinbort, “The Critical Radius in Sampling-based Motion Planning”,
    Robotics: Science and Systems, 2018 [link].

Contacts

Kiril Solovey home icon contact
Michal Kleinbort http://acg.cs.tau.ac.il/danhalperin contact
Document Actions