Conceptual Comparison of Compilation-Based Solvers for Multi-Agent Path Finding: MIP vs. SAT

Abstract

The task in multi-agent path finding (MAPF) is to find paths through which agents can navigate from their starting positions to given individual goal positions. The combination of two additional requirements makes the problem challenging: (i) agents must not collide with each other and (ii) the paths must be optimal with respect to some objective. We summarize and compare main ideas of contemporary compilation-based solvers for MAPF using MIP and SAT formalisms.