42+ Flavors of Multi-Agent Path Finding

Abstract

Multi-Agent Path Finding (MAPF) is a well-studied problem. In recent years, many derivations of MAPF – MAPF flavors – have been formulated and solved. Although some flavors only lift some assumptions present in MAPF, others result from combining two or more flavors. So far, no published work has focused specifically on these newly derived problems, which resulted in incomplete coverage of this area of MAPF, even if it enjoys significant research focus. We present a survey on MAPF flavors, in which we collected 48 existing MAPF-derived problems, categorized them, identified their key defining features, and mapped the relationships between them. The survey is designed to serve as a crossroads for both new and experienced researchers looking to obtain or update their knowledge about MAPF-adjacent problems and readers with such a problem looking for a solution or a reference method. The collected problems are therefore presented in a way that allows an interested reader to find and identify both new and related problems, learn about the state-of-the-art solution methods, and find literature that explains them in greater detail.