Branch-and-cut-and-price for multi-agent path finding. (August 2022)

• Record Type: Journal Article
• Authors: Lam, Edward; Le Bodic, Pierre; Harabor, Daniel; Stuckey, Peter J.
• Is Part Of: Computers & operations research. Volume 144(2022)
• Publication Date: 2022-08
• Subjects: Multi-agent path finding -- Multi-agent planning -- Column generation -- Cutting plane -- Valid inequality; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2022.105809
• Languages: English
• ISSNs: 0305-0548

Abstract

Abstract: The Multi-Agent Path Finding problem aims to find a set of collision-free paths that minimizes the total cost of all paths. The problem is extensively studied in artificial intelligence due to its relevance to robotics, video games and logistics applications, but is seldom considered in the mathematical optimization community. This paper tackles the problem using a branch-and-cut-and-price algorithm that incorporates a shortest path pricing problem for finding paths for every agent independently and thirteen classes of constraints for resolving different types of conflicts. Experimental results show that this mathematical approach solves 2402 of 4430 instances compared to 2039 and 1939 by the state-of-the-art solvers Lazy CBS and CBSH2-RTC published in artificial intelligence venues. Highlights: The MAPF problem finds minimal-cost collision-free paths for cooperating agents. This paper presents BCP, an exact algorithm for MAPF. BCP uses branch-and-cut-and-price to decompose MAPF into easier subproblems. It finds paths independently for each agent using a novel shortest path problem. It then resolves thirteen classes of conflicts between agents using constraints. BCP outperforms the two state-of-the-art solvers CBSH2-RTC and Lazy CBS.