Solving the Multi-Agent Path Finding (MAPF) problem optimally is known to be NP-Hard for both make-span and total arrival time minimization. While many algorithms have been developed to solve MAPF problems, there is no dominating optimal MAPF algorithm that works well in all types of problems and no standard guidelines for when to use which algorithm. In this work, we develop the deep convolutional network MAPFAST (Multi-Agent Path Finding Algorithm SelecTor), which takes a MAPF problem instance and attempts to select the fastest algorithm to use from a portfolio of algorithms. We improve the performance of our model by including single-agent shortest paths in the instance embedding given to our model and by utilizing supplemental loss functions in addition to a classification loss. We evaluate our model on a large and diverse dataset of MAPF instances, showing that it outperforms all individual algorithms in its portfolio as well as the state-of-the-art optimal MAPF algorithm selector. We also provide an analysis of algorithm behavior in our dataset to gain a deeper understanding of optimal MAPF algorithms' strengths and weaknesses to help other researchers leverage different heuristics in algorithm designs.
翻译:最佳解决多者路径定位( MAPF) 问题的最佳方法已知是 NP- Hard, 用于 制造和 全部到达时间最小化。 虽然已经开发了许多算法来解决MAPF 问题, 但是没有主导在所有类型的问题中行之有效的最佳MAPF 算法, 也没有标准指南用于何时使用哪种算法。 在这项工作中, 我们开发深层革命网络 MAPFAST ( Multi- Agent Path Find Algorithm SelecTor), 它将出现一个问题实例, 并尝试从一个算法组合中选择使用最快的算法。 我们改进了模型的性能, 将单一代理人最短的路径嵌入模型中, 并利用补充性损失函数, 除分类损失之外, 。 我们评估了我们模型中大型和多样化的MAPFPF实例的数据集, 表明它超越了组合中的所有个体算法, 以及最先进的MAPF 算法选择器 。 我们还在数据集中帮助分析算法行为, 以便更深入地了解最优的MAPFSLAVC 的弱点和各种算法研究机的弱点。