Decentralized Unlabeled Multi-Agent Pathfinding Via Target And Priority Swapping

Авторы

Яковлев К. С. Дергачёв С. А.

Аннотация

In this paper we study a challenging variant of the multi-agent pathfinding problem (MAPF), when a set of agents must reach a set of goal locations, but it does not matter which agent reaches a specific goal – Anonymous MAPF (AMAPF). Current optimal and suboptimal AMAPF solvers rely on the existence of a centralized controller which is in charge of both target assignment and pathfinding. We extend the state of the art and present the first AMAPF solver capable of solving the problem at hand in a fully decentralized fashion, when each agent makes decisions individually and relies only on the local communication with the others. The core of our method is a priority and target swapping procedure tailored to produce consistent goal assignments (i.e. making sure that no two agents are heading towards the same goal). Coupled with an established rule-based path planning, we end up with a TP-SWAP, an efficient and flexible approach to solve decentralized AMAPF. On the theoretical side, we prove that TP-SWAP is complete (i.e. TP-SWAP guarantees that each target will be reached by some agent). Empirically, we evaluate TP-SWAP across a wide range of setups and compare it to both centralized and decentralized baselines. Indeed, TP-SWAP outperforms the fully-decentralized competitor and can even outperform the semi-decentralized one (i.e. the one relying on the initial consistent goal assignment) in terms of flowtime (a widespread cost objective in MAPF).

Внешние ссылки

DOI: 10.3233/FAIA240545

Скачать статью (PDF) на сайте издателя IOS Press (англ.): https://ebooks.iospress.nl/volumearticle/70105

Скачать сборник трудов конференции (PDF) на сайте издателя IOS Press (англ.): https://ebooks.iospress.nl/doi/10.3233/FAIA392

Скачать PDF на arXiv.org (англ.): https://arxiv.org/html/2408.14948v1

ResearchGate: https://www.researchgate.net/publication/385023731_Decentralized_Unlabeled_Multi-Agent_Pathfinding_Via_Target_And_Priority_Swapping

Ссылка при цитировании

Stepan Dergachev, Konstantin Yakovlev. Decentralized Unlabeled Multi-Agent Pathfinding Via Target And Priority Swapping // Proceedings of ECAI-2024, the 27th European Conference on Artificial Intelligence, 19–24 October 2024, Santiago de Compostela, Spain — Including 13th Conference on Prestigious Applications of Intelligent Systems (PAIS 2024). Volume 392. IOS Press, 2024. Pp. 4344–4351.