Dual-Layer PIBT for Lifelong Multi-Agent Pathfinding with Narrow Passages
Zhenyu Song, Ronghao Zheng, Meiqin Liu, Senlin Zhang
AI summary
Problem
Existing lifelong MAPF algorithms struggle with head-on conflicts and deadlocks in narrow passages, while optimization-based approaches are too computationally heavy for real-time use in dynamic, space-constrained environments.
Approach
The method decomposes the environment into loops and assigns priority-based, unidirectional constraints to narrow passages to preserve global connectivity, then uses PIBT for real-time conflict resolution and path planning.
Key results
- Proposes a dual-layer PIBT framework for lifelong MAPF in biconnected graphs with narrow passages
- Uses loop decomposition and priority-based direction assignment to proactively prevent head-on collisions
- Significantly reduces makespan and task service time compared to standard PIBT baselines
- Achieves comparable path lengths to optimization-based methods with substantially lower computation time
Why it matters
Enables scalable, real-time multi-agent navigation in space-efficient logistics and warehouse systems where narrow corridors are unavoidable.
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.