Modifying optimal SAT-based approach to multi-agent path-finding problem to suboptimal variants Academic Article uri icon

abstract

  • Abstract: 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. Subjects: Artificial Intelligence (cs. AI) Cite as: arXiv: 1707.00228 [cs. AI](or arXiv: 1707.00228 v1 [cs. AI] for this version) Submission history From: Pavel Surynek [view email][v1] Sun, 2 Jul 2017 03: 08: 26 GMT (2558kb, D)

publication date

  • January 1, 2017