跳到正文
arXiv cs.AI· Jingtao Tang, Zining Mao, Lufan Yang, Hang Ma·· 2 小时前AI 评分18

基于时空凸集图的时空与多机器人运动规划框架 ST-GCS

Spatiotemporal and Multi-Robot Motion Planning on Graphs of Space-Time Convex Sets

AI 导读

研究者提出基于时空凸集图(ST-GCS)的连续时空规划与多机器人协调框架,将无碰撞时空表示为凸集,联合优化区域序列与分段线性轨迹的几何和时序,并配合 Exact Convex Decomposition(ECD)处理移动障碍物占用。该框架集成优先级多机器人规划与动态窗口协调,实验显示大规模仿真可在 1 分钟内协调最多 100 个机器人,并有真实机器人演示验证实用性。

正文 · 原文

View PDF HTML (experimental)

Abstract:Decoupled multi-robot motion planning avoids the high-dimensional joint configuration space but requires repeated single-robot planning among moving obstacles, where route choice and timing are coupled. We develop a framework based on graphs of space-time convex sets (ST-GCSs) for continuous spatiotemporal planning and multi-robot coordination. An ST-GCS represents collision-free space-time by convex sets, allowing the sequence of regions and the geometry and timing of piecewise-linear trajectories to be optimized jointly under velocity limits. To incorporate moving obstacles and previously planned robots, we develop Exact Convex Decomposition (ECD), which removes their swept occupancies while maintaining a convex decomposition for subsequent planning queries. Building on path-based GCS search, we develop a best-first solver tailored to the ST-GCS motion model, exploiting temporal reachability for dominance pruning and using admissible heuristics with separate or joint search-key evaluation. Precomputed heuristic bounds can also be reused across reservation-updated graphs. We integrate ST-GCS planning and ECD into prioritized multi-robot planning and introduce windowed coordination with dynamic window adjustment to limit reservation-induced graph growth. Experiments demonstrate improved scalability and competitive solution quality against optimization-based and sampling-based planners on challenging spatiotemporal and multi-robot problems. Large-scale simulations coordinate up to $100$ robots within a minute, while real-robot demonstrations showcase the practical applicability of the framework. Project homepage: this https URL.
Subjects: Robotics (cs.RO); Artificial Intelligence (cs.AI)
Cite as: arXiv:2607.00444 [cs.RO]
  (or arXiv:2607.00444v2 [cs.RO] for this version)
  https://doi.org/10.48550/arXiv.2607.00444

arXiv-issued DOI via DataCite

Submission history

From: Jing Tao Tang [view email]
[v1] Wed, 1 Jul 2026 04:58:00 UTC (3,543 KB)
[v2] Tue, 17 Nov 2026 06:59:13 UTC (3,604 KB)

来源:arXiv cs.AI · arxiv.org