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

Jul 16, 2026

Upload by Himbo

Spatiotemporal motion planning, especially in multi-robot settings, requires reasoning about collision-free regions that evolve over time and are often transient and geometrically constrained. The work proposes an algorithmic framework using graphs of space-time convex sets (ST-GCSs), where collision-free regions become convex sets in space-time and trajectories are graph paths plus continuous motions inside selected sets. Time-optimal planning is cast as a graph-search problem with admissible heuristics and dominance checks, and an Exact Convex Decomposition reserves space-time occupancies to handle dynamic obstacles and multi-robot interactions. Experiments show speedups and high-quality solutions, including up to 100 robots solved in minutes.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages31

Reading Time1 h 18 min

Introduction

Problem Overview

Related Work and Challenges

Proposed Framework: ST-GCS

Path-Indexed Graph Search Formulation

Best-First Search Solver Components

Search-Based Spatiotemporal and Multi-Robot Motion Planning on Graphs of Space-Time Convex Sets Jingtao Tang∗, Zining Mao, Lufan Yang, and Hang Ma Simon Fraser University, Canada arXiv :2607 .00444v 1 [ cs .RO] 1 Jul 2026 Abstract Spatiotemporal motion planning, especially in multirobot settings, requires robots to reason about collisionfree 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 bestfirst 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 multirobot motion planner can solve instances with up to 100 robots within only a few minutes. Project homepage: [https://sites.google.com/view/stgcs](https://sites.google.com/view/stgcs). Keywords: Motion Planning, Multi-Robot Coordination, Heuristic Search, Graphs of Convex Sets 1 Introduction Spatiotemporal motion planning is a core problem in robotics. A robot must move from a start state toa goal while avoiding both static obstacles and timevarying constraints induced by dynamic environments or other robots. This problem becomes particularly challenging in continuous domains when feasible regions are ∗ Corresponding author email: jingtao [tang@sfu.ca](tang@sfu.ca) Figure 1: Demonstration of the proposed MRMP planner on ST-GCS, where robots 1 and 3 exchange positions with robots 2 and 4, respectively. Left: Solution trajectories visualized in 2D space, with higher transparency indicating states at later time stamps. Right: Solution trajectories τ1 and τ2 visualized in 3D space-time, where τ2 treats τ1 as a space-time obstacle and plans a trajectory through space-time collision-free convex sets (colored polyhedra) that exclude the τ1 occupancy. transient, geometrically constrained, and tightly coupled with time. Such conditions arise naturally in MultiRobot Motion Planning (MRMP), where each robot must treat the trajectories of others as dynamic obstacles, as well as in single-robot planning tasks with moving obstacles or temporal constraints. Despite extensive progress, existing approaches still struggle to provide efficient and reliable solutions in these settings. Sampling-based planners, such as PRM (Kavraki et al. , 1996) and RRT (LaValle, 1998), and their spatiotemporal variants (H¨uppi et al., 2022; Grothe et al., 2022), offer modeling flexibility but rely on random exploration, which can be ineffective in capturing narrow or short-lived feasible regions in spacetime. Their performance further degrades due to repeated collision checking in a time-augmented state space. Optimization-based approaches based on the Graph of Convex Sets (GCS) replace random exploration with deterministic reasoning over convex decompositions (Marcucci et al., 2023, 2024b), but extending them to dynamic environments requires a unified treatment of time, velocity constraints, and dyna

FAQs

What is the key representation introduced for spatiotemporal motion planning?

The document introduces a Graph of Space-Time Convex Sets (ST-GCS), where vertices correspond to collision-free convex sets in space-time and edges represent nonempty intersections between sets.

How is time-optimal planning formulated on the ST-GCS?

Time-optimal planning is formulated as a graph-search problem over path-indexed states, because feasibility and cost depend on the entire prefix path rather than only the reached vertex.

How does the method handle dynamic obstacles and multi-robot interactions?

It integrates ST-GCS planning with an Exact Convex Decomposition (ECD) scheme that reserves trajectory occupancies in space-time, enabling unified handling of dynamic obstacles and coordination constraints among robots.

Jul 16, 2026

Upload by Himbo