Comparison of Classic and Recent Multi-Agent Path Finding Methods via MAPFame
Jiaqi Huang, Yangming Zhou, MengChu Zhou, Wei Liu · 2023
A Multi-Agent Path Finding (MAPF) problem aims to plan paths for multiple agents given a prescribed map and ensure they do not conflict with each other and travel the shortest distance or lowest cost in the minimal time. MAPF is useful in many practical applications, e.g., automated warehouses and intelligent factories. It has been widely-studied in the past decade. Existing MAPF algorithms have evolved from those solving single-agent path finding problems. When realized in different programming languages, they tend to deliver varying results regarding execution time and solution quality. Many kinds of simulated maps are used but some of them are not directly related to actual application environment. In this paper, we experimentally compare existing MAPF algorithms based on an open-source simulation platform called Multi-Agent Path Finding based on Advanced Methods and Evaluation (MAPFame). We analyze and test the effects of obstacle density, different maps, and agents counts on their performance indices. Hence, our research outcomes can be used by practitioners to select a right method for their particular applications.