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

Authors

  • Pavel Surynek Czech Technical University in Prague, Faculty of Information Technology

Keywords:

Methodology And Critiques Of Current Practice, Problem Compilation, Search In Boolean Satisfiability

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.

Downloads

Published

2021-07-22