Divide and Conquer: Advancing Large-Scale Multi-Agent Pathfinding With Hierarchical Reinforcement Learning

Abstract

Dynamic multi-robot systems face the intricate multi-agent pathfinding (MAPF) challenge as a pivotal hurdle. It has been uncovered through recent research that tackling MAPF issues can be effectively approached through reinforcement learning, offering a fully decentralized solution. Nonetheless, the escalation in the scale of the multi-robot system introduces sample inefficiency, posing a significant barrier for learning-based methods. We introduce a novel hierarchical reinforcement learning architecture aimed at addressing large-scale MAPF by leveraging spatial and temporal abstraction. This approach enhances exploration efficiency by recognizing intermediate rewards. The framework employs an upper-tier controller that segments the map into linked regions, thereby streamlining the optimization of agents' paths on a regional basis to foster improved global outcomes. To tackle each segmented problem, a subordinate-level controller is designed, which integrates heuristic directions and an inter-agent communication strategy. The merit of our methodology is confirmed by empirical experiments, showcasing advancements over prevailing methods in success rates and reduction in completion time across test scenarios of various magnitudes.