{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T16:15:43Z","timestamp":1743005743376,"version":"3.40.3"},"publisher-location":"Cham","reference-count":49,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783031210891"},{"type":"electronic","value":"9783031210907"}],"license":[{"start":{"date-parts":[[2022,12,15]],"date-time":"2022-12-15T00:00:00Z","timestamp":1671062400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2022,12,15]],"date-time":"2022-12-15T00:00:00Z","timestamp":1671062400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023]]},"DOI":"10.1007\/978-3-031-21090-7_18","type":"book-chapter","created":{"date-parts":[[2022,12,14]],"date-time":"2022-12-14T18:11:35Z","timestamp":1671041495000},"page":"294-311","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Exponential Convergence of\u00a0Infeasibility Proofs for\u00a0Kinematic Motion Planning"],"prefix":"10.1007","author":[{"given":"Sihui","family":"Li","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Neil T.","family":"Dantam","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,12,15]]},"reference":[{"key":"18_CR1","doi-asserted-by":"crossref","unstructured":"Amato, N.M., Wu, Y.: A randomized roadmap method for path and manipulation planning. In: ICRA. vol.\u00a01, pp. 113\u2013120. IEEE (1996)","DOI":"10.1109\/ROBOT.1996.503582"},{"key":"18_CR2","doi-asserted-by":"crossref","unstructured":"Basch, J., Guibas, L.J., Hsu, D., Nguyen, A.T.: Disconnection proofs for motion planning. In: ICRA. vol.\u00a02, pp. 1765\u20131772. IEEE (2001)","DOI":"10.1109\/ROBOT.2001.932865"},{"issue":"4","key":"18_CR3","first-page":"549","volume":"14","author":"O Ben-Shahar","year":"1998","unstructured":"Ben-Shahar, O., Rivlin, E.: Practical pushing planning for rearrangement tasks. T-RO 14(4), 549\u2013565 (1998)","journal-title":"T-RO"},{"key":"18_CR4","unstructured":"Berenson, D., Srinivasa, S.S., Ferguson, D., Kuffner, J.J.: Manipulation planning on constraint manifolds. In: ICRA"},{"key":"18_CR5","doi-asserted-by":"crossref","unstructured":"Boissonnat, J.D., Chazal, F., Yvinec, M.: Geometric and Topological Inference. Cambridge Texts in Applied Mathematics. Cambridge University Press (2018). https:\/\/hal.inria.fr\/hal-01615863","DOI":"10.1017\/9781108297806"},{"issue":"1","key":"18_CR6","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1007\/s00454-013-9557-2","volume":"51","author":"JD Boissonnat","year":"2014","unstructured":"Boissonnat, J.D., Ghosh, A.: Manifold reconstruction using tangential Delaunay complexes. Discret. Comput. Geom. 51(1), 221\u2013267 (2014)","journal-title":"Discret. Comput. Geom."},{"key":"18_CR7","doi-asserted-by":"crossref","unstructured":"Boor, V., Overmars, M.H., Van Der\u00a0Stappen, A.F.: The Gaussian sampling strategy for probabilistic roadmap planners. In: RSS. vol.\u00a02, pp. 1018\u20131023. IEEE (1999)","DOI":"10.1109\/ROBOT.1999.772447"},{"key":"18_CR8","doi-asserted-by":"crossref","unstructured":"Branicky, M.S., LaValle, S.M., Olson, K., Yang, L.: Quasi-randomized path planning. In: ICRA, vol.\u00a02, pp. 1481\u20131487. IEEE (2001)","DOI":"10.1109\/ROBOT.2001.932820"},{"issue":"1","key":"18_CR9","first-page":"104","volume":"28","author":"S Cambon","year":"2009","unstructured":"Cambon, S., Alami, R., Gravot, F.: A hybrid approach to intricate motion, manipulation and task planning. IJRR 28(1), 104\u2013126 (2009)","journal-title":"IJRR"},{"issue":"5","key":"18_CR10","doi-asserted-by":"publisher","first-page":"504","DOI":"10.1093\/comjnl\/36.5.504","volume":"36","author":"J Canny","year":"1993","unstructured":"Canny, J.: Computing roadmaps of general semi-algebraic sets. Comput. J. 36(5), 504\u2013514 (1993)","journal-title":"Comput. J."},{"key":"18_CR11","first-page":"145","volume":"1","author":"B Chazelle","year":"1985","unstructured":"Chazelle, B.: Approximation and decomposition of shapes. Algorithm. Geom. Aspects of Robot. 1, 145\u2013185 (1985)","journal-title":"Algorithm. Geom. Aspects of Robot."},{"issue":"4","key":"18_CR12","first-page":"72","volume":"19","author":"IA \u015eucan","year":"2012","unstructured":"\u015eucan, I.A., Moll, M., Kavraki, L.E.: The open motion planning library. RAM 19(4), 72\u201382 (2012)","journal-title":"RAM"},{"key":"18_CR13","doi-asserted-by":"crossref","unstructured":"\u015eucan, I.A., Kavraki, L.E.: A sampling-based tree planner for systems with complex dynamics. T-RO 28(1), 116\u2013131 (2012). http:\/\/dx.doi.org\/10.1109\/tro.2011.2160466","DOI":"10.1109\/TRO.2011.2160466"},{"key":"18_CR14","volume-title":"Task and Motion Planning","author":"NT Dantam","year":"2020","unstructured":"Dantam, N.T.: Task and Motion Planning. Springer, Berlin, Heidelberg (2020)"},{"issue":"10","key":"18_CR15","first-page":"1134","volume":"37","author":"NT Dantam","year":"2018","unstructured":"Dantam, N.T., Kingston, Z.K., Chaudhuri, S., Kavraki, L.E.: An incremental constraint-based framework for task and motion planning. IJRR 37(10), 1134\u20131151 (2018)","journal-title":"IJRR"},{"issue":"1","key":"18_CR16","first-page":"18","volume":"33","author":"A Dobson","year":"2014","unstructured":"Dobson, A., Bekris, K.E.: Sparse roadmap spanners for asymptotically near-optimal motion planning. IJRR 33(1), 18\u201347 (2014)","journal-title":"IJRR"},{"issue":"5","key":"18_CR17","doi-asserted-by":"publisher","first-page":"1048","DOI":"10.1145\/174147.174150","volume":"40","author":"B Donald","year":"1993","unstructured":"Donald, B., Xavier, P., Canny, J., Reif, J.: Kinodynamic motion planning. JACM 40(5), 1048\u20131066 (1993)","journal-title":"JACM"},{"key":"18_CR18","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1146\/annurev-control-091420-084139","volume":"4","author":"CR Garrett","year":"2021","unstructured":"Garrett, C.R., Chitnis, R., Holladay, R., Kim, B., Silver, T., Kaelbling, L.P., Lozano-P\u00e9rez, T.: Integrated task and motion planning. Ann. Rev. control, Robot. Autonom. Syst. 4, 265\u2013293 (2021)","journal-title":"Ann. Rev. control, Robot. Autonom. Syst."},{"issue":"3","key":"18_CR19","first-page":"233","volume":"21","author":"D Hsu","year":"2002","unstructured":"Hsu, D., Kindel, R., Latombe, J.C., Rock, S.: Randomized kinodynamic motion planning with moving obstacles. IJRR 21(3), 233\u2013255 (2002)","journal-title":"IJRR"},{"issue":"1","key":"18_CR20","first-page":"46","volume":"37","author":"L Janson","year":"2018","unstructured":"Janson, L., Ichter, B., Pavone, M.: Deterministic sampling-based motion planning: optimality, complexity, and performance. IJRR 37(1), 46\u201361 (2018)","journal-title":"IJRR"},{"issue":"7","key":"18_CR21","first-page":"883","volume":"34","author":"L Janson","year":"2015","unstructured":"Janson, L., Schmerling, E., Clark, A., Pavone, M.: Fast marching tree: a fast marching sampling-based method for optimal motion planning in many dimensions. IJRR 34(7), 883\u2013921 (2015)","journal-title":"IJRR"},{"key":"18_CR22","doi-asserted-by":"crossref","unstructured":"Kalakrishnan, M., Chitta, S., Theodorou, E., Pastor, P., Schaal, S.: STOMP: stochastic trajectory optimization for motion planning. In: ICRA, pp. 4569\u20134574. IEEE (2011)","DOI":"10.1109\/ICRA.2011.5980280"},{"issue":"7","key":"18_CR23","first-page":"846","volume":"30","author":"S Karaman","year":"2011","unstructured":"Karaman, S., Frazzoli, E.: Sampling-based algorithms for optimal motion planning. IJRR 30(7), 846\u2013894 (2011)","journal-title":"IJRR"},{"issue":"1","key":"18_CR24","first-page":"166","volume":"14","author":"LE Kavraki","year":"1998","unstructured":"Kavraki, L.E., Kolountzakis, M.N., Latombe, J.C.: Analysis of probabilistic roadmaps for path planning. T-RO 14(1), 166\u2013171 (1998)","journal-title":"T-RO"},{"issue":"1","key":"18_CR25","first-page":"50","volume":"57","author":"LE Kavraki","year":"1998","unstructured":"Kavraki, L.E., Latombe, J.C., Motwani, R., Raghavan, P.: Randomized query processing in robot path planning. JCSS 57(1), 50\u201360 (1998)","journal-title":"JCSS"},{"issue":"4","key":"18_CR26","first-page":"566","volume":"12","author":"LE Kavraki","year":"1996","unstructured":"Kavraki, L.E., Svestka, P., Latombe, J.C., Overmars, M.H.: Probabilistic roadmaps for path planning in high-dimensional configuration spaces. T-RO 12(4), 566\u2013580 (1996)","journal-title":"T-RO"},{"issue":"10\u201311","key":"18_CR27","first-page":"1151","volume":"38","author":"Z Kingston","year":"2019","unstructured":"Kingston, Z., Moll, M., Kavraki, L.E.: Exploring implicit spaces for constrained sampling-based planning. IJRR 38(10\u201311), 1151\u20131178 (2019)","journal-title":"IJRR"},{"key":"18_CR28","doi-asserted-by":"crossref","unstructured":"Kuffner, J.J., LaValle, S.M.: RRT-connect: an efficient approach to single-query path planning. In: ICRA, vol.\u00a02, pp. 995\u20131001. IEEE (2000)","DOI":"10.1109\/ROBOT.2000.844730"},{"key":"18_CR29","doi-asserted-by":"crossref","unstructured":"Ladd, A.M., Kavraki, L.E.: Fast tree-based exploration of state space for robots with dynamics. In: Algorithmic Foundations of Robotics VI, pp. 297\u2013312. Springer (2004)","DOI":"10.1007\/10991541_21"},{"key":"18_CR30","doi-asserted-by":"crossref","unstructured":"Lafferriere, G., Sussmann, H.: Motion planning for controllable systems without drift. In: ICRA, pp. 1148\u20131149. IEEE Computer Society (1991)","DOI":"10.1109\/ROBOT.1991.131763"},{"key":"18_CR31","unstructured":"LaValle, S.M.: Rapidly-exploring random trees: a new tool for path planning. Technical Report TR-98-11, Computer Science Department, Iowa State University (1998)"},{"key":"18_CR32","doi-asserted-by":"crossref","unstructured":"LaValle, S.M.: Planning Algorithms. Cambridge University Press (2006)","DOI":"10.1017\/CBO9780511546877"},{"issue":"5","key":"18_CR33","first-page":"378","volume":"20","author":"SM LaValle","year":"2001","unstructured":"LaValle, S.M., Kuffner, J.J.: Randomized kinodynamic planning. IJRR 20(5), 378\u2013400 (2001)","journal-title":"IJRR"},{"key":"18_CR34","doi-asserted-by":"crossref","unstructured":"Li, S., Dantam, N.T.: Learning proofs of motion planning infeasibility. In: RSS (2021)","DOI":"10.15607\/RSS.2021.XVII.064"},{"issue":"5","key":"18_CR35","first-page":"528","volume":"35","author":"Y Li","year":"2016","unstructured":"Li, Y., Littlefield, Z., Bekris, K.E.: Asymptotically optimal sampling-based kinodynamic planning. IJRR 35(5), 528\u2013564 (2016)","journal-title":"IJRR"},{"key":"18_CR36","unstructured":"Makino, H.: Assembly robot (1982), US Patent 4,341,502"},{"key":"18_CR37","doi-asserted-by":"crossref","unstructured":"McCarthy, Z., Bretl, T., Hutchinson, S.: Proving path non-existence using sampling and alpha shapes. In: ICRA, pp. 2563\u20132569. IEEE (2012)","DOI":"10.1109\/ICRA.2012.6225300"},{"issue":"11","key":"18_CR38","first-page":"1319","volume":"37","author":"M Mukadam","year":"2018","unstructured":"Mukadam, M., Dong, J., Yan, X., Dellaert, F., Boots, B.: Continuous-time Gaussian process motion planning via probabilistic inference. IJRR 37(11), 1319\u20131340 (2018)","journal-title":"IJRR"},{"key":"18_CR39","unstructured":"Murray, S., Floyd-Jones, W., Qi, Y., Sorin, D.J., Konidaris, G.D.: Robot motion planning on a chip. In: RSS (2016)"},{"key":"18_CR40","doi-asserted-by":"crossref","unstructured":"Orthey, A., Toussaint, M.: Sparse multilevel roadmaps for high-dimensional robotic motion planning. In: ICRA, pp. 7851\u20137857 (2021)","DOI":"10.1109\/ICRA48506.2021.9562053"},{"key":"18_CR41","doi-asserted-by":"crossref","unstructured":"Ota, J.: Rearrangement of multiple movable objects-integration of global and local planning methodology. In: ICRA, vol.\u00a02, pp. 1962\u20131967. IEEE (2004)","DOI":"10.1109\/ROBOT.2004.1308111"},{"issue":"7","key":"18_CR42","first-page":"797","volume":"35","author":"M Otte","year":"2016","unstructured":"Otte, M., Frazzoli, E.: RRTX: asymptotically optimal single-query sampling-based motion planning with quick replanning. IJRR 35(7), 797\u2013822 (2016)","journal-title":"IJRR"},{"issue":"4","key":"18_CR43","first-page":"597","volume":"21","author":"E Plaku","year":"2005","unstructured":"Plaku, E., Bekris, K.E., Chen, B.Y., Ladd, A.M., Kavraki, L.E.: Sampling-based roadmap of trees for parallel motion planning. T-RO 21(4), 597\u2013608 (2005)","journal-title":"T-RO"},{"issue":"9","key":"18_CR44","first-page":"1251","volume":"33","author":"J Schulman","year":"2014","unstructured":"Schulman, J., Duan, Y., Ho, J., Lee, A., Awwal, I., Bradlow, H., Pan, J., Patil, S., Goldberg, K., Abbeel, P.: Motion planning with sequential convex optimization and convex collision checking. IJRR 33(9), 1251\u20131270 (2014)","journal-title":"IJRR"},{"issue":"6","key":"18_CR45","doi-asserted-by":"publisher","first-page":"477","DOI":"10.1163\/156855300741960","volume":"14","author":"T Sim\u00e9on","year":"2000","unstructured":"Sim\u00e9on, T., Laumond, J.P., Nissoux, C.: Visibility-based probabilistic roadmaps for motion planning. Adv. Robot. 14(6), 477\u2013493 (2000)","journal-title":"Adv. Robot."},{"key":"18_CR46","doi-asserted-by":"crossref","unstructured":"Varava, A., Carvalho, J.F., Pokorny, F.T., Kragic, D.: Caging and path non-existence: a deterministic sampling-based verification algorithm. In: Robotics Research, pp. 589\u2013604. Springer (2020)","DOI":"10.1007\/978-3-030-28619-4_43"},{"key":"18_CR47","doi-asserted-by":"crossref","unstructured":"Zhang, L., Kim, Y.J., Manocha, D.: A hybrid approach for complete motion planning. In: IROS, pp. 7\u201314. IEEE\/RSJ (2007)","DOI":"10.1109\/IROS.2007.4399064"},{"key":"18_CR48","doi-asserted-by":"crossref","unstructured":"Zhang, L., Kim, Y.J., Manocha, D.: A simple path non-existence algorithm using c-obstacle query. In: Algorithmic Foundation of Robotics VII, pp. 269\u2013284. Springer (2008)","DOI":"10.1007\/978-3-540-68405-3_17"},{"issue":"9\u201310","key":"18_CR49","first-page":"1164","volume":"32","author":"M Zucker","year":"2013","unstructured":"Zucker, M., Ratliff, N., Dragan, A.D., Pivtoraiko, M., Klingensmith, M., Dellin, C.M., Bagnell, J.A., Srinivasa, S.S.: CHOMP: covariant Hamiltonian optimization for motion planning. IJRR 32(9\u201310), 1164\u20131193 (2013)","journal-title":"IJRR"}],"container-title":["Springer Proceedings in Advanced Robotics","Algorithmic Foundations of Robotics XV"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-21090-7_18","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,10]],"date-time":"2024-10-10T10:41:59Z","timestamp":1728556919000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-21090-7_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,12,15]]},"ISBN":["9783031210891","9783031210907"],"references-count":49,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-21090-7_18","relation":{},"ISSN":["2511-1256","2511-1264"],"issn-type":[{"type":"print","value":"2511-1256"},{"type":"electronic","value":"2511-1264"}],"subject":[],"published":{"date-parts":[[2022,12,15]]},"assertion":[{"value":"15 December 2022","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WAFR","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on the Algorithmic Foundations of Robotics","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":", MD","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"USA","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2022","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22 June 2022","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"24 June 2022","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"wafr2022","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/wafr2022.github.io","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}