AAAI

Association for the Advancement of Artificial Intelligence

Home > Proceedings / Proceedings of the International Symposium on Combinatorial Search, 10

Modifying Optimal SAT-Based Approach to Multi-Agent Path-Finding Problem to Suboptimal Variants

Authors

Pavel Surynek,Ariel Felner,Roni Stern,Eli Boyarski

National Institute of Advanced Industrial Science and Technology,Ben-Gurion University of the Negev,Ben-Gurion University of the Negev,Bar-Ilan University


Proceedings:

Proceedings of the International Symposium on Combinatorial Search, 10

Volume

Issue:

Vol. 10 No. 1 (2017): Tenth Annual Symposium on Combinatorial Search

Track:

Extended Abstracts

Downloads:

Download PDF

Abstract:

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.

DOI:

10.1609/socs.v8i1.18417


SOCS

Vol. 10 No. 1 (2017): Tenth Annual Symposium on Combinatorial Search