Modeling and Solving the Multi-agent Pathfinding Problem in Picat
Modeling and Solving the Multi-agent Pathfinding Problem in Picat
复制标题
在 Picat 中建模并解决多智能体寻路问题
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Pavel Surynek
中科院分区：
文献类型：
--
作者：
R. Barták;Neng;Roni Stern;Eli Boyarski;Pavel Surynek
多智能体寻径（MAPF）问题因其与实际应用的关系而受到广泛关注。在本文中，我们提出了一个基于约束的MAPF声明模型，以及它在Picat（一种基于逻辑的编程语言）中的实现。我们通过实验证明，基于picat的实现具有很强的竞争力，有时甚至优于以前的方法。重要的是，建议的Picat实现非常通用。我们通过展示如何轻松地调整它来优化不同的MAPF目标（例如最小化makespan或最小化成本总和）以及一系列MAPF变体来演示这一点。此外，基于picat的模型可以自动编译成几个通用求解器，如SAT求解器和混合整数规划求解器（MIP）。这对于MAPF来说尤其重要，因为一些MAPF变体在编译为SAT时解算更有效，而另一些变体在编译为MIP时解算更有效。我们分析了这些差异以及不同的声明模型和编码对经验性能的影响。
The multi-agent pathfinding (MAPF) problem has attracted considerable attention because of its relation to practical applications. In this paper, we present a constraint-based declarative model for MAPF, together with its implementation in Picat, a logic-based programming language. We show experimentally that our Picat-based implementation is highly competitive and sometimes outperforms previous approaches. Importantly, the proposed Picat implementation is very versatile. We demonstrate this by showing how it can be easily adapted to optimize different MAPF objectives, such as minimizing makespan or minimizing the sum of costs, and for a range of MAPF variants. Moreover, a Picat-based model can be automatically compiled to several general-purpose solvers such as SAT solvers and Mixed Integer Programming solvers (MIP). This is particularly important for MAPF because some MAPF variants are solved more efficiently when compiled to SAT while other variants are solved more efficiently when compiled to MIP. We analyze these differences and the impact of different declarative models and encodings on empirical performance.