Combining Strengths of Optimal Multi-Agent Path Finding Algorithms
Combining Strengths of Optimal Multi-Agent Path Finding Algorithms
复制标题
结合最优多智能体路径查找算法的优势
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
R. Barták
中科院分区：
文献类型：
--
作者：
Jirí Svancara;R. Barták
本文研究了多智能体寻路（MAPF）问题。最优求解 MAPF 是一个计算难题，多年来已经设计了许多不同的最优算法。这些算法对于某些问题实例具有良好的运行时间，而对于其他实例则表现不佳。有趣的是，这些硬实例在不同的算法中通常是不同的。这就产生了一种想法，即结合不同算法的优势，将输入问题实例分割成不相交的子问题，并通过适当的算法解决每个子问题，从而比对整个实例使用任何一种算法的计算速度更快。通过手动问题分解，我们将凭经验证明上述想法是可行的。我们还将勾勒出自动化问题分解的未来可能的工作。
The problem of multi-agent path finding (MAPF) is studied in this paper. Solving MAPF optimally is a computationally hard problem and many different optimal algorithms have been designed over the years. These algorithms have good runtimes for some problem instances, while performing badly for other instances. Interestingly, these hard instances are often different across the algorithms. This leads to an idea of combining the strengths of different algorithms in such a way that an input problem instance is split into disjoint subproblems and each subproblem is solved by appropriate algorithm resulting in faster computation than using either of the algorithms for the whole instance. By manual problem decomposition we will empirically show that the above idea is viable. We will also sketch a possible future work on automated problem decomposition.