{"id":{"repo_id":"colo-mines","oai_identifier":"oai:repository.mines.edu:11124/179290"},"canonical_url":"https://search.dev.ndltd.org/etd/colo-mines/oai:repository.mines.edu:11124/179290","repository":{"repo_id":"colo-mines","name":"Colorado School of Mines","base_url":"https://repository.mines.edu/server/oai/request"},"display":{"title":"Proving infeasibility in motion planning","abstract":"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.","abstract_html":"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.","abstract_has_math":false,"creators":["Li, Sihui"],"institution":"Colorado School of Mines. Arthur Lakes Library","degree_name":"Doctor of Philosophy (Ph.D.)","degree_level":"Doctoral","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":[],"advisors":["Dantam, Neil T."],"committee_chairs":[],"committee_members":["Mehta, Dinesh P.","Belviranli, Mehmet E.","Kavraki, Lydia E.","Petruska, Andrew J."],"year":2024,"date_issued":"2024","date_published":"2024","updated_at":"2026-07-24T01:42:45Z","subjects":[],"languages":["eng","English"],"rights":["Copyright of the original work is retained by the author."],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier.other","label":"Dc Identifier Other","values":["T 9738"],"render_values":[{"text":"T 9738","href":null,"code":true}]}]},"links":{"outbound_url":"https://hdl.handle.net/11124/179290","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Dantam, Neil T."]},{"key":"dc:contributor.committeemember","label":"Committee Member","values":["Mehta, Dinesh P.","Belviranli, Mehmet E.","Kavraki, Lydia E.","Petruska, Andrew J."]},{"key":"dc:creator","label":"Author","values":["Li, Sihui"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2025-02-04T22:48:55Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2025-02-04T22:48:55Z"]},{"key":"dc:date.issued","label":"Date","values":["2024"]},{"key":"dc:publisher","label":"Institution","values":["Colorado School of Mines. Arthur Lakes Library"]},{"key":"dc:type","label":"Dc Type","values":["Text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Doctoral"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Doctor of Philosophy (Ph.D.)"]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["Colorado School of Mines"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["English"]},{"key":"dc:language.iso","label":"Language (ISO)","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright of the original work is retained by the author."]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["Li_mines_0052E_12827.pdf"]},{"key":"dc:identifier.other","label":"Dc Identifier Other","values":["T 9738"]},{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://hdl.handle.net/11124/179290"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Includes bibliographical references.","2024 Spring."]},{"key":"dc:description.abstract","label":"Abstract","values":["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."]},{"key":"dc:format.medium","label":"Dc Format Medium","values":["born digital","doctoral dissertations"]},{"key":"dc:title","label":"Title","values":["Proving infeasibility in motion planning"]}]}],"canonical_facts":{"dc:contributor.advisor":["Dantam, Neil T."],"dc:contributor.committeemember":["Mehta, Dinesh P.","Belviranli, Mehmet E.","Kavraki, Lydia E.","Petruska, Andrew J."],"dc:creator":["Li, Sihui"],"dc:date.accessioned":["2025-02-04T22:48:55Z"],"dc:date.available":["2025-02-04T22:48:55Z"],"dc:date.issued":["2024"],"dc:description":["Includes bibliographical references.","2024 Spring."],"dc:description.abstract":["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."],"dc:format.medium":["born digital","doctoral dissertations"],"dc:identifier":["Li_mines_0052E_12827.pdf"],"dc:identifier.other":["T 9738"],"dc:identifier.uri":["https://hdl.handle.net/11124/179290"],"dc:language":["English"],"dc:language.iso":["eng"],"dc:publisher":["Colorado School of Mines. Arthur Lakes Library"],"dc:rights":["Copyright of the original work is retained by the author."],"dc:title":["Proving infeasibility in motion planning"],"dc:type":["Text"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Doctoral"],"thesis:degree_name":["Doctor of Philosophy (Ph.D.)"],"thesis:institution_name":["Colorado School of Mines"]},"updated_at":"2026-07-24T01:42:45Z"}