Multi-Agent Path Finding (MAPF) is a problem that requires one to compute a set of collision-free paths for a team of moving agents. The problem appears in variety of practical applications including warehouse logistics, traffic management, aircraft towing and computer games. The general version of the problem (minimizing makespan or sum of path costs, on graphs with parallel actions and rotations) is known to be NP-hard. One of the leading methods for solving MAPF optimally, employs a strategy known as Conflict-based Search (CBS). The central idea is to plan paths for each agent independently and resolve collisions by branching the current plan. Each branch is a new candidate plan wherein one agent or the other is forced to find a new path that avoids the selected collision. When we examine CBS from an optimisation perspective, it is clearly a form of (Logic-based) Benders Decomposition. This begs the question: can we use combinatorial optimisation techniques to tackle the MAPF problem efficiently? In this talk, I will show two approaches: the first uses core-guided search together with a no good learning Constraint Programming solver; the second uses Branch-and-Cut-and-Price together with a MIP solver. Both methods prove to be highly competitive to previous CBS approaches.

Peter Stuckey is the Deputy Director of OPTIMA, and a Professor in the Faculty of Information Technology at Monash University, and a project leader in the Data61 CSIRO laboratory.