Search papers, labs, and topics across Lattice.
This paper introduces an algorithmic framework for spatiotemporal motion planning in multi-robot systems using graphs of space-time convex sets (ST-GCSs) to represent dynamic collision-free regions. The authors formulate time-optimal planning as a graph-search problem and develop a best-first search solver that optimizes trajectories while accommodating dynamic obstacles and multi-robot interactions through an Exact Convex Decomposition (ECD) scheme. Experimental results indicate that the proposed approach significantly outperforms existing planners, achieving substantial speedups and maintaining high-quality solutions, even in complex environments with transient feasible regions.
Multi-robot motion planning can now be solved in minutes for up to 100 robots, even in challenging environments with dynamic obstacles.
Spatiotemporal motion planning, especially in multi-robot settings, requires robots to reason about collision-free 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 best-first 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 multi-robot motion planner can solve instances with up to $100$ robots within only a few minutes. Project homepage: https://sites.google.com/view/stgcs
