Publication

Y. Yang, M. Fan, C. He, J. Wang, H. Huang and G. Sartoretti. Attention-Based Priority Learning for Limited Time Multi-Agent Path Finding. 2024.

Abstract: Solving large-scale Multi-Agent Path Finding (MAPF) within a limited time remains an open challenge, despite its importance for many robotic applications. Recent learning-based methods scale better than conventional ones, but remain suboptimal and often exhibit low success rates within a limited time on large-scale instances. These limitations often stem from their black-box nature. In this study, we propose a hybrid approach that incorporates prioritized planning with learning-based methods to explicitly address these challenges. We formulate prioritized planning as a Markov Decision Process and introduce a reinforcement learningbased prioritized planning paradigm. In doing so, we develop a novel Synthetic Score-based Attention Network (S2AN) to learn conflict/blocking relationships among agents, and deliver blocking-free priorities. By integrating priority mechanisms and leveraging a new attention-based neural network for enhanced multi-agent cooperative strategies, our method enhances solution completeness while trading off scalability and maintains linear time complexity, thus offering a robust avenue for large-scale MAPF tasks. Comparisons demonstrate its superiority over current learning-based methods in terms of solution quality, completeness, and reachability within limited time constraints, especially in largescale scenarios. Moreover, an extensive set of numerical results reveals superior completeness compared to restricted-time PriorityBased Search (PBS) and Priority Inheritance with Backtracking (PIBT) in medium to large-scale obstacle-dense scenarios.

Download the paper in pdf.