Sample Complexity of Probabilistic Roadmaps via $ε$-nets
This work addresses theoretical gaps in motion planning algorithms for robotics, offering finite-time guarantees that are incremental improvements over asymptotic analyses.
The paper tackles the problem of providing finite-time completeness and optimality guarantees for probabilistic roadmaps (PRM) in motion planning, by introducing the notion of (δ,ε)-completeness and using ε-nets to derive lower and upper bounds on sample complexity, with a practical sampling distribution that achieves similar coverage to grids using significantly fewer samples.
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>0}$. We develop the notion of ${(δ,ε)}$-completeness of the parameters ${\mathcal{X}, r}$, which indicates that for every motion-planning problem of clearance at least ${δ>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 significantly fewer samples.