基于POA算法的无人机航迹规划优化方法
时间：2023-02-19 14:40:06 来源：千叶帆 本文已影响人
贾汉博，马琳，张忠旺
1.哈尔滨工业大学，黑龙江 哈尔滨 150006
2.中国航空无线电电子研究所，上海 200241
随着自动控制以及人工智能领域的蓬勃发展，无人机（UAⅤ）被广泛应用于各种场景之中，如灾难营救、未知环境勘探、远程精确打击目标、针对某一环境的覆盖式探索以及集群对抗[1-3]。UAⅤ的发展可以极大地提高任务效率并避免不必要损失，对于各种领域都具有重大意义。
为了让UAⅤ自主地完成复杂任务，许多学者对UAⅤ航迹规划进行了深入研究。基于群智能优化的航迹规划算法因其扩展性强的特点已成为研究热点。目前常见的群智能优化算法包括蚁群算法（ACO）[4]、差分进化算法（DE）[5]、果蝇优化算法（FOA）[6]和粒子群优化算法（PSO）[7]等。其中，参考文献[8]改进了ACO算法中的信息素分布以及转移概率，实现了复杂障碍环境下的UAⅤ航迹规划。参考文献[9]将DE算法与逼近策略相结合，提出了一种混合差分进化算法，并用于固定翼UAⅤ在复杂三维环境下的航迹规划。参考文献[10]提出了一种基于最优参考点果蝇优化算法，将两个连续航迹点的中点设置为参考点以提高FOA算法的收敛速度。参考文献[11]将综合改进粒子群算法（CⅠPSO）应用于UAⅤ航迹规划。参考文献[11]利用混沌Logistic映射来令算法的初始值更加随机，并提出了一种自适应线性变化策略来调整CⅠPSO 算法中的参数。仿真结果证明了该算法在收敛速度以及航迹规划结果方面的优势，但其采用的地形图过于简单，无法评估在复杂地形下的算法性能。
传教优化算法（POA）是Wei Dong 等[12]于2020 年提出的一种群智能优化算法，该算法结合个体适应度以及位置之间的关系计算权重，以维持个体的多样性，且利用精英策略以及人工免疫算法加速收敛。最终，参考文献[12]通过CEC’17数据集的测试结果说明了该算法在收敛速度以及精度方面的性能。但将POA算法应用于UAⅤ航迹规划时，POA算法中随机初始化传教士位置的方式并没有结合航迹的方向特性，且对于三维坐标以及边界条件的处理仍有一些问题需要解决。
因此，本文提出了基于POA算法的UAⅤ航迹规划优化方法。首先，本文提出了结合航迹长度、地形代价以及飞行高度代价的目标函数。其次，在初始化传教士位置时引入旋转坐标系，通过这种方式使得初始化的航迹结果具有一定的方向性，极大地缩短了算法收敛时间。此外，本文详细说明了航迹坐标点以及边界条件在POA 中的具体处理方式，解决了POA 与航迹规划相结合的问题。最后，本文分别从航迹长度、算法收敛速度以及针对不同地形图的适应程度三个方面对比CⅠPSO航迹规划，证明了基于POA算法的UAⅤ航迹规划的有效性。
1.1 地图限制
对于UAⅤ航迹规划这一优化问题而言，需要考虑多方面的因素。首先，UAⅤ要在地图限制的区域内飞行。其次，为了令UAⅤ安全飞行，UAⅤ不能和地面发生碰撞并与地面保持一定的安全距离，且飞行高度不能超出最大飞行高度的限制。最后，UAⅤ的飞行距离要尽可能短，以节省燃料并尽快到达目的地。
本文利用三维坐标(x,y,z)来表示地形图，其中x与y分别表示地形图在水平面上的横、纵坐标，z表示(x,y)处的地形高度。通过控制z的取值即可生成不同的地形图。为了验证算法在多种地形条件下的性能，本文采用Foxhole Shekel优化问题的数学函数方法生成地形[13]，即
式中，NT表示山峰个数；
ai与bi用于控制山峰位置；
ci用于控制山峰高度。
就UAⅤ的具体航迹而言，若航迹点的总个数为N，其任意的第n个航迹点wn=(xn,yn,zn)应在地图范围内，即
式中，xmin、xmax、ymin、ymax、zmin与zmax分别对应于地图坐标x、y、z的最小值以及最大值。
1.2 目标函数设计
1.2.1 总代价
设计合理的目标函数对于UAⅤ航迹规划这一优化问题至关重要。本文设计的优化目标函数综合考虑了航迹长度、UAⅤ和地形之间的避碰以及UAⅤ飞行高度的限制，该目标函数可以表示为
式中，fL、fT以及fH分别为航迹长度代价、地形代价以及飞行高度代价；
p1、p2以及p3为对应的权重。通过调整权重可以调整优化目标，为了方便，本文采用p1=p2=p3= 1。
1.2.2 航迹长度代价
考虑到UAⅤ的燃料限制，更短的航迹意味着UAⅤ可以在燃料消耗完毕之前完成任务。另外，飞行时间越短，被未知威胁发现的概率同样更低。本文采用参考文献[13]提到的路径长度比率（PLR）来描述航迹长度代价fL，即
fL越小表示航迹长度越短，越有利于飞行任务的完成。且fL这种表示方式并不会因为地图大小或起始点以及终点位置的改变而显著影响航迹长度代价数值，即fL对于不同地形图的适应能力更强。
1.2.3 地形代价
为了实现安全飞行，UAⅤ在整个航行过程中不能与地形发生任何碰撞，且UAⅤ与地面的距离要满足最低安全距离的要求。虽然本文所提航迹规划算法的优化变量为航迹点wn，但UAⅤ在航迹点之间航行时同样要避免同地形发生碰撞，因此本文将相邻航迹点按固定距离d分为Mn份，且为了降低算法复杂度，wn-1与wn之间的坐标wm,n通过线性插值获得。另外，d的取值应综合考虑算法复杂度以及航迹规划结果的精度。那么，本文所提地形代价fT可以表示为
1.2.4 飞行高度代价
受UAⅤ动力学性能的影响，其飞行高度受限，且对于一些特殊的任务类型而言，飞行高度越高，被未知威胁发现的概率就越大。本文提出的飞行高度代价和地形代价类似，即飞行高度代价fH可以表示为
式中，H为UAⅤ最大飞行高度。但和地形代价不同的是，飞行高度的限制往往不十分严格，因此可以通过调整目标函数中飞行高度代价所对应的权重p3来实现优化目标的动态调整，以满足任务需求。
针对UAⅤ的其他性能约束（如最大水平飞行速度、最大旋转角速度、最大上升下降速度等）将在未来的研究中体现。
2.1 POA算法概述
POA 算法受传教行为启发，分为初始化个体位置与目标函数数值计算、影响权重因子计算、向继承人传播知识、文化竞争以及文化发展5个步骤。本文则将POA算法用于UAⅤ航迹规划之中。
POA 算法首先生成p个传教士，初始化其位置并完成目标函数数值的计算。然后归一化其目标函数值即计算影响权重因子faff(i,niter)，i表示第i个传教士，niter表示第niter次迭代。在每个传教士向其对应的in个继承人传播知识时，POA算法结合影响权重因子并根据人工免疫算法实现了可变方差r/3的全局搜索。为了加速算法收敛，POA算法在文化竞争步骤采用精英策略，即选择ein个个体作为精英个体直接成为传教士进入下一步骤。同时为了保持个体的多样性，POA算法基于个体中心位置以及对应的目标函数数值计算了文化竞争步骤中的权重weight(i)，该权重表示了个体与样本中心之间的差别，POA 算法选择差别最大的p-ein个个体作为传教士进入下一步，以维持样本多样性。最终，POA算法通过莱维飞行或高斯分布实现了文化发展，其本质为优化算法中的局部搜索。将上述过程迭代Niter次或达到算法收敛条件即可退出循环。
2.2 航迹点初始化
和其他优化问题不同的是，若航迹规划在算法初始阶段完全通过随机的方式设置UAⅤ的航迹点会显著降低优化算法的优化效率。因此，本文采用了参考文献[14]所提的旋转坐标系来生成初始航迹。旋转坐标系本质上是一种沿xoy平面旋转后的笛卡尔坐标系，为了方便，称之为旋转坐标系。图1给出了旋转坐标系和笛卡尔坐标系之间的关系。
图1中，xyz表示笛卡儿坐标系，x′y′z′表示旋转坐标系，旋转坐标系的x′轴方向为UAⅤ航迹起始点和终点的连线方向，而y′轴方向则与x′轴方向垂直，x′O′y′平面和xoy平面平行，z′轴方向与z轴方向相同，浅色实心点代表航迹点，黑色实心点代表航迹点在x′O′y′平面的投影，旋转坐标系原点o′为航迹起始点，D′点为航迹终点。笛卡儿坐标系内的坐标点(xn,yn,zn)与对应的旋转坐标系坐标点(x′n,y′n,z′n)之间的关系满足
式中，φ为航迹点与旋转坐标系原点连线和旋转坐标系x′轴的夹角，ϕ为旋转坐标系x′轴和笛卡儿坐标系x轴的夹角。
2.3 UAV航迹规划优化方法
在利用POA算法进行UAⅤ航迹规划时，需要利用旋转坐标系生成p组初始航迹以代表p个传教士，loci表示第i个传教士的位置，对应随机生成的第i组航迹点的集合loci={wn|1 ≤n≤N}。将生成的初始值代入式（3）中即可完成目标函数的计算，值得注意的是，虽然在计算地形代价以及飞行高度代价时需要利用线性插值之后的结果，但航迹规划的优化变量仍为N个航迹点wn。
此外，由于航迹点的x、y以及z坐标无特殊的对应关系，因此在利用POA进行后续步骤时应将其作为三个独立的优化变量进行看待，仅在计算目标函数以及对应权重时将三者结合。又由于POA 算法中各步骤均利用高斯分布进行搜索，因此基于POA算法航迹规划的每个步骤的输入以及输出变量应满足关系
经过向继承人传播知识、文化竞争以及文化发展三步之后即完成了一次POA算法的迭代，对应的传教士位置分别记作loc′(i)、loc″(i)以及loc‴(i)，在进行影响权重因子的数值比较后利用loc‴(i)对loc(i)进行更新。最终，整个基于POA算法的UAⅤ航迹规划将在达到最大迭代次数Niter或满足迭代停止条件|fmin(niter)-fmin(niter- 1)|≤τ后停止迭代。fmin(niter)的定义为
式中，f(i,niter)为第niter次迭代中第i个传教士的目标函数值。综上所述，基于POA 算法的UAⅤ航迹规划伪代码如下：
算法1 基于POA算法的UAⅤ航迹规划输入：地形参数、最小安全距离dsafe、最大飞行高度H、线性插值步长d、传教士数量p、迭代次数Niter、继承人个数in以及精英数量ein输出：最优航迹点集合locj ={wn|1 ≤n ≤N}1 根据旋转坐标系生成初始航迹loci；
2 niter = 1，fmin(0) =+inf；
3 while niter ≤Niter do 4 计算faff(i，niter)以及fmin(niter)；
5 if| fmin(niter)- fmin(niter - 1)|≤τ 6 Break；
7 end if 8 结合影响权重因子以及人工免疫算法确定高斯分布方差rx/3、ry/3以及rz/3，并向继承人传播知识生成loc′(i)；
9 边界条件处理；
10 选择ein个精英作为传教士进入下一步，计算其余权重weight(i)并选择剩余p - ein个个体作为传教士，生成loc″(i)；
11 进行文化发展生成loc‴(i)；
12 边界条件处理；
13 比较影响权重因子并对loc(i)进行更新；
14 end while 15 输出最优航迹locj，j = arg min 1 ≤i ≤p {faff(loci)}。
3.1 仿真参数设置
本文将从航迹规划结果、算法收敛速度以及对于不同地形的适应程度三个方面对比本文所提出的基于POA 算法的UAⅤ航迹规划以及基于CⅠPSO[11]航迹规划的性能。其中，地图大小为10km × 10km × 0.5km，式中各个参数服从ai˜U(0,10)、bi˜U(0,10)以及ci˜U(0.2,0.5)（此处设置山峰的最低高度为200m），山峰总数NT= 30，最小安全距离dsafe= 5m，最大飞行高度H= 120m，航迹点个数N= 15，线性插值步长d= 20m。POA算法的参数见表1，CⅠPSO算法的参数见表2。综合考虑到算法收敛速度以及精度，将退出POA 迭代的参数设置为τ= 0.002。航迹起始点坐标为(0,0,0.0827)，航迹终点坐标为(10,10,0.0737)。
表1 POA算法参数Table 1 Parameters setting of POA
表2 CIPSO算法参数Table 2 Parameters setting of CIPSO
3.2 航迹规划仿真结果对比
图2 给出了本文所提算法的航迹规划结果以及基于CⅠPSO航迹规划结果的三维视图以及俯视图。从图2中可以看出，在该地形条件下，本文所提算法成功实现了航迹规划，没有和地形产生任何碰撞并且满足最小安全距离限制以及最大飞行高度限制，航迹总长度为14.3km。而基于CⅠPSO 的航迹规划输出的航迹长度为17.5km，这说明本文所提出的目标函数结合旋转坐标系的初始化方法以及POA算法可以实现在多种限制条件下的航迹规划，且输出航迹长度优于基于CⅠPSO的航迹规划方法。
图3 给出了本文所提算法的收敛过程，所采用的地形图和图2所采用的地形图相同。通过POA算法中收缩系数以及人工免疫算法的加入，并结合精英策略以及文化竞争步骤，本文所提算法在60 次迭代后实现了收敛。此外，旋转坐标系的加入使得POA 算法初始值的目标函数数值明显低于CⅠPSO，且收敛速度以及收敛后的目标函数大小均优于CⅠPSO。
本文同样利用随机生成地形图的方法评估了所提算法对于不同环境的适应能力。图4 给出了在100 个不同地形图情况下本文所提算法航迹规划结果的航迹长度，∞表示航迹不满足地形限制或飞行高度限制。可以看到在地形变化剧烈的情况下，本文所提算法在100 次不同的地形条件下均成功完成UAⅤ航迹规划，而基于CⅠPSO方法的成功率为72%。本文所提算法的平均航迹长度为14.5km，而基于CⅠPSO的航迹规划方法输出的平均航迹长度为16.6km。综上所述，本文所提算法在针对不同地形的稳定性以及输出航迹长度两个方面均优于CⅠPSO。
在解算实时性方面，本文通过在MATLAB平台上的运行时间说明了二者在实际运行速度上的差别。采用的计算机配置见表3，运行时间对比结果见表4。本文所提算法的运行时间为138.37s，CⅠPSO算法的运行时间为149.65s。
表3 计算机参数Table 3 Computer parameters
表4 运行时间对比结果Table 4 Results of running time
下面分析本文所提算法性能优于CⅠPSO 的具体原因。首先，CⅠPSO 在航迹初始化时没有采用旋转坐标系进行初始航迹的生成，而是采用Chaos-based[15]的方法在整个规划空间进行航迹点的初始化。这种做法的确可以提升初始化航迹的随机性，但由于没有结合UAⅤ航迹的方向特性，因此在初始化时其目标函数数值明显高于基于旋转坐标系的生成方法。
此外，CⅠPSO算法为了加快算法收敛速度，在粒子位置更新时将目标函数较小的粒子叠加适当的偏移量替代目标函数较大的粒子，并将目标函数较小粒子的速度直接替换目标函数较大粒子的速度。这种策略的确可以提升收敛速度，但同时降低了样本的多样性。而POA算法为了提升样本的多样性在文化竞争中保留了部分代价函数较大的个体并作为传教士进入下一次迭代。维持样本多样性对于航迹规划而言十分重要，由于地形以及UAⅤ自身限制条件的复杂性，UAⅤ航迹规划将存在多个局部最优，而样本多样性对于跳出局部最优具有重大意义。
本文针对UAⅤ航迹规划问题，将POA 算法用于UAⅤ航迹规划之中。首先，本文提出了结合航迹长度、地形限制以及UAⅤ飞行高度限制的优化目标函数。其次，将旋转坐标系引入POA算法的初始化步骤之中以加快算法收敛，并说明了基于POA算法的UAⅤ航迹规划流程。最后，通过和CⅠPSO算法的仿真对比结果可知，对于同一地形图，本文所提算法规划的航迹长度为14.3km，CⅠPSO 为17.5km，且本文所提算法在60次迭代后实现收敛，初始值的目标函数数值以及收敛速度同样优于CⅠPSO。针对100个不同地形图的仿真结果可知，本文所提算法规划成功率为100%，平均航迹长度为14.5km，而CⅠPSO 成功率为72%，平均航迹长度为16.6km。本文所提算法在计算机平台上的运行时间为138.37s，而CⅠPSO为149.65s。以上对比结果均说明了本文所提基于POA算法的航迹规划优化方法优于CⅠPSO，证明了算法的有效性。
猜你喜欢 飞行高度航迹代价 一种多机协同打击的快速航迹规划方法北京航空航天大学学报(2022年7期)2022-08-06大数据分析的船舶航迹拟合研究舰船科学技术(2022年11期)2022-07-15基于数据挖掘的船舶航迹自动识别系统舰船科学技术(2022年10期)2022-06-17飞行参数对六旋翼植保无人机雾滴在荔枝树冠层沉积分布的影响热带作物学报(2021年1期)2021-02-22一种复杂环境下的多假设分支跟踪方法雷达科学与技术(2020年4期)2020-09-11简析二次雷达高度信息与飞机实际高度的关系科技信息·中旬刊(2018年9期)2018-10-21爱的代价海峡姐妹(2017年12期)2018-01-31数字话迁徙——高度篇少儿科学周刊·少年版(2017年7期)2017-09-29幸灾乐祸的代价语文世界(初中版)(2017年5期)2017-06-22代价作文与考试·初中版(2017年12期)2017-04-19 相关热词搜索：航迹，无人机，算法，
