A robot configuration \(\textbf {x}_k\)  is an \(\epsilon -\) safe configuration with respect to an obstacle location \(\textbf {s}\) , if the probability of collision is such that \(P\left(\mathcal {C}_{\textbf {x}_k,\textbf {s}}\right) \le 1 - \epsilon \) .

For example, a \(0.99-\) safe configuration implies that the probability of this configuration colliding with the obstacle is at most \(0.01\) . We use the sampling based Probabilistic Roadmap (PRM) [1]} to compute motion plans. As a result we can only guarantee probabilistic completeness for returning \(\epsilon -\) safe configurations since the PRM motion planner is probabilistically complete [2]}, that is the probability of failure decays to zero exponentially with the number of samples used in the construction of the roadmap. The failure to find an \(\epsilon -\) safe configuration might be because such a configuration indeed does not exist or simply because there were not enough samples.
