Speaker
Description
Multi-Agent Path Finding (MAPF) focuses on determining conflict-free paths for multiple agents navigating through a shared space to reach specified goal locations. This problem becomes computationally challenging, particularly when handling large numbers of agents, as frequently encountered in practical applications like coordinating autonomous vehicles or drone swarms. Quantum Computing (QC) is a promising candidate for overcoming such scalability limits. However, current quantum hardware remains constrained in terms of computing power, connectivity, and error robustness. In this work, we present the first optimal hybrid quantum-classical MAPF algorithms, based on the Branch-and-Cut-and-Price paradigm. QC is integrated by iteratively solving Quadratic Unconstrained Binary Optimization (QUBO) problems defined over dynamically generated conflict graphs. Our method is designed to exploit future hardware advances, while already providing practical benefits through hardware-aware QUBO formulations. Extensive experiments on actual quantum hardware and benchmark datasets show that our approach outperforms prior QUBO-based MAPF methods and competes well with state-of-the-art classical solvers. This work opens a scalable path forward for applying quantum techniques to combinatorial path planning problems.
