Abstract:

The Multi-agent Path Finding (MAPF) problem is a core fundamental issue in multi-agent systems and has been widely applied in practical scenarios such as automated intelligent warehousing, autonomous driving, and swarm robotics. From the perspective of problem attributes, the key difficulty lies in enabling multiple intelligent agents to travel along paths simultaneously while ensuring no collisions occur, making it an NP-hard combinatorial optimization problem. However, the aforementioned realworld applications require algorithms to find high-quality, collision-free paths for a large number of intelligent agents within a short computation time. Shorter paths lead to higher system throughput and lower operating costs, presenting significant challenges for classical MAPF optimization algorithms. As a result, in recent years, numerous studies have begun focusing on using machine learning methods to empower MAPF research, aiming to accelerate solution speed and improve solution quality. This paper presents a comprehensive review in three parts, including the core concepts, optimization objectives, and benchmark tasks of the MAPF problem. It also covers the problem modeling, core ideas, and strengths and weaknesses of traditional MAPF algorithms. Additionally and most importantly, this paper introduces a series of machine learning-empowered MAPF algorithms with varying degrees of machine learning involvement, providing corresponding schematic diagrams and pseudocode. This paper further summarizes the major challenges currently faced by machine learning-driven MAPF algorithms and proposes potential future research directions. This is intended to assist researchers in the field and promote the development of machine learning methods in the classical MAPF domain.

Key words: machine learning, multi-agent pathfinding, multi-agent reinforcement learning