Rapid Randomized Restarts for Multi-Agent Path Finding Solvers
Rapid Randomized Restarts for Multi-Agent Path Finding Solvers
复制标题
多智能体路径寻找求解器的快速随机重启
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Sven Koenig
中科院分区：
文献类型：
--
作者：
L. Cohen;Glenn Wagner;David Chan;T. K. S. Kumar;H. Choset;Sven Koenig
多智能体寻径（Multi-Agent Path Finding， MAPF）是人工智能和机器人学中研究较多的np困难问题。最近，随机化MAPF求解器显示出运行时的重尾分布，可以利用它来提高给定运行时限制下的成功率。在本文中，我们讨论了随机化MAPF求解器的不同方法，并评估了最先进的MAPF求解器（如iECBS，带高速公路的M*和CBS-CL）的简单快速随机重启策略。
Multi-Agent Path Finding (MAPF) is an NP-hard problem that has been well studied in artificial intelligence and robotics. Recently, randomized MAPF solvers have been shown to exhibit heavy-tailed distributions of runtimes, which can be exploited to boost their success rate for a given runtime limit. In this paper, we discuss different ways of randomizing MAPF solvers and evaluate simple rapid randomized restart strategies for state-of-the-art MAPF solvers such as iECBS, M* with highways and CBS-CL.