Feasibility Study: Using Bypass Directly in Structured Warehouse for Multi-Agent Path Finding

Abstract

In warehouse environments, corridor conflicts often lead to traffic congestion, which result in many Multi-Agent Path Finding (MAPF) algorithms failing to find solutions within a reasonable time limit. Previous works have studied using corridor reasoning techniques or incorporating guidance, such as highways, to address this problem. However, these approaches often either encounter timeouts or yield low-quality solutions. In this work, based on Conflict-Based Search (CBS), we propose a technique called Reversible Lanes, specifically designed to address corridor conflicts by imposing a new constraint that forces agents to use bypasses for conflict resolution. Our approach is motivated by three key observations from prior research: (1) in warehouse maps, the overhead associated with maintaining solution optimality via corridor reasoning technique is often disproportionate to the benefits gained; (2) the fixed nature of manually designed highways exhibits a lack of adaptability, leading to poor solution quality on certain instances; and (3) the structural properties of warehouse layouts render direct bypass usage feasible and incur minimal additional costs. Theoretically, we demonstrate the feasibility of our algorithm by analyzing its relationship to both corridor reasoning techniques and highways. Experimentally, the results show that our algorithm provides a more effective approach for resolving corridor conflicts compared to these existing methods, achieving a superior trade off between solution quality and computational efficiency by finding near-optimal solutions with reduced runtime.