Lifelong Multi-Agent Collaborative Path Finding: A Unified Framework for Task Assignment and Path Planning

Coordinating lifelong collaboration among multiple agents poses significant challenges, particularly when agents must work together to complete tasks in dynamic environments. Existing methods typically separate task allocation from path planning, resulting in inefficient coordination, idle agents, and frequent deadlocks when collaboration is required. These issues are particularly critical in real-world domains, such as warehouse logistics, where multi-agent cooperation is crucial for handling large or complex tasks. To overcome these limitations, we propose the Lifelong Multi-Agent Collaborative Path Finding (LMACPF) as a unified framework, which tightly integrates task assignment and path planning for lifelong, collaboration-intensive scenarios. LMACPF combines Multi-Level Task Assignment (MLTA) with Collaborative Agent Search (CAS) and Collaborative Revised Prioritized Planning (CRPP) to optimize task allocation and path planning, particularly for cooperative agent behaviors. MLTA hierarchically assigns tasks based on collaboration requirements to ensure that multi-agent tasks are prioritized. CAS and CRPP enable synchronized planning and formation maintenance among agents. In addition, the Evaluation-Based Collaborative Large Neighborhood Search (EBC-LNS) is presented for a task-level evaluation that prioritizes collaborative agent groups and balances the path quality with real-time responsiveness. Experiments show MLTA increases task-ready agents by 45.8% over MAPD. LMACPF improves throughput and task success over state-of-the-art methods, demonstrating its effectiveness in scalable, lifelong multi-agent collaboration.