Probabilistically Complete Planning with End-Effector Pose Constraints

We present a proof for the probabilistic completeness of RRT-based algorithms when planning with constraints on end-effector pose. Pose constraints can induce lower-dimensional constraint manifolds in the configuration space of the robot, making rejection sampling techniques infeasible. RRT-based algorithms can overcome this problem by using the sample-project method: sampling coupled with a projection operator to move configuration space samples onto the constraint manifold. Until now it was not known whether the sample-project method produces adequate coverage of the constraint manifold to guarantee probabilistic completeness. The proof presented in this paper guarantees probabilistic completeness for a class of RRT-based algorithms given an appropriate projection operator. This proof is valid for constraint manifolds of any fixed dimensionality.