Algorithm Selection for Optimal Multi-Agent Path Finding via Graph Embedding
This addresses the challenge of efficiently choosing the best solver for MAPF problems, which is crucial for applications like warehouse robotics and self-driving cars, but the approach is incremental as it builds on existing algorithm selection techniques.
The paper tackles the problem of selecting optimal multi-agent path finding (MAPF) solvers by proposing a novel algorithm selection method called MAG, which uses graph embeddings to encode MAPF problems and combines them with existing encodings, resulting in performance that is either on-par or significantly better than prior methods.
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.