# Space-Time Graphs of Convex Sets for Multi-Robot Motion Planning

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 34 references that are in the map.
- First posted on arXiv 1 Mar 2025.

## Builds on (most cited first, 17 of 17)

- [Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks](https://mlsanity.com/paper/1906.08291/) (2019)
- [Searching with Consistent Prioritization for Multi-Agent Path Finding](https://mlsanity.com/paper/1812.06356/) (2018)
- [Motion Planning around Obstacles with Convex Optimization](https://mlsanity.com/paper/2205.04422/) (2022)
- [Shortest Paths in Graphs of Convex Sets](https://mlsanity.com/paper/2101.11565/) (2021)
- [Representation-Optimal Multi-Robot Motion Planning using Conflict-Based Search](https://mlsanity.com/paper/1909.13352/) (2019)
- [Finding a needle in an exponential haystack: Discrete RRT for exploration of implicit roadmaps in multi-robot motion planning](https://mlsanity.com/paper/1305.2889/) (2013)
- [Conflict-based Search for Multi-Robot Motion Planning with Kinodynamic Constraints](https://mlsanity.com/paper/2207.00576/) (2022)
- [Temporal Logic Motion Planning with Convex Optimization via Graphs of Convex Sets](https://mlsanity.com/paper/2301.07773/) (2023)
- [Certified Polyhedral Decompositions of Collision-Free Configuration Space](https://mlsanity.com/paper/2302.12219/) (2023)
- [Non-Euclidean Motion Planning with Graphs of Geodesically-Convex Sets](https://mlsanity.com/paper/2305.06341/) (2023)
- [Multi-Agent Motion Planning with B'ezier Curve Optimization under Kinodynamic Constraints](https://mlsanity.com/paper/2311.14145/) (2023)
- [GCS*: Forward Heuristic Search on Implicit Graphs of Convex Sets](https://mlsanity.com/paper/2407.08848/) (2024)
- [ST-RRT*: Asymptotically-Optimal Bidirectional Motion Planning through Space-Time](https://mlsanity.com/paper/2203.02176/) (2022)
- [Fast Path Planning Through Large Collections of Safe Boxes](https://mlsanity.com/paper/2305.01072/) (2023)
- [Approximating Robot Configuration Spaces with few Convex Sets using Clique Covers of Visibility Graphs](https://mlsanity.com/paper/2310.02875/) (2023)
- [Implicit Graph Search for Planning on Graphs of Convex Sets](https://mlsanity.com/paper/2410.08909/) (2024)
- [Reevaluation of Large Neighborhood Search for MAPF: Findings and Opportunities](https://mlsanity.com/paper/2407.09451/) (2024)

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

- [Search-Based Spatiotemporal and Multi-Robot Motion Planning on Graphs of Space-Time Convex Sets](https://mlsanity.com/paper/2607.00444/) (2026)
- [Unified Branch-and-Bound Search for the Steiner Traveling Salesman Problem on Graphs of Convex Sets](https://mlsanity.com/paper/2608.21319/) (2026)

## Abstract (arXiv)

We address the Multi-Robot Motion Planning (MRMP) problem of computing collision-free trajectories for multiple robots in shared continuous environments. While existing frameworks effectively decompose MRMP into single-robot subproblems, spatiotemporal motion planning with dynamic obstacles remains challenging, particularly in cluttered or narrow-corridor settings. We propose Space-Time Graphs of Convex Sets (ST-GCS), a novel planner that systematically covers the collision-free space-time domain with convex sets instead of relying on random sampling. By extending Graphs of Convex Sets (GCS) into the time dimension, ST-GCS formulates time-optimal trajectories in a unified convex optimization that naturally accommodates velocity bounds and flexible arrival times. We also propose Exact Convex Decomposition (ECD) to "reserve" trajectories as spatiotemporal obstacles, maintaining a collision-free space-time graph of convex sets for subsequent planning. Integrated into two prioritized-planning frameworks, ST-GCS consistently achieves higher success rates and better solution quality than state-of-the-art sampling-based planners -- often at orders-of-magnitude faster runtimes -- underscoring its benefits for MRMP in challenging settings.