webmaster: Sven Koenig

Learn all about Multi-Agent Path Finding (MAPF)


D. Atzmon, Y. Zax, E. Kivity, L. Avitan, J. Morag and A. Felner. Generalizing Multi-Agent Path Finding for Heterogeneous Agents. In Proceedings of the International Symposium on Combinatorial Search (SoCS), pages 101-105, 2020.

Abstract: Multi-Agent Path Finding (MAPF) is the problem of finding non-colliding paths for multiple agents. The classical problem assumes that all agents are homogeneous, with a fixed size and behavior. However, in reality agents are heterogeneous, with different sizes and behaviors. In this paper, we generalize MAPF to G-MAPF for the case of heterogeneous agents. We then show how two previous settings of large agents and k-robust agents are special cases of G-MAPF. Finally, we introduce G-CBS, a variant of the Conflict-Based Search (CBS) algorithm for G-MAPF, which does not cause significant extra overhead.

Download the paper in pdf.

(last updated in 2020)