Robust Multiagent Combinatorial Path Finding
Proceedings of the AAAI Conference on Artificial Intelligence · 14.03.2026 · 40 (35) · 29513-29520
DOI: 10.1609/aaai.v40i35.40193 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the AAAI Conference on Artificial Intelligence, online erschienen am 14.03.2026. Verfasst von Yehonatan Kidushim und 3 weiteren Autor:innen.
Abstract (Originalsprache)
Consider a system of multiple physical agents tasked with collaboratively collecting a set of spatially distributed goals as quickly as possible while avoiding collisions with the environment and with each other. This type of problem, which involves Multi-Agent Path Finding (MAPF) and task allocation, is called Multi-Agent Combinatorial Path Finding (MCPF). Prior work on MCPF assumed each agent has a final goal it must reach, there are no orientation constraints on the agents' movements, and the agents will follow their planned actions as intended. These assumptions rarely hold in real physical robots, which limits the applicability of existing MCPF algorithms in practical applications. We propose the Robust CBSS framework, a robust planning approach that solves MCPF without the aforementioned simplifying assumptions, and provide two implementations: a baseline version (RCbssBase) and an efficient version (RCbssEff). RCbssEff generalizes the Conflict-Based Steiner Search (CBSS) algorithm, building on ideas from the p-Robust CBS algorithm and algorithms for solving the Equality Generalized Traveling Salesman Problem. We prove that RCbssEff is complete and can be configured to return optimal solutions. Experimental results on benchmark MCPF problems show that RCbssEff balances planning time, solution cost, and collision reduction compared to baselines.
Zitieren
APA
Kidushim, Y., Natan, A., Stern, R., & Kalech, M. (2026). Robust Multiagent Combinatorial Path Finding. Proceedings of the AAAI Conference on Artificial Intelligence, 40(35), 29513-29520. https://doi.org/10.1609/aaai.v40i35.40193
Vancouver
Kidushim Y, Natan A, Stern R, Kalech M. Robust Multiagent Combinatorial Path Finding. Proceedings of the AAAI Conference on Artificial Intelligence. 2026;40(35):29513-29520. doi:10.1609/aaai.v40i35.40193
BibTeX
@article{Kidushim2026,
author = {Kidushim, Yehonatan and Natan, Avraham and Stern, Roni and Kalech, Meir},
title = {Robust Multiagent Combinatorial Path Finding},
journal = {Proceedings of the AAAI Conference on Artificial Intelligence},
year = {2026},
volume = {40},
number = {35},
pages = {29513--29520},
doi = {10.1609/aaai.v40i35.40193}
}
EUVIMED