论文标题
基于基于冲突的搜索（CBS）和焦点搜索（FS）的组合，对任何时间MAPF求解器的分析
Analysis Of The Anytime MAPF Solvers Based On The Combination Of Conflict-Based Search (CBS) and Focal Search (FS)
论文作者
论文摘要
基于冲突的搜索（CBS）是一种广泛使用的算法，用于最佳地解决多代理探路（MAPF）问题。 CBS的核心思想是运行层次搜索，当在高级别上探索解决方案树时，探索了候选者的树，并且在低级方面进行了针对特定代理的个人计划（受某些约束）。为了使运行时间的折衷方案设计了有界亚最佳CB的不同变体，这改变了CBS的高级和低级搜索程序。此外，CBS的任何时间变体都存在将焦点搜索（FS）应用于CBS的高级搜索 - 任何时间BCB。但是，与天真的CB相比，与幼稚的CB相比，该算法的性能与降低的cbs相比，没有全面分析该算法的表现。这项工作旨在填补这一空白。此外，我们介绍并评估另一个在两个CBS上使用FS的CBS Anytime版本。从经验上讲，我们表明其行为主要与任何时间BCB所证明的行为不同。最后，我们比较这两种算法正对头，并表明在两个级别的CBS上使用焦点搜索可能在广泛的设置中是有益的。
Conflict-Based Search (CBS) is a widely used algorithm for solving multi-agent pathfinding (MAPF) problems optimally. The core idea of CBS is to run hierarchical search, when, on the high level the tree of solutions candidates is explored, and on the low-level an individual planning for a specific agent (subject to certain constraints) is carried out. To trade-off optimality for running time different variants of bounded sub-optimal CBS were designed, which alter both high- and low-level search routines of CBS. Moreover, anytime variant of CBS does exist that applies Focal Search (FS) to the high-level of CBS - Anytime BCBS. However, no comprehensive analysis of how well this algorithm performs compared to the naive one, when we simply re-invoke CBS with the decreased sub-optimality bound, was present. This work aims at filling this gap. Moreover, we present and evaluate another anytime version of CBS that uses FS on both levels of CBS. Empirically, we show that its behavior is principally different from the one demonstrated by Anytime BCBS. Finally, we compare both algorithms head-to-head and show that using Focal Search on both levels of CBS can be beneficial in a wide range of setups.
