Abstract | ||
---|---|---|
We study fundamental theoretical aspects of probabilistic roadmaps (PRM) in the finite time (non-asymptotic) regime. In particular, we investigate how completeness and optimality guarantees of the approach are influenced by the underlying deterministic sampling distribution $\\mathcal{X}$ and connection radius r \u003e 0. We develop the notion of (δ,)-completeness of the parameters $\\mathcal{X}$,r, which indicates that for every motionplanning problem of clearance at least δ \u003e 0, PRM using $\\mathcal{X}$,r returns a solution no longer than 1+ϵ times the shortest δ-clear path. Leveraging the concept of ϵ -nets, we characterize in terms of lower and upper bounds the number of samples needed to guarantee (δ, ϵ)-completeness. This is in contrast with previous work which mostly considered the asymptotic regime in which the number of samples tends to infinity. In practice, we propose a sampling distribution inspired by -nets that achieves nearly the same coverage as grids while using fewer samples. |
Year | DOI | Venue |
---|---|---|
2020 | 10.1109/ICRA40945.2020.9196917 | ICRA |
DocType | Volume | Issue |
Conference | 2020 | 1 |
Citations | PageRank | References |
0 | 0.34 | 8 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Matthew Tsao | 1 | 0 | 2.37 |
Kiril Solovey | 2 | 71 | 10.30 |
Marco Pavone | 3 | 588 | 74.40 |