Modifying Optimal SAT-Based Approach to Multi-Agent Path-Finding Problem to Suboptimal Variants
Modifying Optimal SAT-Based Approach to Multi-Agent Path-Finding Problem to Suboptimal Variants
复制标题
将多智能体寻路问题的基于 SAT 的最优方法修改为次优变体
DOI：
10.1609/socs.v8i1.18417
复制
发表时间：
2017
影响因子：
8.5
通讯作者：
Eli Boyarski
中科院分区：
文献类型：
--
作者：
Pavel Surynek;Ariel Felner;Roni Stern;Eli Boyarski
在多代理路径查找（MAPF）中，任务是为多种代理找到非冲突的路径。最近，与其他基于搜索的求解器相比，在许多情况下，开发了一种基于SAT的方法来解决此问题，并在许多情况下被证明是有益的。在本文中，我们介绍了基于SAT的无界和有界的次观算法，并将它们与相关的基于搜索的算法进行比较。
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.