QUAV: Quantum-Assisted Path Planning and Optimization for UAV Navigation with Obstacle Avoidance

技术摘要：QUAV —— 用于无人机导航的量子辅助路径规划与优化

问题陈述
本文探讨了在具有密集障碍物和受限空域的复杂动态环境中，无人机（UAV）实时路径规划所面临的挑战。传统的经典方法，如图搜索算法（A*、Dijkstra）和基于采样的算法（RRT），在扩展到高维优化问题时，往往面临难以承受的计算负载。这些方法在同时满足碰撞规避约束、动态禁飞区和地理空间精度要求的同时，难以高效地评估海量的潜在路线。作者认为，这些问题的组合特性需要能够更高效探索解空间的替代框架。

方法论
作者提出了 QUAV，这是一个利用**量子近似优化算法（QAOA）**将无人机路径规划重新表述为量子优化任务的量子辅助框架。该方法论分为四个不同的阶段：

1. 空间预处理： 将输入数据（起始点、终点和障碍物的 GPS 坐标）转换为通用横轴墨卡托（UTM）坐标，以确保度量精度。障碍物被建模为带有附加安全缓冲区的多边形，以保证预定义的间距。
2. 路径寻找与分段： 将连续环境离散化为结构化网格。构建一个图 $G=(V, E)$，其中节点代表航路点，边代表有效的连接。枚举候选路径，并将总路径根据可用的量子资源（量子比特数量）分割成离散的边。
3. 代价分配： 为每个路径段（边）分配一个代价函数。该函数包括：
   • 欧几里得距离代价。
   • 障碍物惩罚（在靠近安全缓冲区时呈指数级增加）。
   • 用于锚定路径的起始段负偏差。
   • 穿过障碍物的段的高额惩罚。
4. 量子辅助优化： 每个路径段被映射到一个量子比特。QAOA 电路初始化在等叠加态中。算法迭代地应用代价哈密顿量 ($H_C$) 来编码问题约束（惩罚碰撞和低效性）以及混合哈密顿量 ($H_B$) 来探索解空间。经典优化器（Adam）更新变分参数（$\gamma$ 和 $\beta$），以最小化代价哈密顿量的期望值。

核心贡献
论文概述了四项主要贡献：

• 基于 QAOA 的框架： 开发了 QUAV，它将障碍物规避约束直接集成到量子优化过程中。作者指出，据其所知，这是将 QAOA 特别用于无人机轨迹优化的首批应用之一。
• 理论复杂度分析： 证明了在固定优化设置下，QUAV 在电路深度上相对于边数表现出线性缩放（$O(S \cdot |E|)$），这为其与某些最坏情况下的经典指数缩放相比的可行性提供了见解。
• 性能评估： 通过六个场景的广泛模拟，评估了该框架在不同环境约束下生成可行、无碰撞路径的能力。
• 真实硬件实现： 在 IBM 的 ibm_kyiv 量子处理器（QPU）上执行了 QUAV。这验证了该框架针对现实世界硬件约束（包括噪声、退相干和量子比特连通性限制）的鲁棒性。

结果
研究展示了模拟和真实硬件执行的结果：

• 障碍物规避： 在所有六个测试场景中，QUAV 都成功生成了无碰撞路径。虽然由于 QAOA 的概率性质以及安全缓冲区与路径长度之间的权衡，某些路径表现出锯齿状模式，但该算法始终能够避开障碍物。
• 路径效率： 与经典基准相比：
  • A*： 始终生成最短路径（最优），但被指出在高维空间中存在可扩展性问题。
  • RRT： 生成了更长、更具探索性的路径，且方差较高。
  • QUAV： 在路径长度方面通常优于 RRT（例如，场景 5：447.08m 对比 662.88m），但并不总是能达到 A* 的绝对最优性。在场景 3 中，QUAV 生成的路径比 A* 长，但仍显著短于 RRT。
• 硬件性能： 在 ibm_kyiv 后端上的执行表明，尽管噪声会导致代价函数的初始波动，但优化器能够成功收敛到较低代价的解。结果强调了硬件噪声的影响以及误差缓解策略的必要性。

意义与主张
作者将 QUAV 定位为迈向可扩展量子辅助路径规划的务实第一步，而非目前在所有指标上都超越成熟经典方法的解决方案。

• 可行性： 主要主张是验证了使用 QAOA 进行无人机导航的基本可行性。
• 可扩展性： 随着量子硬件的成熟，该框架为大规模、动态环境提供了一个充满希望的方向，并可能对经典方法形成补充。
• 未来展望： 论文指出，虽然完全的量子优势仍处于理论阶段，但将 QAOA 与经典预处理或格罗弗算法（Grover's algorithm）等技术相结合可以提高效率。这项工作强调，随着量子硬件的改进，QUAV 有潜力在特定的复杂优化语境下超越经典方法。