arXiv cs.AI· Jingtao Tang, Zining Mao, Lufan Yang, Hang Ma·· 4 小时前AI 评分24
基于时空凸集图(ST-GCS)的时空与多机器人运动规划
Spatiotemporal and Multi-Robot Motion Planning on Graphs of Space-Time Convex Sets
AI 导读
研究者提出基于时空凸集图(ST-GCS)的框架,将无碰撞时空用凸集表示,联合优化区域序列与分段线性轨迹的几何和时序,并配合精确凸分解(ECD)处理移动障碍与已规划机器人。该方法集成到优先级多机器人规划中,引入动态窗口调整的窗口化协调以抑制预留导致的图增长。实验显示大规模仿真可在一分钟内协调多达 100 台机器人,并在真实机器人演示中验证了实用性。
正文 · 原文
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