{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,12]],"date-time":"2026-06-12T19:16:51Z","timestamp":1781291811474,"version":"3.54.1"},"reference-count":57,"publisher":"SAGE Publications","issue":"9","license":[{"start":{"date-parts":[[2023,11,3]],"date-time":"2023-11-03T00:00:00Z","timestamp":1698969600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"funder":[{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"publisher","award":["N00014-18-1-2210"],"award-info":[{"award-number":["N00014-18-1-2210"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["EFMA-1830901"],"award-info":[{"award-number":["EFMA-1830901"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006602","name":"Air Force Research Laboratory","doi-asserted-by":"publisher","award":["FA8750-19-2-1000"],"award-info":[{"award-number":["FA8750-19-2-1000"]}],"id":[{"id":"10.13039\/100006602","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100019800","name":"MIT Quest","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100019800","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["journals.sagepub.com"],"crossmark-restriction":true},"short-container-title":["The International Journal of Robotics Research"],"published-print":{"date-parts":[[2024,8]]},"abstract":"<jats:p>\n                    Understanding the geometry of collision-free configuration space (C-free) in the presence of Cartesian-space obstacles is an essential ingredient for collision-free motion planning. While it is possible to check for collisions at a point using standard algorithms, to date no practical method exists for computing C-free\n                    <jats:italic>regions<\/jats:italic>\n                    with rigorous certificates due to the complexity of mapping Cartesian-space obstacles through the kinematics. In this work, we present the first to our knowledge rigorous method for approximately decomposing a rational parametrization of C-free into certified polyhedral regions. Our method, called\n                    <jats:sc>C-Iris<\/jats:sc>\n                    (C-space Iterative Regional Inflation by Semidefinite programming), generates large, convex polytopes in a rational parameterization of the configuration space which are rigorously certified to be collision-free. Such regions have been shown to be useful for both optimization-based and randomized motion planning. Based on convex optimization, our method works in arbitrary dimensions, only makes assumptions about the convexity of the obstacles in the\n                    <jats:italic>3D Cartesian<\/jats:italic>\n                    space, and is fast enough to scale to realistic problems in manipulation. We demonstrate our algorithm\u2019s ability to fill a non-trivial amount of collision-free C-space in several 2-DOF examples where the C-space can be visualized, as well as the scalability of our algorithm on a 7-DOF KUKA iiwa, a 6-DOF UR3e, and 12-DOF bimanual manipulators. An implementation of our algorithm is open-sourced in\n                    <jats:ext-link xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" ext-link-type=\"uri\" xlink:href=\"https:\/\/drake.mit.edu\">Drake<\/jats:ext-link>\n                    . We furthermore provide examples of our algorithm in interactive\n                    <jats:ext-link xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" ext-link-type=\"uri\" xlink:href=\"https:\/\/deepnote.com\/workspace\/alexandre-amice-c018b305-0386-4703-9474-01b867e6efea\/project\/C-IRIS-7e82e4f5-f47a-475a-aad3-c88093ed36c6\/notebook\/2d_example_bilinear_alternation-14f1ee8c795e499ca7f577b6885c10e9\">Python notebooks<\/jats:ext-link>\n                    .\n                  <\/jats:p>","DOI":"10.1177\/02783649231201437","type":"journal-article","created":{"date-parts":[[2023,11,3]],"date-time":"2023-11-03T20:14:46Z","timestamp":1699042486000},"page":"1322-1341","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":21,"title":["Certified polyhedral decompositions of collision-free configuration space"],"prefix":"10.1177","volume":"43","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6131-3620","authenticated-orcid":false,"given":"Hongkai","family":"Dai","sequence":"first","affiliation":[{"name":"Toyota Research Institute, Los Altos, CA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3955-9560","authenticated-orcid":false,"given":"Alexandre","family":"Amice","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology (MIT), Cambridge, MA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Peter","family":"Werner","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology (MIT), Cambridge, MA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6664-9417","authenticated-orcid":false,"given":"Annan","family":"Zhang","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology (MIT), Cambridge, MA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Russ","family":"Tedrake","sequence":"additional","affiliation":[{"name":"Toyota Research Institute, Los Altos, CA, USA"},{"name":"Massachusetts Institute of Technology (MIT), Cambridge, MA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"179","published-online":{"date-parts":[[2023,11,3]]},"reference":[{"key":"e_1_3_5_2_1","doi-asserted-by":"crossref","unstructured":"Ahmadi AA Krstic M Parrilo PA (2011) A globally asymptotically stable polynomial vector field with no polynomial lyapunov function. In: 2011 50th IEEE Conference on Decision and Control and European Control Conference. Orlando FL 12-15 December 2011 pp. 7579\u20137580.","DOI":"10.1109\/CDC.2011.6161499"},{"key":"e_1_3_5_3_1","volume-title":"Geometry of 3d Environments and Sum of Squares Polynomials","author":"Ahmadi AA","year":"2016","unstructured":"Ahmadi AA, Hall G, Makadia A, et al. (2016) Geometry of 3d Environments and Sum of Squares Polynomials. Cornell Universiry. arXiv preprint arXiv:1611.07369."},{"key":"e_1_3_5_4_1","doi-asserted-by":"crossref","unstructured":"Amice A Dai H Werner P et al. (2022) Finding and optimizing certified collision-free regions in configuration space for robot manipulators. In: Algorithmic Foundations of Robotics XV: Proceedings of the Fifteenth Workshop on the Algorithmic Foundations of Robotics. College Park Maryland USA 2022 pp. 328\u2013348.","DOI":"10.1007\/978-3-031-21090-7_20"},{"key":"e_1_3_5_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-3216-0_8"},{"key":"e_1_3_5_6_1","volume-title":"The MOSEK Optimization Toolbox for MATLAB Manual","author":"ApS M","year":"2019","unstructured":"ApS M (2019) The MOSEK Optimization Toolbox for MATLAB Manual. URL http:\/\/docs.mosek.com\/9.0\/toolbox\/index.html."},{"key":"e_1_3_5_7_1","volume-title":"On Moment Approximation and the Effective Putinar\u2019s Positivstellensatz","author":"Baldi L","year":"2021","unstructured":"Baldi L, Mourrain B (2021) On Moment Approximation and the Effective Putinar\u2019s Positivstellensatz. Online ahead of print."},{"key":"e_1_3_5_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972290"},{"key":"e_1_3_5_9_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804441"},{"key":"e_1_3_5_10_1","doi-asserted-by":"publisher","unstructured":"Branicky M Newman W (1990) Rapid computation of configuration space obstacles. In: Proceedings IEEE International Conference on Robotics and Automation Cincinnati OH 13-18 May 1990. DOI: 10.1109\/ROBOT.1990.125992.","DOI":"10.1109\/ROBOT.1990.125992"},{"key":"e_1_3_5_11_1","doi-asserted-by":"crossref","unstructured":"Brossette S Wieber PB (2017) Collision avoidance based on separating planes for feet trajectory generation. In: 2017 IEEE-RAS 17th International Conference on Humanoid Robotics (Humanoids). Birmingham UK 15-17 November 2017.","DOI":"10.1109\/HUMANOIDS.2017.8246920"},{"key":"e_1_3_5_12_1","volume-title":"The Complexity of Robot Motion Planning","author":"Canny J","year":"1988","unstructured":"Canny J (1988) The Complexity of Robot Motion Planning. MIT press."},{"key":"e_1_3_5_13_1","volume-title":"Introduction to Robotics: Mechanics and Control","author":"Craig JJ","year":"2005","unstructured":"Craig JJ (2005) Introduction to Robotics: Mechanics and Control. Pearson Educacion."},{"key":"e_1_3_5_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-16595-0_7"},{"key":"e_1_3_5_15_1","doi-asserted-by":"crossref","unstructured":"Deits R Tedrake R (2015b) Efficient mixed-integer planning for uavs in cluttered environments. In: 2015 IEEE International Conference on Robotics and Automation (ICRA). Seattle WA 26-30 May 2015.","DOI":"10.1109\/ICRA.2015.7138978"},{"key":"e_1_3_5_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/0217060"},{"key":"e_1_3_5_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702405139"},{"key":"e_1_3_5_18_1","doi-asserted-by":"publisher","DOI":"10.1051\/cocv:2000104"},{"key":"e_1_3_5_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cad.2012.10.032"},{"key":"e_1_3_5_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0036144504446096"},{"key":"e_1_3_5_21_1","volume-title":"A Configuration-Space Decomposition Scheme for Learning-Based Collision Checking","author":"Han Y","year":"2019","unstructured":"Han Y, Zhao W, Pan J, et al. (2019) A Configuration-Space Decomposition Scheme for Learning-Based Collision Checking. Online ahead of print."},{"key":"e_1_3_5_22_1","doi-asserted-by":"crossref","unstructured":"Jarvis-Wloszek Z Feeley R Tan W et al. (2003) Some controls applications of sum of squares programming. In:42nd IEEE international conference on decision and control (IEEE Cat. No. 03CH37475) Maui HI 09-12 December 2003.","DOI":"10.1109\/CDC.2003.1272309"},{"key":"e_1_3_5_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/70.388783"},{"key":"e_1_3_5_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/70.508439"},{"key":"e_1_3_5_25_1","volume-title":"Robot Motion Planning","author":"Latombe JC","year":"2012","unstructured":"Latombe JC (2012) Robot Motion Planning. Springer Science & Business Media."},{"key":"e_1_3_5_26_1","volume-title":"Rapidly-exploring Random Trees: A New Tool for Path Planning","author":"LaValle SM","year":"1998","unstructured":"LaValle SM (1998) Rapidly-exploring Random Trees: A New Tool for Path Planning. Lowa University."},{"key":"e_1_3_5_27_1","doi-asserted-by":"crossref","unstructured":"Lien JM Amato NM (2007) Approximate convex decomposition of polyhedra. In: Proceedings of the 2007 ACM Symposium on Solid and Physical Modeling June 2007.","DOI":"10.1145\/1236246.1236265"},{"key":"e_1_3_5_28_1","doi-asserted-by":"crossref","unstructured":"Lin X Fernandez GI Hong DW (2022) Reduce: reformulation of mixed integer programs using data from unsupervised clusters for learning efficient strategies. In: 2022 International Conference on Robotics and Automation (ICRA). Philadelphia PA 23-27 May 2022.","DOI":"10.1109\/ICRA46639.2022.9811566"},{"key":"e_1_3_5_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0012784"},{"issue":"32","key":"e_1_3_5_30_1","first-page":"579","article-title":"Spatial planning: a configuration space approach","volume":"100","author":"Lozano-Perez T","year":"1983","unstructured":"Lozano-Perez T (1983) Spatial planning: a configuration space approach. IEEE Transactions on Computers 100(32): 579.","journal-title":"IEEE Transactions on Computers"},{"key":"e_1_3_5_31_1","doi-asserted-by":"publisher","DOI":"10.1177\/0278364917712421"},{"key":"e_1_3_5_32_1","doi-asserted-by":"crossref","unstructured":"Mamou K Ghorbel F (2009) A simple and efficient approach for 3d mesh approximate convex decomposition. In: 2009 16th IEEE International Conference on Image Processing (ICIP). Cairo Egypt 07-10 November 2009.","DOI":"10.1109\/ICIP.2009.5414068"},{"key":"e_1_3_5_33_1","volume-title":"Shortest Paths in Graphs of Convex Sets","author":"Marcucci T","year":"2021","unstructured":"Marcucci T, Umenberger J, Parrilo PA, et al. (2021) Shortest Paths in Graphs of Convex Sets. Online ahead of print."},{"key":"e_1_3_5_34_1","volume-title":"Motion Planning Around Obstacles with Convex Optimization","author":"Marcucci T","year":"2022","unstructured":"Marcucci T, Petersen M, von Wrangel D, et al. (2022) Motion Planning Around Obstacles with Convex Optimization. Online ahead of print."},{"key":"e_1_3_5_35_1","first-page":"516","article-title":"Positive polynomials and sums of squares","volume":"146","author":"Marshall M","year":"2008","unstructured":"Marshall M (2008) Positive polynomials and sums of squares. American Mathematical Society, 146: 516.","journal-title":"American Mathematical Society"},{"key":"e_1_3_5_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11081-011-9176-9"},{"key":"e_1_3_5_37_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1110.0498"},{"key":"e_1_3_5_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2006.07.002"},{"key":"e_1_3_5_39_1","volume-title":"Structured Semidefinite Programs and Semialgebraic Geometry Methods in Robustness and Optimization","author":"Parrilo PA","year":"2000","unstructured":"Parrilo PA (2000) Structured Semidefinite Programs and Semialgebraic Geometry Methods in Robustness and Optimization. California Institute of Technology."},{"key":"e_1_3_5_40_1","first-page":"7","volume-title":"SIAG\/OPT Views-And-News: A Forum for the SIAM Activity Group on Optimization","author":"Parrilo PA","year":"2004","unstructured":"Parrilo PA (2004) Sum of squares programs and polynomial inequalities. In: SIAG\/OPT Views-And-News: A Forum for the SIAM Activity Group on Optimization, 15, pp. 7\u201315."},{"key":"e_1_3_5_41_1","doi-asserted-by":"publisher","DOI":"10.1137\/0212053"},{"key":"e_1_3_5_42_1","doi-asserted-by":"publisher","DOI":"10.1512\/iumj.1993.42.42045"},{"key":"e_1_3_5_43_1","volume-title":"Principles of Mathematical Analysis","author":"Rudin W","year":"1976","unstructured":"Rudin W (1976) Principles of Mathematical Analysis. New York: McGraw-Hill, Volume 3."},{"key":"e_1_3_5_44_1","doi-asserted-by":"crossref","unstructured":"Schouwenaars T De Moor B Feron E et al. (2001) Mixed integer programming for multi-vehicle path planning. In: 2001 European Control Conference (ECC). Porto Portugal 04-07 September 2001 pp. 2603\u20132608.","DOI":"10.23919\/ECC.2001.7076321"},{"key":"e_1_3_5_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-45058-0_3"},{"key":"e_1_3_5_46_1","doi-asserted-by":"crossref","unstructured":"Shen S Tedrake R (2020) Sampling quotient-ring sum-of-squares programs for scalable verification of nonlinear systems. In: 2020 59th IEEE Conference on Decision and Control (CDC). Jeju Korea 14-18 December 2020 pp. 2535\u20132542.","DOI":"10.1109\/CDC42340.2020.9304028"},{"key":"e_1_3_5_47_1","volume-title":"Calculus","author":"Spivak M","year":"1994","unstructured":"Spivak M (1994) Calculus. Third Edition. Cambridge University Press."},{"key":"e_1_3_5_48_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcom.1996.0011"},{"key":"e_1_3_5_49_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1022497624378"},{"key":"e_1_3_5_50_1","volume-title":"Robotic Manipulation","author":"Tedrake R","year":"2021","unstructured":"Tedrake R (2021) Robotic Manipulation. Manipulation. https:\/\/manipulation.mit.edu\/pick.html."},{"key":"e_1_3_5_51_1","volume-title":"Underactuated Robotics","author":"Tedrake R","year":"2022","unstructured":"Tedrake R (2022) Underactuated Robotics. https:\/\/underactuated.csail.mit.edu."},{"key":"e_1_3_5_52_1","volume-title":"Drake: Model-Based Design and Verification for Robotics","author":"Tedrake R","year":"2019","unstructured":"Tedrake R, the Drake Development Team (2019) Drake: Model-Based Design and Verification for Robotics. Drake, https:\/\/drake.mit.edu."},{"key":"e_1_3_5_53_1","doi-asserted-by":"publisher","DOI":"10.1177\/0278364910369189"},{"key":"e_1_3_5_54_1","volume-title":"Globally Optimal Solution to Inverse Kinematics of 7dof Serial Manipulator","author":"Trutman P","year":"2020","unstructured":"Trutman P, Mohab SED, Henrion D, et al. (2020) Globally Optimal Solution to Inverse Kinematics of 7dof Serial Manipulator. Online ahead of print."},{"key":"e_1_3_5_55_1","doi-asserted-by":"publisher","DOI":"10.1109\/LRA.2022.3147458"},{"key":"e_1_3_5_56_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0962492911000067"},{"key":"e_1_3_5_57_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00371-014-0954-1"},{"key":"e_1_3_5_58_1","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2021.3056611"}],"container-title":["The International Journal of Robotics Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/02783649231201437","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/full-xml\/10.1177\/02783649231201437","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/02783649231201437","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/02783649231201437","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T10:17:20Z","timestamp":1777457840000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/02783649231201437"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,11,3]]},"references-count":57,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2024,8]]}},"alternative-id":["10.1177\/02783649231201437"],"URL":"https:\/\/doi.org\/10.1177\/02783649231201437","relation":{},"ISSN":["0278-3649","1741-3176"],"issn-type":[{"value":"0278-3649","type":"print"},{"value":"1741-3176","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,11,3]]}}}