Multi-Agent Path Finding (MAPF), i.e., finding collision-free paths for multiple robots, is important for many applications where small runtimes are important, 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 solution 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 inadmissibly estimate the cost of the solution under each high-level node and uses EES to choose which high-level node to expand next. We also investigate recent improvements to CBS and adapt them to EECBS. We find that EECBS with the improvements runs significantly faster than the MAPF algorithms ECBS, BCP-7, and eMDD-SAT on a variety of MAPF instances. We hope that the scalability of EECBS enables wider adoption of MAPF formulations in practical applications.

通过基于在线学习的inadmissible估计和EES算法，在研究现有的bounded-suboptimal MAPF算法的基础上，提出一种新的bounded-suboptimal算法EECBS，相较于ECBS，BCP-7和eMDD-SAT等先进算法，在运行时间上表现更快，希望其可推广到更多bounded-suboptimal MAPF算法的应用中。

EECBS: 多智能体路径规划的有界次优搜索