  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.
