arXiv：cs.AI· Issa Hanou, Eric Kemmeren, Devin Wild Thomas, Mathijs de Weerdt·· 7 小时前AI 评分26
FlexSIPP：利用时间灵活性预计算多智能体路径重规划
Precomputing Multi-Agent Path Replanning Using Temporal Flexibility
AI 导读
FlexSIPP 通过追踪其他智能体的时间灵活性——即在不改变与其他智能体顺序的前提下所能容忍的最大延迟——来高效重规划单个延迟智能体，避免级联延迟。该算法预计算延迟智能体的所有可能路径，并在荷兰铁路网络案例和 MovingAI MAPF 基准测试中验证，能在合理时间内给出有效方案。代码修复后 MAPF 与铁路结果有调整，但结论不变。
正文
Abstract: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.
| Comments: | Revision after a bug was found in the code. The fixes do not alter the conclusions; the MAPF results are slightly different from those published at SoCS26. The railway results changed as the code was rearranged, now returning proper valid paths, with a new data representation to show the actual differences between FlexSIPP and MAEDeR. In the Fig1 example a3s route changed to show a1s rerouting |
| Subjects: | Artificial Intelligence (cs.AI) |
| Cite as: | arXiv:2601.04884 [cs.AI] |
| (or arXiv:2601.04884v4 [cs.AI] for this version) | |
| https://doi.org/10.48550/arXiv.2601.04884 arXiv-issued DOI via DataCite |
|
| Related DOI: | https://doi.org/10.1609/socs.v19i1.43072
DOI(s) linking to related resources |
Submission history
From: Issa Hanou [view email]
[v1]
Thu, 8 Jan 2026 12:30:36 UTC (464 KB)
[v2]
Fri, 10 Apr 2026 11:54:48 UTC (527 KB)
[v3]
Wed, 10 Jun 2026 08:21:24 UTC (835 KB)
[v4]
Tue, 6 Oct 2026 12:48:01 UTC (822 KB)
来源：arXiv：cs.AI · arxiv.org