Proving infeasibility in motion planning

Motion planning is a fundamental problem in robotics that has received a lot of attention. The motion planning problem is NP-complete, but previous works in motion planning have been very successful in efficiently finding a valid path in motion planning problems. One class of solutions for solving high-dimensional motion planning problems is sampling-based algorithms. For motion planning algorithms, completeness is a crucial and desirable attribute. A complete motion planner returns a plan when one exists and also reports failure when no plan exists. However, complete motion planning is challenging, and many approaches aim for weaker notions of completeness. Most sampling-based motion planners are probabilistically complete which means when a feasible plan exists, they find the plan given enough time. But when a plan does not exist, they can run forever or until a timeout. Reporting failure, or proving infeasibility, when no plan exists is another side of the problem that has not been well-studied previously. This thesis focuses on finding infeasibility proofs in motion planning. An infeasibility proof is a closed manifold in the obstacle region of the configuration space that separates the start and goal into disconnected components of the free configuration space. We introduce two algorithms for generating infeasibility proofs. The first algorithm grows facets of the infeasibility proof manifold directly, and works for up-to 3-D configuration spaces. The second algorithm uses a learned manifold to generate the infeasibility proof, which works for up-to 4-D configuration spaces. We further extended the algorithm for up-to 5-D configuration spaces. The learned manifold not only helps with the construction of infeasibility proof but also helps with narrow passage motion planning. Our algorithm, Sample-Driven Connectivity Learning (SDCL), leverages this manifold to help sampling in narrow passages. Additionally, we prove that the learned manifold converges to an infeasibility proof exponentially. Combining prior approaches for sampling-based planning and our converging infeasibility proofs, we propose the term asymptotic completeness to describe the property of returning a plan or infeasibility proof in the limit. We compare the empirical convergence of different sampling strategies to validate our analysis.

Name thesis:degree_name

Doctor of Philosophy (Ph.D.)

Level thesis:degree_level

Doctoral

Discipline thesis:degree_discipline

Computer Science

Grantor dc:publisher

Colorado School of Mines. Arthur Lakes Library

Year dc:date.issued

2024

Author dc:creator

• Li, Sihui

Advisor dc:contributor.advisor

• Dantam, Neil T.

Committee members dc:contributor.committeemember

• Mehta, Dinesh P.
• Belviranli, Mehmet E.
• Kavraki, Lydia E.
• Petruska, Andrew J.

Statement dc:rights

• Copyright of the original work is retained by the author.

Language dc:language.iso

eng, English

Dc Identifier Other

T 9738

OAI identifier oai:identifier

oai:repository.mines.edu:11124/179290