Publication

M. Ivanova and P. Surynek. Adversarial Multi-Agent Path Finding is Intractable. In Proceedings of the International Conference on Tools with Artificial Intelligence (ICTAI), pages 481-486, 2021.

Abstract: Adversarial Multi-Agent Path Finding (AMAPF) extends the standard discrete Multi-Agent Path Finding with an adversarial element. Agents of two competing teams are deployed in a shared environment represented by an undirected graph. The first team aims to navigate all its agents from their initial locations to given goal locations, while the second team aims to prevent agents of the first team from fulfilling their goal. We prove that the problem of finding a winning strategy is EXPTIME-complete.

Download the paper in pdf.