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

summary

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

In short

The paper formulates spatiotemporal motion planning for multiple robots as a graph search problem on Graphs of Space-Time Convex Sets (ST-GCSs). It introduces an Exact Convex Decomposition (ECD) scheme to handle dynamic obstacles and inter-robot interactions. The resulting Windowed-PBS + BFS planner offers a scalable, search-based method that achieves high quality and speed in complex multirobot scenarios.

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 used across episodes

This episode discusses

The paper

Spatiotemporal and Multi-Robot Motion Planning on Graphs of Space-Time Convex Sets · Read on arXiv

Simon Fraser University

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.

More episodes

← Home