# Shortest Paths in Graphs of Convex Sets

arXiv: https://arxiv.org/abs/2101.11565 · HTML: https://mlsanity.com/paper/2101.11565/

## Key facts

- Cited by 22 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Jan 2021.

## Built on by (most cited first, 22 of 22)

- [ReKep: Spatio-Temporal Reasoning of Relational Keypoint Constraints for Robotic Manipulation](https://mlsanity.com/paper/2409.01652/) (2024)
- [PointWorld: Scaling 3D World Models for In-The-Wild Robotic Manipulation](https://mlsanity.com/paper/2601.03782/) (2026)
- [Provable Guarantees for Generative Behavior Cloning: Bridging Low-Level Stability and High-Level Behavior](https://mlsanity.com/paper/2307.14619/) (2023)
- [Model-Based Control with Sparse Neural Dynamics](https://mlsanity.com/paper/2312.12791/) (2023)
- [Constant-time Motion Planning with Anytime Refinement for Manipulation](https://mlsanity.com/paper/2311.00837/) (2023)
- [A Mixed-Integer Conic Program for the Moving-Target Traveling Salesman Problem based on a Graph of Convex Sets](https://mlsanity.com/paper/2403.04917/) (2024)
- [Simulation-Informed Diffusion for Decentralized Multi-robot Motion Planning](https://mlsanity.com/paper/2605.27697/) (2026)
- [A^* for Graphs of Convex Sets](https://mlsanity.com/paper/2407.17413/) (2024)
- [The State of Robot Motion Generation](https://mlsanity.com/paper/2410.12172/) (2024)
- [Space-Time Graphs of Convex Sets for Multi-Robot Motion Planning](https://mlsanity.com/paper/2503.00583/) (2025)
- [GHOST: Solving the Traveling Salesman Problem on Graphs of Convex Sets](https://mlsanity.com/paper/2511.06471/) (2025)
- [Double-Bounded Nonlinear Optimal Transport for Size Constrained Min Cut Clusterin](https://mlsanity.com/paper/2501.18143/) (2025)
- [Toward Generalist Neural Motion Planners for Robotic Manipulators: Challenges and Opportunities](https://mlsanity.com/paper/2603.24318/) (2026)
- [Search-Based Spatiotemporal and Multi-Robot Motion Planning on Graphs of Space-Time Convex Sets](https://mlsanity.com/paper/2607.00444/) (2026)
- [Robust Stochastic Shortest-Path Planning via Risk-Sensitive Incremental Sampling](https://mlsanity.com/paper/2408.08668/) (2024)
- [A Schema-aware Logic Reformulation for Graph Reachability](https://mlsanity.com/paper/2410.02533/) (2024)
- [Real-Time Sampling-based Online Planning for Drone Interception](https://mlsanity.com/paper/2502.14231/) (2025)
- [Constant-Time Planning for Chaining Collision-free Motion to Manipulation Behaviors](https://mlsanity.com/paper/2512.00939/) (2025)
- [Approximately Optimal Global Planning for Contact-Rich SE(2) Manipulation on a Graph of Reachable Sets](https://mlsanity.com/paper/2601.10827/) (2026)
- [Tempered Sequential Monte Carlo for Trajectory and Policy Optimization with Differentiable Dynamics](https://mlsanity.com/paper/2604.21456/) (2026)
- [Unified Branch-and-Bound Search for the Steiner Traveling Salesman Problem on Graphs of Convex Sets](https://mlsanity.com/paper/2608.21319/) (2026)
- [Optimal Control with Learned Critics under Unmodeled State Dependencies](https://mlsanity.com/paper/2610.05359/) (2026)

## Abstract (arXiv)

Given a graph, the shortest-path problem requires finding a sequence of edges with minimum cumulative length that connects a source vertex to a target vertex. We consider a variant of this classical problem in which the position of each vertex in the graph is a continuous decision variable constrained in a convex set, and the length of an edge is a convex function of the position of its endpoints. Problems of this form arise naturally in many areas, from motion planning of autonomous vehicles to optimal control of hybrid systems. The price for such a wide applicability is the complexity of this problem, which is easily seen to be NP-hard. Our main contribution is a strong and lightweight mixed-integer convex formulation based on perspective operators, that makes it possible to efficiently find globally optimal paths in large graphs and in high-dimensional spaces.