Sample Complexity of Probabilistic Roadmaps via $\epsilon$-nets

Matthew Tsao, Kiril Solovey, Marco Pavone

We study fundamental theoretical aspects of probabilistic roadmaps (PRM) in the finite time (non-asymptotic) regime. In particular, we investigate how completeness and optimality g…