A Scalable Framework for Lifelong Multiagent Path Finding With Asynchronous Actions

초록

Lifelong multiagent path finding (LMAPF) requires continuous task assignment and collision-free path planning for large robot fleets. However, existing LMAPF methods assume synchronous unit-time actions, whereas real robots execute movements asynchronously with nonuniform durations. This mismatch can lead to execution-time collisions and makes frequent replanning challenging in large-scale systems. We study LMAPF with asynchronous actions and present a framework that ensures safety under asynchronous execution and real-time scalability through coordinated path planning and action scheduling, complemented by a simple greedy task allocation. To ensure safety, the path planner eliminates cycle conflicts to prevent structural deadlocks, while a lightweight action scheduler enforces vertex precedence during execution, resolving following conflicts without explicit temporal modeling. To achieve real-time performance, the planner performs partial replanning by reusing the residual paths of nonidle agents, which are converted into a synchronous form through the scheduler's path resynchronization, enabling consistent and efficient replanning. Experiments in warehouse environments with up to 1000 robots demonstrate that our framework more than doubles throughput compared with state-of-the-art LMAPF methods, while maintaining safe operations under asynchronous actions.

키워드