论文标题
EECB：一个有界的次观搜索多代理路径查找
EECBS: A Bounded-Suboptimal Search for Multi-Agent Path Finding
论文作者
论文摘要
多代理路径查找（MAPF），即为多个机器人找到无碰撞路径，对于许多需要小型运行时间的应用非常重要，包括亚马逊经营的那种自动化仓库。 CBS是用于最佳求解MAPF的领先的两级搜索算法。 ECBS是CBS的一个有界的临时变体，它使用焦点搜索来通过牺牲最佳性来加快CBS的速度，而不是保证其解决方案的成本在给定的最佳因素之内。在本文中，我们研究了如何使用不可接受的启发式方法进一步降低其运行时。在明确的估计搜索（EES）中，我们提出了明确的估计CBS（EECB），CBS是CBS的新有界量的变体，它使用在线学习来获得每个高级节点解决方案的不可接受的估计，并使用EES使用EES来选择哪个高级node来扩展下一步。我们还研究了CBS的最新改进并将其适应EECB。我们发现，具有改进的EECB的运行速度明显快于各种MAPF实例上最新的有界界定次观MAPF算法ECB，BCP-7和EMDD-SAT。我们希望EECB的可伸缩性启用有限次点MAPF算法的其他应用程序。
Multi-Agent Path Finding (MAPF), i.e., finding collision-free paths for multiple robots, is important for many applications where small runtimes are necessary, including the kind of automated warehouses operated by Amazon. CBS is a leading two-level search algorithm for solving MAPF optimally. ECBS is a bounded-suboptimal variant of CBS that uses focal search to speed up CBS by sacrificing optimality and instead guaranteeing that the costs of its solutions are within a given factor of optimal. In this paper, we study how to decrease its runtime even further using inadmissible heuristics. Motivated by Explicit Estimation Search (EES), we propose Explicit Estimation CBS (EECBS), a new bounded-suboptimal variant of CBS, that uses online learning to obtain inadmissible estimates of the cost of the solution of each high-level node and uses EES to choose which high-level node to expand next. We also investigate recent improvements of CBS and adapt them to EECBS. We find that EECBS with the improvements runs significantly faster than the state-of-the-art bounded-suboptimal MAPF algorithms ECBS, BCP-7, and eMDD-SAT on a variety of MAPF instances. We hope that the scalability of EECBS enables additional applications for bounded-suboptimal MAPF algorithms.
