Abstract
The Multi-Agent Pathfinding (MAPF) problem is the funda- mental problem of planning paths for multiple agents, where the key constraint is that the agents will be able to follow these paths concurrently without colliding with each other. Applications of MAPF include automated warehouses and autonomous vehicles.
Research on MAPF has been flourish- ing in the past couple of years. Different MAPF research pa- pers make different assumptions, e.g., whether agents can tra- verse the same road at the same time, and have different ob- jective functions, e.g., minimize makespan or sum of agents' actions costs.
These assumptions and objectives are some- times implicitly assumed or described informally. This makes it difficult to establish appropriate baselines for comparison in research papers, as well as making it difficult for practitioners to find the papers relevant to their concrete application.
This paper aims to fill this gap and support researchers and prac- titioners by providing a unifying terminology for describing common MAPF assumptions and objectives. In addition, we also provide pointers to two MAPF benchmarks.
In partic- ular, we introduce a new grid-based benchmark for MAPF, and demonstrate experimentally that it poses a challenge to contemporary MAPF algorithms.