Modifying Optimal SAT-Based Approach to Multi-Agent Path-Finding Problem to Suboptimal Variants
Pavel Surynek, Ariel Felner, Roni Stern, Eli Boyarski · Proceedings of the International Symposium on Combinatorial Search · 2021
In multi-agent path finding (MAPF) the task is to find non-conflicting paths for multiple agents. Recently, a SAT-based approach was developed to solve this problem and proved beneficial in many cases when compared to other search-based solvers. In this paper, we introduce SAT-based unbounded- and bounded-suboptimal algorithms and compare them to relevant search-based algorithms.