改进沙猫群优化算法的无人机三维路径规划_贾鹤鸣.pdf

近年来随着科学技术的发展，无人机已广泛应用于农业、电力、通信、影视、气象、勘探、执法、救援和快递等诸多行业.随着无人机面对的工作环境日益复杂，无人机的路径规划就显得尤其重要.关于如何在复杂障碍环境下，快速找到距离更短、安全性更高、无碰撞、能耗更低且更符合无人机运动约束的路径是目前亟待解决的问题之一.目前无人机的路径规划方法主要有 A*搜索算法1、RRT算法2、遗传算法3和速度障碍法4等.A*搜索算法是最直接有效的搜索方法，但只适用于静态环境；基于随机规划方法的RRT算法鲁棒性良好且可以处理多约束条件问题，但算法节点的随机采样性导致该算法得到的路径往往不是最优值；遗传算法通过个体的多次迭代筛选从而得到最佳避障路径，具有较好的鲁棒性和寻优能力，但寻优速度难以控制，运算速度较慢，往往需要大量的时间和运行内存；速度障碍法可以较好地应对障碍环境中运动的障碍物，但计算复杂度较高.本研究为使算法更具实际工程意义，引入新的成本函数，将路径规划转换为一个函数求解问题，包含障碍物威胁、飞行高度等地图约束条件与俯仰角、偏航角等平稳约束条件5,6.总成本函数计算出的适应度值越低，则代表规划出的无人机路径越平稳且安全.沙猫群优化算法(sand cat swarm optimization,SCSO)是2022年提出的元启发式优化算法7，该算法灵感来源于沙猫的捕食行为，沙猫群会通过搜索阶段和捕食阶段获得食物.其中算法额外使用自适应的rG和R以达到搜索阶段和捕食阶段的无缝切换.该算法具有寻优能力强、收敛速度快等特点，但仍存在全局探索能力较弱、算法后期易陷入局部最优等缺点.提高算法性能有多种策略8，如准反向学习策略9可以提高种群多样性，增强算法的搜索空间，因此本文将准反向学习策略引入沙猫群优化算法，形成融合准反向学习策略的沙猫群优化算法(quasi reflection learning sand cat swarm optimization,QRLSCSO)，以增强算法全局搜索能力和跳出局部最优的能力.为验证QRLSCSO算法在实际应用中的有效性，对7种不同的群智能算法在5种不同的障碍模型下进行对比.仿真实验结果表明，QRLSCSO算法比其他算法的避障能力更强，寻优性更好，且在不同的障碍环境中都能够找到最优路径，有效验证了该算法在无人机三维路径规划中的工程实用性.改进沙猫群优化算法的无人机三维路径规划贾鹤鸣，王琢，文昌盛，饶洪华，苏媛媛（三明学院信息工程学院,福建三明365004）摘要：为提高无人机在复杂三维障碍环境中的路径规划效率及准确性,提出一种融合准反向学习策略的沙猫群优化算法.根据实际情况构建适合本场景的数学模型,再通过成本函数将三维路径规划问题转化为目标函数求解问题,同时考虑无人机的安全性、偏航角和俯仰角等相关约束,从而找出最优飞行路径.仿真实验结果表明,在相同障碍环境下进行多次重复实验，沙猫群优化算法只有约40%概率能够寻找到满足相关约束的最优飞行路径，而融合准反向学习策略的沙猫群优化算法能够准确找出最优飞行路径且在不同的障碍环境下也能够高效寻找最优路径.关键词：三维路径规划；沙猫群优化算法；准反向学习策略；障碍环境；飞行安全中图分类号：TP301.6文献标识码：A文章编号：2095-2481（2023）02-0171-09收稿日期：2022-09-29作者简介：贾鹤鸣(1983-),男,教授.E-mail：基金项目：国家级大学生创新创业训练计划项目（202311311019）.第 35 卷第 2 期2023 年 6 月宁德师范学院学报(自然科学版)Journal of Ningde Normal University（Natural Science)Vol.35 No.2Jun.2023DOI:10.15911/ki.35-1311/n.2023.02.005宁德师范学院学报(自然科学版)2023年6月1模型建立让无人机在多障碍的环境中规划出一条安全无碰撞的最佳路径是本文的研究重点，因此选取文献10中的4个成本函数与1个总成本函数以达到研究目的.1.1路径成本无人机三维路径规划需要满足原始地图和障碍区域等条件的限制，为了能够实现无人机的安全飞行,无人机的路径规划需要在一定条件下进行，本文选取文献10中的路径成本函数，其具体公式为F1(Ji)=j=1n-1Pi,jPi,j+1.（1）式中：Ji为无人机的飞行路径，包括n个路径节点Pi,j=(xij,yij,zij)的集合；i表示第i架无人机；j表示该无人机飞行路径的第j个节点；Pi,jO,O为无人机的飞行空间；Pi,jPi,j+1表示两个相邻节点的直线距离.1.2威胁成本无人机三维路径规划除需要最短的路径长度外，还需要无人机在飞行时远离障碍物，以确保无人机的飞行安全，选取文献10中的障碍物威胁成本，其具体图像如图1.设M为所有存在威胁的障碍物集合；障碍物模型为圆柱体，其投影的圆心为Cm；Rm为障碍物的半径；D为无人机的直径.S表示障碍物的危险区域，该值取决于无人机的定位精度与飞行环境.如果无人机处于静态环境中且GPS信号良好，那么S的值可能是几十米；如果环境中存在移动的物体或GPS信号差，那么S的值将超过百米.对于一个路径段Pi,jPi,j+1，其威胁成本与dm的值成反比，威胁代价计算式为|F2(Ji)=j=1n-1m=1MTm(Pi,jPi,j+1).Tm(Pi,jPi,j+1)=|0,if dm S+D+Rm;(S+D+Rm)-dm,if D+Rm 1.（16）3基于QRLSCSO的无人机三维路径规划3.1改进的沙猫群优化算法在原始的沙猫群优化算法中，沙猫会根据食物的位置不断更新自身所在的位置，该算法的开发能力很强但是全局性略显不足，易陷入局部最优.因此文中在平衡机制后引入准反向学习机制，增强算法全局探索能力，避免陷入局部最优.反向学习思想是Tizhoosh于2005年提出的一种优化策略，其原理为根据已知解生成一个反向解，对比反向解，选择更好的解.准反向学习是反向学习的一种变体，由Rahnamayan等9提出，根据反向解生成的准反向解搜索范围更大，更容易找到最优值.准反向学习的公式为CS=(ub+lb)/2.（17）MP=(ub+lb)-Xi,j.（18）Xnew(i,j)=CS+a (MP-CS),if MP CS；CS+a (CS-MP),if MP 1.（23）通过上述QRLSCSO算法的位置更新公式最终可以求得无人机飞行路径的向量集合i，将其转换到空间直角坐标系中得到飞行路径Ji，其中路径Ji中的每个点Pij=(xij,yij,zij)转换公式为xij=xi,j-1+ij sinij cosij；（24）-175宁德师范学院学报(自然科学版)2023年6月yij=yi,j-1+ij sinij sinij；（25）zij=zi,j-1+ij cosij.（26）将转后的Ji代入式(9)中计算适应度值，从而获得优化后的无人机三维路径.基于QRLSCSO的无人机三维路径规划方法的流程图如图5.开始初始化地图，障碍及参数初始化种群更新参数R和获得随机角度|R 1否是通过公式（21）进行探索通过公式（22）进行开发结束输出最优路径是否t T计算路径适应度值进行准反向学习图5基于QRLSCSO的无人机三维路径规划4仿真结果与分析仿真环境：主频为2.50 GHz的11th Gen Intel(R)Core(TM)i7-11700处理器；16 GB内存；操作系统为64位Windows11的电脑上使用MATLAB2021a完成.4.1多种优化算法仿真结果对比在本次实验中，算法的迭代次数Iter=500，个体数量N=50，维度dim=10，无人机的起点和终点分别是start=(100,100,150)；end=(600,600,150).本实验选取了SCSO算法、爬行动物搜索算法(RSA)11、鱼优化算法(ROA)12、鲸鱼优化算法(WOA)13、分组教学优化算法(GTOA)14、哈里斯鹰优化算法(HHO)15、天鹰优化算法(AO)16进行对比试验，其中GTOA无任何参数.对比算法的参数设置见表1.各算法独立运行10次的统计数据见表2.其中，Best表示最佳适应度值；Mean表示平均适应度值，Std表示适应度值标准差.表2中QRLSCSO算法得到了最好的适应度值、平均适应度值和适应度值标准差；SCSO算法得到的最优适应度值与QRLSCSO算法相近，但平均适应度值为Inf，可以看出SCSO算法可能无法找到符合种约束的飞行路径；ROA 得到的最优适应度值与QRLSCSO算法相近，但平均适应度值明显较差，可以看出ROA的稳定性弱于QRLSCSO算法.通过统计数据的分析可知，QRLSCSO算法在无人机三维路径规划中明显优于对比算法，基于QRLSCSO算法的无人机三维路径规划方法拥有较好的鲁棒性.序号123456算法名称RSAROAWOAGTOAHHOAO参数=0.1,=0.005C=0.1b=1=1.5=0.1,=0.1表1对比算法的参数设置-176第2期贾鹤鸣，等：改进沙猫群优化算法的无人机三维路径规划各算法在同一场景中得到无人机飞行路径如图6.通过图6中的立体图可以看出 QRLSCSO 算法和 WOA 求得的飞行路径位于最佳路径区域内，SCSO、RSA、GTOA和AO算法求得的飞行路径都偏移较大，ROA 偏离最远，HHO算法并没有绕开障碍物不符合实际应用；随后通过侧视图，可以看到ROA 算法求得的飞行路径、飞行高度起伏不定，与实际飞行不符；最后通过俯视图与侧视图可以看到QRLSCSO算法得到的飞行路径比较平稳，且能够依据地形调整飞行高度.ymzmxmxmzmyma)立体图b)俯视图c)侧视图图6同一场景下不同优化算法的规划路径各优化算法在同一场景中的适应度值收敛曲线如图7.HHO算法因为无法绕开障碍物适应度值是Inf；RSA和WOA明显无法收敛，未能跳出局部最优；AO算法虽然长期陷入局部最优，但表现出了不错的跳出局部最优的能力，但效果仍然不太理想；QRLSCSO、SCSO、ROA和GTOA算法收敛能力明显较强，而QRLSCSO算法在迭代前期便找到了明显优于其他对比算法的飞行路径.通过对收敛曲线进行分析，QRLSCSO算法通常在迭代60次时就已经达到最优值，而SCSO算法往往需要110次迭代才能达到最优值，改进后的QRLSCSO算法能够更有效减短任务执行时间，求解速度更快.QRLSCSO算法在无人机三维路径规划问题上具有更好的性能.10 0009 0008 0007 0006 0005 0004 0003 0000 050100150200250300350400450500最优值迭代次数图7各优化算法在同一场景中的适应度值收敛曲线算法QRLSCSOSCSORSAROAWOAGTOAHHOAOBest3.651033.711034.121033.731034.461033.861033.861034.57103Mean3.70103Inf4.911034.091035.411034.171034.401035.45103Std53.975 077 45NaN4.741025.071027.111021.521025.961024.88102表2各优化算法的最优值、平均值和方差-177宁德师范学院学报(自然科学版)2023年6月4.2基于QRLSCSO的不同障碍场景规划仿真为了进一步测试 QRLSCSO 算法的性能，在原有地图基础上通过增加障碍物以检验其性能.QRLSCSO算法在 4种不同障碍物场景下求得飞行路径的立体图和俯视图如图 811.仿真结果表明，QRLSCSO算法在多种障碍物模拟场景中均可找到较好的路径.a)立体图b)俯视图a)立体图b)俯视图图8QRLSCSO在障碍物为4的环境中生成的路径图9QRLSCSO在障碍物为5的环境中生成的路径a)立体图b)俯视图a)立体图b)俯视图图10QRLSCSO在障碍物为6的环境中生成的路径图11QRLSCSO在障碍物为7的环境中生成的路径5结语文中提出了一种融合准反向学习策略的沙猫群优化算法，在原SCSO算法中加入准反向学习策略，提高了算法的全局探索能力.针对无人机三维路径规划使用了4种成本函数：路径成本、威胁成本、高度成本和平稳成本，将其相加得到飞行路径的总成本函数.先通过对比其他优化算法，探究该算法路径规划的实际性能，随后使用变更障碍物数量的方法来模拟实际飞行的不同环境，从而验证该算法的工程实用性.当前对于无人机三维路径规划的研究仅是单无人机的航迹规划，并不能较好地解决实际航迹规划问题，今后将对多无人机三维路径规划展开相应的研究.参考文献：1 SZCZERBA R J,GALKOWSKI P.Robust algorithm for real-time route planning J.IEEE Transactions on Aerospace&Electronic Systems,2000,36(3):869-878.2 路引,郭昱津,王道波.基于RRT算法的某型无人机航路在线规划设计 J.兵器装备工程学报,2016,37(12):4.3 XUE Y.Mobile robot path planning with a non-dominated sorting genetic algorithm J.Applied Sciences,2018,8(11):2253.4 代进进,李相民,薄宁,等.基于模型预测控制的无人机避障路径规划方法 J.火力与指挥控制,2020,45(1):6.5 贾鹤鸣,姜子超,李瑶.基于改进秃鹰搜索算法的同步优化特征选择 J.控制与决策,2022,37(2)：445-454.6 贾鹤鸣,姜子超,李瑶,等.基于改进斑点鬣狗优化算法的同步优化特征选择 J.计算机应用,2021,41(5):1290-1298.7 SEYYEDABBASI A,KIANI F.Sand Cat swarm optimization:A nature-inspired algorithm to solve global optimization problems J.Engineering with Computers,2022:1-25.-178第2期贾鹤鸣，等：改进沙猫群优化算法的无人机三维路径规划8 贾鹤鸣,刘宇翔,刘庆鑫,等.融合随机反向学习的黏菌与算术混合优化算法 J.计算机科学与探索,2022,16(5):1182-1192.9 RAHNAMAYAN S,TIZHOOSH H R,SALAMA M.Quasi-oppositional differential evolution C.2007 IEEE Congress on Evolutionary Computation,2007:2229-2236.10 PHUNG M D,HA Q P.Safety-enhanced UAV path planning with spherical vector-based particle swarm optimization J.Applied Soft Computing,2021,107:107376.11 ABUALIGA H L,ELAZIZ M A,SUMARI P,et al.Reptile search algorithm(RSA):A nature-inspired meta-heuristic optimizer J.Expert Systems with Applications(S0957-4174),2021,191(11):116158.12 JIA H M,PENG X H,LANG C B.Remora optimization algorithm J.Expert Systems With Applications(S0957-4174),2021,185(9):15665.13 MIRJALILI S,LEWIS A.The whale optimization algorithm J.Advances in Engineering Software,2016,95:51-67.14 ZHANG Y Y,JIN Z G.Group teaching optimization algorithm:A novel metaheuristic method for solving global optimizationproblems J.Expert Systems With Applications(S0957-4174),2020:148.15 AAHA B,SM C,HF D,et al.Harris hawks optimization:Algorithm and applications J.Future Generation Computer Systems,2019,97:849-872.16 ABUALIGAH L,YOUSRI D,ELAZIZ M A,et al.Aquila optimizer:A novel meta-heuristic optimization algorithm J.Computer&Industrial Engineering,2021,157:107250.UAV 3D path planning based on improved sand cat swarmoptimization algorithmJIA He-ming,WANG Zhuo,WEN Chang-sheng,RAO Hong-hua,SU Yuan-yuan(Department of Information Engineering,Sanming University,Sanming,Fujian 365004,China)Abstract:In order to improve the efficiency and accuracy of path planning of unmanned aerial vehicles in complex three-dimensional obstacle environment,this paper proposes a quasi-reflection learning Sand Cat SwarmOptimization(QRLSCSO)optimization algorithm that integrates quasi-reverse learning strategies.At the sametime,we consider the relevant constraints such as the safety,yaw angle and pitch angle of the UAV to find theoptimal flight path.The simulation results show that the SCSO algorithm can find the optimal flight path satisfying the relevant constraints only with a probability of about 40%after repeated experiments in the same obstacle environment,while the QRLSCSO algorithm can find the optimal flight path accurately and efficiently indifferent obstacle environments.Key words:3D path planning;sand cat swarm optimization algorithm;quasi-reverse learning strategies;barrier environment;flight safety责任编辑郭涓-179