基于改进元胞蚁群算法的无人机路径规划_余稼洋.pdf

引用格式:余稼洋，郭建胜，张晓丰，等 基于改进元胞蚁群算法的无人机路径规划J 电光与控制，2023，30(7):46-50 YU J Y,GUO JS,ZHANG X F,et al UAV path planning based on improved cellular ant colony algorithm J Electronics Optics Control,2023,30(7):46-50基于改进元胞蚁群算法的无人机路径规划余稼洋，郭建胜，张晓丰，解涛，周楚涵，刘纳川(空军工程大学，西安710000)摘要:针对传统方法在解决复杂环境下无人机路径规划问题中仿真时长不一致、易陷入局部最优等问题，在栅格化地图的基础上，提出了改进元胞蚁群算法。首先，为统一仿真时间步长，采用六边形栅格地图对飞行空域进行建模;然后，提出一种改进元胞蚁群算法进行路径规划，算法引入势场概念对启发函数进行修正、采用差别搜索策略以引导蚁群快速向目标搜索，并设计一种自适应信息素更新方式以选出优质路线。实验结果表明，所提模型和算法解决了矩形栅格地图中仿真时长不统一的问题，并有效提升了路径寻优速度和全局搜索能力，避免算法陷入局部最优。关键词:无人机路径规划;元胞蚁群算法;六边形栅格中图分类号:V249文献标志码:Adoi:10 3969/j issn 1671 637X 2023 07 008UAV Path Planning Based on Improved CellularAnt Colony AlgorithmYU Jiayang,GUO Jiansheng,ZHANG Xiaofeng,XIE Tao,ZHOU Chuhan,LIU Nachuan(Air Force Engineering University,Xi an 710000,China)Abstract:Aiming at the problems that traditional methods are inconsistent in simulation time and easy tofall into local optimization in solving UAV path planning problems in complex environment,an improvedcellular ant colony algorithm is proposed on the basis of grid map Firstly,in order to unify the simulationtime step,the hexagonal grid map is used to model the flight space;Then,an improved cellular ant colonyalgorithm is proposed for path planning The algorithm introduces the concept of potential field to modify theheuristic function,adopts the differential search strategy to guide the ant colony to search for the targetquickly,and designs an adaptive pheromone update method to select the optimal route The experimentalresults show that the model and algorithm proposed in this paper solve the problem of non-uniform simulationtime in rectangular grid map,effectively improve the speed of path optimization and global search ability,andavoid the algorithm falling into local optimizationKey words:UAV path planning;cellular ant colony algorithm;hexagonal grid0引言无人机随其技术的发展而被广泛用于各领域，在军事领域的应用尤为突出。无人机路径规划问题是一个复杂的多目标优化问题，规划出合理的飞行路径是确保无人机安全、高效完成任务的重要保证。目前，路径规划问题的求解方法主要有基于图论的方法 1、基于势场的方法2、基于随机采样的方法3、基于启发信息的方法 4 及群智能算法5 6，其中，群智能类算法优势较为明显，并有相关学者开展了大量研究。文收稿日期:2022-06-06修回日期:2022-06-28作者简介:余稼洋(1999)，男，浙江天台人，硕士生。献 7 将人工鱼群算法融合蚁群算法，并引入了混沌映射改进信息素更新方式，提高了蚁群算法的全局搜索能力;文献 8提出了一种融合人工势场的蚁群算法，解决了蚁群算法收敛慢、易陷入局部最优的问题;文献 9 11基于灰狼算法，运用 A*算法、变异策略等初始化方法，并设计了新的收敛因子和位置更新策略，有效提高了算法求解精度和收敛速度;文献 12在蚁群算法的基础上引入独狼视场机制，解决了蚂蚁寻优中路径停滞问题，有效避免了算法陷入局部最优。以上文献虽取得一定的效果，但仍存在以下几点问题:一是路径规划模型仅仅以距离作为目标函数，未考虑雷达、电磁干扰等给无人机带来的威胁，影响了模型的真实性;二是采用矩形栅格对空域进行划分，未能解决Vol 30No 7July 2023第 30 卷第 7 期2023 年 7 月电光与控制Electronics Optics Control余稼洋等:基于改进元胞蚁群算法的无人机路径规划仿真时间步长不一致的问题;三是在寻优过程中未根本性改善算法的寻优机制。例如，混沌理论本身存在不确定性，在复杂环境中仍可能使算法陷入局部最优以及算法未考虑全局性和局部性等。针对上述问题，本文以路径长度和无人机所受威胁程度作为目标函数，采用六边形栅格地图对空域进行建模，设计一种改进元胞蚁群算法进行求解，实现了无人机路径规划优化及快速收敛。1基于六边形栅格的无人机路径规划建模无人机路径规划问题是指在综合考虑地形、电磁干扰及雷达威胁等因素的前提下，规划出符合无人机机动性能约束并使综合代价最小的飞行路径。在传统路径规划问题求解中，一般使用矩形栅格地图对飞行空域进行建模，并采用 Moore 型邻域描述无人机的转移状态，即 M=C1，C2，C8，其中，Ci 0，1。Ci=1，表示邻域元胞 i 被选中，黑色元胞是不可达元胞，表示边界或障碍物;白色元胞是自由元胞，表示无人机可正常通行，如图1(a)所示。图 1栅格示意图Fig 1Grid diagram矩形栅格地图降低了环境建模的复杂度，但在相邻元胞转换时存在时间步长不一致等问题，影响了模型的真实性。假定栅格长为 h，则按照 Moore 型邻域选择下一元胞时，元胞在横纵向和斜向移动距离分别为h 和2h，如图 1(b)所示。当元胞以匀速 v(标量)移动时，则元胞在一次移动中的时间可能为 h/v 或2h/v，导致了时间步长不一致，影响了模型的真实性。故本文提出一种六边形栅格地图(见图 1(c)，栅格长为 h时，元胞移动距离为3h，移动时间为3h/v，有效解决了时间步长不一致问题。六边形栅格地图构建如下。以地图左下角为原点建立笛卡尔坐标系，以栅格内切圆圆心作为中心点，中心点坐标(x，y)与栅格编号之间的对应关系为x=2 5h+3h(j 1)mod(i，2)=0h+3h(j 1)mod(i，2)=1(1)y=05 3h i(2)式中，i和 j分别为栅格的行、列号。在求解无人机航路规划问题前，需确定优化问题的性能指标，本文采用罚函数法将约束方程转化到目标代价函数中，即F=k1f+k2C(3)式中:C 为无人机航程;f 分别为威胁代价函数，包含了无人机飞行中的雷达威胁和电磁干扰威胁等，单位飞行路径 si的威胁代价 服从不确定分布 si();k1和 k2为对应的惩罚系数。显然，式(3)模型中的优化目标为不确定变量，由于不确定变量之间无法比较大小，故需先将其转化为确定型模型。期望值是不确定变量的重要统计特征，LIU13 以最小化目标函数的期望值为准则，构建了期望值模型以解决不确定规划问题。故目标函数可转换为E(F)=k1E(f)+k2C。(4)2改进元胞蚁群算法2 1传统元胞蚁群算法元胞蚁群算法可由(Tm n，Im n，Cw，C，CN，C，O)表示。其中，Tm n为栅格地图的信息矩阵;Im n为信息素矩阵;Cw为元胞空间，w 为元胞空间维度，这里取 2;C=0，1，是元胞状态，表示当前元胞是否被占用，C=1，表示元胞被占用;CN为元胞邻域，一般采用 Moore 型;C为元胞转移规则，是蚁群移动的约束条件，包含以下 3点:1)所选元胞不能是边界和障碍物;2)所选元胞要有利于找到目标元胞;3)元胞的转移概率取决于概率转移算式，即pkij(t)=ij(t)ij(t)rCkir(t)ir(t)j Ck0其他(5)式中:Ck为 Moore 邻域元胞的集合;ij(t)和 ij(t)=1/dij，分别为元胞 i，j 间信息素值和启发式值，反映了元胞 j 对蚂蚁的吸引程度，dij为元胞间的欧氏距离;和 分别为信息素启发因子和期望启发因子，反映了ij(t)和 ij(t)的重要程度。信息素更新策略 O 采用全局更新策略，具体算式为ij(t+1)=(1 )ij(t)+ij(t)(6)ij(t)=Q/Lk蚂蚁经过该路径0其他(7)74第 7 期式中:为信息素挥发因子;ij(t)为本次循环中元胞i，j 间的信息素增量;Q 为信息素强度系数;Lk为本次蚂蚁所走路径长度。相较于传统蚁群算法，元胞蚁群算法的性能有一定优势，但仍存在以下问题:1)算法效率有待提升;2)易陷入局部最优，甚至会出现图 2 所示的死锁现象，导致无法获得可行解。因此，本文对启发函数和信息素更新方式进行优化并引入差别搜索策略以解决上述问题。图 2死锁现象示意图Fig 2Deadlock diagram2 2算法改进2 2 1基于势场的启发函数传统蚁群算法将两元胞间距离的倒数作为启发函数，以此反映邻域元胞被选择的期望程度，但六边形栅格中任意两元胞间的距离值相等，故原启发函数失效，无法有效引导算法寻优。本文引入势场概念，势场值反映了邻域元胞与目标元胞的距离，距离越小，势场值越大，符合算法对启发函数的要求。此外，无人机飞行中的大幅度转弯行为会增加安全隐患，故将转弯代价B 加入启发函数中，以减少无人机的转弯次数 T，减小转弯角度。综上，启发函数算式为cost(B)=T+(8)ij=1d3jE+cost(B)(9)式中:和 分别为转弯次数和角度的代价系数;djE为邻域元胞到目标元胞的距离。通过引入势场，能够有效增强蚁群算法的搜索效率，减少无人机急转弯的次数，提高了全局寻优能力和飞行的安全性。2 2 2差别搜索策略中心线是指起点与终点两点连线。一般而言，某条路径离中心线越近，其成为最短路径的概率越大。故可以根据当前路径到中心线的距离确定下一步选择该路径权重。引入差别搜索后，转移概率为pkij(t)=ij(t)ij(t)ij(t)rCkir(t)ir(t)j Ck0其他(10)式中，ij(t)为 t 时刻路径与中心线距离 d 远近取不同的值，服从 N(0，1)的正态分布。通过引入差别搜索可以提高蚁群搜索的效率。2 2 3自适应信息素更新策略信息素更新方式主要有全局更新和实时更新。有研究表明，采用全局更新方式搜索效率较高，但易陷入局部最优;采用实时更新方式容易发现高质量解，但算法搜索效率低14。为此，本文将两种方式融合到一起，提出一种新的自适应更新策略，具体表达式为ij(t+1)=(1 )ij(t)+1Qf(spbest)+2Qf(sgbest)(11)式中:spbest为当前最优路径;sgbest为全局最优路径。在搜索前期，1较大，使信息素更新更依赖当前迭代最优路径，有利于发现更多优质解，避免算法陷入局部最优;在搜索后期，2较大，采用全局最优蚂蚁进行信息素更新，使算法快速收敛。3仿真实验为说明本文所提六边形栅格模型及改进元胞蚁群算法在解决路径规划问题上的有效性，本文在路径规划问题上进行实例仿真验证，实验总体分为以下两个:1)分别采用矩形栅格和六边形栅格对 20 20 规模的路径规划问题进行建模，使用元胞蚁群算法验证两种栅格模型的优劣性;2)首先在 20 20 规模问题上验证改进蚁群算法中各参数对算法性能的影响，然后运用本文所提算法与传统的元胞蚁群算法在不同规模问题上进行实例仿真，分析本文所提算法的优劣性。实验采用的软件平台为 Matlab 2019a。3 1不同栅格路径规划结果分析为说明本文所提六边形栅格模型在解决路径规划问题上的有效性，分别使用矩形栅格和六边形栅格对20 20 规模的路径规划问题进行建模，使用元胞蚁群算法进行求解，实验结果如图 3 所示。图 3不同栅格地图仿真结果图Fig 3Simulation results of different grid maps由图3 可知，矩形栅格和六边形栅格均能实现路径规划。在面对 U 型陷阱时，前者规划得到的路径无法有效避开，而后者能够有效避开;此外，前者规划得到的路径中有10 次转弯，而后者为6 次，减少了转弯次数，说明了六边形栅格在解决路径规划问题上的有效性。84第 30 卷电光与控制余稼洋等:基于改进元胞蚁群算法的无人机路径规划3 2不同算法路径规划结果分析3 2 1算法参数分析为验证信息素启发因子、期望启发因子、信息素挥发因子 对算法性能的影响，本文在 20 20 规模路径规划问题中对所提算法进行仿真实验，记录最优路径的迭代次数和最小代价。实验结果如图 4 所示。图 4不同参数对算法性能影响结果Fig 4Effect of different parameters onalgorithm performance由图 4 可知，当 1，2，5，8，0 3，0 6 时，算法能够找到最优路径且收敛速度较快，此时算法具有较好的性能。此外，文献 15指出，当蚁群数量为自由元胞数量的 1/6 时，算法性能较好。结合上述分析，本文算法参数设置见表 1。表 1算法参数设置Table 1Setting of algorithm parameters参数规模数值20 20 30 301520 20 30 30720 20 30 3003Q20 20 30 30120 20 30 3005参数规模数值蚂蚁数量20 2055蚂蚁数量30 30115迭代次数20 20 30 3010020 20 30 30053 2 2路径规划结果分析将本文算法与元胞蚁群算法分别在 20 20(小规模)和 30 30(大规模)路径规划问题上进行对比实验，以检验算法性能，路径规划结果如图 5 所示。如图 5(a)所示，在小规模问题中，两种算法找到的路径代价相差不大，但是本文算法求解得到的路径要略优于元胞蚁群算法得到的路径;图 5(b)中，随着问题规模增大以及复杂障碍的出现，本文算法求解得到的路径结果明显优于元胞蚁群算法，后者会陷入局部最优，甚至出现如图 5(c)所示的死锁现象，即无法成功规划出可行的路径。图 5不同规模地图中各算法的路径规划结果Fig 5Path planning results on different scale maps从仿真结果来看，环境较为简单时，两种算法的差异并不明显，随着环境的复杂性增加，本文算法性能明显优于元胞蚁群算法。一方面，本文算法利用了新的信息素更新机制，综合考虑当前路径和历史最优路径，有效提高了算法寻优精度;另一方面，本文算法引入差别搜索策略和势场概念，提高了算法的搜索速度。此外，算法的启发函数还考虑了转弯代价，确保了无人机飞行过程中的安全性。为进一步说明本文算法优势，分别从算法的稳定性和收敛性进行详细分析。3 2 3稳定性分析为验证算法稳定性，采用元胞蚁群算法和本文算法对不同规模的路径规划问题进行求解。每种算法独立运行30 次，最大迭代次数为100，实验结果如表2 所示。表 2各算法在不同规模问题中路径规划结果Table 2The path planning results of each algorithmin different scale problems规模算法均值方差最佳路线次数路径转弯次数20 20元胞蚁群算法4671310786本文算法4254030430 30元胞蚁群算法8827 12937112本文算法7621084266由表 2 可知，本文算法求解得到路径的代价均值及方差均小于元胞蚁群算法，且元胞蚁群算法基本陷入了局部最优，而本文算法能够跳出局部最优，找到最优路径。以 20 20 规模为例，本文算法代价的均值比传统算法降低了 8 93%，且其均找到了最优路径，而传统算法基本陷入了局部最优。此外，本文算法搜索得到的路径转弯次数要少于元胞蚁群算法，有效提升了无人机在飞行过程中的安全性。94第 7 期3 2 4收敛性分析为验证算法收敛性能，让2 种算法在不同规模地图中分别迭代100 次，参数设置同上，收敛曲线见图6。图 6各算法在不同规模地图中的收敛曲线Fig 6Convergence curves of each algorithm indifferent scale maps由图6 可知，两种算法在迭代前期呈现震荡趋势，但大体上为下降趋势，路径代价均能收敛到一个稳定值。一方面，本文算法相对于元胞蚁群算法迭代次数更少，能够以更快的速度收敛，这是因为其引入差别搜索策略，使得蚁群在较优位置上具有更高的信息素水平，加速算法搜索;另一方面，本文算法相对于元胞蚁群算法收敛的值更小，在 20 20 和 30 30 规模问题上最优路径代价分别为 44 53 和 73 98，而元胞蚁群算法求解的路径代价分别为4853，8595，其解的质量有所提高。4结束语本文研究无人机路径规划问题，主要得到以下结论:1)提出一种六边形栅格模型，有效解决了传统矩形栅格模型时间步长不一致等问题;2)目标函数综合考虑了路径距离和战场环境中的威胁，确保规划得到的路径足够安全，使模型更加贴近战场实际;3)设计了一种改进元胞蚁群算法，在原有算法的基础上引入差别搜索策略及基于势场的启发函数提高算法的搜索效率，利用自适应信息更新策略提高算法求解精度，并通过仿真实验证明了本文算法的优越性。由于引入差别搜索策略以及自适应信息素更新机制，在一定程度上提高了算法的时间复杂度，后续将对算法的性能进一步优化，缩短算法的搜索时间。参 考 文 献 1 BAUMANN M,LONAD S,COFT E A,et al Path plan-ning for improved visibility using a probabilistic road map J IEEE Transactions on obotics,2010,26(1):195-200 2 MASOUD A A Decentralized self-organizing potential field-based control for individually motivated mobile agents in acluttered environment:a vector-harmonic potential field ap-proachJ IEEE Transactions on Systems,Man,and Cy-bernetics,Part A,Systems and Humans,2007,37(3):372-390 3 熊佳新 基于滚动优化的多无人机航迹规划与协调算法研究 D 哈尔滨:哈尔滨工业大学，2017 4 SZCZEBA J,GALKOWSKI P,GLICKTEIN I S,et alobust algorithm for real-time route planningJ IEEETransactions on Aerospace and Electronic Systems,2000,36(3):869-878 5 CAO Y,WEI W Y,BAI Y,et al Multi-base multi-UAV coop-erative reconnaissance path planning with genetic algorithm J Cluster Computing,2019,22(S3):5175-5184 6 LIU Y,ZHANG X J,ZHANG Y,et al Collision free 4D pathplanning for multiple UAVs based on spatial refined votingmechanism and PSO approach J Chinese Journal of Aero-nautics,2019,32(6):1504-1519 7 马铭希，吴军，岳龙飞，等 基于改进人工鱼群优化的蚁群算法无人机自主航路规划J 兵器装备工程学报，2022，43(3):257-265 8 孔维立，王峰，周平华，等 改进蚁群算法的无人机三维路径规划 J 电光与控制，2023，30(3):63-69 9 许乐，赵文龙 基于新型灰狼优化算法的无人机航迹规划 J 电子测量技术，2022，45(5):55-61 10 曹建秋，张广吉，徐鹏 A*初始化的变异灰狼优化的无人机路径规划J 计算机工程与应用，2022，58(4):275-282 11 柳长安，王晓鹏，刘春阳，等 基于改进灰狼优化算法的无人机三维航迹规划J 华中科技大学学报，2017，45(10):38-42 12 张毅，权浩，文家富 基于独狼蚁群混合算法的移动机器人路径规划方法J 华中科技大学学报，2020，48(1):127-132 13 LIU B D Uncertainty theory M 2nd ed Berlin:Spring-er,2007:9-103 14 陈迎欣 基于改进蚁群算法的车辆路径优化问题研究 J 计算机应用研究，2012，29(6):2031-2034 15 杜玉红，张岩，赵焕峰 基于参数优化蚁群算法的机器人路径规划研究 J 现代制造工程，2020(9):7-1405第 30 卷电光与控制