Path Passing Sequence Search for Lifelong Multi-Agent Pathfinding With Uncertain Delays

Abstract

The Lifelong Multi-Agent Path Finding (LMAPF) problem in practice faces significant challenges due to uncertain delays and the interleaving of planning and execution. Traditional solvers often rely on precise time-step reservations, which are prone to failure when agents deviate from their schedules, leading to inaccurate collision predictions between planning and executing agents. To address this limitation, this letter proposes a Path-Passing-Sequence Search (PPSS) framework that constructs robust passing sequences directly during the planning phase without strict reliance on time steps. PPSS extends the A* algorithm by expanding the search state space to determine spatial routes and valid insertion positions within existing passing orders simultaneously. Furthermore, a novel collision prediction strategy is introduced to evaluate potential conflicts and deadlock cycles by analyzing the relative passing ranks of Anchor-Anchor Movement Units (AAMUs). Extensive experiments in discrete-time settings and a preliminary real-world deployment in a continuous-time setting demonstrate that PPSS effectively generates collision-free paths and maintains safe passing orders even under practical uncertain delays.