提升多智能体路径规划中双向依赖关系，增强对延迟的鲁棒性。
BTPG-max: Achieving Local Maximal Bidirectional Pairs for Bidirectional Temporal Plan Graphs
- 提出BTPG-max算法，局部最优地生成更多双向路径对
- 实验显示双向边数量显著增加，且在延迟下表现更稳定
- 适合需要高鲁棒性的实际多智能体系统部署
多智能体路径规划（MAPF）需为多个智能体在共享环境中计算无碰撞路径。传统方法假设每个智能体在特定时间到达指定位置，但在实际系统中常因延迟而无法实现。为应对延迟导致的冲突，引入了时序计划图（TPG），将时变的MAPF解转化为时不变的智能体间依赖关系。近期提出的双向TPG（BTPG）将部分依赖关系松弛为“双向对”，提升了执行效率。本文提出BTPG-max算法，可构造出局部最优的BTPG，即无法再添加额外双向对。理论证明该算法具有局部最优性，实践中显著增加了双向边数量，表现出更优的任意时间行为，并增强了对延迟的鲁棒性。
原文摘要 · Abstract (English)
Multi-Agent Path Finding (MAPF) requires computing collision-free paths for multiple agents in shared environment. Most MAPF planners assume that each agent reaches a specific location at a specific timestep, but this is infeasible to directly follow on real systems where delays often occur. To address collisions caused by agents deviating due to delays, the Temporal Plan Graph (TPG) was proposed, which converts a MAPF time dependent solution into a time independent set of inter-agent dependencies. Recently, a Bidirectional TPG (BTPG) was proposed which relaxed some dependencies into ``bidirectional pairs" and improved efficiency of agents executing their MAPF solution with delays. Our work improves upon this prior work by designing an algorithm, BPTG-max, that finds more bidirectional pairs. Our main theoretical contribution is in designing the BTPG-max algorithm is locally optimal, i.e. which constructs a BTPG where no additional bidirectional pairs can be added. We also show how in practice BTPG-max leads to BTPGs with significantly more bidirectional edges, superior anytime behavior, and improves robustness to delays.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。