Adversarial Multi-Agent Path Finding is Intractable
Marika Ivanová, Pavel Surynek · 2021 IEEE 33rd International Conference on Tools with Artificial Intelligence (ICTAI) · 2021
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.