Search-Based Spatiotemporal and Multi-Robot Motion Planning on Graphs of Space-Time Convex Sets
作者: Jingtao Tang, Zining Mao, Lufan Yang, Hang Ma
分类: cs.RO, cs.AI
发布日期: 2026-07-01
💡 一句话要点
提出基于时空凸集的多机器人运动规划算法以解决动态环境中的碰撞问题
🎯 匹配领域: 支柱一：机器人控制 (Robot Control) 支柱八：物理动画 (Physics-based Animation)
关键词: 时空运动规划 多机器人系统 图搜索 动态环境 碰撞检测 轨迹优化 精确凸分解
📋 核心要点
- 现有的多机器人运动规划方法在处理动态环境中碰撞区域时面临挑战，尤其是当可行区域瞬态且几何约束复杂时。
- 本文提出了一种基于时空凸集的图搜索算法，通过将无碰撞区域表示为时空中的凸集，实现了高效的时间最优规划。
- 实验结果显示，所提方法在解决多机器人问题时，能够在几分钟内处理多达100个机器人的实例，且速度显著提升，解决方案质量高。
📝 摘要（中文）
时空运动规划，尤其是在多机器人环境中，需要机器人推理随时间变化的无碰撞区域，这在连续空间中是一个挑战。本文提出了一种基于时空凸集（ST-GCS）的算法框架，将无碰撞区域表示为时空中的凸集，轨迹对应于图上的路径及所选集内的连续运动。我们将ST-GCS上的时间最优规划形式化为路径索引状态上的图搜索问题，并开发了一种最佳优先搜索求解器，通过连续轨迹优化评估部分路径，辅以可接受启发式和支配性检查。此外，提出的精确凸分解（ECD）方案能够在时空中保留轨迹占用情况，从而统一处理动态障碍和多机器人交互。实验表明，该方法在狭窄和瞬态可行区域中显著加速了单机器人和多机器人问题的求解。
🔬 方法详解
问题定义：本文旨在解决多机器人在动态环境中进行时空运动规划的问题。现有方法在处理瞬态和几何约束复杂的可行区域时，效率低下且难以保证碰撞安全。
核心思路：提出了一种基于时空凸集（ST-GCS）的算法框架，将动态环境中的无碰撞区域表示为时空中的凸集，利用图搜索方法进行时间最优规划。
技术框架：整体架构包括图搜索求解器、连续轨迹优化模块和精确凸分解（ECD）方案。图搜索求解器负责路径搜索，ECD方案用于处理动态障碍和多机器人交互。
关键创新：最重要的创新在于将时空凸集与图搜索相结合，形成了一种新的运动规划方法，能够有效处理动态环境中的复杂碰撞问题。
关键设计：在算法设计中，采用了可接受启发式和支配性检查来优化路径评估，同时在ECD方案中保留轨迹占用信息，以支持动态障碍的处理。
🖼️ 关键图片
📊 实验亮点
实验结果表明，所提多机器人运动规划算法在处理多达100个机器人的实例时，仅需几分钟，且在狭窄和瞬态可行区域中相比于其他规划器实现了显著的速度提升，解决方案质量保持高水平。
🎯 应用场景
该研究的潜在应用领域包括自动驾驶、无人机编队、智能制造等多机器人协作场景。通过提高多机器人在动态环境中的运动规划效率，能够显著提升系统的整体性能和安全性，具有重要的实际价值和广泛的应用前景。
📄 摘要（原文）
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