Publication

J. Svancara, P. Obermeier, M. Husar, R. Bartak and T. Schaub. Multi-Agent Pathfinding on Large Maps Using Graph Pruning: This Way or That Way?. In International Conference on Agents and Artificial Intelligence (ICAART), pages 199-206, 2023.

Abstract: Multi-agent pathfinding is the task of navigating a set of agents in a shared environment from their start locations to their desired goal locations without collisions. Solving this problem optimally is a hard task and various algorithms have been devised. The algorithms can generally be split into two categories, search- and reduction-based ones. It is known that reduction-based algorithms struggle with large instances in terms of the size of the environment. A recent study tried to mitigate this drawback by pruning some vertices of the environment map. The pruning is done based on the vicinity to a shortest path of an agent. In this paper, we study the effect of choosing such shortest paths. We provide several approaches to choosing the paths and we perform an experimental study to see the effect on the runtime.

Download the paper in pdf.