Multi-agent Pathfinding on Large Maps Using Graph Pruning: This Way or That Way? (Extended Abstract)
DOI:
https://doi.org/10.1609/socs.v15i1.21799Keywords:
Problem Compilation, Bounding And Pruning Techniques, Combinatorial OptimizationAbstract
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.Downloads
Published
2022-07-17
Issue
Section
Extended Abstracts