Modifying Optimal SAT-based Approach to Multi-agent Path-finding Problem to Suboptimal Variants
This work addresses the multi-agent path finding problem for robotics and AI planning, but it is incremental as it modifies an existing optimal SAT-based approach to suboptimal variants.
The paper tackled the problem of finding suboptimal solutions for the multi-agent path finding (MAPF) sum-of-costs variant by developing SAT-based unbounded- and bounded-suboptimal algorithms, and experimental results showed that the SAT-based solver significantly outperforms search-based solvers in many cases.
In multi-agent path finding (MAPF) the task is to find non-conflicting paths for multiple agents. In this paper we focus on finding suboptimal solutions for MAPF for the sum-of-costs variant. Recently, a SAT-based approached was developed to solve this problem and proved beneficial in many cases when compared to other search-based solvers. In this paper, we present SAT-based unbounded- and bounded-suboptimal algorithms and compare them to relevant algorithms. Experimental results show that in many case the SAT-based solver significantly outperforms the search-based solvers.