Abstract
In multi-agent path finding (MAPF), it is usually assumed that planning is performed centrally and that the destinations of the agents are common knowledge. We will drop both assumptions and analyze under which conditions it can be guaranteed that the agents reach their respective destinations using implicitly coordinated plans without communication. Furthermore, we will analyze what the computational costs associated with such a coordination regime are. As it turns out, guarantees can be given assuming that the agents are of a certain type. However, the implied computational costs are quite severe. In the distributed setting, we either have to solve a sequence of NP-complete problems or have to tolerate exponentially longer executions. In the setting with destination uncertainty, bounded plan existence becomes PSPACE-complete. This clearly demonstrates the value of communicating about plans before execution starts.
Original language | English |
---|---|
Journal | Journal of Artificial Intelligence Research |
Volume | 64 |
Pages (from-to) | 497-527 |
ISSN | 1076-9757 |
DOIs | |
Publication status | Published - 2019 |
Keywords
- Computer Theory (Includes Formal Logic, Automata Theory, Switching Theory and Programming Theory)
- Computational complexity
- Common knowledge
- Computational costs
- Multi agent
- Path finding
- PSPACE-complete
- Multi agent systems