将量子计算与经典算法结合，高效解决多智能体路径规划难题。
Hybrid Quantum-Classical Multi-Agent Pathfinding
- 用分支定界定价框架，迭代求解冲突图对应的QUBO问题。
- 在真实量子硬件上验证，性能超越传统QUBO方法和主流求解器。
- 适合需要大规模协同路径规划的自动驾驶等场景。
多智能体路径规划（MAPF）旨在为多个智能体在共享空间中规划无冲突路径以到达目标位置。该问题在智能体数量庞大时计算复杂度急剧上升，常见于自动驾驶等实际应用。量子计算有望突破此限制，但当前量子硬件仍处于初级阶段，算力与容错能力有限。本文首次提出基于分支定界定价框架的最优混合量子-经典MAPF算法，通过迭代求解基于冲突图的二次无约束二值优化（QUBO）问题融合量子计算。在真实量子硬件及基准数据集上的实验表明，该方法优于先前的QUBO建模方式，并显著超越当前最先进的MAPF求解器。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。