Multi-agent path finding (MAPF) is the problem of finding paths for multiple
agents such that they do not collide. This problem manifests in numerous
real-world applications such as controlling transportation robots in automated
warehouses, moving characters in video games, and coordinating self-driving
cars in intersections. Finding optimal solutions to MAPF is NP-Hard, yet modern
optimal solvers can scale to hundreds of agents and even thousands in some
cases. Different solvers employ different approaches, and there is no single
state-of-the-art approach for all problems. Furthermore, there are no clear,
provable, guidelines for choosing when each optimal MAPF solver to use. Prior
work employed Algorithm Selection (AS) techniques to learn such guidelines from
past data. A major challenge when employing AS for choosing an optimal MAPF
algorithm is how to encode the given MAPF problem. Prior work either used
hand-crafted features or an image representation of the problem. We explore
graph-based encodings of the MAPF problem and show how they can be used
on-the-fly with a modern graph embedding algorithm called FEATHER. Then, we
show how this encoding can be effectively joined with existing encodings,
resulting in a novel AS method we call MAPF Algorithm selection via Graph
embedding (MAG). An extensive experimental evaluation of MAG on several MAPF
algorithm selection tasks reveals that it is either on-par or significantly
better than existing methods.

多智能体路径规划问题（MAPF）是寻找多个智能体不发生碰撞的路径的问题，该研究论文提出了一种基于图嵌入的解决方案，称为 MAPF 算法选择图嵌入（MAG），通过对 MAPF 问题进行图形编码并利用现代图嵌入算法，该方法在多个 MAPF 算法选择任务上表现出与现有方法相当或显著更好的性能。