{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,20]],"date-time":"2026-05-20T09:13:04Z","timestamp":1779268384595,"version":"3.51.4"},"publisher-location":"Cham","reference-count":46,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783031210891","type":"print"},{"value":"9783031210907","type":"electronic"}],"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_20","type":"book-chapter","created":{"date-parts":[[2022,12,14]],"date-time":"2022-12-14T18:11:35Z","timestamp":1671041495000},"page":"328-348","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":19,"title":["Finding and\u00a0Optimizing Certified, Collision-Free Regions in\u00a0Configuration Space for\u00a0Robot Manipulators"],"prefix":"10.1007","author":[{"given":"Alexandre","family":"Amice","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hongkai","family":"Dai","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Peter","family":"Werner","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Annan","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Russ","family":"Tedrake","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,12,15]]},"reference":[{"key":"20_CR1","doi-asserted-by":"crossref","unstructured":"Lozano-Perez, T.: Spatial planning: a configuration space approach. IEEE Trans. Comput. 100(32), 108\u2013120 (1983)","DOI":"10.1109\/TC.1983.1676196"},{"issue":"3","key":"20_CR2","doi-asserted-by":"publisher","first-page":"408","DOI":"10.1109\/70.388783","volume":"11","author":"L.E Kavraki","year":"1995","unstructured":"Kavraki, L..E.: Computation of configuration-space obstacles using the fast fourier transform. IEEE Trans. Robot. Autom. 11(3), 408\u2013413 (1995)","journal-title":"IEEE Trans. Robot. Autom."},{"key":"20_CR3","unstructured":"Branicky, M., Newman, W.: Rapid computation of configuration space obstacles. In: Proceedings of IEEE International Conference on Robotics and Automation (1990)"},{"key":"20_CR4","doi-asserted-by":"crossref","unstructured":"Canny, J.: The Complexity of Robot Motion Planning. MIT Press (1988)","DOI":"10.1109\/SFCS.1988.21947"},{"key":"20_CR5","unstructured":"LaValle, S.M. et al.: Rapidly-exploring random trees: A new tool for path planning (1998)"},{"issue":"4","key":"20_CR6","doi-asserted-by":"publisher","first-page":"566","DOI":"10.1109\/70.508439","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. IEEE Trans. Robot. Autom. 12(4), 566\u2013580 (1996)","journal-title":"IEEE Trans. Robot. Autom."},{"key":"20_CR7","doi-asserted-by":"crossref","unstructured":"Verghese, M., Das, N., Zhi, Y., Yip, M.: Configuration space decomposition for scalable proxy collision checking in robot planning and control (2022). arXiv:2201.04314","DOI":"10.1109\/LRA.2022.3147458"},{"key":"20_CR8","doi-asserted-by":"crossref","unstructured":"Han, Y., Zhao, W., Pan, J., Ye, Z., Yi, R., Liu, Y.-J.: A configuration-space decomposition scheme for learning-based collision checking (2019). arXiv:1911.08581","DOI":"10.1109\/IROS45743.2020.9341526"},{"issue":"6","key":"20_CR9","doi-asserted-by":"publisher","first-page":"729","DOI":"10.1007\/s00371-014-0954-1","volume":"30","author":"T.H Wong","year":"2014","unstructured":"Wong, T..H., Leach, G., Zambetta, F.: An adaptive octree grid for GPU-based collision detection of deformable objects. Vis. Comput. 30(6), 729\u2013738 (2014)","journal-title":"Vis. Comput."},{"key":"20_CR10","unstructured":"Lingas, A.: The power of non-rectilinear holes. In: International Colloquium on Automata, Languages, and Programming"},{"issue":"3","key":"20_CR11","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/S0097539702405139","volume":"32","author":"S.J Eidenbenz","year":"2003","unstructured":"Eidenbenz, S..J., Widmayer, P.: An approximation algorithm for minimum convex cover with logarithmic performance guarantee. SIAM J. Comput. 32(3), 1 (2003)","journal-title":"SIAM J. Comput."},{"key":"20_CR12","doi-asserted-by":"crossref","unstructured":"Lien, J.-M., Amato, N.M.: Approximate convex decomposition of polyhedra. In: Proceedings of the 2007 ACM Symposium on Solid and Physical Modeling","DOI":"10.1145\/1236246.1236265"},{"issue":"2","key":"20_CR13","doi-asserted-by":"publisher","first-page":"494","DOI":"10.1016\/j.cad.2012.10.032","volume":"45","author":"M Ghosh","year":"2013","unstructured":"Ghosh, M., Amato, M.N., Lu, Y., Lien, J..-M.: Fast approximate convex decomposition using relative concavity. Comput.-Aided Des. 45(2), 494\u2013504 (2013)","journal-title":"Comput.-Aided Des."},{"key":"20_CR14","doi-asserted-by":"crossref","unstructured":"Deits, R., Tedrake, R.: Computing large convex regions of obstacle-free space through semidefinite programming. In: Algorithmic Foundations of Robotics XI, pp. 109\u2013124. Springer (2015)","DOI":"10.1007\/978-3-319-16595-0_7"},{"key":"20_CR15","unstructured":"Diankov, R.: Automated construction of robotic manipulation programs (2010)"},{"key":"20_CR16","doi-asserted-by":"crossref","unstructured":"Trutman, P., Mohab, S.E.D., Henrion, D., Pajdla, T.: Globally optimal solution to inverse kinematics of 7dof serial manipulator (2020). arXiv:2007.12550","DOI":"10.1109\/LRA.2022.3163444"},{"key":"20_CR17","doi-asserted-by":"crossref","unstructured":"Sommese, A.J., Wampler, C.W. et al.: The Numerical Solution of Systems of Polynomials Arising in Engineering and Science. World Scientific (2005)","DOI":"10.1142\/5763"},{"key":"20_CR18","doi-asserted-by":"crossref","unstructured":"Deits, R., Tedrake, R.: Efficient mixed-integer planning for UAVs in cluttered environments. In: 2015 IEEE International Conference on Robotics and Automation (ICRA)","DOI":"10.1109\/ICRA.2015.7138978"},{"key":"20_CR19","doi-asserted-by":"crossref","unstructured":"Schouwenaars, T., De Moor, B., Feron, E., How, J.: Mixed integer programming for multi-vehicle path planning. In: 2001 European Control Conference (ECC)","DOI":"10.23919\/ECC.2001.7076321"},{"key":"20_CR20","unstructured":"Marcucci, T., Petersen, M., von Wrangel, D., Tedrake, R.: Motion planning around obstacles with convex optimization (2022). https:\/\/arxiv.org\/abs\/2205.04422"},{"key":"20_CR21","unstructured":"Tedrake, R.: Robotic Manipulation (2021). https:\/\/manipulation.mit.edu\/pick.html#monogram"},{"key":"20_CR22","doi-asserted-by":"crossref","unstructured":"Boyd, S., Boyd, S.P., Vandenberghe, L.: Convex Optimization. Cambridge University Press (2004)","DOI":"10.1017\/CBO9780511804441"},{"key":"20_CR23","unstructured":"Bishop, C.M.: Pattern Recognition. Machine Learning, vol. 128, Issue 9 (2006)"},{"key":"20_CR24","unstructured":"Parrilo, P.A.: Structured Semidefinite Programs and Semialgebraic Geometry methods in Robustness and Optimization. California Institute of Technology (2000)"},{"key":"20_CR25","doi-asserted-by":"crossref","unstructured":"Blekherman, G., Parrilo, P.A., Thomas, R.R.: Semidefinite Optimization and Convex Algebraic Geometry. SIAM (2012)","DOI":"10.1137\/1.9781611972290"},{"issue":"8","key":"20_CR26","doi-asserted-by":"publisher","first-page":"1038","DOI":"10.1177\/0278364910369189","volume":"29","author":"R Tedrake","year":"2010","unstructured":"Tedrake, R., Manchester, I.R., Tobenkin, M., Roberts, J.W.: Lqr-trees: feedback motion planning via sums-of-squares verification. Int. J. Robot. Res. 29(8), 1038\u20131052 (2010)","journal-title":"Int. J. Robot. Res."},{"issue":"8","key":"20_CR27","doi-asserted-by":"publisher","first-page":"947","DOI":"10.1177\/0278364917712421","volume":"36","author":"A Majumdar","year":"2017","unstructured":"Majumdar, A., Tedrake, R.: Funnel libraries for real-time robust feedback motion planning. Int. J. Robot. Res. 36(8), 947\u2013982 (2017)","journal-title":"Int. J. Robot. Res."},{"key":"20_CR28","doi-asserted-by":"crossref","unstructured":"Shen, S., Tedrake, R.: Sampling quotient-ring sum-of-squares programs for scalable verification of nonlinear systems. In: 2020 59th IEEE Conference on Decision and Control (CDC)","DOI":"10.1109\/CDC42340.2020.9304028"},{"key":"20_CR29","unstructured":"Jarvis-Wloszek, Z., Feeley, R., Tan, W., Sun, K., Packard, A.: Some controls applications of sum of squares programming. In: 42nd IEEE International Conference on Decision and Control (IEEE Cat. No. 03CH37475), vol. 5, pp. 4676\u20134681. IEEE (2003)"},{"issue":"12","key":"20_CR30","doi-asserted-by":"publisher","first-page":"6025","DOI":"10.1109\/TAC.2021.3056611","volume":"66","author":"H Yin","year":"2021","unstructured":"Yin, H., Arcak, M., Packard, A., Seiler, P.: Backward reachability for polynomial systems on a finite horizon. IEEE Trans. Autom. Control 66(12), 6025\u20136032 (2021)","journal-title":"IEEE Trans. Autom. Control"},{"key":"20_CR31","unstructured":"Ahmadi, A.A., Hall, G., Makadia, A., Sindhwani, V.: Geometry of 3d environments and sum of squares polynomials (2016). arXiv:1611.07369"},{"issue":"2","key":"20_CR32","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1007\/BF01362149","volume":"207","author":"G Stengle","year":"1974","unstructured":"Stengle, G.: A nullstellensatz and a positivstellensatz in semialgebraic geometry. Mathematische Annalen 207(2), 87\u201397 (1974)","journal-title":"Mathematische Annalen"},{"issue":"3","key":"20_CR33","doi-asserted-by":"publisher","first-page":"969","DOI":"10.1512\/iumj.1993.42.42045","volume":"42","author":"M Putinar","year":"1993","unstructured":"Putinar, M.: Positive polynomials on compact semi-algebraic sets. Ind. Univ. Math. J. 42(3), 969\u2013984 (1993)","journal-title":"Ind. Univ. Math. J."},{"key":"20_CR34","doi-asserted-by":"crossref","unstructured":"Wampler, C.W., Morgan, A., Sommese, A.: Numerical continuation methods for solving polynomial systems arising in kinematics (1990)","DOI":"10.1115\/1.2912579"},{"key":"20_CR35","doi-asserted-by":"publisher","first-page":"469","DOI":"10.1017\/S0962492911000067","volume":"20","author":"C.W Wampler","year":"2011","unstructured":"Wampler, C..W., Sommese, A..J.: Numerical algebraic geometry and algebraic kinematics. Acta Numer. 20, 469\u2013567 (2011)","journal-title":"Acta Numer."},{"key":"20_CR36","unstructured":"Craig, J.J.: Introduction to Robotics: Mechanics and Control. Pearson Education (2005)"},{"key":"20_CR37","unstructured":"Spivak, M.: Calculus Third Edition. Cambridge University Press (1994)"},{"key":"20_CR38","unstructured":"Prestel, A., Delzell, C.: Positive Polynomials: From Hilbert\u2019s 17th Problem to Real Algebra. Springer Science & Business Media (2013)"},{"issue":"4","key":"20_CR39","doi-asserted-by":"publisher","first-page":"777","DOI":"10.1137\/0212053","volume":"12","author":"J.S Provan","year":"1983","unstructured":"Provan, J..S., Ball, M..O.: The complexity of counting cuts and of computing the probability that a graph is connected. SIAM J. Comput. 12(4), 777\u2013788 (1983)","journal-title":"SIAM J. Comput."},{"issue":"5","key":"20_CR40","doi-asserted-by":"publisher","first-page":"967","DOI":"10.1137\/0217060","volume":"17","author":"ME Dyer","year":"1988","unstructured":"Dyer, M.E., Frieze, A.M.: On the complexity of computing the volume of a polyhedron. SIAM J. Comput. 17(5), 967\u2013974 (1988)","journal-title":"SIAM J. Comput."},{"key":"20_CR41","unstructured":"ApS, M.: The MOSEK optimization toolbox for MATLAB manual. Version 9.0 (2019). https:\/\/docs.mosek.com\/9.0\/toolbox\/index.html"},{"issue":"4","key":"20_CR42","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1145\/37402.37422","volume":"21","author":"WE Lorensen","year":"1987","unstructured":"Lorensen, W.E., Cline, H.E.: Marching cubes: a high resolution 3d surface construction algorithm. ACM Siggraph Comput. Graph. 21(4), 163\u2013169 (1987)","journal-title":"ACM Siggraph Comput. Graph."},{"key":"20_CR43","unstructured":"Parrilo, P.A.: Sum of squares programs and polynomial inequalities. In: SIAG\/OPT Views-and-News: A Forum for the SIAM Activity Group on Optimization, vol. 15, Issue 2 (2004)"},{"issue":"2","key":"20_CR44","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1023\/A:1022497624378","volume":"3","author":"B Sturmfels","year":"1994","unstructured":"Sturmfels, B.: On the newton polytope of the resultant. J. Algebraic Comb. 3(2), 207\u2013236 (1994)","journal-title":"J. Algebraic Comb."},{"key":"20_CR45","doi-asserted-by":"crossref","unstructured":"Ferrier, C.: Computation of the distance to semi-algebraic sets. ESAIM: Control, Optimisation and Calculus of Variations, vol. 5","DOI":"10.1051\/cocv:2000104"},{"issue":"1","key":"20_CR46","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1137\/S0036144504446096","volume":"47","author":"PE Gill","year":"2005","unstructured":"Gill, P.E., Murray, W., Saunders, M.A.: Snopt: an SQP algorithm for large-scale constrained optimization. SIAM Rev. 47(1), 99\u2013131 (2005)","journal-title":"SIAM Rev."}],"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_20","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,14]],"date-time":"2022-12-14T18:18:26Z","timestamp":1671041906000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-21090-7_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,12,15]]},"ISBN":["9783031210891","9783031210907"],"references-count":46,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-21090-7_20","relation":{},"ISSN":["2511-1256","2511-1264"],"issn-type":[{"value":"2511-1256","type":"print"},{"value":"2511-1264","type":"electronic"}],"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"}}]}}