Spatiotemporal and Multi-Robot Motion Planning on Graphs of Space-Time Convex Sets
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Robotics Radio. Generated commentary on the latest robotics and control papers.
Rosa: I'm Rosa.
Dev: And I'm Dev, here with Taro.
Rosa: We're looking at the paper: "Spatiotemporal and Multi-Robot Motion Planning on Graphs of Space-Time Convex Sets".
Title and authors: Rosa: Let's talk about the people behind this work. It’s Rosa and Dev who are leading this discussion today, looking at "Spatiotemporal and Multi-Robot Motion Planning on Graphs of Space-Time Convex Sets." The title itself tells you exactly what they're tackling: planning motion in space and time for multiple robots.
Dev: Yes. The authors are Jingtao Tang, Zining Mao, Lufan Yang, and Hang Ma from Simon Fraser University in Canada. They’ve built this framework based on the idea of using graphs of space-time convex sets to solve motion planning problems where the safe areas change over time in continuous spaces.
Taro: When you hear "space-time convex sets," it sounds mathematically dense, but what does that mean for a robot trying to move? Is it just a fancy way to say "where we are allowed to be"?
Rosa: It means collision-free regions are represented as these specific geometric shapes across the entire space and time domain. A trajectory is then a path connecting vertices on this graph, combined with continuous movement inside those sets, which captures both the physical location and when it happens.
Dev: The authors are focusing on making time-optimal planning practical by developing a bestfirst search solver that uses continuous trajectory optimization to evaluate partial paths, guided by admissible heuristics and dominance checks. This is key because standard shortest path methods don't work easily here because the cost of reaching a spot depends on the entire path taken to get there.
Taro: So they’re essentially using this graph structure not just for connectivity, but as a framework to guide a continuous optimization process during the search, which sounds like it handles that path dependency better.
Rosa: That's right. And they also introduced this Exact Convex Decomposition scheme to reserve those trajectory occupancies directly in space and time, which allows for the unified handling of both dynamic obstacles and how robots interact with each other across all these time steps.
The paper's summary: Dev: Moving on to what the paper actually summarizes, they are proposing this Graph of Space-Time Convex Sets approach. It’s a representation where vertices are collision-free sets in space and time, and edges connect sets that overlap in time and space.
Rosa: So they extend a standard spatial graph by adding the time dimension, meaning you can capture both geometric constraints and temporal constraints within this single structure. This naturally allows for spatiotemporal planning in changing environments.
Taro: And they solve the problem of finding the time-optimal path on this structure by treating it as a graph search over path-indexed states, where the cost of reaching a point isn't just about that point, but about the whole history of how you got there.
Dev: Exactly. To make this search practical, they developed a bestfirst search solver that evaluates partial paths using continuous trajectory optimization and relies on admissible heuristics and dominance checks to guide the process efficiently through the large state space.
Rosa: Beyond just planning, they also present an ECD scheme that lets them reserve future trajectory occupancies directly into these space-time sets, which is crucial for managing dynamic obstacles and inter-robot conflicts simultaneously.
Taro: So if you have a set of robots moving, this structure lets you reserve where they *will* be in time, and then the search avoids those reserved areas while optimizing the actual movement within the remaining safe regions.
Dev: That's the gist of it: they use this graph representation for planning and an ECD scheme for reserving trajectories to make multi-robot motion planning manageable by unifying geometric and temporal constraints.
The paper's improvements: Rosa: Now let’s talk about what they did to improve existing methods. They shifted from a single large optimization problem to a search-based formulation, which is a big change because traditional methods often get stuck trying to solve one massive optimization equation at once.
Dev: That shift is important because it allows them to generalize the ECD scheme to arbitrary dimensions of space and time, not just the specific case they first used. They also introduced windowed coordination, which focuses planning effort on relevant time intervals for multi-robot interactions.
Taro: Windowed coordination sounds like a way to reduce the computational load by only looking at a finite window W instead of trying to plan the entire horizon from start to finish every single time.
Rosa: They also introduced a specific planner they call Windowed-PBS plus BFS, which uses windowed Prioritized Planning with an NC node expansion rule and a coordinator that calculates the planning horizon based on the limit of velocity.
Dev: That coordinator is defined by Delta plan being equal to Delta execution, which is five times the radius divided by the infinity norm of the velocity limit vector. It’s a specific way they define how much time they look ahead based on how fast things can move.
Taro: And for the low-level solver, they use a BFS solver employing hmax, epsilon equals ten, upper bound pruning, and delta pos as their low-level component to refine the path selection within that windowed framework.
Rosa: These improvements are what make it practical: avoiding one huge mixed integer formulation while still optimizing continuous trajectories along the candidate paths found by the search structure.
Conclusion: Dev: So, to wrap up on "Spatiotemporal and Multi-Robot Motion Planning on Graphs of Space-Time Convex Sets," they’ve shown that this graph-search approach combined with ECD is a viable way to tackle complex spatiotemporal motion planning for multiple robots. It offers a search-based formulation instead of a monolithic optimization problem, which is much more scalable.
Rosa: The results show substantial speedups over other optimization-based approaches while keeping the solution quality high, even in challenging scenarios. For instance, they solved bottlenecked fifty robot instances in one point six four meters and dense one hundred robot instances in one point six zero meters.
Taro: That’s a lot of robots handled quickly; it suggests this method remains the most consistent quality-scalability trade-off across all the domains they tested. I'm curious about what they stopped doing, though?
Dev: They also implemented trajectory optimization postprocessing to smooth out those piecewise-linear trajectories that come out of the planner by solving a quadratic program over sampled spatial positions at fixed time samples. This regularizes the velocity variation between those points.
Rosa: And this smoothing helps bridge the gap between the discrete planning and the actual continuous motion, giving you smoother trajectories that are certified collision-free only at those sampled states where constraints are imposed.
Taro: It seems like it’s a solid framework for large-scale MRMP problems, especially because they found it to be the only viable choice for the most challenging instances across all their tested domains. But the authors did mention that future work will involve extending trajectory representations beyond just piecewise-linear forms and developing more robust window selection rules for complete coordination in finite windows.
Dev: They are also looking toward using those continuous optimization techniques to solve global trajectory optimization using a sequential rolling-horizon variant, optimizing a short block of time samples at a time while keeping the rest fixed. That keeps each local problem small but still achieves that smoothing objective.
Rosa: So, in summary, this paper shows how you can use graphs of space-time convex sets to create a framework for planning that handles continuous motion and multiple robots efficiently by combining search with trajectory reservation techniques like ECD and windowed coordination.
Simon Fraser University
cs.RO, cs.AI
Submitted: 2026-07-01
Updated: 2026-11-17
Project page: https://sites.google.com/view/stgcs
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Importance score: 92/100
The gist: Spatiotemporal motion planning, particularly in multirobot settings, is addressed by formulating it as a graph-search problem on Graphs of Space-Time Convex Sets (ST-GCSs).
Key concepts
- Graphs of Space-Time Convex Sets (ST-GCSs)
- This framework models the entire planning problem by representing collision-free regions in both space and time as convex sets. Trajectories are then treated as paths on a graph connecting these sets, allowing robots to reason about continuous motion within these time-varying safe zones.
- Exact Convex Decomposition (ECD)
- ECD reserves trajectory occupancies directly in the space-time domain. This allows for the unified management of dynamic obstacles and robot interactions by reserving specific piecewise-linear trajectory volumes within the ST-GCS, which are then removed from available space.
- Windowed Coordination Scheme
- This technique improves multi-robot efficiency by focusing planning effort on relevant time intervals. Instead of planning for the entire horizon, it restricts coordination to a finite window W, significantly reducing computation cost while maintaining practical coordination for robot interactions.
- Windowed-PBS + BFS Planner
- This is the proposed planner combining Windowed Prioritized Planning (Windowed-PBS) and a Breadth-First Search (BFS) solver. It uses heuristics like hmax and dominance checks to guide the search, avoiding large mixed-integer formulations while optimizing continuous trajectories along candidate paths.
Terminology
Summary
Spatiotemporal motion planning, particularly in multirobot settings, is addressed by formulating it as a graph-search problem on Graphs of Space-Time Convex Sets (ST-GCSs). p. 0 In this framework, collision-free regions are represented as convex sets within the space-time domain, and trajectories are defined as paths on this graph combined with continuous motions within the selected convex sets. p. 0 Time-optimal planning is achieved by performing a graph search over path-indexed states, employing a bestfirst search solver that evaluates partial paths through continuous trajectory optimization guided by admissible heuristics and dominance checks. p. 0
A key innovation is the Exact Convex Decomposition (ECD) scheme, which reserves trajectory occupancies directly in space-time. p. 0 This allows for the unified handling of dynamic obstacles and inter-robot interactions. p. 0 For multi-robot motion planning (MRMP), ST-GCS planning and ECD are integrated into prioritized planning methods, enhanced by a windowed coordination scheme to boost efficiency. p. 1
The work extends prior research by shifting from a monolithic optimization problem to a search-based formulation, generalizing the ECD scheme to arbitrary-dimensional space-time, and introducing windowed coordination. p. 1 The proposed planner is termed Windowed-PBS + BFS, which utilizes windowed Prioritized Planning (Windowed-PBS) with an NC node expansion rule and delta plan = delta exec = 5r/v lim infinity as the high-level coordinator, coupled with a BFS solver employing h max, epsilon=10, upper bound pruning, and delta pos as the low-level solver. p. 1 This approach avoids a single large mixed-integer formulation while optimizing continuous trajectories along candidate paths. p. 1
Empirical evaluations demonstrate that this framework provides substantial speedups over optimization-based approaches while maintaining high solution quality in challenging spatiotemporal scenarios. p. 0 The proposed Windowed-PBS + BFS planner has shown strong performance, solving bottlenecked 50-robot instances in 1. p. 164m and dense 100-robot instances in 1. p. 160m, establishing it as the most consistent quality-scalability tradeoff across various domains. p. 0 Furthermore, trajectory optimization postprocessing smooths piecewise-linear trajectories by solving a Quadratic Program over sampled spatial positions at fixed time samples to regularize velocity variation. p. 5 The framework's scalability is further validated by its effectiveness on large-scale MRMP problems, suggesting it remains the only viable choice for the most challenging instances across all tested domains. Future work is motivated by extending trajectory representations beyond piecewise-linear forms and developing more robust window selection rules for completeness in finite-window coordination. p. 3
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Spatiotemporal motion planning can be performed efficiently in continuous spaces by formulating it as a graph search problem on graphs of space-time convex sets (ST-GCSs). This allows robots to reason about collisionfree regions that change over time, treating trajectories as paths on the graph together with continuous motions within the selected sets.
-
A bestfirst search solver can be developed for planning on ST-GCSs by repeatedly evaluating partial paths via continuous trajectory optimization, guided by admissible heuristics and dominance checks. This makes the planning process practical and scalable for complex scenarios, as shown by its ability to solve instances with up to 100 robots within only a few minutes.
-
An Exact Convex Decomposition (ECD) scheme can be introduced to reserve trajectory occupancies in arbitrary-dimensional spacetime by updating an ST-GCS, thereby enabling a unified handling of dynamic obstacles and multi-robot interactions. This allows for the reservation of piecewise-linear trajectory occupancies, which are then removed from the relevant space-time convex sets.
-
Windowed coordination schemes can be integrated into prioritized planning methods to improve efficiency in multi-robot coordination by focusing planning effort on the relevant time intervals. This reduces the computation cost associated with full-horizon reservation by only considering trajectory portions inside a finite planning window W.
-
The system can utilize admissible heuristics such as hmax, which combines motion-only, triplet-relaxation, and interface-to-set cost heuristics to preserve the strongest available lower bound at each search node. This combination ensures that the search remains guided by the most informative relaxation across different constraint sets.
-
Pairwise dominance checks can be employed to prune the search tree using safe set containment check delta set, heuristic arrival-state-containment check delta state, or heuristic position-based dominance check delta pos. These checks allow for pruning based on whether a retained node N' dominates N, which preserves the theoretical guarantee of an epsilon optimal trajectory if the checks are safe.
-
The system can solve multi-robot motion planning by using prioritized planning (PP) or priority-based search (PBS) over ST-GCSs and ECD reservations. This allows for sequential planning where each lower-priority robot plans on a progressively updated ST-GCS, ensuring it avoids all higher-priority trajectories and their endpoint staying portions.
-
The system can implement a closed-loop execution with receding horizon by using windowed coordination, where the coordinator commits the returned trajectory only over a finite window W and replans from the updated window-start states after each successful call. This provides a practical way to manage full-horizon robot coordination while reducing computation cost.
-
Trajectory optimization postprocessing can be applied to smooth piecewise-linear trajectories produced by the planner by solving a Quadratic Program (QP) over sampled spatial positions at fixed time samples. This results in trajectories that are certified to be space-time collisionfree only at the sampled states where constraints are imposed, while maintaining smoothness between them.
-
The system can perform global trajectory optimization using a sequential rolling-horizon variant that optimizes a short block of consecutive time samples, fixes the accepted prefix, and advances the block until all samples have been processed. This decomposition keeps each local trajectory-optimization QP small and makes the full problem easier to solve, while retaining the same smoothing objective.
Sources
- GCS*: Forward Heuristic Search on Implicit Graphs of Convex Sets
- Towards Tight Convex Relaxations for Contact-Rich Manipulation
- Collision-free time-optimal path parameterization for multi-robot teams
- A biconvex method for minimum-time motion planning through sequences of convex sets
- Multi-Query Shortest-Path Problem in Graphs of Convex Sets
- Mixed Discrete and Continuous Planning using Shortest Walks in Graphs of Convex Sets
- Systematic Constraint Formulation and Collision-Free Trajectory Planning Using Space-Time Graphs of Convex Sets
- Safe Interval RRT* for Scalable Multi-Robot Path Planning in Continuous Space
- $A^*$ for Graphs of Convex Sets
- Superfast Configuration-Space Convex Set Computation on GPUs for Online Motion Planning
- Motion Planning with Precedence Specifications via Augmented Graphs of Convex Sets
Related papers
- Rethinking Actions: Continuity-Aware Priors for World-Model Planning
- MOSAIC: Modular Obstacle and Spatial-Aware Framework for Manipulation In Cluttered Scenes
- SAGAS: Semantic-Aware Graph-Assisted Stitching for Offline Temporal Logic Planning
- DexSeed: Expanding Human Hand-Object Interactions into Robot Demonstrations for Dexterous Policy Learning
- LaST0.5: A Generalist World Action Model with Interaction-Centric Latent Reasoning
- CIALLO: Learning Shared Intent Representations for Cross-Embodiment Manipulation