用凸集覆盖时空域，高效规划多机器人无碰撞路径。
Space-Time Graphs of Convex Sets for Multi-Robot Motion Planning
- 以凸集替代随机采样，系统覆盖无碰撞时空区域
- 统一凸优化求解时间最优轨迹，支持速度约束与灵活到达时间
- 适合复杂狭窄环境，比现有方法快数倍且成功率更高
针对多机器人在共享连续环境中规划无碰撞轨迹的多机器人运动规划（MRMP）问题，现有框架虽能将问题分解为单机器人子问题，但在动态障碍物、复杂或狭窄通道场景中仍具挑战。本文提出时空凸集图（ST-GCS），通过将凸集图（GCS）拓展至时间维度，以凸集系统覆盖无碰撞时空域，避免依赖随机采样。该方法在统一凸优化框架中求解时间最优轨迹，自然融入速度约束与灵活到达时间。同时提出精确凸分解（ECD），将已规划路径作为时空障碍物“预留”，保持后续规划所需的无碰撞时空凸集图。集成至两种优先级规划框架后，ST-GCS 在挑战性环境下持续实现更高成功率与更优解质量，运行时间常快于现有采样类方法数个数量级，凸显其在复杂场景下的显著优势。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。