Adversarial Multi-Agent Path Finding is Intractable

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.

Keywords

• Adversarial
• Multi-Agent
• Path
• Finding
• Intractable