Decentralized Unlabeled Multi-Agent Pathfinding Via Target And Priority Swapping

Authors

Yakovlev K. Dergachyov S.

Annotation

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).

External links

DOI: 10.3233/FAIA240545

Download the article (PDF) from the IOS Press publisher: https://ebooks.iospress.nl/volumearticle/70105

Download the conference proceedings (PDF) from the IOS Press publisher: https://ebooks.iospress.nl/doi/10.3233/FAIA392

Download PDF from 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

Reference link

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.