{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,3]],"date-time":"2026-07-03T12:45:25Z","timestamp":1783082725694,"version":"3.54.6"},"reference-count":57,"publisher":"American Association for the Advancement of Science (AAAS)","issue":"84","content-domain":{"domain":["www.science.org"],"crossmark-restriction":true},"short-container-title":["Sci. Robot."],"published-print":{"date-parts":[[2023,11,22]]},"abstract":"<jats:p>From quadrotors delivering packages in urban areas to robot arms moving in confined warehouses, motion planning around obstacles is a core challenge in modern robotics. Planners based on optimization can design trajectories in high-dimensional spaces while satisfying the robot dynamics. However, in the presence of obstacles, these optimization problems become nonconvex and very hard to solve, even just locally. Thus, when facing cluttered environments, roboticists typically fall back to sampling-based planners that do not scale equally well to high dimensions and struggle with continuous differential constraints. Here, we present a framework that enables convex optimization to efficiently and reliably plan trajectories around obstacles. Specifically, we focus on collision-free motion planning with costs and constraints on the shape, the duration, and the velocity of the trajectory. Using recent techniques for finding shortest paths in Graphs of Convex Sets (GCS), we design a practical convex relaxation of the planning problem. We show that this relaxation is typically very tight, to the point that a cheap postprocessing of its solution is almost always sufficient to identify a collision-free trajectory that is globally optimal (within the parameterized class of curves). Through numerical and hardware experiments, we demonstrate that our planner, which we name GCS, can find better trajectories in less time than widely used sampling-based algorithms and can reliably design trajectories in high-dimensional complex environments.<\/jats:p>","DOI":"10.1126\/scirobotics.adf7843","type":"journal-article","created":{"date-parts":[[2023,11,15]],"date-time":"2023-11-15T18:58:12Z","timestamp":1700074692000},"update-policy":"https:\/\/doi.org\/10.34133\/aaas_crossmark","source":"Crossref","is-referenced-by-count":152,"title":["Motion planning around obstacles with convex optimization"],"prefix":"10.1126","volume":"8","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8249-0434","authenticated-orcid":true,"given":"Tobia","family":"Marcucci","sequence":"first","affiliation":[{"name":"Department of Electrical Engineering and Computer Science, MIT, Cambridge, MA, USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0005-1427-6096","authenticated-orcid":true,"given":"Mark","family":"Petersen","sequence":"additional","affiliation":[{"name":"School of Engineering and Applied Sciences, Harvard University, Cambridge, MA, USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0000-1963-0879","authenticated-orcid":true,"given":"David","family":"von Wrangel","sequence":"additional","affiliation":[{"name":"Department of Electrical Engineering and Computer Science, MIT, Cambridge, MA, USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8712-7092","authenticated-orcid":true,"given":"Russ","family":"Tedrake","sequence":"additional","affiliation":[{"name":"Department of Electrical Engineering and Computer Science, MIT, Cambridge, MA, USA."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"221","reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1017\/S0263574714000289"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.2514\/2.4231"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1177\/0278364910369189"},{"key":"e_1_3_2_5_2","doi-asserted-by":"crossref","unstructured":"F. Augugliaro A.\u00a0P.\u00a0Schoellig R.\u00a0D\u2019Andrea Generation of collision-free trajectories for a quadrocopter fleet: A sequential convex programming approach in 2012 IEEE\/RSJ International Conference on Intelligent Robots and Systems (IEEE 7 to 12 October 2012).","DOI":"10.1109\/IROS.2012.6385823"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1177\/0278364914528132"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1177\/0278364917712421"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCST.2019.2949540"},{"key":"e_1_3_2_9_2","doi-asserted-by":"crossref","unstructured":"N. Ratliff M.\u00a0Zucker J.\u00a0A.\u00a0Bagnell S.\u00a0Srinivasa Chomp: Gradient optimization techniques for efficient motion planning 2009 IEEE in International Conference on Robotics and Automation (IEEE 12 to 17 May 2009).","DOI":"10.1109\/ROBOT.2009.5152817"},{"key":"e_1_3_2_10_2","doi-asserted-by":"crossref","unstructured":"M. Kalakrishnan S.\u00a0Chitta E.\u00a0Theodorou P.\u00a0Pastor S.\u00a0Schaal STOMP: Stochastic trajectory optimization for motion planning in 2011 IEEE International Conference on Robotics and Automation (IEEE 9 to 19 May 2011).","DOI":"10.1109\/ICRA.2011.5980280"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2016.2623345"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1109\/70.508439"},{"key":"e_1_3_2_13_2","unstructured":"S.\u00a0M.\u00a0LaValle Rapidly-exploring random trees: A new tool for path planning TR 98\u201311 Computer Science Department Iowa State University (1998)."},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1109\/ACCESS.2014.2302442"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1177\/0278364911406761"},{"key":"e_1_3_2_16_2","doi-asserted-by":"crossref","unstructured":"J.\u00a0D.\u00a0Gammell S.\u00a0S.\u00a0Srinivasa T.\u00a0D.\u00a0Barfoot Informed RRT*: Optimal sampling-based path planning focused via direct sampling of an admissible ellipsoidal heuristic in 2014 IEEE\/RSJ International Conference on Intelligent Robots and Systems (IEEE 14 to 18 September 2014).","DOI":"10.1109\/IROS.2014.6942976"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1177\/0278364915577958"},{"key":"e_1_3_2_18_2","doi-asserted-by":"crossref","unstructured":"D.\u00a0J.\u00a0Webb J.\u00a0Van Den Berg Kinodynamic RRT*: Asymptotically optimal motion planning for robots with linear dynamics in 2013 IEEE International Conference on Robotics and Automation (IEEE 6 to 10 May 2013).","DOI":"10.1109\/ICRA.2013.6631299"},{"key":"e_1_3_2_19_2","doi-asserted-by":"crossref","unstructured":"G. Goretkin A.\u00a0Perez R.\u00a0Platt G.\u00a0Konidaris Optimal sampling-based planning for linear-quadratic kinodynamic systems in 2013 IEEE International Conference on Robotics and Automation (IEEE 6 to 10 May 2013).","DOI":"10.1109\/ICRA.2013.6630907"},{"key":"e_1_3_2_20_2","doi-asserted-by":"crossref","unstructured":"A. Wu S.\u00a0Sadraddini R.\u00a0Tedrake R3T: Rapidly-exploring random reachable set tree for optimal kinodynamic planning of nonlinear hybrid systems in 2020 IEEE International Conference on Robotics and Automation (IEEE 31 May to 31 August 2020).","DOI":"10.1109\/ICRA40945.2020.9196802"},{"key":"e_1_3_2_21_2","doi-asserted-by":"crossref","unstructured":"T. Schouwenaars B.\u00a0De Moor E.\u00a0Feron J.\u00a0How Mixed integer programming for multi-vehicle path planning in 2001 European Control Conference (IEEE 4 to 7 September 2001).","DOI":"10.23919\/ECC.2001.7076321"},{"key":"e_1_3_2_22_2","doi-asserted-by":"crossref","unstructured":"A. Richards J.\u00a0P.\u00a0How Aircraft trajectory planning with collision avoidance using mixed integer linear programming in 2002 American Control Conference (IEEE 8 to 10 May 2002).","DOI":"10.1109\/ACC.2002.1023918"},{"key":"e_1_3_2_23_2","doi-asserted-by":"crossref","unstructured":"D. Mellinger A.\u00a0Kushleyev V.\u00a0Kumar Mixed-integer quadratic program trajectory generation for heterogeneous quadrotor teams in 2012 IEEE International Conference on Robotics and Automation (IEEE 14 to 18 May 2012).","DOI":"10.1109\/ICRA.2012.6225009"},{"key":"e_1_3_2_24_2","doi-asserted-by":"crossref","unstructured":"R. Deits R.\u00a0Tedrake Efficient mixed-integer planning for UAVs in cluttered environments in 2015 IEEE International Conference on Robotics and Automation (IEEE 26 to 30 May 2015).","DOI":"10.1109\/ICRA.2015.7138978"},{"key":"e_1_3_2_25_2","doi-asserted-by":"crossref","unstructured":"T. Marcucci R.\u00a0Tedrake Mixed-integer formulations for optimal control of piecewise-affine systems in 22nd ACM International Conference on Hybrid Systems: Computation and Control (ACM 16 to 18 April 2019).","DOI":"10.1145\/3302504.3311801"},{"key":"e_1_3_2_26_2","unstructured":"S. Boyd L.\u00a0Vandenberghe Convex Optimization (Cambridge Univ. Press 2013)."},{"key":"e_1_3_2_27_2","doi-asserted-by":"crossref","unstructured":"J.\u00a0H.\u00a0Reif Complexity of the mover\u2019s problem and generalizations in 20th Annual Symposium on Foundations of Computer Science (IEEE Computer Society 29 to 31 October 1979).","DOI":"10.1109\/SFCS.1979.10"},{"key":"e_1_3_2_28_2","doi-asserted-by":"crossref","unstructured":"J. Canny The Complexity of Robot Motion Planning (MIT press 1988).","DOI":"10.1109\/SFCS.1988.21947"},{"key":"e_1_3_2_29_2","doi-asserted-by":"crossref","unstructured":"B. El Khadir J.\u00a0B.\u00a0Lasserre V.\u00a0Sindhwani Piecewise-linear motion planning amidst static moving or morphing obstacles in 2021 IEEE International Conference on Robotics and Automation (IEEE 30 May to 5 June 2021).","DOI":"10.1109\/ICRA48506.2021.9561614"},{"key":"e_1_3_2_30_2","unstructured":"T. Marcucci J.\u00a0Umenberger P.\u00a0A.\u00a0Parrilo R.\u00a0Tedrake Shortest paths in graphs of convex sets. arXiv:2101.11565 (2021). https:\/\/doi.org\/10.48550\/arXiv.2101.11565."},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2005.10.005"},{"key":"e_1_3_2_32_2","doi-asserted-by":"crossref","unstructured":"N. Ayanian V.\u00a0Kumar Abstractions and controllers for groups of robots in environments with obstacles in 2010 IEEE International Conference on Robotics and Automation (IEEE 3 to 7 May 2010).","DOI":"10.1109\/ROBOT.2010.5509534"},{"key":"e_1_3_2_33_2","first-page":"494","article-title":"Fast approximate convex decomposition using relative concavity","volume":"45","author":"Ghosh M.","year":"2013","unstructured":"M.\u00a0Ghosh, N. M.\u00a0Amato, Y.\u00a0Lu, J.-M.\u00a0Lien, Fast approximate convex decomposition using relative concavity. Comput. Des. 45, 494\u2013504 (2013).","journal-title":"Comput. Des."},{"key":"e_1_3_2_34_2","doi-asserted-by":"crossref","unstructured":"R. Deits R.\u00a0Tedrake Computing large convex regions of obstacle-free space through semidefinite programming in Algorithmic Foundations of Robotics XI (Springer 2015) pp.\u00a0109\u2013124.","DOI":"10.1007\/978-3-319-16595-0_7"},{"key":"e_1_3_2_35_2","doi-asserted-by":"crossref","unstructured":"A. Amice H.\u00a0Dai P.\u00a0Werner A.\u00a0Zhang R.\u00a0Tedrake Finding and optimizing certified collision-free regions in configuration space for robot manipulators in Algorithmic Foundations of Robotics XV (Springer 2023) pp.\u00a0328\u2013348.","DOI":"10.1007\/978-3-031-21090-7_20"},{"key":"e_1_3_2_36_2","doi-asserted-by":"crossref","unstructured":"H. Dai A.\u00a0Amice P.\u00a0Werner A.\u00a0Zhang R.\u00a0Tedrake Certified polyhedral decompositions of collision-free configuration space. arXiv:2302.12219 (2023). https:\/\/doi.org\/10.48550\/arXiv.2302.12219.","DOI":"10.1177\/02783649231201437"},{"key":"e_1_3_2_37_2","unstructured":"M. Petersen R.\u00a0Tedrake Growing convex collision-free regions in configuration space using nonlinear programming. arXiv:2303.14737 (2023). https:\/\/doi.org\/10.48550\/arXiv.2303.14737."},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1109\/LRA.2022.3147458"},{"key":"e_1_3_2_39_2","unstructured":"M.\u00a0E.\u00a0Flores Real-time trajectory generation for constrained nonlinear dynamical systems using non-uniform rational B-spline basis functions Ph.D. thesis California Institute of Technology (2008)."},{"key":"e_1_3_2_40_2","doi-asserted-by":"crossref","unstructured":"B. Lau C.\u00a0Sprunk W.\u00a0Burgard Kinodynamic motion planning for mobile robots using splines in 2009 IEEE\/RSJ International Conference on Intelligent Robots and Systems (IEEE 10 to 15 October 2009).","DOI":"10.1109\/IROS.2009.5354805"},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10846-014-0172-0"},{"key":"e_1_3_2_42_2","unstructured":"F.\u00a0A.\u00a0Koolen Balance control and locomotion planning for humanoid robots using nonlinear centroidal models Ph.D. thesis Massachusetts Institute of Technology (2020)."},{"key":"e_1_3_2_43_2","doi-asserted-by":"crossref","unstructured":"N. Csomay-Shanklin A.\u00a0J.\u00a0Taylor U.\u00a0Rosolia A.\u00a0D.\u00a0Ames Multi-rate planning and control of uncertain nonlinear systems: Model predictive control and control Lyapunov functions 2022 IEEE 61st Conference on Decision and Control (IEEE 6 to 9 December 2022).","DOI":"10.1109\/CDC51059.2022.9992902"},{"key":"e_1_3_2_44_2","doi-asserted-by":"crossref","unstructured":"D. Mellinger V.\u00a0Kumar Minimum snap trajectory generation and control for quadrotors in 2011 IEEE International Conference on Robotics and Automation (IEEE 9 to 13 May 2011).","DOI":"10.1109\/ICRA.2011.5980409"},{"key":"e_1_3_2_45_2","unstructured":"C. Phillips-Grafflin Common robotics utilities."},{"key":"e_1_3_2_46_2","unstructured":"R. Tedrake The Drake Development Team Drake: Model-based design and verification for robotics (2019)."},{"key":"e_1_3_2_47_2","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2005.847599"},{"key":"e_1_3_2_48_2","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2013.2240176"},{"key":"e_1_3_2_49_2","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2014.2331091"},{"key":"e_1_3_2_50_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702405139"},{"key":"e_1_3_2_51_2","unstructured":"A. Sarmientoy R.\u00a0Murrieta-Cidz S.\u00a0Hutchinsony A sample-based convex cover for rapidly finding an object in a 3-D environment in 2005 IEEE International Conference on Robotics and Automation (IEEE 2005) 18 to 22 April 2005."},{"key":"e_1_3_2_52_2","doi-asserted-by":"publisher","DOI":"10.1163\/156855300741960"},{"key":"e_1_3_2_53_2","doi-asserted-by":"crossref","unstructured":"L. Jaillet T.\u00a0Sim\u00e9on A PRM-based motion planner for dynamically changing environments in 2004 IEEE\/RSJ International Conference on Intelligent Robots and Systems (IEEE 28 September to 2 October 2004).","DOI":"10.1109\/IROS.2004.1389625"},{"key":"e_1_3_2_54_2","unstructured":"J. Van Den Berg D.\u00a0Ferguson J.\u00a0Kuffner Anytime path planning and replanning in dynamic environments in 2006 IEEE International Conference on Robotics and Automation (IEEE 15 to 19 May 2006)."},{"key":"e_1_3_2_55_2","doi-asserted-by":"publisher","DOI":"10.1146\/annurev-control-091420-084139"},{"key":"e_1_3_2_56_2","doi-asserted-by":"crossref","unstructured":"N.\u00a0M.\u00a0Patrikalakis T.\u00a0Maekawa Shape Interrogation for Computer Aided Design and Manufacturing (Springer 2002).","DOI":"10.1007\/978-3-642-04074-0"},{"key":"e_1_3_2_57_2","doi-asserted-by":"crossref","unstructured":"H. Prautzsch W.\u00a0Boehm M.\u00a0Paluszny B\u00e9zier and B-spline Techniques (Springer 2002).","DOI":"10.1007\/978-3-662-04919-8"},{"key":"e_1_3_2_58_2","doi-asserted-by":"crossref","unstructured":"T. Marcucci M.\u00a0Petersen D.\u00a0von Wrangel R.\u00a0Tedrake Code for the article motion planning around obstacles with convex optimization Zenodo DOI: 10.5281\/zenodo.10005653 (2023).","DOI":"10.1126\/scirobotics.adf7843"}],"container-title":["Science Robotics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.science.org\/doi\/pdf\/10.1126\/scirobotics.adf7843","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,2]],"date-time":"2024-11-02T01:53:14Z","timestamp":1730512394000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.science.org\/doi\/10.1126\/scirobotics.adf7843"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,11,22]]},"references-count":57,"journal-issue":{"issue":"84","published-print":{"date-parts":[[2023,11,22]]}},"alternative-id":["10.1126\/scirobotics.adf7843"],"URL":"https:\/\/doi.org\/10.1126\/scirobotics.adf7843","relation":{},"ISSN":["2470-9476"],"issn-type":[{"value":"2470-9476","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,11,22]]},"assertion":[{"value":"2022-11-12","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-10-19","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-11-15","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}],"article-number":"eadf7843"}}