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.

Demonstration of the proposed PBS+TGCS method for MRMP: (a)(b) The solution visualized in (a) spatial coordinates and (b) space-time coordinates with the starts (squares), goals (stars), and trajectories (dot lines) of the robots highlighted in colors; (c) Low-level planner solving a TGCS program to generate a trajectory (blue solid line) through space-time collision-free convex sets (colored polyhedrons), which avoids trajectories of a high-priority robot (red solid line); (d) Magnified view of the congested region in (c), located at the center of the map.

We now introduce two prioritized planning frameworks for MRMP that use ST-GCS. In both frameworks, robots plan one at a time using ST-GCS as a low-level trajectory planner to avoid collisions with higher-priority robots’ trajectories, which are incorporated as dynamic obstacles through ECD. 

The following shows several examples of performance comparison between SP+T-PRM [5], SP+ST-RRT* [6] and our RP+ST-GCS and PBS+ST-GCS on 2D mobile robots (SP represents sequential planning at high level). Black regions are the (static/dynamic) obstacles, and colored regions are the space collision-free convex sets. The Sum-of-Costs (SoC; the sum of time costs of all trajectories), makespan (MS; the maximum time costs of all trajectories), and planning runtime (RT) are reported as metrics. Please check our paper for more detailed results.

[1] Marcucci, Tobia, et al. "Shortest paths in graphs of convex sets." SIAM Journal on Optimization 34.1 (2024): 507-532. 

[2] Marcucci, Tobia, et al. "Motion planning around obstacles with convex optimization." Science robotics 8.84 (2023): eadf7843.

[3] Erdmann, Michael, and Tomas Lozano-Perez. "On multiple moving objects." Algorithmica 2 (1987): 477-521.

[4] Ma, Hang, et al. "Searching with consistent prioritization for multi-agent path finding." Proceedings of the AAAI conference on artificial intelligence. Vol. 33. No. 01. 2019.

[5] Hüppi, Matthias, et al. "T-prm: Temporal probabilistic roadmap for path planning in dynamic environments." 2022 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). IEEE, 2022.

[6] Grothe, Francesco, et al. "St-rrt*: Asymptotically-optimal bidirectional motion planning through space-time." 2022 International Conference on Robotics and Automation (ICRA). IEEE, 2022.