EUVIMEDEUVIMED entdecken
Crossref

Precomputing Multi-Agent Path Replanning Using Temporal Flexibility

Issa Hanou, Eric Kemmeren, Devin Wild Thomas, Mathijs de Weerdt

Proceedings of the International Symposium on Combinatorial Search · 14.08.2026 · 19 (1) · 47-55

DOI: 10.1609/socs.v19i1.43072 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the International Symposium on Combinatorial Search, online erschienen am 14.08.2026. Verfasst von Issa Hanou und 3 weiteren Autor:innen.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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.

Zitieren

APA

Hanou, I., Kemmeren, E., Thomas, D. W., & Weerdt, M. D. (2026). Precomputing Multi-Agent Path Replanning Using Temporal Flexibility. Proceedings of the International Symposium on Combinatorial Search, 19(1), 47-55. https://doi.org/10.1609/socs.v19i1.43072

Vancouver

Hanou I, Kemmeren E, Thomas DW, Weerdt MD. Precomputing Multi-Agent Path Replanning Using Temporal Flexibility. Proceedings of the International Symposium on Combinatorial Search. 2026;19(1):47-55. doi:10.1609/socs.v19i1.43072

BibTeX
@article{Hanou2026,
  author = {Hanou, Issa and Kemmeren, Eric and Thomas, Devin Wild and Weerdt, Mathijs de},
  title = {Precomputing Multi-Agent Path Replanning Using Temporal Flexibility},
  journal = {Proceedings of the International Symposium on Combinatorial Search},
  year = {2026},
  volume = {19},
  number = {1},
  pages = {47--55},
  doi = {10.1609/socs.v19i1.43072}
}
Kostenlos starten →