Hybrid Quantum-Classical Multi-Agent Pathfinding

Thore Gerlach, Loong Kuan Lee, Frederic Barbaresco, Nico Piatkowski
Proceedings of the 42nd International Conference on Machine Learning, PMLR 267:19161-19171, 2025.

Abstract

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. Quantum Computing (QC) is a promising candidate in overcoming such limits. However, current quantum hardware is still in its infancy and thus limited in terms of computing 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-prize. QC is integrated by iteratively solving QUBO problems, based on conflict graphs. Experiments on actual quantum hardware and results on benchmark data suggest that our approach dominates previous QUBO formulations and state-of-the-art MAPF solvers.

Cite this Paper

BibTeX
@InProceedings{pmlr-v267-gerlach25a, title = {Hybrid Quantum-Classical Multi-Agent Pathfinding}, author = {Gerlach, Thore and Lee, Loong Kuan and Barbaresco, Frederic and Piatkowski, Nico}, booktitle = {Proceedings of the 42nd International Conference on Machine Learning}, pages = {19161--19171}, year = {2025}, editor = {Singh, Aarti and Fazel, Maryam and Hsu, Daniel and Lacoste-Julien, Simon and Berkenkamp, Felix and Maharaj, Tegan and Wagstaff, Kiri and Zhu, Jerry}, volume = {267}, series = {Proceedings of Machine Learning Research}, month = {13--19 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v267/main/assets/gerlach25a/gerlach25a.pdf}, url = {https://proceedings.mlr.press/v267/gerlach25a.html}, abstract = {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. Quantum Computing (QC) is a promising candidate in overcoming such limits. However, current quantum hardware is still in its infancy and thus limited in terms of computing 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-prize. QC is integrated by iteratively solving QUBO problems, based on conflict graphs. Experiments on actual quantum hardware and results on benchmark data suggest that our approach dominates previous QUBO formulations and state-of-the-art MAPF solvers.} }
Endnote
%0 Conference Paper %T Hybrid Quantum-Classical Multi-Agent Pathfinding %A Thore Gerlach %A Loong Kuan Lee %A Frederic Barbaresco %A Nico Piatkowski %B Proceedings of the 42nd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2025 %E Aarti Singh %E Maryam Fazel %E Daniel Hsu %E Simon Lacoste-Julien %E Felix Berkenkamp %E Tegan Maharaj %E Kiri Wagstaff %E Jerry Zhu %F pmlr-v267-gerlach25a %I PMLR %P 19161--19171 %U https://proceedings.mlr.press/v267/gerlach25a.html %V 267 %X 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. Quantum Computing (QC) is a promising candidate in overcoming such limits. However, current quantum hardware is still in its infancy and thus limited in terms of computing 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-prize. QC is integrated by iteratively solving QUBO problems, based on conflict graphs. Experiments on actual quantum hardware and results on benchmark data suggest that our approach dominates previous QUBO formulations and state-of-the-art MAPF solvers.
APA
Gerlach, T., Lee, L.K., Barbaresco, F. & Piatkowski, N.. (2025). Hybrid Quantum-Classical Multi-Agent Pathfinding. Proceedings of the 42nd International Conference on Machine Learning, in Proceedings of Machine Learning Research 267:19161-19171 Available from https://proceedings.mlr.press/v267/gerlach25a.html.

Related Material