Adaptive Lifelong Multi-Agent Path Finding With Multiple Priorities

In this letter, we introduce the Lifelong Evaluation-Based Large Neighborhood Search (LEB-LNS) algorithm designed to address the Lifelong Adaptive Multiple Priorities Multi-Agent Path Finding (LAMP-MAPF) challenge. This challenge involves agents that must navigate from one location to another across varying priority levels, constrained by limited calculation time for each interval. Initially, a
$\gamma$
-based evaluation function is utilized to determine the significance of different priority levels. Following this, the evaluation led to the development of the Evaluation-Based LNS (EB-LNS) Algorithm, tailored for the Adaptive Multiple Priorities MAPF (AMP-MAPF) issue. By integrating task assignment, we further extend LEB-LNS algorithm for the LAMP-MAPF problem. The efficacy of LEB-LNS algorithm is verified through simulations conducted on fulfillment and sorting center maps, supplemented by real-world experiments. Results demonstrate that the LEB-LNS algorithm effectively resolves LAMP-MAPF problem, significantly enhancing agent throughput and reducing delays for high-priority agents.