基于改进粒子群算法的无人机航迹规划

杜云　刘冰　邵士凯　彭瑜

摘 要：针对当前基本粒子群算法无人机航迹规划在后期收敛速度比较慢、效率不高、易陷入局部最优等问题，提出一种改进粒子群算法。首先，在迭代前期和后期分段设置惯性权值的调整，实现粒子惯性和寻优行为的平衡;其次，设置一个定值与相邻2次适应度函数最优值比较策略，防止陷入局部最优;最后，引入遗传算法的交叉、变异机制，得出更优的结果。并通过仿真验证了改进粒子群算法在三维空间航迹规划的有效性和可行性。结果表明，与其他航迹规划算法相比，新算法具有路径长度更短、耗时更少、路径更平滑等优点，加快了收敛速度，提高了航迹规划效率和稳定性。因此，改进算法的航迹规划可得到满足约束关系的最优航迹，对实现自主飞行有重要的参考价值。

关键词：计算机仿真;无人机;航迹规划;粒子群算法;惯性权值;遗传算法

中图分类号：TP29   文献标志码：A

Abstract：Aiming at the problems of slow convergence， low efficiency and easy to fall into local optimum for the UAV flight path planning of basic particle swarm optimization， an improved method is provided. Firstly， the adjustment of the inertia weight is set in the early and late stages of the iteration to achieve the balance between particle inertia and optimization behavior. Secondly， a comparison strategy is set between the fixed value and the adjacent two fitness function optimal values to prevent falling into local optimum. Finally， the crossover and mutation mechanism of the genetic algorithm is introduced to get better results. The effectiveness and feasibility of the improved particle swarm optimization algorithm in 3D space track planning are verified by simulation results. Compared with other track planning algorithms， it has the advantages of shorter path length， less time-consuming， smoother path， etc.， which accelerates the convergence speed and improves the overall efficiency and stability. The flight path planning based on the improved algorithm can obtain the optimal flight path satisfying the constraint relation， which has important reference value for realizing autonomous flight.

Keywords：computer simulation; UAV; track planning; particle swarm optimization; inertia weight; genetic algorithm

现今社会科技进步日新月异，无人机开始大量投入使用。对无人机的任务航迹进行有效并且合理的规划，需要综合考虑无人机本身的性能、最远飞行距离以及油耗、地形和气象威胁等等。在这些限制条件下，需要找出飞行地域范围内起始点与目标点之间的最优航迹，从而高效地完成指定的作战任务并保证自身安全。对无人机任务航迹进行规划的主旨是进行多约束的目标优化，以找出无人机最优或次优路线。在无人机航迹规划过程中，面对的威胁有很大的不可测性，地形环境复杂多变，且要面對未知的天气因素。因此航迹规划的条件多且模糊性较大[1]，不仅要考虑这些因素自身特有的控制方式，还要考虑各因素之间存在的强耦合关系，这就大大增加了航迹规划的难度。国内外学者们提出了许多关于航迹规划的算法，如神经网络[2]，退火算法[3]、遗传算法[4]、蚁群算法[5]等。但是由于无人机航迹规划空间复杂，约束条件多，模糊性较大，导致传统航迹搜索算法寻优能力不足、计算量大，航迹规划在最优性以及实时性两方面亟待提高。粒子群算法优点明显，能够在处理一些优化问题时取得相对更优结果，但存在后期收敛速度过慢，容易陷入局部最优的情况[6]。本文对粒子群算法进行改进，并结合改进后的算法对无人机航迹进行规划。

图8为遗传算法迭代收敛曲线，可看出遗传算法迭代初期和后期收敛速度较慢，中期收敛速度虽然加快，但迭代结束后没有达到收敛，最终代价较高。图9为标准粒子群算法迭代收敛曲线，可看出标准粒子群算法前期收敛速度较快，但后期收敛速度明显变慢，最终代价为132，表明规划结果可能陷入了局部最优。图10为改进粒子群算法迭代收敛曲线，从图中明显看出收敛速度优于遗传算法和标准粒子群算法，并在第80次迭代达到最优，代价为128，表明设计的改进算法加快了收敛速度，提升了解的最优性。

4 结 语

针对现有无人机航迹规划算法存在过早收敛和易陷入局部最优的缺点，提出了一种基于改进粒子群算法的无人机航迹规划方法。通过调整粒子群算法中的惯性权重，控制参数，并引入遗传算法交叉、变异思想，提高搜索无人机航迹最优性，大大加强了算法稳定性。无人机航迹规划仿真结果表明，改进粒子群算法收敛到最优解的有效性高，且相比遗传算法和标准粒子群算法得出的路径更加平缓，路径更短。利用设计的改进算法虽然可得到最优航迹，但在实时性方面仍有很大的提升空间，在下一步工作中，将把无人机在线航迹规划作为研究重点，并将通过无人机实际飞行对规划方案进行验证。

参考文献/References：

[1] 简康. 无人机航迹规划算法研究[D]. 西安：西安电子科技大学， 2014.

IAN Kang. A Study of UAV Path Planning Algorithms[D]. Xi’an： Xidian University，2014.

[2] 徐卓. 基于神经网络算法的无人机航迹规划研究[D]. 石家庄：河北科技大学，2016.

XU Zhuo. Research on UAV Path Planning Based on Neural Networks[D]. Shijiazhuang：ebei University of Science and Technology，2016.

[3] 王强， 张安， 吴忠杰. 改进人工势场法与模拟退火算法的无人机航路规划. 火力与指挥控制， 2014，39（8）：70-73.

WANG Qiang， ZANG An， WU Zhongjie.UCAV path planning based on improved artificial potential field and simulated annealing. Fire Control & Command Control， 2014，39（8）：70-73.

[4] 张鑫源， 胡晓敏， 林盈. 遗传算法和粒子群优化算法的性能对比分析. 计算机科学与探索， 2014， 8（1）：90-102.

ZANG Xinyuan，U Xiaomin，LIN Ying. Comparisons of genetic algorithm and particle swarm optimization. ournal of Frontiers of Computer Science and Technology， 2014， 8（1）：90-102.

[5] 吴学礼， 贾云聪， 张建华，等. 一种改进蚁群算法的无人机避险方法仿真研究. 河北科技大学学报， 2018，39（2）：166-175.

WU Xueli， IA Yuncong， ZANG ianhua， et al. Simulation study of UAV conflict resolution based on an improved ant colony algorithm. ournal of ebei University of Science and Technology， 2018，39（2）：166-175.

[6] LI ianping. Improved quantum-behaved particle swarm optimization. Open ournal of Applied Sciences，2015 （5）：240-250.

[7] 瞿博阳，刘丁明，乔百豪，等.粒子群算法及其改进研究.自动化应用，2016（11）：49-51.

[8] 朱收涛， 曹林平， 翁兴伟，等.采用改进粒子群算法的无人机协同航迹规划. 电光与控制， 2012，19（12）：29-33.

ZU Shoutao，CAO Linping，WENG Xingwei， et al. Cooperative path planning for UCAVs based on improved PSO algorithm. Electronics Optics & Control， 2012，19（12）：29-33.

[9] 傅阳光. 粒子群优化算法的改进及其在航迹规划中的应用研究[D]. 武汉：华中科技大学， 2011.

FU Yangguang. Research on Modified Particle Swarm Optimization and Their Application in Route Planning for UAV[D]. Wuhan：uazhong University of Science and Technology，2011.

[10]陈攀峰， 刘文军， 王为. 基于粒子群算法的无人机航迹规划. 电子设计工程， 2013， 21（22）：36-39.

CEN Panfeng，LIU Wenjun，WANG Wei. Route planning of UAV based on particle swarm optimization （PSO） algorithm . Electronic Design Engineering， 2013， 21（22）：36-39.

[11]KENNEDY ， EBERART R C. Particle swarm optimization[C]//IEEE International Conlerence on Neural Networks.[S.l.]：[s.n.]，1995： 1942-1948.

[12]高明君， 张国义， 高家一，等.基于粒子群优化的网络动态可靠性分析. 计算机测量与控制， 2015， 23（1）：307-309.

GAO Mingjun， ZANG Guoyi，GAO iayi， et al. Time-variant reliability analysis for network based on PSO. Computer Measurement & Control， 2015， 23（1）：307-309.

[13]方群， 徐青. 基于改進粒子群算法的无人机三维航迹规划. 西北工业大学学报， 2017， 35（1）：66-73.

FANG Qun，XU Qing. 3D route planning for UAV based on improved PSO algorithm. ournal of Northwestern Polytechnical University， 2017， 35（1）：66-73.

[14]熊军华， 谢飞. 基于混沌理论和杂交策略改进的粒子群优化算法. 信息技术与信息化， 2017（10）：55-57.

[15]周璐， 李军华. 一种满足方向约束的动态航迹规划方法. 计算机应用研究， 2018， 35（7）：1982-1985.

ZOU Lu， LI unhua. Dynamic route planning method based on directional constraints. Application Research of Computers， 2018， 35（7）： 1982-1985.