{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,15]],"date-time":"2026-07-15T17:30:44Z","timestamp":1784136644074,"version":"3.55.0"},"reference-count":86,"publisher":"SAGE Publications","issue":"10","license":[{"start":{"date-parts":[[2024,2,2]],"date-time":"2024-02-02T00:00:00Z","timestamp":1706832000000},"content-version":"vor","delay-in-days":365,"URL":"http:\/\/www.sagepub.com\/licence-information-for-chorus"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["IIS-1849348"],"award-info":[{"award-number":["IIS-1849348"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["journals.sagepub.com"],"crossmark-restriction":true},"short-container-title":["The International Journal of Robotics Research"],"published-print":{"date-parts":[[2023,9]]},"abstract":"<jats:p>We present a learning-based approach to prove infeasibility of kinematic motion planning problems. 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. We apply data generated during multi-directional sampling-based planning (such as PRM) to a machine learning approach to construct an infeasibility proof. 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 train the manifold using common machine learning techniques and then triangulate the manifold into a polytope to prove containment in the obstacle region. Under assumptions about the hyper-parameters and robustness of configuration space optimization, the output is either an infeasibility proof or a motion plan in the limit. We demonstrate proof construction for up to 4-DOF configuration spaces. A large part of the algorithm is parallelizable, which offers potential to address higher dimensional configuration spaces.<\/jats:p>","DOI":"10.1177\/02783649231154674","type":"journal-article","created":{"date-parts":[[2023,2,3]],"date-time":"2023-02-03T02:20:17Z","timestamp":1675390817000},"page":"938-956","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":7,"title":["A sampling and learning framework to prove motion planning infeasibility"],"prefix":"10.1177","volume":"42","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1766-4316","authenticated-orcid":false,"given":"Sihui","family":"Li","sequence":"first","affiliation":[{"name":"Department of Computer Science, Colorado School of Mines, Golden, CO, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0907-2241","authenticated-orcid":false,"given":"Neil T.","family":"Dantam","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Colorado School of Mines, Golden, CO, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"179","published-online":{"date-parts":[[2023,2,2]]},"reference":[{"key":"bibr1-02783649231154674","doi-asserted-by":"publisher","DOI":"10.1111\/1467-8659.00479"},{"key":"bibr2-02783649231154674","doi-asserted-by":"crossref","unstructured":"Amato NM, Wu Y (1996) A randomized roadmap method for path and manipulation planning. In: 1996. IEEE International Conference on Robotics and Automation (ICRA), Vol. 1, pp. 113\u2013120.","DOI":"10.1109\/ROBOT.1996.503582"},{"key":"bibr3-02783649231154674","doi-asserted-by":"publisher","DOI":"10.1109\/CDC40024.2019.9030133"},{"key":"bibr4-02783649231154674","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA48506.2021.9561949"},{"key":"bibr5-02783649231154674","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2001.932865"},{"key":"bibr6-02783649231154674","doi-asserted-by":"publisher","DOI":"10.1109\/70.704220"},{"key":"bibr7-02783649231154674","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2009.5152399"},{"key":"bibr8-02783649231154674","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2013.6696513"},{"key":"bibr9-02783649231154674","doi-asserted-by":"publisher","DOI":"10.1017\/9781108297806"},{"key":"bibr10-02783649231154674","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-013-9557-2"},{"key":"bibr11-02783649231154674","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2001.932820"},{"key":"bibr12-02783649231154674","doi-asserted-by":"publisher","DOI":"10.1177\/0278364908097884"},{"key":"bibr13-02783649231154674","doi-asserted-by":"publisher","DOI":"10.1145\/1961189.1961199"},{"key":"bibr14-02783649231154674","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2016.2521373"},{"key":"bibr15-02783649231154674","doi-asserted-by":"publisher","DOI":"10.1109\/tro.2011.2160466"},{"key":"bibr16-02783649231154674","doi-asserted-by":"publisher","DOI":"10.1109\/MRA.2012.2205651"},{"key":"bibr17-02783649231154674","doi-asserted-by":"publisher","DOI":"10.1177\/0278364920931948"},{"key":"bibr18-02783649231154674","volume-title":"Encyclopedia of Robotics","author":"Dantam NT","year":"2020"},{"key":"bibr19-02783649231154674","doi-asserted-by":"publisher","DOI":"10.1177\/0278364918761570"},{"key":"bibr20-02783649231154674","doi-asserted-by":"publisher","DOI":"10.1177\/0278364913498292"},{"key":"bibr21-02783649231154674","doi-asserted-by":"publisher","DOI":"10.1145\/174147.174150"},{"key":"bibr22-02783649231154674","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-25116-0_9"},{"key":"bibr23-02783649231154674","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA48506.2021.9560934"},{"key":"bibr24-02783649231154674","doi-asserted-by":"publisher","DOI":"10.1177\/02783649211056967"},{"key":"bibr25-02783649231154674","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA40945.2020.9197291"},{"key":"bibr26-02783649231154674","doi-asserted-by":"publisher","DOI":"10.3233\/AIC-150697"},{"key":"bibr27-02783649231154674","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-39658-1_57"},{"key":"bibr28-02783649231154674","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-17283-0"},{"key":"bibr29-02783649231154674","doi-asserted-by":"publisher","DOI":"10.1146\/annurev-control-091420-084139"},{"key":"bibr30-02783649231154674","first-page":"1311","volume-title":"Handbook of Discrete and Computational Geometry","author":"Halperin D","year":"2017"},{"key":"bibr31-02783649231154674","doi-asserted-by":"publisher","DOI":"10.1177\/0278364918780999"},{"key":"bibr32-02783649231154674","doi-asserted-by":"publisher","DOI":"10.1007\/s003710050126"},{"key":"bibr33-02783649231154674","doi-asserted-by":"publisher","DOI":"10.1177\/0278364913507795"},{"key":"bibr34-02783649231154674","first-page":"2","volume":"6","author":"Hauser KK","year":"2013","journal-title":"Proceedings of Robotics: Science and Systems"},{"key":"bibr35-02783649231154674","volume-title":"Marching Triangles: Delaunay Implicit Surface Triangulation","author":"Hilton A","year":"1997"},{"key":"bibr36-02783649231154674","doi-asserted-by":"publisher","DOI":"10.1177\/027836402320556421"},{"key":"bibr37-02783649231154674","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2019.8793946"},{"key":"bibr38-02783649231154674","volume-title":"GUDHI User and Reference Manual","author":"Jamin C","year":"2020","edition":"3"},{"key":"bibr39-02783649231154674","doi-asserted-by":"publisher","DOI":"10.1177\/0278364917714338"},{"key":"bibr40-02783649231154674","doi-asserted-by":"publisher","DOI":"10.1177\/0278364915577958"},{"key":"bibr41-02783649231154674","volume-title":"Meshing Submanifolds Using Coxeter Triangulations","author":"Kachanovich S","year":"2019"},{"key":"bibr42-02783649231154674","doi-asserted-by":"publisher","DOI":"10.1177\/0278364913484072"},{"key":"bibr43-02783649231154674","doi-asserted-by":"publisher","DOI":"10.1177\/0278364911406761"},{"key":"bibr44-02783649231154674","doi-asserted-by":"publisher","DOI":"10.1109\/38.909016"},{"key":"bibr45-02783649231154674","doi-asserted-by":"publisher","DOI":"10.1109\/70.508439"},{"key":"bibr46-02783649231154674","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2015.7139535"},{"key":"bibr47-02783649231154674","doi-asserted-by":"publisher","DOI":"10.1177\/0278364919868530"},{"key":"bibr48-02783649231154674","unstructured":"Kraft D (1988) A software package for sequential quadratic programming. Oberpfaffenhofen: Institut f\u00fcr Dynamik der Flugsysteme. Technical Report DFVLR-FB 88-28."},{"key":"bibr49-02783649231154674","doi-asserted-by":"crossref","unstructured":"Kuffner JJ, LaValle SM (2000) RRT-connect: An efficient approach to single-query path planning. In: IEEE International Conference on Robotics and Automation (ICRA), Vol. 2, pp. 995\u20131001.","DOI":"10.1109\/ROBOT.2000.844730"},{"key":"bibr50-02783649231154674","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2018.8593947"},{"key":"bibr51-02783649231154674","first-page":"297","volume-title":"Algorithmic Foundations of Robotics VI","author":"Ladd AM","year":"2004"},{"key":"bibr52-02783649231154674","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.1991.131763"},{"key":"bibr53-02783649231154674","doi-asserted-by":"publisher","DOI":"10.1177\/0278364915619022"},{"key":"bibr54-02783649231154674","volume-title":"Rapidly-Exploring Random Trees: A New Tool for Path Planning","author":"LaValle SM","year":"1998"},{"key":"bibr55-02783649231154674","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511546877"},{"key":"bibr56-02783649231154674","doi-asserted-by":"publisher","DOI":"10.1109\/IROS45743.2020.9340804"},{"key":"bibr57-02783649231154674","doi-asserted-by":"publisher","DOI":"10.15607\/RSS.2021.XVII.064"},{"key":"bibr58-02783649231154674","doi-asserted-by":"publisher","DOI":"10.1177\/0278364915614386"},{"key":"bibr59-02783649231154674","doi-asserted-by":"publisher","DOI":"10.1016\/S0005-1098(98)00193-9"},{"key":"bibr60-02783649231154674","unstructured":"Makino H (1982) Assembly robot. US Patent 4,341,502."},{"key":"bibr61-02783649231154674","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2012.6225300"},{"key":"bibr62-02783649231154674","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA48506.2021.9562053"},{"key":"bibr63-02783649231154674","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2004.1308111"},{"key":"bibr64-02783649231154674","doi-asserted-by":"publisher","DOI":"10.1163\/156855308X392654"},{"key":"bibr65-02783649231154674","doi-asserted-by":"publisher","DOI":"10.1177\/0278364915594679"},{"key":"bibr66-02783649231154674","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2012.6225337"},{"key":"bibr67-02783649231154674","doi-asserted-by":"publisher","DOI":"10.1177\/0278364911429335"},{"key":"bibr68-02783649231154674","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2005.847599"},{"key":"bibr69-02783649231154674","doi-asserted-by":"publisher","DOI":"10.1007\/s10703-008-0058-5"},{"key":"bibr70-02783649231154674","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24743-2_32"},{"key":"bibr71-02783649231154674","doi-asserted-by":"publisher","DOI":"10.1109\/LRA.2019.2895845"},{"key":"bibr72-02783649231154674","unstructured":"Shkolnik A, Tedrake R (2011) Sample-based planning with volumes in configuration space. arXiv preprint arXiv:1109.3145."},{"key":"bibr73-02783649231154674","doi-asserted-by":"publisher","DOI":"10.1163\/156855300741960"},{"key":"bibr74-02783649231154674","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2014.6906922"},{"key":"bibr75-02783649231154674","doi-asserted-by":"publisher","DOI":"10.1142\/S0219843605000545"},{"key":"bibr76-02783649231154674","doi-asserted-by":"publisher","DOI":"10.1177\/0278364908098457"},{"key":"bibr77-02783649231154674","unstructured":"Thomason W, Knepper RA (2019) A unified sampling-based approach to integrated task and motion planning. In: International Symposium on Robotics Research."},{"key":"bibr78-02783649231154674","unstructured":"Toussaint M (2015) Logic-geometric programming: an optimization-based approach to combined task and motion planning. In: Twenty-Fourth International Joint Conference on Artificial Intelligence."},{"key":"bibr79-02783649231154674","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-28619-4_43"},{"key":"bibr80-02783649231154674","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-43089-4_34"},{"key":"bibr81-02783649231154674","doi-asserted-by":"publisher","DOI":"10.1109\/RCAR.2016.7784090"},{"key":"bibr82-02783649231154674","doi-asserted-by":"publisher","DOI":"10.1109\/LRA.2019.2894861"},{"key":"bibr83-02783649231154674","doi-asserted-by":"publisher","DOI":"10.1007\/BF01530890"},{"key":"bibr84-02783649231154674","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068417000321"},{"key":"bibr85-02783649231154674","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2007.4399064"},{"key":"bibr86-02783649231154674","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-68405-3_17"}],"container-title":["The International Journal of Robotics Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/02783649231154674","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/full-xml\/10.1177\/02783649231154674","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/02783649231154674","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/02783649231154674","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T10:16:58Z","timestamp":1777457818000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/02783649231154674"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,2,2]]},"references-count":86,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2023,9]]}},"alternative-id":["10.1177\/02783649231154674"],"URL":"https:\/\/doi.org\/10.1177\/02783649231154674","relation":{},"ISSN":["0278-3649","1741-3176"],"issn-type":[{"value":"0278-3649","type":"print"},{"value":"1741-3176","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,2,2]]}}}