Improved Heuristics for Multi-Agent Path Finding with Conflict-Based Search: Preliminary Results
Improved Heuristics for Multi-Agent Path Finding with Conflict-Based Search: Preliminary Results
复制标题
通过基于冲突的搜索改进多代理路径查找的启发式：初步结果
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Hang Ma
中科院分区：
文献类型：
--
作者：
Jiaoyang Li;Ariel Felner;Eli Boyarski;Sven Koenig;Hang Ma
基于冲突的搜索（CBS）及其增强功能是多试路径发现的最强算法之一。最近的工作引入了可接受的启发式方法，以指导对CBS的高级搜索。在这项工作中，我们证明了这种启发式的局限性，因为它仅基于红衣主教冲突。然后，我们通过推理代理之间的成对依赖性来介绍两个新的可接受的启发式方法。从经验上讲，具有新启发式的CBS可以显着提高CBS的成功率，并以最近的启发式态度提高了CBS的成功率，并将扩展的节点和运行时的数量减少到50倍。
Conflict-Based Search (CBS) and its enhancements are among the strongest algorithms for Multi-Agent Path Finding. Recent work introduced an admissible heuristic to guide the high-level search of CBS. In this work, we prove the limitation of this heuristic, as it is based on cardinal conflicts only. We then introduce two new admissible heuristics by reasoning about the pairwise dependencies between agents. Empirically, CBS with either new heuristic significantly improves the success rate over CBS with the recent heuristic and reduces the number of expanded nodes and runtime by up to a factor of 50.
影响因子：
5.2
作者：
W. Hönig;Scott Kiesel;Andrew Tinka;Joseph W. Durham;Nora Ayanian
通讯作者：
W. Hönig;Scott Kiesel;Andrew Tinka;Joseph W. Durham;Nora Ayanian
大型代理的多代理路径查找
DOI：
--
发表时间：
2019
期刊：
Proceedings of the AAAI Conference on Artificial Intelligence (AAAI
影响因子：
--
作者：
Li, J.;Surynek, P.;Felner, A.;Ma, H.;Kumar, S.;Koenig, S.
通讯作者：
Koenig, S.