A Review of Multi-Agent Path Finding Algorithms
Mengdie Wu, Wenyao Yan, Haslin Hasan, Robiatul A’dawiah Jamaluddin · 2023
In the context of Industry 4.0, Autonomous Guided Vehicles (AGVs) and other types of Multi-Agent System (MAS) have been widely used in large-scale warehouses and unmanned factories. Coordination of AGVs in shared space is drawing increasing attention of researchers, especially in the field of Multi-Agent Path Finding (MAPF). The MAPF problem has been studied a lot, and there are many kinds of solutions. Not all kinds of MAPF solvers can be applied in the field of AGV. Few literature focused on which MAPF solutions are suitable for AGV navigation. This review categorized existing MAPF algorithms into five branches, Conflict-Based Search (CBS) algorithms, Rule-Based algorithms, Priority-Based algorithms, Numerical Optimization-based algorithms and Learning-based algorithms. Furthermore, we evaluate these algorithms in terms of their optimality, lifelong property, scalability and computational cost. Finally, we analyzed which MAPF solvers are suitable for AGV navigation.