{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,2]],"date-time":"2026-05-02T10:02:00Z","timestamp":1777716120509,"version":"3.51.4"},"reference-count":74,"publisher":"SAGE Publications","issue":"10-11","license":[{"start":{"date-parts":[[2024,12,16]],"date-time":"2024-12-16T00:00:00Z","timestamp":1734307200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc\/4.0\/"},{"start":{"date-parts":[[2024,12,16]],"date-time":"2024-12-16T00:00:00Z","timestamp":1734307200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"funder":[{"name":"Frederick and Barbara Cronin Fellowship"},{"name":"Amazon.com","award":["PO No. 2D-06310236"],"award-info":[{"award-number":["PO No. 2D-06310236"]}]}],"content-domain":{"domain":["journals.sagepub.com"],"crossmark-restriction":true},"short-container-title":["The International Journal of Robotics Research"],"published-print":{"date-parts":[[2025,9]]},"abstract":"<jats:p>Computing optimal, collision-free trajectories for high-dimensional systems is a challenging and important problem. Sampling-based planners struggle with the dimensionality, whereas trajectory optimizers may get stuck in local minima due to inherent nonconvexities in the optimization landscape. The use of mixed-integer programming to encapsulate these nonconvexities and find globally optimal trajectories has recently shown great promise, thanks in part to tight convex relaxations and efficient approximation strategies that greatly reduce runtimes. These approaches were previously limited to Euclidean configuration spaces, precluding their use with mobile bases or continuous revolute joints. In this paper, we handle such scenarios by modeling configuration spaces as Riemannian manifolds, and we describe a reduction procedure for the zero-curvature case to a mixed-integer convex optimization problem. We further present a method for obtaining approximate solutions via piecewise-linear approximations that is applicable to manifolds of arbitrary curvature. We demonstrate our results on various robot platforms, including producing efficient collision-free trajectories for a PR2 bimanual mobile manipulator.<\/jats:p>","DOI":"10.1177\/02783649241302419","type":"journal-article","created":{"date-parts":[[2024,12,16]],"date-time":"2024-12-16T12:37:51Z","timestamp":1734352671000},"page":"1840-1862","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":0,"title":["Non-Euclidean motion planning with graphs of geodesically convex sets"],"prefix":"10.1177","volume":"44","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5411-0710","authenticated-orcid":false,"given":"Thomas","family":"Cohn","sequence":"first","affiliation":[{"name":"MIT"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mark","family":"Petersen","sequence":"additional","affiliation":[{"name":"Harvard"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Max","family":"Simchowitz","sequence":"additional","affiliation":[{"name":"MIT"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Russ","family":"Tedrake","sequence":"additional","affiliation":[{"name":"MIT"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"179","published-online":{"date-parts":[[2024,12,16]]},"reference":[{"issue":"3","key":"e_1_3_4_2_1","first-page":"2531","article-title":"Simultaneous contact, gait, and motion planning for robust multilegged locomotion via mixed-integer convex optimization","volume":"3","author":"Aceituno-Cabezas B","year":"2017","unstructured":"Aceituno-Cabezas B, Mastalli C, Dai H, et al. (2017) Simultaneous contact, gait, and motion planning for robust multilegged locomotion via mixed-integer convex optimization. IEEE Robotics and Automation Letters 3(3): 2531\u20132538.","journal-title":"IEEE Robotics and Automation Letters"},{"key":"e_1_3_4_3_1","doi-asserted-by":"crossref","unstructured":"Adu-Bredu A Devraj N Jenkins OC (2022) Optimal constrained task planning as mixed integer programming. ArXiv preprint arXiv:2211.09632.","DOI":"10.1109\/IROS47612.2022.9981237"},{"key":"e_1_3_4_4_1","doi-asserted-by":"crossref","unstructured":"Amice A Dai H Werner P et al. (2023) Finding and optimizing certified collision-free regions in configuration space for robot manipulators. In: International workshop on the algorithmic foundations of robotics College Park MD 22\u201324 June 2022 328\u2013348. Springer.","DOI":"10.1007\/978-3-031-21090-7_20"},{"issue":"1","key":"e_1_3_4_5_1","first-page":"1","article-title":"On the product Riemannian manifolds","volume":"5","author":"Atceken M","year":"2003","unstructured":"Atceken M, Keles S (2003) On the product Riemannian manifolds. Differential Geometry - Dynamical Systems 5(1): 1\u20137.","journal-title":"Differential Geometry - Dynamical Systems"},{"key":"e_1_3_4_6_1","doi-asserted-by":"publisher","DOI":"10.1515\/9783110361629"},{"issue":"1","key":"e_1_3_4_7_1","doi-asserted-by":"crossref","first-page":"63","DOI":"10.2307\/2308932","article-title":"A derivation of n-dimensional spherical coordinates","volume":"67","author":"Blumenson L","year":"1960","unstructured":"Blumenson L (1960) A derivation of n-dimensional spherical coordinates. The American Mathematical Monthly 67(1): 63\u201366.","journal-title":"The American Mathematical Monthly"},{"key":"e_1_3_4_8_1","volume-title":"An Introduction to Optimization on Smooth Manifolds","author":"Boumal N","year":"2022","unstructured":"Boumal N (2022) An Introduction to Optimization on Smooth Manifolds. Cambridge, UK: Cambridge University Press. URL: https:\/\/www.nicolasboumal.net\/book."},{"key":"e_1_3_4_9_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804441"},{"key":"e_1_3_4_10_1","doi-asserted-by":"publisher","DOI":"10.1090\/gsm\/033"},{"key":"e_1_3_4_11_1","doi-asserted-by":"crossref","unstructured":"Bylard A Bonalli R Pavone M (2021) Composable geometric motion policies using multi-task pullback bundle dynamical systems. In: 2021 IEEE international conference on robotics and automation (ICRA) Xi\u2019an China 30 May\u20135 June 2021 7464\u20137470. IEEE.","DOI":"10.1109\/ICRA48506.2021.9561320"},{"key":"e_1_3_4_12_1","volume-title":"Frontiers and Applications Series","author":"Cartan \u00c9","year":"1983","unstructured":"Cartan \u00c9 (1983) Geometry of Riemannian spaces: lie groups; history. In: Frontiers and Applications Series. Berkeley CA: Math Science Press, Vol. 13."},{"key":"e_1_3_4_13_1","volume-title":"Comparison Theorems in Riemannian Geometry","author":"Cheeger J","year":"1975","unstructured":"Cheeger J, Ebin DG, Ebin DG (1975) Comparison Theorems in Riemannian Geometry. Amsterdam, the Netherlands: North-Holland publishing company, Vol. 9."},{"key":"e_1_3_4_14_1","unstructured":"Chen J Li J Huang Y et al. (2022) Cooperative task and motion planning for multi-arm assembly systems. ArXiv preprint arXiv:2203.02475."},{"key":"e_1_3_4_15_1","doi-asserted-by":"crossref","unstructured":"Cheng CA Mukadam M Issac J et al. (2018) RMPflow: a computational graph for automatic motion policy generation. In: International workshop on the algorithmic foundations of robotics Merida Mexico 9\u201311 December 2018 441\u2013457. Springer.","DOI":"10.1007\/978-3-030-44051-0_26"},{"key":"e_1_3_4_16_1","unstructured":"Chew Chia SY Jiang RH Graesdal BP et al. (2024) GCS*: forward heuristic search on implicit graphs of convex sets. In: Proceedings of the 16th international workshop on the algorithmic foundations of robotics (WAFR) Chicago IL 7 October 2024 (To appear)."},{"key":"e_1_3_4_17_1","volume-title":"Studies in Mathematics and Its Applications","author":"Ciarlet PG","year":"1988","unstructured":"Ciarlet PG (1988) Mathematical elasticity volume I: three-dimensional elasticity. In: Studies in Mathematics and Its Applications. London, UK: Elsevier Science."},{"key":"e_1_3_4_18_1","first-page":"167","volume-title":"Metro: Measuring Error on Simplified Surfaces","author":"Cignoni P","year":"1998","unstructured":"Cignoni P, Rocchini C, Scopigno R (1998) Metro: Measuring Error on Simplified Surfaces. Hoboken, NJ: Wiley Online Library, Vol. 17, pp. 167\u2013174."},{"key":"e_1_3_4_19_1","doi-asserted-by":"crossref","unstructured":"Cohn T Devraj N Jenkins OC (2022) Topologically-informed atlas learning. In: 2022 international conference on robotics and automation (ICRA) Philadelphia PA 23\u201327 May 2022 3598\u20133604. IEEE.","DOI":"10.1109\/ICRA46639.2022.9812311"},{"key":"e_1_3_4_20_1","doi-asserted-by":"publisher","unstructured":"Cohn T Petersen M Simchowitz M et al. (2023) Non-Euclidean motion planning with graphs of geodesically-convex sets. In: Proceedings of robotics: science and systems Daegu Republic of Korea 15\u201319 July 2023. DOI: 10.15607\/RSS.2023.XIX.057.","DOI":"10.15607\/RSS.2023.XIX.057"},{"key":"e_1_3_4_21_1","doi-asserted-by":"crossref","unstructured":"Cohn T Shaw S Simchowitz M et al. (2024) Constrained bimanual planning with analytic inverse kinematics. In: 2024 IEEE international conference on robotics and automation (ICRA) Yokohama Japan 13\u201318 May 2024 6935\u20136942. IEEE.","DOI":"10.1109\/ICRA57147.2024.10610675"},{"key":"e_1_3_4_22_1","doi-asserted-by":"crossref","unstructured":"Dahl VA Dahl AB Larsen R (2014) Surface detection using round cut. In: 2014 2nd international conference on 3D vision Tokyo Japan 8\u201311 December 2014 82\u201389. IEEE.","DOI":"10.1109\/3DV.2014.60"},{"key":"e_1_3_4_23_1","doi-asserted-by":"publisher","DOI":"10.1177\/0278364919846512"},{"key":"e_1_3_4_24_1","volume-title":"Quaternions, Interpolation and Animation","author":"Dam EB","year":"1998","unstructured":"Dam EB, Koch M, Lillholm M (1998) Quaternions, Interpolation and Animation. Princeton, NJ: Citeseer, Vol. 2."},{"key":"e_1_3_4_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972573"},{"key":"e_1_3_4_26_1","doi-asserted-by":"crossref","unstructured":"Deits R Tedrake R (2014) Footstep planning on uneven terrain with mixed-integer convex optimization. In: 2014 IEEE-RAS international conference on humanoid robots Atlanta GA 18\u201320 November 2014 279\u2013286. IEEE.","DOI":"10.1109\/HUMANOIDS.2014.7041373"},{"key":"e_1_3_4_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-16595-0_7"},{"key":"e_1_3_4_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-2201-7"},{"key":"e_1_3_4_29_1","volume-title":"Piecewise Linear Reconstruction and Meshing of Submanifolds of Euclidean Space","author":"Ghosh A","year":"2012","unstructured":"Ghosh A (2012) Piecewise Linear Reconstruction and Meshing of Submanifolds of Euclidean Space. PhD Thesis, Universit\u00e9 de Nice Sophia Antipolis, Nice, France."},{"key":"e_1_3_4_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0036144504446096"},{"key":"e_1_3_4_31_1","volume-title":"User\u2019s Guide for SNOPT 7.7: Software for Large-Scale Nonlinear Programming. Center for Computational Mathematics Report CCoM 18-1, Department of Mathematics","author":"Gill PE","year":"2018","unstructured":"Gill PE, Murray W, Saunders MA, et al. (2018) User\u2019s Guide for SNOPT 7.7: Software for Large-Scale Nonlinear Programming. Center for Computational Mathematics Report CCoM 18-1, Department of Mathematics. San Diego, CA: University of California."},{"key":"e_1_3_4_32_1","volume-title":"Gurobi Optimizer Reference Manual","author":"Gurobi Optimization LLC","year":"2023","unstructured":"Gurobi Optimization LLC (2023) Gurobi Optimizer Reference Manual. Beaverton, OR: Gurobi Optimization LLC."},{"key":"e_1_3_4_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSSC.1968.300136"},{"key":"e_1_3_4_34_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218127402004498"},{"key":"e_1_3_4_35_1","volume-title":"Introduction to Operations Research","author":"Hillier FS","year":"2015","unstructured":"Hillier FS, Lieberman GJ (2015) Introduction to Operations Research. New York, NY: McGraw-Hill."},{"key":"e_1_3_4_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.arcontrol.2020.10.008"},{"key":"e_1_3_4_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2012.2222272"},{"key":"e_1_3_4_38_1","doi-asserted-by":"crossref","unstructured":"Kalakrishnan M Chitta S Theodorou E et al. (2011) STOMP: stochastic trajectory optimization for motion planning. In: 2011 IEEE international conference on robotics and automation Shanghai China 9\u201313 May 2011 4569\u20134574. IEEE.","DOI":"10.1109\/ICRA.2011.5980280"},{"key":"e_1_3_4_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/70.508439"},{"key":"e_1_3_4_40_1","doi-asserted-by":"crossref","unstructured":"Klein H Jaquier N Meixner A et al. (2022) A Riemannian take on human motion analysis and retargeting. In: 2022 IEEE\/RSJ international conference on intelligent robots and systems (IROS) Kyoto Japan 23\u201327 October 2022 5210\u20135217. IEEE.","DOI":"10.1109\/IROS47612.2022.9982127"},{"key":"e_1_3_4_41_1","unstructured":"Knyazev AV Zhu P (2012) Principal angles between subspaces and their tangents. ArXiv preprint arXiv:1209.0523."},{"key":"e_1_3_4_42_1","doi-asserted-by":"crossref","unstructured":"Landry B Deits R Florence PR et al. (2016) Aggressive quadrotor flight through cluttered environments using mixed integer programming. In: 2016 IEEE international conference on robotics and automation (ICRA) Stockholm Sweden 16\u201321 May 2016 1469\u20131475. IEEE.","DOI":"10.1109\/ICRA.2016.7487282"},{"key":"e_1_3_4_43_1","article-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. The Annual Research Report.","journal-title":"The Annual Research Report"},{"key":"e_1_3_4_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4419-9982-5_1"},{"key":"e_1_3_4_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-91755-9"},{"key":"e_1_3_4_46_1","unstructured":"Liverani C (2019) Implicit function theorem 1 (a quantitative version). retrieved January 13. https:\/\/www.mat.uniroma2.it\/\u02dcliverani\/Calcolo1-2016\/implicit.pdf."},{"key":"e_1_3_4_47_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(01)00348-1"},{"key":"e_1_3_4_48_1","unstructured":"Marcucci T Umenberger J Parrilo PA et al. (2021) Shortest paths in graphs of convex sets. ArXiv preprint arXiv:2101.11565."},{"key":"e_1_3_4_49_1","doi-asserted-by":"publisher","DOI":"10.1126\/scirobotics.adf7843"},{"key":"e_1_3_4_50_1","unstructured":"MOSEK ApS (2019) MOSEK optimization suite."},{"key":"e_1_3_4_51_1","doi-asserted-by":"publisher","DOI":"10.2307\/1968928"},{"key":"e_1_3_4_52_1","doi-asserted-by":"publisher","DOI":"10.1115\/1.2826114"},{"key":"e_1_3_4_53_1","unstructured":"Petersen M Tedrake R (2023) Growing convex collision-free regions in configuration space using nonlinear programming. ArXiv preprint arXiv:2303.14737."},{"key":"e_1_3_4_54_1","unstructured":"Phillips-Grafflin C (2023) Common robotics Utilities."},{"key":"e_1_3_4_55_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jat.2007.03.002"},{"key":"e_1_3_4_56_1","doi-asserted-by":"crossref","unstructured":"Porta JM Jaillet L (2010) Path planning on manifolds using randomized higher-dimensional continuation. In: Algorithmic foundations of robotics IX: selected contributions of the ninth international workshop on the algorithmic foundations of robotics Singapore 13\u201315 December 2010 337\u2013353. Springer.","DOI":"10.1007\/978-3-642-17452-0_20"},{"key":"e_1_3_4_57_1","doi-asserted-by":"crossref","unstructured":"Rana MA Li A Fox D et al. (2021) Towards coordinated robot motions: end-to-end learning of motion policies on transform trees. In: 2021 IEEE\/RSJ international conference on intelligent robots and systems (IROS) Prague Czech Republic 27 September\u20131 October 2021 7792\u20137799. IEEE.","DOI":"10.1109\/IROS51168.2021.9636097"},{"key":"e_1_3_4_58_1","unstructured":"Ratliff ND Issac J Kappler D et al. (2018) Riemannian motion policies. ArXiv preprint arXiv:1801.02854."},{"key":"e_1_3_4_59_1","doi-asserted-by":"publisher","DOI":"10.1109\/LRA.2017.2755078"},{"key":"e_1_3_4_60_1","doi-asserted-by":"crossref","unstructured":"Suh HT Xiong X Singletary A et al. (2020) Energy-efficient motion planning for multi-modal hybrid locomotion. In: 2020 IEEE\/RSJ international conference on intelligent robots and systems (IROS) Las Vegas NV 25\u201329 October 2020 7027\u20137033. IEEE.","DOI":"10.1109\/IROS45743.2020.9340761"},{"key":"e_1_3_4_61_1","unstructured":"Tedrake R (2022) Robotic manipulation. URL: https:\/\/manipulation.mit.edu."},{"key":"e_1_3_4_62_1","unstructured":"Tedrake R the Drake Development Team R (2019) Drake: model-based design and verification for robotics. URL: https:\/\/drake.mit.edu."},{"key":"e_1_3_4_63_1","doi-asserted-by":"crossref","unstructured":"Tika A Gashi F Bajcinca N (2022) Robot online task and trajectory planning using mixed-integer model predictive control. In: 2022 European control conference (ECC) London UK 12\u201315 July 2022 2005\u20132011. IEEE.","DOI":"10.23919\/ECC55457.2022.9838243"},{"key":"e_1_3_4_64_1","unstructured":"Toussaint M (2014) Newton methods for k-order Markov constrained motion problems. ArXiv preprint arXiv:1407.0414."},{"key":"e_1_3_4_65_1","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.2003.11920004"},{"key":"e_1_3_4_66_1","volume-title":"Mixed-integer Convex Optimization for Planning Aggressive Motions of Legged Robots over Rough Terrain","author":"Valenzuela AK","year":"2016","unstructured":"Valenzuela AK (2016) Mixed-integer Convex Optimization for Planning Aggressive Motions of Legged Robots over Rough Terrain. PhD Thesis, Massachusetts Institute of Technology, Cambridge, MA."},{"key":"e_1_3_4_67_1","doi-asserted-by":"publisher","DOI":"10.1109\/LRA.2022.3143311"},{"key":"e_1_3_4_68_1","unstructured":"Vishnoi NK (2018) Geodesic convex optimization: differentiation on manifolds geodesics and convexity. ArXiv preprint arXiv:1806.06373."},{"key":"e_1_3_4_69_1","volume-title":"Guiding Nonconvex Trajectory Optimization with Hierarchical Graphs of Convex Sets","author":"von Wrangel D","year":"2024","unstructured":"von Wrangel D (2024) Guiding Nonconvex Trajectory Optimization with Hierarchical Graphs of Convex Sets. PhD Thesis, Massachusetts Institute of Technology, Cambridge, MA."},{"key":"e_1_3_4_70_1","doi-asserted-by":"crossref","unstructured":"Werner P Amice A Marcucci T et al. (2024) Approximating robot configuration spaces with few convex sets using clique covers of visibility graphs. In: 2024 IEEE international conference on robotics and automation (ICRA) Yokohama Japan 13\u201318 May 2024 10359\u201310365. IEEE.","DOI":"10.1109\/ICRA57147.2024.10610005"},{"key":"e_1_3_4_71_1","unstructured":"Wu Y Spasojevic I Chaudhari P et al. (2024) Optimal convex cover as collision-free space approximation for trajectory generation. ArXiv preprint arXiv:2406.09631."},{"key":"e_1_3_4_72_1","doi-asserted-by":"publisher","DOI":"10.1109\/TRA.2004.824640"},{"key":"e_1_3_4_73_1","doi-asserted-by":"publisher","DOI":"10.3390\/app12084018"},{"key":"e_1_3_4_74_1","unstructured":"Zhang H Sra S (2016) First-order methods for geodesically convex optimization. In: Conference on learning theory New York NY 23\u201326 June 2016 1617\u20131638. PMLR."},{"key":"e_1_3_4_75_1","doi-asserted-by":"publisher","DOI":"10.1177\/0278364913488805"}],"container-title":["The International Journal of Robotics Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/02783649241302419","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/full-xml\/10.1177\/02783649241302419","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/02783649241302419","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T10:17:24Z","timestamp":1777457844000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/02783649241302419"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,12,16]]},"references-count":74,"journal-issue":{"issue":"10-11","published-print":{"date-parts":[[2025,9]]}},"alternative-id":["10.1177\/02783649241302419"],"URL":"https:\/\/doi.org\/10.1177\/02783649241302419","relation":{},"ISSN":["0278-3649","1741-3176"],"issn-type":[{"value":"0278-3649","type":"print"},{"value":"1741-3176","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,12,16]]}}}