Sample Complexity of Probabilistic Roadmaps via ε-nets
share
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 and connection radius r>0. We develop the notion of (δ,ϵ)-completeness of the parameters , r, which indicates that for every motion-planning problem of clearance at least δ>0, PRM using , 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.
READ FULL TEXT