Reduction-based Solving of Multi-agent Pathfinding on Large Maps Using Graph Pruning

Multi-agent pathfinding is the problem of finding collision-free paths for a set of agents. Solving this problem optimally is computationally hard, therefore many techniques based on reductions to other formalisms were developed. In comparison to search-based techniques, the reduction-based techniques fall behind on large maps even for a small number of agents. To combat this phenomenon, we propose several strategies for pruning vertices off large instances that will most likely not be used by agents. First, we introduce these strategies conceptually and prove which of them maintain completeness and optimality. Eventually, we conduct an exhaustive evaluation and show that graph pruning strategies make reduction-based solvers comparable to search-based techniques on large maps while maintaining their advantage on small dense maps.

Authors

• Matej Husár Charles University
• Jiří Švancara
• Philipp Obermeier
• Roman Barták Charles University
• Torsten Schaub

Keywords

• Multi-agent pathfinding
• Scalability
• Answer set programming
• Satisfiability
• Subgraph
• Graph pruning
• Logic programming