Multi-agent Pathfinding on Large Maps Using Graph Pruning: This Way or That Way? (Extended Abstract)

This paper extends a study on improving the performance of reduction-based solvers for the problem of multi-agent pathfinding. The task is to navigate a set of agents in a graph without collisions. Solvers that reduce this problem to other formalisms often have issues scaling to larger instances in terms of the graph size. A previous study suggests that pruning the graph of most vertices based on a randomly chosen shortest path for each agent. In this paper, we study the effect of different choices of these paths.

Authors

• Jirí Svancara
• Philipp Obermeier
• Matej Husár
• Roman Barták
• Torsten Schaub

Keywords

• Problem Compilation
• Bounding And Pruning Techniques
• Combinatorial Optimization