基于改进PSO算法的无人机城域三维路径规划

黄 晋, 李云飞, 王圣淳, 刘厚荣

(中国民用航空飞行学院,四川 广汉 618000)

0 引言

近年来无人机技术日新月异,得益于体积小、机动性强等优势,无人机被广泛运用于农林植保、线路巡检、遥感勘测等领域[1]。随着城市地面交通压力的增加,物流无人机逐渐兴起[2],改善了“最后一公里”的物流运输问题[3]。国内外学者对于物流无人机航路网络的构建进行了大量研究,中国民用航空局也颁布了城市场景轻小型无人驾驶航空器物流航线划设规范[4]。合理的航路网络能够有效保障飞行任务的秩序,但是在面临一些特殊情况,如战时侦察、压制、进攻[5]等,需要将无人机快速部署到现场,此时应规划出一条尽可能高效的路径。

使用传统算法规划无人机三维路径时,往往因为过程复杂而效果不佳,而群智能算法可以在较短的时间内找到可行的解决方案[6]。粒子群优化(Particle Swarm Optimization,PSO)算法具有收敛快、易实现等优点。国内外学者在使用PSO算法进行三维路径规划的同时,也对其进行了大量改进。文献[7]提出了基于ε贪心策略的PSO算法,使算法收敛速度和搜索精度都有所提升;文献[8]通过引入基于高斯分布的粒子变异方式改善了算法易陷入局部最优解的缺陷;文献[9]将PSO算法与遗传算法(Genetic Algorithm,GA)相结合,有效提高了多无人机搜索任务的路径效率和针对性。

为解决三维路径规划中PSO算法收敛精度低和易停滞的缺点[10],本文对PSO算法做出以下改进:首先,使用均匀化级联Logistics映射初始化粒子位置;其次,为了改善前后期的搜索步长,使用了自适应参数机制;最后,设计了加速度因子和自适应调整系数,对粒子速度和位置更新公式进行优化,并通过仿真验证该算法相较传统PSO算法效果更佳。

1 改进粒子群优化(IPSO)算法

1.1 粒子群算法概述

PSO算法是一种群智能优化算法,通过模拟动物寻找食物的行为初始化一群粒子,再对其进行迭代。在迭代过程中通过跟踪两个最优值并根据

(1)

X(t+1)=X(t)+v(t+1)

(2)

更新粒子的速度和位置。其中:i为粒子数;d为粒子的维度;t为迭代次数;w为惯性权重;c1,c2分别为个体、社会学习因子;r1,r2为(0,1)之间随机数;pbest为粒子个体最优位置;gbest为全局最优位置。

1.2 IPSO算法设计

传统的PSO算法虽然有鲁棒性较强、参数较少、易收敛等优点,但仍然存在一些问题[11]:1) 未对粒子的初始位置进行调整,合理的初始位置有利于增强搜索的多样性,提高算法性能;2) 粒子的运动随着迭代的进行会逐渐趋同,导致算法陷入局部最优解。

针对传统算法的缺陷,本文通过以下方式进行改进。

1.2.1 粒子初始位置优化

Logistics映射也叫作虫口模型[6],是一种经典的混沌映射,数学表达式为

Li+1=μLi(1-Li)

(3)

式中:Li∈(0,1);μ∈[0,4],当μ=4时,序列为满映射。但是Logistics映射分布还不够均匀,遗漏范围较多。因此,本文在初始化粒子位置时,引入在此基础上改进的均匀化级联Logistics映射[12],均匀化级联Logistics映射在[0,1]上均匀分布,改善了种群初始位置的随机性,有益于提高搜寻的便利性。其表达式为

(4)

X(0)=a+(b-a)S′i

(5)

其中:X(0)为初代粒子初始位置;a,b为搜索上下界,与粒子取值范围有关。粒子进行初始化时首先通过式(4)得到均匀化级联混沌序列[S′i],再根据式(5)进行线性变换获得每个粒子的初始位置。

1.2.2 自适应参数优化

在对PSO算法的优化研究中,对于惯性权重w经常采用线性减小的优化方式。线性变化的方式在迭代过程的前期效果一般,并且随着搜索次数的增加,惯性因子骤然下降会导致算法容易陷入局部最优解[13]。因此,本文使用惯性权重分段自适应变化方式,使得算法在进行全局搜索时使用大惯性权重,在局部搜索时使用小惯性权重以提升精准度。具体算式为

(6)

式中:F为算法适应度函数;Favg为算法适应度函数平均值;Fmin为算法适应度函数最小值;wmax,wmin分别为惯性权重最大值和最小值。

在迭代前期,通常希望粒子有较强的个体学习能力;后期则要求粒子有较强的社会学习能力。因此对学习因子使用指数函数进行变化,相对于线性变化,指数函数的上升速率更高,可能会提升算法的收敛速度。具体算式为

(7)

(8)

其中:t为当前迭代次数;tmax为最大迭代次数;c1为个体学习因子;c2为社会学习因子。

1.2.3 针对陷入局部极值的优化

当粒子的适应度连续3次都大于粒子群的平均适应度时,可以认为粒子出现陷入局部极值的趋势[14],导致结果并非最优规划。因此本文引入了加速度概念,对处于较差区域的粒子赋予一个加速度,使其较快地离开适应度较差的区域。加速度因子为

(9)

式中:Fi(t+1)为第i个粒子在第t+1次迭代周期的适应度值;Fmax(t)为t代粒子的最优适应度值;Favg(t)为粒子群第t次迭代周期的平均适应度值。

改进后赋予加速度因子的粒子速度更新为

(10)

1.2.4 粒子位置更新算法的改进

在粒子迭代的初期,为了尽可能地搜索出至目标点的路径,应该具有较大的步长,随着迭代次数的增加,待搜寻的解空间逐渐缩小,为了避免错过最优解,此时粒子的搜索步长也应适当减小。根据以上原理,使用基于反正切函数的自适应调整系数φ对粒子位置更新进行优化,φ的算式为

(11)

并增加(0,1)的随机搜索因子以改善粒子搜索的随机性。优化后的位置更新算式为

X(t+1)=rand(0,1)·φ·[X(t)+v(t+1)]。

(12)

1.3 算法流程

改进后的粒子群算法流程具体如下。

1) 根据均匀化级联Logistics映射初始化粒子群,包括种群数量、迭代次数、粒子的初始位置及其余各项参数。

2) 根据目标函数计算出粒子在解空间内的适应度值,更新个体和全局最优并保存。

3) 根据适应度计算并选择惯性权重,更新学习因子。

4) 使用更新后的参数结合式(9)～(10)更新符合条件粒子的速度,根据式(12)求得新位置,并计算适应度值,更新粒子个体最优和全局最优。

5) 重复上述步骤,直至符合循环终止条件,输出最优值。

1.4 IPSO算法验证

为测试改进后的算法性能,本文选取4种标准测试函数进行验证,具体测试函数见表1。同时,将使用灰狼优化(GWO)算法、传统PSO算法以及SPSO算法(自适应参数调整的PSO算法)[15]进行对比。3种算法的种群数量统一为150,迭代次数统一为1000。各算法在同一测试函数上独立求解30次,计算各算法30次实验结果得到的最优值(Best)、平均值(Mean)和方差(Std)。PSO算法中学习因子c1=c2=1.2,权重w=0.8,实验环境为内存16 GiB,锐龙R5800H,Windows 11操作系统。

表1 测试函数Table 1 Test functions

各算法寻优结果见表2,适应度函数曲线见图1。

图1 不同算法的适应度函数曲线Fig.1 Fitness function curves of different algorithms

表2 各算法寻优结果Table 2 Optimization results of each algorithm

表中:f1和f2为单峰函数,用于检测算法的寻优精度;f3和f4为多峰函数,存在许多局部极小值,可以检验算法跳出局部最优解的能力和全局搜索性能。在f1和f2函数中,仅有IPSO算法达到了全局最优解,在f3和f4函数中,SPSO算法采用了自适应参数调整,因此相较传统PSO算法更容易避免早熟,在此基础上加以改进的IPSO算法得到了质量最高的解。综合以上内容可看出,IPSO算法表现出了更高的精度和稳定性,更快的收敛速度,由此证明了该算法改进的合理性。

2 路径规划问题建模

2.1 环境建模

本文使用栅格法对城市静态环境进行建模,以研究城域内路径规划。传统栅格法建模通常对每个单元格进行0/1赋值,即根据该栅格是否可以通行分别赋值为0或1。在进行路径规划时,通常将存在障碍物的栅格赋值为1,不可通行;而赋值为0的栅格可以作为扩展路径。这种赋值方式较为单一,忽略了有些位置虽然可以通过,但依然存在着一定的风险[16]。

本文使用栅格法对城市空间进行建模后,将存在障碍物的栅格赋值为1,不会被扩展为路径点,其余栅格存在危险度差异,引入二维栅格i危险度di=No/Ns,以提高飞行路径的安全性。其中,No为栅格i周围障碍物数量,Ns为栅格i周围栅格总数。图2为栅格法规划空间示意图。

图2 栅格法规划空间示意图Fig.2 Schematic diagram of the raster method for space planning

2.2 约束条件

2.2.1 飞行高度约束

考虑执行飞行任务时的安全性及相关空域规定,无人机飞行高度应加以限制,即

Hmin≤zi≤Hmax

(13)

式中:Hmin为最低飞行高度;Hmax为最高飞行高度。

2.2.2 偏航角度约束

无人机在执行任务时水平方向会发生改变,其水平方向偏航角度应在自身允许的最大范围内,即

(14)

f1=(xi-xi-1)(xi+1-xi)+(yi-yi-1)(yi+1-yi)

(15)

(16)

2.2.3 俯仰角度约束

无人机在执行任务时会产生俯仰运动,其俯仰角度应在自身允许的最大范围内,即

(17)

2.3 代价函数设计

对航空器使用群智能算法进行航迹规划时,代价函数是用来评价航迹质量的重要指标,也是体现算法性能的重要依据。本文将从以下3个方面设置代价函数。

2.3.1 威胁代价

障碍物是航迹规划中必须考虑的因素,航空器与障碍物之间的距离将直接决定规划得到的航迹是否可行。威胁代价F1可表示为

(18)

式中,di为第i个航迹点的危险度。

2.3.2 航程代价

无人机在执行任务过程中,自身能源有限,因此航程需要有所限制,设途经路径点坐标Ci为(xi,yi,zi),航程代价函数为

(19)

2.3.3 无人机高度代价

频繁地调整飞行高度不仅会增加能源消耗,而且也不利于飞行的安全,因此希望无人机在飞行过程中尽可能保持平稳。高度代价函数为

(20)

式中:M为航空器总质量;g为重力加速度值;Δz为前后两个航迹点的高度差。

综上,目标函数F为

minF=α1F1+α2F2+α3F3

(21)

式中,α1,α2,α3为权重系数,并且满足α1+α2+α3=1。

3 仿真实验

在构建的城市空间内进行无人机路径规划实验,部分参数设置参考了文献[17],如表3所示。

表3 参数设置Table 3 Model simulation parameters

将PSO,IPSO,SPSO和GWO算法基于上述参数,在简单和复杂环境下进行仿真,结果分别如图3和图4所示,单个栅格边长为10 m,4种算法规划出的路径均能够顺利到达目标点,但IPSO算法规划的路径相较于其余算法更加平滑,转弯次数较少,航程也更短。显然IPSO算法得到的路径质量更优。

图3 简单环境下仿真Fig.3 Simulation in a simple environment

图4 复杂环境下仿真Fig.4 Simulation in complex environment

各算法不同环境下适应度函数对比曲线如图5所示,可见,IPSO算法在空间较为复杂的环境下适应度函数值和收敛速度方面仍然优于其余3种算法。因此,本文所提IPSO算法在无人机航路规划领域具有可行性与有效性。

图5 不同环境下适应度函数曲线Fig.5 Fitness function curves in different environments

4 结束语

针对无人机在城市执行任务时的飞行环境,建立了基于飞行安全、性能约束等条件的城市无人机路径规划模型。结合PSO算法在寻优过程中搜寻精度低、易陷入局部最优的缺陷,提出了一种改进PSO算法。在部分测试函数上对所提算法进行了对比测试,并进行了仿真实验,结果表明,使用改进的均匀化级联Logistics映射可以提高种群初始多样性,引入分段自适应惯性权重和指数变化学习因子动态地平衡了算法的全局搜索能力与局部搜索能力,增加的加速度因子改善了粒子摆脱局部极值的性能。改进后的算法在搜寻能力和稳定性上都有较好的提升,在路径规划问题中具有一定的可行性。