Low-Level Search on Time Intervals in Branch-and-Cut-and-Price for Multi-Agent Path Finding

Multi-agent path finding is the problem of navigating a set of agents from their starting locations to their target locations while avoiding collisions. A leading method for optimal multi-agent path finding is branch-and-cut-and-price, a framework based on mathematical optimization. The reference implementation, named BCP-MAPF, shows highly competitive results against AI-based search. This paper presents BCP2-MAPF, a new implementation of branch-and-cut-and-price paired with a novel low-level path finder based on time intervals. Experimental results demonstrate that BCP2-MAPF significantly outperforms the other state-of-the-art optimal algorithms BCP-MAPF, Lazy CBS and CBSH2-RTC.