基于改进量子粒子群算法的无人机路径规划

郭蕴华,王晓宗

(武汉理工大学a.船舶动力工程技术交通行业重点实验室;b.能源与动力工程学院,武汉 430063)



基于改进量子粒子群算法的无人机路径规划

郭蕴华,王晓宗

(武汉理工大学a.船舶动力工程技术交通行业重点实验室;b.能源与动力工程学院,武汉 430063)

针对无人机路径规划算法收敛速度慢、易陷入局部最优等问题，提出一种改进的量子粒子群算法。该算法根据粒子与局部吸引点和可行解边界的距离动态的修正粒子更新位置，改善了算法的全局寻优能力和收敛性能。仿真实验表明所提出的改进QPSO算法比其他已有算法可以得到更高质量的航迹，并且其收敛性较好。

无人机;改进量子粒子群算法;最小威胁面;航迹规划

在船舶海洋事业快速发展的今天，利用船用无人机探测即时天气变化将成为一种趋势。由于无人机的续航能力有限，实际应用中往往需要合理的规划其飞行轨迹以节约能耗，因此无人机路径规划也成为目前的研究热点之一。所谓无人机路径规划，就是指综合考虑无人机机动性能、突防概率、碰撞概率和飞行时间等约束条件，寻找从起点到目标点的最优或可行的飞行轨迹[1]。目前用于无人机路径规划的方法大致分为如下几类：①路线图方法，像随机路线图法等[2]；②启发式算法，例如A*算法等[3]；③进化算法，如粒子群优化(particle swarm optimization, PSO)算法[4]、差分进化(Diffrential Evolution, DE)算法[5]、量子粒子群优化(quantum-behaved particle swarm optimization, QPSO)算法[6-7]和具有高斯分布局部吸引点的QPSO(QPSO with gaussian distributed local attractor point, GAQPSO)算法[8]等。相对于其他方法而言，进化算法以航迹代价模型为目标函数，在种群演化过程中逐步获取更好的优化性能，因此可以得到更加合理的飞行路径。不过，PSO、DE、QPSO等进化算法往往也有收敛速度慢、易陷入局部最优等缺点。为此，本文提出了一种基于改进QPSO算法的无人机路径规划方法。该算法根据粒子与局部吸引点和可行解边界的距离动态的修正粒子更新位置，改善了算法的全局寻优能力和收敛性能。通过仿真实验将这种改进QPSO算法与标准QPSO、GAQPSO、PSO和DE等算法进行了比较，实验结果表明，这种新算法可以得到更高质量的航迹，且具有较好的收敛性。

1　航迹代价建模

种群中每一个粒子代表着一条航迹。种群可以用一个矩阵表示，即X= [X1，X2，…,Xm]。式中：m为种群的大小；Xi为第i条航迹。对于二维航迹规划而言，设各航迹除起点和目标点外有n个航迹点，则航迹点位置信息可以表示为Xi=[xi,1,xi,2,…,xi,n,xi,n+1,…,xi,2n]。粒子的维数为2n。

在二维航迹规划中，其代价函数只考虑航迹的长度代价、威胁代价以及水平转角代价等。对于给定的航迹路径Xi来说，其长度代价就可以用从起点到终点的所有路径之和表示[6-7]

(1)

式中：di,0和di,n+1——分别为第i条航迹的起点到第1个节点的距离和最后一个节点到目标点的距离；

j——航迹节点。

航迹的威胁代价按式(2)计算[7]，即

(2)

式中：sk——威胁强度系数；

Jk,j——第k个威胁圈对第j段航迹段的威胁度，按式(3)计算，即

(3)

式中：dk, j——第k个威胁圈到第j段航迹段之间的垂线距离；

Rk——第k个威胁圈的半径；

lk, j——第j段航迹段在第k个威胁圈内的弦长。

此外，航迹还必须满足水平转角约束条件[7]，即

(4)

式中：α——无人机当前的水平转角；

αmax——无人机预设的最大转角。无人机的当前转角可以利用三角函数和向量来求解，记第i条航迹的航迹段j的水平投影为：

(5)

那么它当前的转角α应如下所得[7]。

(6)

式中：‖ai,j‖——矢量ai,j的长度，j= 2,3,…,n-1。

综上，无人机航迹规划的适应度函数应为下式。

(7)

式中：w1、w2、w3——分别为权重系数，必须满足w1+w2+w3=1。

2　改进量子群算法

2.1标准QPSO算法

经典PSO算法的主要缺点是容易陷入局部最优，为此孙俊等[9-10]提出了QPSO算法，以提高全局寻优能力。在QPSO算法中，粒子的状态不再由粒子的位置和速度来描述，取而代之的则是粒子的波函数，通过求解薛定谔方程得到粒子在空间某一点出现的概率密度函数，再通过蒙特卡罗方法求解，可以得到第t次迭代时粒子i的第d维的位置更新方程[9-10]。

(8)

式中：pid(t)——局部吸引点，即

(9)

uid(t),φd(t)为[0,1]之间的随机数；Pid(t)粒子i的第d维的个体最优位置；Gd(t)为种群第d维的全局最优位置。式(8)中的Lid(t)由下式确定。

(10)

式中：参数Cd(t)称为平均最优位置，可由下式计算得到:

(11)

综合可得到其更新方程

(12)

式中：参数α称为压缩-扩张因子，迭代过程中一般在1～0.5之间递减[10]，rnd为[0, 1]上均匀分布的随机数。

2.2改进QPSO算法

在标准QPSO算法中，压缩-扩张因子α一般在1～0.5之间递减(线性递减最常见)，这相当于α只压缩而不扩张。如此操作有其合理性，可以在迭代后期改善局部搜索的精度。不过，假如在迭代过程中发生早熟，则α的递减策略会使粒子很难跳出局部最优点。为了进一步改善算法的全局搜索能力，设计了一种根据粒子与局部吸引点和可行解边界的距离动态的修正粒子更新位置的自适应策略，具体描述如下。

1)如果D

(13)

2)如果D>1，也即粒子越界时，那么其进化方程如下：

(14)

式中：r1～r4——分别为4个在[1,m]上分布的随机整数。

3)若均不属于以上两种情况，则其进化方程应为：

(15)

式中：D——检测距离,

D=|p(t)-x(t)|/|Lupper-Llower|；

Lupper——第k维的上界；

Llower——第k维的下界；

Dmax——检测距离上界；

β——记忆因子，这两个参数与所选目标函数是否有为多峰值有关，具体映射关系如下。

1)如果目标函数可能有较多的峰值，那么则取Dmax=0.05，β=0.75～0.85。

2)如果目标函数为单峰值或较少峰值，则取Dmax=0.02，β=0.50～0.65。

3　仿真及实验结果

在C#编程环境下进行了仿真实验，假定无人机的飞行区域为一个700 m×700 m的正方形区域，包括6个威胁圈，其威胁分布见表1。

表1　威胁分布

起点坐标为(40, 500)，目标点为(600, 300)。种群大小/粒子维度/最大迭代次数依次设为50/10/100。w1～w3的取值分别为0.3、0.4、0.3。对改进QPSO、QPSO、GAQPSO、DE、PSO这5种算法进行了对比实验，每种算法的蒙特卡洛仿真次数为100。

仿真实验结果见图1、图2、表2。

图1　各种算法生成的最优航迹图

图2　平均最优适应度的收敛曲线

算法改进QPSOGAQPSOQPSOPSODE平均最优解282.683350.778312.227389.796370.522

由图1、图2及表2可见，对无人机航迹规划问题，本文提出的改进QPSO算法的收敛速度仅次于GAQPSO算法，但本文算法的全局寻优能力更强，最终其平均最优解要比GAQPSO算法好得多(即可以找到更短的路径，且不会与威胁区有交集，换言之，航迹质量更高)。而对于QPSO、PSO、DE这3种算法，无论是收敛速度(其中以QPSO算法的收敛速度最差)还是全局寻优能力均逊于本文算法。

4　结束语

由于无人机续航能力有限，因此有必要合理地规划无人机路径以降低能耗。本文提出的一种基于改进QPSO的无人机路径规划算法，与标准QPSO算法明显不同之处在于，它可以根据粒子与局部吸引点和可行解边界的距离动态的修正粒子更新位置，增强粒子的扰动特性，提高粒子跳出局部最优的能力，进而提高了种群的全局寻优能力。仿真实验的结果表明，相对于标准QPSO、GAQPSO、PSO、DE等其他几种算法，本文算法能够找到更高质量的最优航迹，且同时成功地避开了威胁区。不过，在几种算法的比较中，本文算法的收敛速度并不是最快的。在下一步的研究工作中，将尝试开发本文算法与其他算法的混合算法，以进一步提高其收敛速度，方便其更易应用于实时环境。

[1] 傅阳光,周成平,丁明跃.基于混合量子粒子群优化算法的三维航迹规划[J].宇航学报,2010,31(12):2657-2664.

[2] 孙汉昌,朱华勇.基于概率地图方法的无人机路径规划研究[J].系统仿真学报,2006,18(11):3050-3054.

[3] 张得舒,黄长强,丁达理,等.基于A*算法的无人机攻击轨迹解算[J].电光与控制,2011,18(3):18-20.

[4] 陈琳,白振兴.应用PSO算法的无人机三维航迹规划[J].电光与控制,2008,15(4):50-53.

[5] 刘波,王凌,金以慧.差分进化算法研究进展[J].控制与决策,2007,22(7):721-729.

[6] FU Y, DING M, ZHOU C. Phase Angle-Encoded and Quantum-Behaved Particle Swarm Optimization Applied to Three-Dimensional Route Planning for UAV[J]. IEEE Transactions on Systems Man & Cybernetics Part A Systems & Human, 2012,42(2):511-526.

[7] FU Y, DING M, ZHOU C, et al. Route Planning for Unmanned Aerial Vehicle (UAV) on the Sea Using Hybrid Differential Evolution and Quantum-Behaved Particle Swarm Optimization[J]. IEEE Transactions on Systems Man & Cybernetics Systems, 2013,43(6):1451-1465.

[8] SUN Jun, FANG Wei, PALADE V, et al. Quantum-behaved Particle Swarm Optimization with Gaussian Distributed Local Attractor Point [J]. Applied Mathematics and Computation, 2011,218:3763-3775.

[9] SUN Jun, XU Wenbo, Feng Bin. A global search strategy of quantum-behaved particle swarm optimization [C]∥IEEE Conference on Cybernetics and Intelligent Systems, 2004(1):111-116.

[10] 方伟,孙俊,谢振平,等.量子粒子群优化算法的收敛性分析及控制参数研究[J].物理学报,2010,59(6):3686-3694.

UAV Path Planning Based on Improved Quantum-behaved Particle Swarm Optimization Algorithm

GUO Yun-hua, WANG Xiao-zong

(a. Key Lab. of Marine Power Engineering & Technology, Ministry of Communications; b. School of Energy and Power Engineering, Wuhan University of Technology, Wuhan 430063,China)

An improved algorithm based on the quantum-behaved particle swarm optimization is proposed for UAV path planning problem. The updated position of the particle is adaptively adjusted by the distance between the particle and the local attractor point and the distance between the particle and the boundary of the feasible region. Simulation results show that the improved QPSO algorithm can get the track with higher quality, and its convergence is better.

UAV; improved QPSO algorithm; minimum face threat; route planning

10.3963/j.issn.1671-7953.2016.01.019

2015-11-19

2015-12-02

国家自然科学基金(51579201)

郭蕴华(1975-)，男,博士，教授

TP24

A

1671-7953(2016)01-0099-04

研究方向:信息融合与工程优化

E-mail:wtugyh@163.com