Charles Explorer logo
🇬🇧

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

Publication at Faculty of Mathematics and Physics |
2022

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.