Scaling Lifelong Multi-Agent Path Finding to More Realistic Settings: Research Challenges and Opportunities
This work addresses scalability and realism issues in LMAPF for robotics and logistics applications, but it is incremental as it builds on existing competition results and outlines challenges rather than presenting new solutions.
The paper identifies key research challenges in scaling Lifelong Multi-Agent Path Finding (LMAPF) to handle large numbers of agents (e.g., 10,000) or high densities (e.g., 97.7%) within limited planning times, such as 1 second per step, and proposes future directions like developing competitive algorithms and addressing real-world gaps.
Multi-Agent Path Finding (MAPF) is the problem of moving multiple agents from starts to goals without collisions. Lifelong MAPF (LMAPF) extends MAPF by continuously assigning new goals to agents. We present our winning approach to the 2023 League of Robot Runners LMAPF competition, which leads us to several interesting research challenges and future directions. In this paper, we outline three main research challenges. The first challenge is to search for high-quality LMAPF solutions within a limited planning time (e.g., 1s per step) for a large number of agents (e.g., 10,000) or extremely high agent density (e.g., 97.7%). We present future directions such as developing more competitive rule-based and anytime MAPF algorithms and parallelizing state-of-the-art MAPF algorithms. The second challenge is to alleviate congestion and the effect of myopic behaviors in LMAPF algorithms. We present future directions, such as developing moving guidance and traffic rules to reduce congestion, incorporating future prediction and real-time search, and determining the optimal agent number. The third challenge is to bridge the gaps between the LMAPF models used in the literature and real-world applications. We present future directions, such as dealing with more realistic kinodynamic models, execution uncertainty, and evolving systems.