Space-Time Graphs of Convex Sets for Multi-Robot Motion Planning

• URL: http://arxiv.org/abs/2503.00583v1
• Date: Sat, 01 Mar 2025 18:28:57 GMT
• Title: Space-Time Graphs of Convex Sets for Multi-Robot Motion Planning
• Abstract summary: Multi-Robot Motion Planning (MRMP) is a problem of computing problem of collision-free trajectories for multiple robots in continuous environments.<n>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.<n>We also propose Convex Decomposition (ECD) to "reserve" trajectories astemporal obstacles, addressing maintaining a collision-free space-time graph sets for subsequent planning.
• Score: 2.3416394753138037
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Biconvex Optimization for Smooth Minimum-Time Trajectories around Convex Obstacles [49.315843050082925]
  We present a bi approach for minimum-time motion planning convex obstacles that is guaranteed to converge.<n>We find that the proposed method produces high-quality trajectories with times to produce state-of-the-art decomposition of variables.
  arXiv  Detail & Related papers  (2026-08-03T19:48:24Z)
• STL-GCS: A Planner-Controller Framework for Signal Temporal Logic via Graphs of Time-varying Convex Sets [1.1470070927586018]
  We present a unified trajectory planning and control framework for satisfaction of Signal Temporal Logic (STL) specifications defined over convex predicates.<n>At the planning layer, STL tasks are encoded as time-varying convex sets in space configuration.<n>At the control layer, the same time-varying sets used for planning are exploited to design a feedback controller that tracks the planned trajectory.
  arXiv  Detail & Related papers  (2026-07-21T15:30:55Z)
• Search-Based Spatiotemporal and Multi-Robot Motion Planning on Graphs of Space-Time Convex Sets [4.512110686124693]
  We present an algorithmic framework based on graphs of space-time convex sets (ST-GCSs)<n>For multi-robot motion planning, we integrate ST-GCS planning and ECD into prioritized planning methods.<n>For large-scale demonstrations, the proposed multi-robot motion planner can solve instances with up to $100$ robots within only a few minutes.
  arXiv  Detail & Related papers  (2026-07-01T04:58:00Z)
• Signal Temporal Logic Motion Planning via Graphs of Convex Sets [8.443328067924298]
  This paper investigates continuous-time motion planning under Signal Temporal Logic (STL) specifications.<n>We propose a framework that combines timed-automata reasoning with graphs of convex sets.<n> Numerical experiments on low-dimensional benchmarks, a $3$-Drotor, a $30$-DoF humanoid, and a hardware experiment on a UR-3 robot arm demonstrate that the proposed method efficiently solves complex STL motion-planning problems.
  arXiv  Detail & Related papers  (2026-05-22T05:19:43Z)
• Navigating the Clutter: Waypoint-Based Bi-Level Planning for Multi-Robot Systems [54.887871365121775]
  Multi-robot control in cluttered environments is a challenging problem that involves complex physical constraints.<n>We propose a hybrid multi-robot control framework that jointly optimize task and motion planning.<n>Our approach consistently improves task success over motion-agnostic and VLA-based baselines.
  arXiv  Detail & Related papers  (2026-04-22T22:58:47Z)
• RAD-2: Scaling Reinforcement Learning in a Generator-Discriminator Framework [49.531001563853984]
  RAD-2 is a unified generator-discriminator framework for closed-loop planning.<n>It produces diverse trajectory candidates, while an RL-optimized discriminator reranks these candidates according to their long-term driving quality.<n>It reduces the collision rate by 56% compared with strong diffusion-based planners.
  arXiv  Detail & Related papers  (2026-04-16T17:59:44Z)
• GPU-Accelerated Continuous-Time Successive Convexification for Contact-Implicit Legged Locomotion [0.4588028371034407]
  Contact-implicit trajectory optimization (CITO) enables the automatic discovery of contact sequences.<n>We introduce integral cross-compITOlementarity constraints, which eliminate the risk of missing contact events between discretization nodes.<n>We show that the resulting framework, contact-implicit successive convexification (ci-SCvx), models full multibody dynamics in maximal coordinates.
  arXiv  Detail & Related papers  (2026-04-11T02:40:29Z)
• Many-RRT*: Robust Joint-Space Trajectory Planning for Serial Manipulators [1.157930969832493]
  Planning in the manipulator's joint space presents significant challenges due to non-invertible forward kinematics.<n>Many-RRT* is an extension of RRT*-Connect that plans to multiple goals in parallel.
  arXiv  Detail & Related papers  (2026-03-04T19:31:37Z)
• Forecasting as Rendering: A 2D Gaussian Splatting Framework for Time Series Forecasting [79.37674445572462]
  Time series forecasting (TSF) remains a challenging problem due to the intricate entanglement of intraperiod-fluctuations and interperiod-trends.<n>Treating reshaped tensors as static images results in a topological mismatch.<n> relying on uniform fixed-size representations allocates modeling capacity inefficiently.<n>TimeGS is a novel framework that fundamentally shifts the forecasting paradigm from regression to 2D generative rendering.
  arXiv  Detail & Related papers  (2026-02-10T14:13:36Z)
• Towards Robust and Generalizable Continuous Space-Time Video Super-Resolution with Events [71.2439653098351]
  Continuous space-time video super-STVSR has garnered increasing interest for its capability to reconstruct high-resolution and high-frame-rate videos at arbitrary temporal scales.<n>We present EvEnhancer, a novel approach that marries unique properties of high temporal and high dynamic range encapsulated in event streams.<n>Our method achieves state-of-the-art performance on both synthetic and real-world datasets, while maintaining generalizability at OOD scales.
  arXiv  Detail & Related papers  (2025-10-04T15:23:07Z)
• ST-GS: Vision-Based 3D Semantic Occupancy Prediction with Spatial-Temporal Gaussian Splatting [21.87807066521776]
  3D occupancy prediction is critical for comprehensive scene understanding in vision-centric autonomous driving.<n>Recent advances have explored utilizing 3D semantic Gaussians to model occupancy while reducing computational overhead.<n>We propose a novel Spatial-Temporal Gaussian Splatting (ST-GS) framework to enhance both spatial and temporal modeling.
  arXiv  Detail & Related papers  (2025-09-20T06:36:30Z)
• Discrete-Guided Diffusion for Scalable and Safe Multi-Robot Motion Planning [56.240199425429445]
  Multi-Robot Motion Planning (MPMP) involves generating trajectories for multiple robots operating in a shared continuous workspace.<n>While discrete multi-agent finding (MAPF) methods are broadly adopted due to their scalability, their coarse discretization trajectory quality.<n>This paper tackles limitations of two approaches by introducing discrete MAPF solvers with constrained generative diffusion models.
  arXiv  Detail & Related papers  (2025-08-27T17:59:36Z)
• Long-Context State-Space Video World Models [66.28743632951218]
  We propose a novel architecture leveraging state-space models (SSMs) to extend temporal memory without compromising computational efficiency.<n>Central to our design is a block-wise SSM scanning scheme, which strategically trades off spatial consistency for extended temporal memory.<n>Experiments on Memory Maze and Minecraft datasets demonstrate that our approach surpasses baselines in preserving long-range memory.
  arXiv  Detail & Related papers  (2025-05-26T16:12:41Z)
• Reinforcement learning with combinatorial actions for coupled restless bandits [62.89013331120493]
  We propose SEQUOIA, an RL algorithm that directly optimize for long-term reward over the feasible action space.<n>We empirically validate SEQUOIA on four novel restless bandit problems with constraints: multiple interventions, path constraints, bipartite matching, and capacity constraints.
  arXiv  Detail & Related papers  (2025-03-01T21:25:21Z)
• Risk-aware Integrated Task and Motion Planning for Versatile Snake Robots under Localization Failures [6.250953826294371]
  Snake robots enable mobility through extreme terrains and confined environments in terrestrial and space applications.<n>To address this issue, we propose Blind-motion with Intermittently Scheduled Scans (BLISS)<n>BLISS combines proprioception-only mobility with intermittent scans to be resilient against both localization failures and collision risks.
  arXiv  Detail & Related papers  (2025-02-27T02:02:51Z)
• Simultaneous Multi-Robot Motion Planning with Projected Diffusion Models [57.45019514036948]
  Simultaneous MRMP Diffusion (SMD) is a novel approach integrating constrained optimization into the diffusion sampling process to produce kinematically feasible trajectories.<n>The paper introduces a comprehensive MRMP benchmark to evaluate trajectory planning algorithms across scenarios with varying robot densities, obstacle complexities, and motion constraints.
  arXiv  Detail & Related papers  (2025-02-05T20:51:28Z)
• Multi-Agent Path Finding in Continuous Spaces with Projected Diffusion Models [57.45019514036948]
  Multi-Agent Path Finding (MAPF) is a fundamental problem in robotics.<n>This work proposes a novel approach that integrates constrained optimization with diffusion models for MAPF in continuous spaces.
  arXiv  Detail & Related papers  (2024-12-23T21:27:19Z)
• A Hybrid Evolutionary Approach for Multi Robot Coordinated Planning at Intersections [0.0]
  Coordinated multi-robot motion planning at intersections is key for safe mobility in roads, factories and warehouses.<n>We propose a new evolutionary-based algorithm using a parametric lattice-based configuration and the discrete-based RRT for collision-free multi-robot planning at intersections.
  arXiv  Detail & Related papers  (2024-12-02T03:40:04Z)
• Solving optimization problems with local light shift encoding on Rydberg quantum annealers [0.0]
  We provide a non-unit disk framework to solve optimization problems on a Rydberg quantum annealer. Our setup consists of a many-body interacting Rydberg system where locally controllable light shifts are applied to individual qubits. Our numerical simulations implement the local-detuning protocol while globally driving the Rydberg annealer to the desired many-body ground state.
  arXiv  Detail & Related papers  (2023-08-15T14:24:45Z)
• Improving Path Planning Performance through Multimodal Generative Models with Local Critics [1.3706331473063877]
  This paper presents a novel method for accelerating path planning tasks in unknown scenes with obstacles. We use Wasserstein Generative Adversarial Networks (WGANs) with Gradient Penalty (GP) to approximate the distribution of the free conditioned configuration space. Our experiments show promising results for accelerating path planning tasks in unknown scenes while generating quasi-optimal paths with our WGAN-GP.
  arXiv  Detail & Related papers  (2023-06-15T19:51:35Z)
• Simultaneous Contact-Rich Grasping and Locomotion via Distributed Optimization Enabling Free-Climbing for Multi-Limbed Robots [60.06216976204385]
  We present an efficient motion planning framework for simultaneously solving locomotion, grasping, and contact problems. We demonstrate our proposed framework in the hardware experiments, showing that the multi-limbed robot is able to realize various motions including free-climbing at a slope angle 45deg with a much shorter planning time.
  arXiv  Detail & Related papers  (2022-07-04T13:52:10Z)
• Time-Optimal Planning for Quadrotor Waypoint Flight [50.016821506107455]
  Planning time-optimal trajectories at the actuation limit of a quadrotor is an open problem. We propose a solution while exploiting the full quadrotor's actuator potential. We validate our method in real-world flights in one of the world's largest motion-capture systems.
  arXiv  Detail & Related papers  (2021-08-10T09:26:43Z)
• Neural Manipulation Planning on Constraint Manifolds [13.774614900994342]
  We present Constrained Motion Planning Networks (CoMPNet), the first neural planner for multimodal kinematic constraints. We show that CoMPNet solves practical motion planning tasks involving both unconstrained and constrained problems. It generalizes to new unseen locations of the objects, i.e., not seen during training, in the given environments with high success rates.
  arXiv  Detail & Related papers  (2020-08-09T18:58:10Z)
• Jump Operator Planning: Goal-Conditioned Policy Ensembles and Zero-Shot Transfer [71.44215606325005]
  We propose a novel framework called Jump-Operator Dynamic Programming for quickly computing solutions within a super-exponential space of sequential sub-goal tasks. This approach involves controlling over an ensemble of reusable goal-conditioned polices functioning as temporally extended actions. We then identify classes of objective functions on this subspace whose solutions are invariant to the grounding, resulting in optimal zero-shot transfer.
  arXiv  Detail & Related papers  (2020-07-06T05:13:20Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.