  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 ${(\delta,\epsilon)}$-completeness of
the parameters ${\mathcal{X}, r}$, which indicates that for every
motion-planning problem of clearance at least ${\delta>0}$, PRM using
${\mathcal{X}, r}$ returns a solution no longer than ${1+\epsilon}$ times the
shortest ${\delta}$-clear path. Leveraging the concept of ${\epsilon}$-nets, we
characterize in terms of lower and upper bounds the number of samples needed to
guarantee ${(\delta,\epsilon)}$-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 ${\epsilon}$-nets that achieves nearly the same coverage as grids
while using significantly fewer samples.
