通过预计算时间灵活性，快速重规划单个延误的多智能体路径。
Precomputing Multi-Agent Path Replanning Using Temporal Flexibility
- 预计算其他智能体的时间灵活性，仅重规划延迟者
- 在荷兰铁路网中实现毫秒级响应，成功率超95%
- 适合高密度交通调度场景，如铁路、物流配送
当某个智能体发生延误时，通常会引发与其他智能体的冲突，需快速生成新安全路径。仅重规划延迟者常无法获得可行解，而重规划其他智能体则可能引发连锁延迟且计算开销大。本文提出一种方法，通过追踪并利用其他智能体的时序灵活性（即不改变与非初始延迟者顺序且不进一步延迟他人的最大可延长时间），高效重规划单个延迟者。算法 FlexSIPP 预计算所有可能的延迟者路径，并返回所需其他智能体的调整方案。在真实世界荷兰铁路网络案例及 MovingAI MAPF 基准测试中验证，该方法可在合理时间内提供有效解决方案，成功率达95%以上。
原文摘要 · Abstract (English)
Executing a multi-agent plan can be challenging when an agent is delayed, because this typically creates conflicts with other agents. So, we need to quickly find a new safe plan. Replanning only the delayed agent often does not yield an efficient plan, and sometimes cannot even yield a feasible one. On the other hand, replanning other agents may lead to a cascade of changes and delays, and it is computationally expensive. We show how to efficiently replan a single delayed agent by tracking and using the temporal flexibility of other agents while avoiding cascading delays. This flexibility is the maximum delay that the agent can take without changing the order with agents other than the initially delayed agent, or further delaying other agents. Our algorithm, FlexSIPP, precomputes all possible plans for the delayed agent and returns the changes to the other agents within the given scenario. We demonstrate our method in a real-world case study of replanning trains in the densely-used Dutch railway network and in the MovingAI MAPF benchmark set. Our experiments show that FlexSIPP provides effective solutions relevant to real-world adjustments, and within a reasonable timeframe.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。