让上千智能体在1秒内生成无碰撞速度轨迹，提升路径执行质量51.7%。
WinkTPG: An Execution Framework for Multi-Agent Path Finding Using Temporal Reasoning
- 基于时间规划图的动态速度优化，实现多智能体路径可执行性。
- 支持1000个智能体在1秒内生成可行速度轨迹，方案质量提升51.7%。
- 适用于真实机器人与高保真仿真，兼顾确定性与概率性保障。
在众多现实应用中，为大量智能体规划无碰撞路径是一项挑战。尽管多智能体路径规划（MAPF）近期取得进展，但传统规划器仍依赖简化运动模型，导致生成路径难以直接执行。为此，我们提出动力学时间规划图（kTPG），一种高效将MAPF解转化为动力学可行速度曲线的算法，并引入执行时间不确定性建模：在有界不确定性下提供确定性保证，在随机模型下提供概率保证。在此基础上，提出窗口化kTPG（WinkTPG），一种基于窗口机制的增量式执行框架，可在运行时动态融合智能体信息以降低不确定性。实验表明，WinkTPG可在1秒内为最多1,000个智能体生成速度轨迹，相较现有方法方案质量最高提升51.7%。我们在高保真物理仿真及真实机器人上验证了其有效性。
原文摘要 · Abstract (English)
Planning collision-free paths for a large group of agents is a challenging problem in many real-world applications. While recent advances in Multi-Agent Path Finding (MAPF) have shown promising progress, standard MAPF planners continue to rely on simplified kinodynamic models, preventing agents from directly following the generated MAPF plan. To bridge this gap, we propose kinodynamic Temporal Plan Graph planning (kTPG), a multi-agent speed optimization algorithm that efficiently refines a MAPF plan into a set of kinodynamically feasible speed profiles. We further incorporate execution timing uncertainty models and provide deterministic guarantees under bounded uncertainty models and probabilistic guarantees under stochastic models. Building on kTPG, we propose Windowed kTPG (WinkTPG), a MAPF execution framework that incrementally refines MAPF plans using a window-based mechanism, dynamically incorporating agent information during execution to reduce uncertainty. Experiments show that WinkTPG can generate speed profiles for up to 1,000 agents within 1 second and improves solution quality by up to 51.7% over existing MAPF execution methods. We further validate WinkTPG in high-fidelity physics-based simulation and on real-world robots.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。