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

DevFeed: [Spatiotemporal and Multi-Robot Motion Planning on Graphs of Space-Time Convex Sets](<https://devfeed.tech/articles/spatiotemporal-and-multi-robot-motion-planning-on-graphs-of-space-time-convex-sets-139786.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2607.00444>)

Author: Jingtao Tang, Zining Mao, Lufan Yang, Hang Ma

Published: 2026-11-18T05:00:00Z

Content type: article

Language: en

Sources: [arXiv: Artificial Intelligence](<https://devfeed.tech/sources/arxiv-artificial-intelligence.md>)

Topics: [Robot Navigation](<https://devfeed.tech/topics/robot-navigation.md>), [Combinatorial optimization](<https://devfeed.tech/topics/combinatorial-optimization.md>), [graph theory](<https://devfeed.tech/topics/graph-theory.md>)

Tags: [continuous](<https://devfeed.tech/tags/continuous.md>), [convex](<https://devfeed.tech/tags/convex.md>), [cs-ai](<https://devfeed.tech/tags/cs-ai.md>), [cs-ro](<https://devfeed.tech/tags/cs-ro.md>), [experiments](<https://devfeed.tech/tags/experiments.md>), [graphs](<https://devfeed.tech/tags/graphs.md>), [motion](<https://devfeed.tech/tags/motion.md>), [motion-planning](<https://devfeed.tech/tags/motion-planning.md>), [planning](<https://devfeed.tech/tags/planning.md>), [pruning](<https://devfeed.tech/tags/pruning.md>), [quality](<https://devfeed.tech/tags/quality.md>), [robot](<https://devfeed.tech/tags/robot.md>), [robots](<https://devfeed.tech/tags/robots.md>), [route](<https://devfeed.tech/tags/route.md>), [scalability](<https://devfeed.tech/tags/scalability.md>), [search](<https://devfeed.tech/tags/search.md>), [simulations](<https://devfeed.tech/tags/simulations.md>), [space](<https://devfeed.tech/tags/space.md>), [temporal](<https://devfeed.tech/tags/temporal.md>), [time](<https://devfeed.tech/tags/time.md>), [timing](<https://devfeed.tech/tags/timing.md>), [velocity](<https://devfeed.tech/tags/velocity.md>)

## AI overview

The framework plans continuous robot motion in space and time by representing collision-free regions as convex sets, jointly optimizing the route and piecewise-linear trajectory timing under velocity limits. Exact Convex Decomposition removes swept space occupied by moving obstacles and previously planned robots while preserving a convex decomposition for later queries. A best-first solver uses temporal reachability for dominance pruning and admissible heuristics; heuristic bounds can be reused after reservation updates. The authors combine these methods with prioritized planning and dynamically adjusted coordination windows to limit graph growth. Experiments report improved scalability and competitive solution quality against optimization-based and sampling-based planners; simulations coordinate up to 100 robots within a minute, with real-robot demonstrations also reported.

## Source excerpt

arXiv:2607.00444v2 Announce Type: replace-cross Abstract: Decoupled multi-robot motion planning avoids the high-dimensional joint configuration space but requires repeated single-robot planning among moving obstacles, where route choice and timing are coupled. We develop a framework based on graphs of space-time convex sets (ST-GCSs) for continuous spatiotemporal planning and multi-robot coordination. An ST-GCS represents collision-free space-time by convex sets, allowing the sequence of regions and the geometry and timing of piecewise-linear trajectories to be optimized jointly under velocity limits. To incorporate moving obstacles and previously planned robots, we develop Exact Convex Decomposition (ECD), which removes their swept occupancies while maintaining a convex decomposition for subsequent planning queries. Building on path-based GCS search, we develop a best-first solver tailored to the ST-GCS motion model, exploiting temporal reachability for dominance pruning and using admissible heuristics with separate or joint search-key evaluation. Precomputed heuristic bounds can also be reused across reservation-updated graphs. We integrate ST-GCS planning and ECD into prioritized multi-robot planning and introduce windowed coordination with dynamic window adjustment to limit reservation-induced graph growth. Experiments demonstrate improved scalability and competitive solution quality against optimization-based and sampling-based planners on challenging spatiotemporal and multi-robot problems. Large-scale simulations coordinate up to $100$ robots within a minute, while real-robot demonstrations showcase the practical applicability of the framework. Project homepage: https://sites.google.com/view/stgcs.