Adding Heuristics to Conflict-Based Search for Multi-Agent Path Finding

Adding Heuristics to Conflict-Based Search for Multi-Agent Path Finding
复制标题

将启发式添加到基于冲突的搜索以实现多代理路径查找

DOI：
--
复制
发表时间：
2018
期刊：
International Conference on Automated Planning and Scheduling
影响因子：
--
通讯作者：
Sven Koenig
Sven Koenig
中科院分区：
--
文献类型：
--
作者：
Ariel Felner;Jiaoyang Li;Eli Boyarski;Hang Ma;L. Cohen;T. K. S. Kumar;Sven Koenig

文献摘要

被引文献

相似文献

基于冲突的搜索（CBS）及其增强功能是多代理探路问题的最强算法之一。但是，CBS的现有变体不会使用任何估计未来工作的启发式方法。在本文中，我们通过汇总了代理商之间的基本冲突来引入CBS的不同可接受的启发式方法。在我们的实验中，具有这些启发式方法的CBS的表现优于先前的最新CBS变体，高达五倍。
Conflict-Based Search (CBS) and its enhancements are among the strongest algorithms for the multi-agent path-finding problem. However,existing variants of CBS do not use any heuristics that estimate future work. In this paper, we introduce different admissible heuristics for CBS by aggregating cardinal conflicts among agents. In our experiments, CBS with these heuristics outperforms previous state-of-the-art CBS variants by up to a factor of five.