Algorithm Selection for Optimal Multi-Agent Path Finding via Graph Embedding

多智能体路径规划（MAPF）是指找到多个智能体的路径，使它们不会相撞。这个问题在许多现实世界的应用中都有体现，例如控制自动化仓库中的运输机器人、在视频游戏中移动角色以及协调自动驾驶汽车在交叉口行驶。找到MAPF的最优解是NP-Hard问题，但现代最优解求解器可以扩展到数百个智能体，甚至在某些情况下可以扩展到数千个智能体。不同的求解器采用不同的方法，没有单一的最先进的方法适用于所有问题。此外，没有明确的、可证明的指导方针来选择何时使用每个最优MAPF求解器。之前的工作采用算法选择（AS）技术从过去的数据中学习这些指导方针。在选择最优MAPF算法时，采用AS的一个主要挑战是如何编码给定的MAPF问题。之前的工作要么使用手工制作的特征，要么使用问题的图像表示。我们探索了MAPF问题的基于图形的编码，并展示了如何使用现代的图形嵌入算法FEATHER来实时使用它们。然后，我们展示了如何有效地将此编码与现有编码相结合，从而产生了一种新的AS方法，我们称之为基于图嵌入的MAPF算法选择（MAG）。对MAG在几个MAPF算法选择任务上进行了广泛的实验评估，结果显示它要么与现有方法相当，要么明显优于现有方法。

本文旨在解决多智能体路径规划（Multi-agent path finding, MAPF）问题，即为多个智能体找到不会碰撞的路径。该问题涉及到自动化仓库中控制运输机器人、视频游戏中角色移动以及协调自动驾驶汽车在交叉口行驶等多种实际应用。该问题的最优解是NP-Hard问题，但现代最优解算法可以扩展到数百个智能体，甚至在某些情况下可以扩展到数千个智能体。然而，不同的解算器采用不同的方法，没有一种单一的最先进方法适用于所有问题。因此，本文旨在通过算法选择（AS）技术从过去的数据中学习选择最优MAPF算法的指南。

本文的关键思路是使用基于图的编码来解决MAPF问题，并展示如何将其有效地与现有编码相结合，从而形成一种新的AS方法，称为MAPF算法选择通过图嵌入（MAG）。该方法使用现代图嵌入算法FEATHER，可以实时地将MAPF问题编码为图形式，然后对其进行处理。

本文的亮点包括使用基于图的编码来解决MAPF问题，提出了一种新的AS方法MAG，该方法在多个MAPF算法选择任务中表现出与现有方法相当或显著更好的性能。该方法还使用了现代图嵌入算法FEATHER来实时编码MAPF问题，并且在多个数据集上进行了广泛的实验评估。该工作的开源代码也可供使用。

最近在这个领域中，还有一些相关的研究，例如《Multi-Agent Path Finding with Kinematic Constraints》、《A Survey of Cooperative Multi-Agent Pathfinding》等。