Learning-based fast alternating direction method of multipliers for multi-agent path finding using temporary variable-fixing

This paper addresses a multi-agent path finding (MAPF) problem, a generalized and complex routing problem widely encountered in transportation and logistics systems but barely investigated in operations research. To tackle it, we use alternating direction method of multipliers (ADMM), which has been successfully applied in machine learning but requires a significant amount of computation time if applied to solve MAPF classically. This paper proposes a novel learning-based ADMM for decomposing and significantly accelerating the solution process of MAPF. For this purpose, we first mathematically formulate the problem into an integer linear program (ILP), then develop speeding-up techniques such as tailored Dijkstra and soft-start, to construct a fast ADMM (FADMM). To further improve the computational efficiency, we develop an imitation learning-based policy network to learn from the iteration data of FADMM by removing unnecessary coordination operations among agents. As shown by computational results from comprehensive experiments with benchmark MAPF instances, this innovative approach drastically reduces the time required across various task settings and outperforms state-of-the-art methods, such as conflict-based search. The proposed FADMM yields near-optimal solutions within 300 s, achieving an average optimality gap of 0.74% on tractable instances, and still just a duality gap of 9.93% even in complex instances with loose bounds. The learning-based method achieves a considerable speed up of 3.01 with only a very tiny degradation (0.05% on average) of the solution quality. Furthermore, this method can be generalized to complex MAPF scenarios and is suited for a wide range of real-world applications.