Adaptive Lifelong Multi-Agent Path Finding With Multiple Priorities

Abstract

In this study, 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 <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\gamma$</tex-math></inline-formula> -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.