Multi-Agent Path Finding For Large Agents Is Intractable

Artem Agafonov, Konstantin Yakovlev

The multi-agent path finding (MAPF) problem asks to find a set of paths on a graph such that when synchronously following these paths the agents never encounter a conflict. In the…