Abstract:

In recent years, with the development of Unmanned Aerial Vehicle (UAV) technology and its widespread application in military, logistics, agriculture, and other fields, the problem of UAV swarm trajectory planning has received extensive attention. Traditional optimization algorithms such as simulated annealing, genetic algorithms, and particle swarm optimization can achieve good results in some cases. However, when dealing with larger and more complex UAV swarm tasks, they often face issues such as low computational efficiency and getting stuck in local optima. Quantum annealing, which has the unique advantage of quantum tunneling, can effectively avoid local optima. Therefore, this study proposes a UAV swarm trajectory planning algorithm based on quantum annealing. The trajectory planning problem is converted into a Quadratic Unconstrained Binary Optimization (QUBO) problem. Using a two-stage processing strategy, the quantum annealing method clusters the task points and simulates the trajectory for each category, effectively reducing time complexity. Results show that quantum annealing has a higher probability of finding better paths than simulated annealing, demonstrating a better ability to escape the local optima problem. Additionally, the study considers four common scenarios that UAV swarms encounter during missions, designs corresponding dynamic task allocation schemes and modifies the objective function and constraints of quantum annealing. Results indicate that the UAV swarm trajectory planning algorithm can handle common scenarios effectively, ensuring that the UAV swarm can flexibly respond and efficiently complete tasks collaboratively.

Key words: Unmanned Aerial Vehicle (UAV) swarm, trajectory planning, quantum annealing, quantum tunneling, time complexity

摘要：

近年来, 随着无人机(UAV)技术的发展及其在军事、物流、农业等领域的广泛应用, 无人机群航迹规划问题受到了广泛关注。传统的优化算法, 如模拟退火、遗传算法和粒子群优化算法等虽然在某些情况下能够取得不错的效果, 但在面对更大规模、更复杂的无人机群任务时, 容易遇到计算效率低、陷入局部最优解等问题。量子退火算法凭借其独特的量子隧穿优势可以有效避免陷入局部最优解。提出基于量子退火的无人机群航迹规划算法, 将航迹规划问题转换成二次无约束二值优化(QUBO)问题, 通过两阶段处理策略, 利用量子退火方法对任务点聚类并对每一类别的航迹进行模拟求解, 有效降低了时间复杂度。研究结果表明量子退火相较于模拟退火有更大的概率求解出更优的航程, 因此量子退火具有更好地跳出局部最优解的能力。此外针对无人机群在执行任务时可能面临的4种常见的应用场景, 设计了相应的动态任务分配方案并对量子退火的目标函数和约束进行修改, 研究结果表明, 该无人机群航迹规划算法可以很好地应对常见的应用场景, 保证无人机群能够灵活应对并协同高效完成任务。

关键词: 无人机群, 航迹规划, 量子退火, 量子隧穿, 时间复杂度