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

Authors

  • Jiří Švancara Charles University, Prague, Czech Republic
  • Philipp Obermeier University of Potsdam, Potsdam, Germany Potassco Solutions, Potsdam, Germany
  • Matej Husár Charles University, Prague, Czech Republic
  • Roman Barták Charles University, Prague, Czech Republic
  • Torsten Schaub University of Potsdam, Potsdam, Germany Potassco Solutions, Potsdam, Germany

Keywords:

Problem Compilation, Bounding And Pruning Techniques, Combinatorial Optimization

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.

Downloads

Published

2022-07-17