Hybrid Quantum-Classical Multi-Agent Pathfinding

Multi-Agent Path Finding (MAPF) focuses on de-termining conflict-free paths for multiple agents navigating through a shared space to reach speci-fied goal locations. This problem becomes compu-tationally challenging, particularly when handling large numbers of agents, as frequently encoun-tered in practical applications like coordinating autonomous vehicles. Quantum Computing (QC) is a promising candidate in overcoming such lim-its. However, current quantum hardware is still in its infancy and thus limited in terms of comput-ing power and error robustness. In this work, we present the first optimal hybrid quantum-classical MAPF algorithms which are based on branch-and-cut-and-price. QC is integrated by iteratively solv-ing QUBO problems, based on conflict graphs. Experiments on actual quantum hardware and results on benchmark data suggest that our ap-proach dominates previous QUBO formulations and state-of-the-art MAPF solvers.