Motion Planning Infeasibility Proof

Infeasibility Proof Manifold

Sampling-based motion planners are effective in high-dimensional spaces but are only probabilistically complete. Consequently, these planners cannot provide a definite answer if no plan exists, which is important for high-level scenarios, such as task-motion planning. This work focus on finding infeasibility guarantees for kinematic motion planning problems. We define motion planning infeasibility proof as a manifold in the configuration space that exists entirely in the obstacle region of the configuration space and separates the start and the goal. Starting from our first algorithm that constructs infeasibility proofs in the configuration space directly, now we have developed a learning-based algorithm to generate infeasibility proofs more efficiently. This work is still in progress.

Learning Motion Planning Infeasibility Proofs

Learning Infeasibility Proof

We treat the samples in the two search trees/graph components as two classes and learn a classifier. Geometrically, the classifier is a separating manifold for the two classes of samples. The learned manifold fits into the obstacle region as more points are sampled, and eventually becomes an infeasibility proof when the manifold is entirely in the obstacle region of the configuration space.

Constructing Infeasibility Proofs Directly

We have presented a general method for motion planning infeasibility proofs and demonstrated the approach on a low-dimensional manipulator. Our approach progressively grows volumes in the obstacle region via sampling and optimization and then attempts to find a closed polytope separating the start and goal via constraint solving.

2D Infeasibility Proof
3D Infeasibility Proof
Infeasibility Proof in Jaco arm's configuration space