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

📄 arXiv: 2503.00583v2 📥 PDF

作者: Jingtao Tang, Zining Mao, Lufan Yang, Hang Ma

分类: cs.RO, cs.AI

发布日期: 2025-03-01 (更新: 2025-06-27)

备注: IROS'25 (to appear)

💡 一句话要点

提出时空凸集图ST-GCS，解决复杂环境下多机器人运动规划问题

🎯 匹配领域: 支柱一：机器人控制 (Robot Control) 支柱八：物理动画 (Physics-based Animation)

关键词: 多机器人运动规划 时空规划 凸集图 凸优化 碰撞避免

📋 核心要点

  1. 现有MRMP方法在复杂环境下，尤其是有动态障碍物时，时空运动规划面临挑战，难以保证规划效率和成功率。
  2. 论文提出ST-GCS，通过在时空域构建凸集图，将多机器人运动规划问题转化为凸优化问题，从而实现高效的轨迹规划。
  3. 实验结果表明，ST-GCS在成功率、解的质量和运行时间上均优于现有基于采样的规划器，尤其在复杂环境中优势明显。

📝 摘要（中文）

本文针对多机器人运动规划(MRMP)问题，旨在为共享连续环境中的多个机器人计算无碰撞轨迹。现有框架虽然能有效将MRMP分解为单机器人子问题，但在复杂或狭窄环境中，动态障碍物下的时空运动规划仍然具有挑战性。为此，我们提出时空凸集图(ST-GCS)，一种新型规划器，它系统地用凸集覆盖无碰撞时空域，而非依赖随机采样。通过将凸集图(GCS)扩展到时间维度，ST-GCS在统一的凸优化中制定时间最优轨迹，自然地适应速度限制和灵活的到达时间。我们还提出了精确凸分解(ECD)来“保留”轨迹作为时空障碍物，为后续规划维护无碰撞的时空凸集图。集成到两个优先级规划框架中，ST-GCS始终比最先进的基于采样的规划器实现更高的成功率和更好的解决方案质量，通常运行时间快几个数量级，突显了其在具有挑战性的MRMP设置中的优势。

🔬 方法详解

问题定义：论文旨在解决多机器人运动规划（MRMP）问题，即在共享的连续环境中，为多个机器人寻找无碰撞的轨迹。现有方法，特别是基于采样的规划器，在复杂环境（例如，拥挤或狭窄的走廊）中，面对动态障碍物时，效率和成功率会显著下降。这些方法通常难以保证解的最优性，并且计算成本较高。

核心思路：论文的核心思路是将环境的时空域分解为一系列凸集，并构建一个图，其中节点代表凸集，边代表凸集之间的可通行路径。通过这种方式，将复杂的非凸运动规划问题转化为一系列凸优化问题，从而可以利用高效的凸优化求解器找到时间最优的轨迹。这种方法避免了随机采样，并能系统地覆盖自由空间。

技术框架：ST-GCS的整体框架包括以下几个主要步骤：1) 使用精确凸分解（ECD）将自由空间分解为凸集；2) 将凸集扩展到时间维度，形成时空凸集；3) 构建时空凸集图（ST-GCS），其中节点代表时空凸集，边代表相邻凸集之间的可行路径；4) 使用凸优化求解器在ST-GCS上寻找时间最优的轨迹；5) 使用ECD将已规划的轨迹“保留”为时空障碍物，以便后续机器人的规划。

关键创新：论文的关键创新在于将凸集图（GCS）的概念扩展到时空域，提出了ST-GCS。与传统的基于采样的规划器不同，ST-GCS系统地覆盖自由空间，避免了随机性，并能保证解的质量。此外，ECD算法能够精确地将自由空间分解为凸集，提高了规划的效率和成功率。将轨迹作为时空障碍物进行“保留”也避免了后续规划中的碰撞。

关键设计：论文的关键设计包括：1) 精确凸分解（ECD）算法，用于将自由空间分解为凸集。ECD算法需要保证分解的精确性，避免过度近似；2) 时空凸集的构建，需要考虑机器人的速度限制和到达时间；3) 凸优化问题的构建，需要选择合适的优化目标（例如，时间最优）和约束条件（例如，速度限制、碰撞避免）；4) 如何有效地将已规划的轨迹作为时空障碍物进行“保留”，避免后续规划中的碰撞。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果表明，ST-GCS在两个优先级规划框架中，始终优于最先进的基于采样的规划器。在复杂环境中，ST-GCS的成功率显著提高，解的质量更好，并且运行时间通常快几个数量级。这表明ST-GCS在解决具有挑战性的多机器人运动规划问题方面具有显著优势。

🎯 应用场景

该研究成果可广泛应用于多机器人协同作业的场景，例如：仓库物流、自动驾驶、无人机编队、以及机器人辅助手术等。通过高效的无碰撞轨迹规划，可以提高多机器人系统的效率和安全性，降低运营成本，并实现更复杂的任务。

📄 摘要（原文）

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.