webmaster: Sven Koenig

Learn all about Multi-Agent Path Finding (MAPF)


J. Svancara and R. Bartak. Combining Strengths of Optimal Multi-Agent Path Finding Algorithms. In Proceedings of the International Conference on Agents and Artificial Intelligence (ICAART), pages 226-231, 2019.

Abstract: The problem of multi-agent path finding (MAPF) is studied in this paper. Solving MAPF optimally is a computationally hard problem and many different optimal algorithms have been designed over the years. These algorithms have good runtimes for some problem instances, while performing badly for other instances. Interestingly, these hard instances are often different across the algorithms. This leads to an idea of combining the strengths of different algorithms in such a way that an input problem instance is split into disjoint subproblems and each subproblem is solved by appropriate algorithm resulting in faster computation than using either of the algorithms for the whole instance. By manual problem decomposition we will empirically show that the above idea is viable. We will also sketch a possible future work on automated problem decomposition.

Download the paper in pdf.

(last updated in 2022)