Technical Report No. 287 - Abstract

Bernhard Nebel, Thomas Bolander, Thorsten Engesser, and Robert Mattmüller
Implicitly Coordinated Multi-Agent Path Finding under Destination Uncertainty

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 NP-complete problems or have to tolerate exponentially longer executions. In the setting with destination uncertainty, plan existence becomes PSPACE-complete. This clearly demonstrates the value of communicating about plans before execution starts.