Lazy CBS: Implicit Conflict-Based Search Using Lazy Clause Generation
Lazy CBS: Implicit Conflict-Based Search Using Lazy Clause Generation
复制标题
Lazy CBS：使用惰性子句生成进行隐式基于冲突的搜索
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Peter James Stuckey
中科院分区：
文献类型：
--
作者：
G. Gange;Daniel Damir Harabor;Peter James Stuckey
基于冲突的搜索（CBS）是一种最佳多代理路径查找的有效方法。但是，CBS方法的性能在具有许多代理的高度竞争图中迅速降解。发生这种情况的原因之一是CBS未检测到独立的子问题。即，它可以在每次沿着另一个分支沿着同一对代理之间进行相同的冲突，直到指数级。通过存储记录冲突原因的Nogoods，使用Nogood学习的约束编程方法可以避免这种努力的重复。这可以指数减少约束编程中的搜索。在这项工作中，我们提出了懒惰的CBS，这是一种新的多代理探路方法，用懒惰的约束编程模型用Nogoods代替了CBS的高级求解器。我们使用核心引导的深度优先搜索来探索冲突的空间，并沿每个分支可重复使用的Nogoods检测到有助于快速识别可行解决方案。我们的实验表明，在SUMOF-ACOSTS度量下，懒惰的CBS可以显着改善最佳MAPF问题的最新问题，尤其是在存在重大争论的情况下。
Conflict-based Search (CBS) is a effective approach to optimal multi-agent path finding. However, performance of CBS approaches degrade rapidly in highly-contended graphs with many agents. One of the reasons this occurs is that CBS does not detect independent subproblems; i.e. it can re-solve the same conflicts between the same pairs of agents up to exponentially many times, each time along a different branch. Constraint programming approaches with nogood learning avoid this kind of duplication of effort by storing nogoods that record the reasons for conflicts. This can exponentially reduce search in constraint programming. In this work, we present Lazy CBS, a new approach to multi-agent pathfinding which replaces the high-level solver of CBS with a lazily constructed constraint programming model with nogoods. We use core-guided depth-first search to explore the space of conflicts and we detect along each branch reusable nogoods which help to quickly identify feasible solutions. Our experiments show that Lazy CBS can significantly improve on the state-of-the-art for optimal MAPF problems under the sumof-costs metric, especially in cases where there exists significant contention.