H₂L: High-Performance Multi-agent Path Finding in High-Obstacle-Density and Large-Size Maps

Multi-Agent Path Finding (MAPF) is vital for large-scale Multi-Agent Systems (MAS), where agents must plan collision-free paths to reach their goals. While Reinforcement Learning (RL) methods aim to enhance real-time performance and scalability over search-based approaches, their success on complex maps is limited. This is due to the use of independent RL algorithms, which fail to address the non-stationarity of the environment, and inappropriate reward functions that cause the agent’s policy to worsen with greater distance to the goal. To tackle these issues, we propose a MAPF algorithm based on a new variant of the Value Decomposition Network (VDN), a multi-agent RL algorithm, and introduce a novel reward function. This VDN variant trains the network using agents within a specific agent’s field of view, addressing non-stationarity and training challenges in large-scale MAS, unlike naive VDN, which considers all agents. We introduce a novel reward function using potential-based reward shaping, rendering the agent’s policy independent of the map size. Additionally, we enhance the reward to alleviate congestion by preventing agents from stopping next to each other and by penalizing the following conflicts. Experiments show our planner has a notably higher success rate than other RL-based planners and slightly lower than the latest state-of-the-art search-based planner, LaCAM*, on complex maps. For instance, on a 160 × 160 map with 30% obstacle density and 1024 agents, our planner achieves an 88% success rate, while other RL-based planners achieve virtually 0%.