Dual-Layer PIBT for Lifelong Multi-Agent Pathfinding with Narrow Passages

Abstract

Lifelong Multi-Agent Pathfinding (Lifelong MAPF) is an extension of the Multi-Agent Pathfinding (MAPF) problem. It has significant applications in scenarios such as warehouse logistics and delivery services. Narrow passages that restrict side-by-side traversal are common in such scenarios, posing a major challenge to lifelong MAPF problem.To address this issue, this paper proposes dual-layer PIBT, a lifelong MAPF method specifically designed for biconnected environments containing narrow passages. The method leverages loop decomposition of the biconnected graph to establish coordinated unidirectional constraints - all narrow passages belonging to the same loop are assigned consistent traversal directions, enabling rapid conflict-free navigation decisions.The experimental results demonstrate significant reductions in both makespan and task service time compared to the baseline method.