Experimental Evaluation of Classical Multi Agent Path Finding Algorithms
Experimental Evaluation of Classical Multi Agent Path Finding Algorithms
复制标题
经典多智能体寻路算法的实验评估
DOI：
--
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Roni Stern
中科院分区：
文献类型：
--
作者：
Omri Kaduri;Eli Boyarski;Roni Stern
现代最优多智能体路径查找（MAPF）算法可以扩展到解决数百个智能体的问题。为了便于这些算法之间的比较，最近提出了MAPF问题的基准。我们报告了一个全面的评估，一组不同的国家的最先进的最佳MAPF算法在整个基准。结果表明，在覆盖率方面，最近提出的LazyCBS算法明显优于其他算法，但通常不是最快的算法。这表明算法选择方法可能是有益的。然后，我们在MAPF中描述了不同的算法选择设置，并评估了每个设置的简单基线。最后，我们提出了一个扩展现有的MAPF基准的形式不同的方式来分配代理的源和目标位置。
Modern optimal multi-agent path finding (MAPF) algorithms can scale to solve problems with hundreds of agents. To facilitate comparison between these algorithms, a benchmark of MAPF problems was recently proposed. We report a comprehensive evaluation of a diverse set of state-of-the-art optimal MAPF algorithms over the entire benchmark. The results show that in terms of coverage, the recently proposed LazyCBS algorithm outperforms all others significantly, but it is usually not the fastest algorithm. This suggests algorithm selection methods can be beneficial. Then, we characterize different setups for algorithm selection in MAPF, and evaluate simple baselines for each setup. Finally, we propose an extension of the existing MAPF benchmark in the form of different ways to distribute the agents’ source and target locations.
使用互斥传播的多代理路径查找
DOI：
--
发表时间：
2020
期刊：
Proceedings of the International Conference on Automated Planning and Scheduling
影响因子：
--
作者：
Zhang, H.;Li, J.;Surynek, P;Koenig, S.;Kumar, S.
通讯作者：
Kumar, S.