Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2501.14568 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908441407127552 |
|---|---|
| author | Gerlach, Thore Lee, Loong Kuan Barbaresco, Frédéric Piatkowski, Nico |
| author_facet | Gerlach, Thore Lee, Loong Kuan Barbaresco, Frédéric Piatkowski, Nico |
| contents | 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-andcut-and-price. 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 formulationsand state-of-the-art MAPF solvers. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_14568 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Hybrid Quantum-Classical Multi-Agent Pathfinding Gerlach, Thore Lee, Loong Kuan Barbaresco, Frédéric Piatkowski, Nico Artificial Intelligence Quantum Physics 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-andcut-and-price. 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 formulationsand state-of-the-art MAPF solvers. |
| title | Hybrid Quantum-Classical Multi-Agent Pathfinding |
| topic | Artificial Intelligence Quantum Physics |
| url | https://arxiv.org/abs/2501.14568 |