# Search-Based Spatiotemporal and Multi-Robot Motion Planning on Graphs of Space-Time Convex Sets

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 36 of its 74 references that are in the map.
- First posted on arXiv 1 Jul 2026.

## Builds on (most cited first, 30 of 36)

- [Robot Operating System 2: Design, Architecture, and Uses In The Wild](https://mlsanity.com/paper/2211.07752/) (2022)
- [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)
- [MADER: Trajectory Planner in Multi-Agent and Dynamic Environments](https://mlsanity.com/paper/2010.11061/) (2020)
- [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)
- [Towards Tight Convex Relaxations for Contact-Rich Manipulation](https://mlsanity.com/paper/2402.10312/) (2024)
- [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)
- [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)
- [Conflict-Based Model Predictive Control for Scalable Multi-Robot Motion Planning](https://mlsanity.com/paper/2303.01619/) (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)
- [Superfast Configuration-Space Convex Set Computation on GPUs for Online Motion Planning](https://mlsanity.com/paper/2504.10783/) (2025)
- [A Complete and Bounded-Suboptimal Algorithm for a Moving Target Traveling Salesman Problem with Obstacles in 3D](https://mlsanity.com/paper/2504.14680/) (2025)
- [A^* for Graphs of Convex Sets](https://mlsanity.com/paper/2407.17413/) (2024)
- [Multi-Query Shortest-Path Problem in Graphs of Convex Sets](https://mlsanity.com/paper/2409.19543/) (2024)
- [Planning Shorter Paths in Graphs of Convex Sets by Undistorting Parametrized Configuration Spaces](https://mlsanity.com/paper/2411.18913/) (2024)
- [Safe Interval Randomized Path Planning For Manipulators](https://mlsanity.com/paper/2412.19567/) (2024)
- [Space-Time Graphs of Convex Sets for Multi-Robot Motion Planning](https://mlsanity.com/paper/2503.00583/) (2025)
- [A biconvex method for minimum-time motion planning through sequences of convex sets](https://mlsanity.com/paper/2504.18978/) (2025)
- [Mixed Discrete and Continuous Planning using Shortest Walks in Graphs of Convex Sets](https://mlsanity.com/paper/2507.10878/) (2025)
- [GHOST: Solving the Traveling Salesman Problem on Graphs of Convex Sets](https://mlsanity.com/paper/2511.06471/) (2025)
- [Scalable Multi-Robot Motion Planning Using Workspace Guidance-Informed Hypergraphs](https://mlsanity.com/paper/2311.10176/) (2023)

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

- [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)

Spatiotemporal motion planning, especially in multi-robot settings, requires robots to reason about collision-free regions that change over time, which is challenging in continuous spaces when feasible regions are transient and geometrically constrained. We present an algorithmic framework based on graphs of space-time convex sets (ST-GCSs), where collision-free regions are represented as convex sets in space-time and trajectories correspond to paths on the graph together with continuous motions within the selected sets. We formulate time-optimal planning on ST-GCSs as a graph-search problem over path-indexed states and develop a best-first search solver that evaluates partial paths via continuous trajectory optimization, guided by admissible heuristics and dominance checks. We further present an Exact Convex Decomposition (ECD) scheme to reserve trajectory occupancies in space-time, enabling unified handling of dynamic obstacles and multi-robot interactions. For multi-robot motion planning, we integrate ST-GCS planning and ECD into prioritized planning methods and introduce a windowed coordination scheme to improve efficiency. Extensive experiments on single-robot and multi-robot problems demonstrate substantial speedups over various planners while maintaining high solution quality, particularly in environments with narrow and transient feasible regions. Large-scale demonstrations further show that the proposed multi-robot motion planner can solve instances with up to 100 robots within only a few minutes. Project homepage: https://sites.google.com/view/stgcs