Automatic Algorithm Selection In Multi-agent Pathfinding
Automatic Algorithm Selection In Multi-agent Pathfinding
复制标题
多智能体寻路中的自动算法选择
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
W. Yeoh
中科院分区：
文献类型：
--
作者：
D. Sigurdson;V. Bulitko;Sven Koenig;Carlos Hernández;W. Yeoh
在多智能体寻径（MAPF）问题中，智能体需要从起点导航到目标位置，而不会相互碰撞。MAPF算法有多种，包括窗口分层合作算法A*、流注释重规划算法A*和有界多智能体算法A*。通常情况下，没有一个单一的算法支配所有的MAPF实例。因此，在本文中，我们研究了使用深度学习从给定MAPF问题实例的算法组合中自动选择最佳MAPF算法。实证结果表明，我们的自动算法选择方法使用现成的卷积神经网络，能够优于我们投资组合中的任何单个MAPF算法。
In a multi-agent pathfinding (MAPF) problem, agents need to navigate from their start to their goal locations without colliding into each other. There are various MAPF algorithms, including Windowed Hierarchical Cooperative A*, Flow Annotated Replanning, and Bounded Multi-Agent A*. It is often the case that there is no a single algorithm that dominates all MAPF instances. Therefore, in this paper, we investigate the use of deep learning to automatically select the best MAPF algorithm from a portfolio of algorithms for a given MAPF problem instance. Empirical results show that our automatic algorithm selection approach, which uses an off-the-shelf convolutional neural network, is able to outperform any individual MAPF algorithm in our portfolio.