A Robust Lifelong Multi-Agent Path Finding With Active Conflict Resolution and Decentralized Execution

Abstract

Multi-Agent Path Finding (MAPF) focuses on navigating agents along cost-efficient and conflict-free paths. This letter investigates a challenging and practical MAPF variant, namely Robust Lifelong MAPF (RLMAPF), where agents sequentially receive tasks and effectively deal with uncertainties. In this letter, we first establish a comprehensive RLMAPF problem model with a novel conflict category methodology: active and passive conflicts. Based on this model, we introduce a decentralized robust path finding algorithm that comprises two fundamental components: the robust path finding and decentralized path execution. The first component focuses on robust MAPF by integrating a conflict prediction oracle, a rolling window for conflict detection, and active conflict resolution. Based on the robust path without active conflicts provided by the planning phase, the path executor aims at passive conflict avoidance in a decentralized method. The empirical evaluation of the proposed algorithm against the state-of-the-art MAPF methods reveals its superiority. Through extensive simulations, we demonstrate that the proposed algorithm has a low replanning frequency and high robustness, maintaining a robustness index of 0.95 in most uncertain environments—at least 20% higher than the state-of-the-art comparison MAPF algorithms.