基于改进PSO混合算法的无人机三维路径规划研究.pdf

第3 6卷 第3期2023 年08月 青 岛 大 学 学 报(自 然 科 学 版)J O U R N A L O F Q I N G D A O U N I V E R S I T Y(N a t u r a l S c i e n c e E d i t i o n)V o l.3 6 N o.3A u g.2023 文章编号:1 0 0 6 1 0 3 7(2 0 2 3)0 3 0 0 5 7 0 7d o i:1 0.3 9 6 9/j.i s s n.1 0 0 6 1 0 3 7.2 0 2 3.0 3.1 0基于改进P S O混合算法的无人机三维路径规划研究唐文倩,徐海芹,刘 洋(东华大学信息科学与技术学院,上海 2 0 1 6 2 0)摘要:针对在无人机路径规划中粒子群算法(P a r t i c l e S w a r m O p t i m i z a t i o n,P S O)容易过早收敛的问题,提出了一种改进粒子群混合优化算法(I m p r o v e d P a r t i c l e S w a r m O p t i m i z a-t i o n,I P S O)。I P S O算法在考虑路径长度代价、高度代价、碰撞代价以及转弯角与爬升角代价的基础上构建适应度函数,将粒子群算法与遗传算法以及和声搜索算法相结合,同时引入引力搜索算法中的加速度思想,设置动态更新的学习因子与凹函数模型的动态惯性权重。仿真结果表明,对比传统的方法,I P S O算法在路径长度,收敛速度,平均消耗时间以及稳定性等方面都具有显著的优势。关键词:无人机;三维路径规划;粒子群混合优化算法;适应度函数中图分类号:T P 3 0 1.6 文献标志码:A收稿日期:2 0 2 2-1 2-1 5基金项目:国家自然科学基金(批准号:6 2 2 4 1 5 0 3)资助;上海市自然科学基金面上项目(批准号:2 2 Z R 1 4 0 1 4 0 0)资助。通信作者:徐海芹,女,博士,副教授,主要研究方向为智能计算、网络优化、无人机路径规划。E-m a i l:x u h a i q i n d h u.e d u.c n 随着社会逐渐往智能化的方向发展,无人机现已被广泛应用在空中巡检、农药喷洒、环境监测等方面,在复杂环境执行任务前,无人机飞行路径规划成为了必要的前提。粒子群优化(P a r t i c l e S w a r m O p t i m i z a t i o n,P S O)算法凭借其需要调整的参数少,实现简单等优势被广泛用于解决路径规划、轨迹优化1等问题,但其容易过早收敛,陷入局部最优。针对该算法的不足之处,许多学者对其进行了不同的改进,有研究通过算法糅合的方式帮助其跳出局部最优,如将P S O算法与人工势场法2、随机路径图法3、k-m e a n s聚类算法4、遗传算法5等相结合对其改进。也有研究从P S O算法的速度更新公式6-1 0及算法参数1 1-1 2着手进行改进,在不同程度上提升了算法的空间搜索能力,有效解决了算法容易早熟收敛等缺点;还有文献使用P S O算法对多个任务点进行路径规划1 3。以上各种改进策略虽然从不同角度对P S O算法作出了改善,但是P S O算法在性能方面依旧具有很大的改进潜力。为此,本文提出一种改进的粒子群优化算法(I m p r o v e d P a r t i c l e S w a r m O p t i m i z a t i o n,I P S O),将P S O算法与遗传算法(G e n e t i c A l g o r i t h m,GA)以及和声搜索(H a r m o n i c S e a r c h,H S)算法相结合,引入引力搜索算法中的加速度思想1 4,及动态学习因子和基于凹函数模型的动态惯性权重,使其能够在不同搜索时期进行动态更新;当判断出粒子陷入局部极值无法跳出时,通过引入随机数进行扰动,帮助其跳出局部最优,并将I P S O算法与传统的P S O、GA、P S O与GA的结合算法1 5(P a r t i c l e S w a r m O p t i m i z a t i o n-G e n e t i c A l g o r i t h m,P S O-GA)以及细菌觅食遗传粒子群混合算法1 6(B a c t e r i a l F o r a g i n g O p t i m i z a t i o n-G e n e t i c A l g o r i t h m-P a r t i c l e S w a r m O p t i m i z a t i o n,B F O-GA-P S O)进行对比,验证了I P S O算法的优越性。1 无人机三维路径规划模型1.1 环境建模无人机航迹规划前,首先进行环境建模,为了模拟无人机飞行的实际场景,本文采用山峰函数作为无人机飞行的基本地形,三维建模时使用圆柱体模仿无人机飞行时遇到的树木、房屋之类的威胁物体。山峰函数青 岛 大 学 学 报(自 然 科 学 版)第3 6卷为Z x,y =Cm=1hme x p-x-xo mxs m 2-y-yo mxs m 2 (1)其中,hm表示第m座山峰的高度,C表示生成山峰的数量,xo m,yo m 与xs m,ys m 分别表示为第m座山峰的中心坐标和坡度。1.2 适应度函数为了简化无人机适应度函数的建立,通常假设无人机在同一高度飞行,将其转换到二维环境中规划路径。但是无人机的实际飞行环境是三维地理环境,因此在构建代价函数时,考虑航迹长度代价、高度代价、碰撞代价、转弯角与爬升角代价,则适应度函数为F=f1+f2+f3+f4(2)其中,F表示航迹代价,f1为航迹长度的代价值,f2为高度发生变化时产生的代价值,f3为无人机与障碍物发生碰撞时产生的代价值,f4为转弯角与爬升角产生的代价值。1.2.1 航迹长度代价 航迹飞行长度是影响无人机飞行时产生能耗的重要指标之一,路径长度越短,无人机消耗的能量越少。P S O算法中的一个粒子则可以规划出一条可行的航迹线,每个粒子规划出的一条航迹线由N个航迹点组成,则一条航迹线的组成为Pi1,Pi2,Pi3,Pi N ,i表示当中的一个粒子,Pi j为该粒子中的 一 个 航 迹 点,位 置 坐 标 为Xi j,Yi j,Zi j ,那 么 该 粒 子 的 下 一 个 航 迹 点 为Pi j+1,坐 标 位 置 为Xi j+1,Yi j+1,Zi j+1 ,这两个航迹点之间的距离为Pi jPi j+1,则该路径长度代价函数f1为f1=N-1j=1Pi jPi j+1(3)1.2.2 高度代价 无人机需要调整飞行高度以防止在飞行过程中碰到障碍物,但是频繁调整无人机的飞行高度导致能量消耗较大,所以引入高度代价约束使无人机尽量在同一高度飞行。设无人机飞行的最高高度为hm a x,最低高度为hm i n,则高度代价f2为f2=hi j-hm a x+hm i n 2 hm i nhi jhm a x o t h e r w i s e (4)1.2.3 碰撞代价 当无人机所在高度低于山峰和圆柱体的高度,且航迹上的点到圆柱体中心的距离小于圆柱体半径Ri时,则会出现碰撞,设航迹点到圆柱体中心的距离为dd i s t,则碰撞的代价函数f3为f3=dd i s tRi(5)其中,为一个较大的值,相当于一个惩罚系数。当无人机到障碍物的距离小于圆柱体半径时,则对代价函数进行惩罚,增大碰撞代价,否则碰撞代价为0。1.2.4 转弯角与爬升角代价 转弯角和爬升角在规划无人机路径时起着很重要的作用1 7,假设无人机此时的航迹点为Pi,j+1,所在的高度为zi,j+1,前后相邻点为Pi j和Pi,j+2,所在的高度分别为zi j、zi,j+2,Pi jPi,j+1和Pi,j+1Pi,j+2在水平面上的投影为P i jP i,j+1和P i,j+1P i,j+2,转弯角的计算公式为i j=a r c t a nP i jP i,j+1P i,j+1P i,j+2P i jP i,j+1P i,j+1P i,j+2(6)爬升角为i j=a r c t a nzi,j+1-zi jp i jp i,j+1(7)转弯角与爬升角代价为f4=a1n-2j=1i j+a2n-1j=1i j-i,j-1(8)其中,1和2分别表示转弯角与爬升角的惩罚系数。85 第3期 唐文倩等:基于改进P S O混合算法的无人机三维路径规划研究2 基于改进P S O算法的U A V三维路径规划2.1 传统粒子群算法粒子群算法主要是通过鸟群觅食的行为找到全局最优解1 8,最终粒子会参考个体历史最优位置Pib e s t和全体最优位置Pgb e s t不断更新自身的速度和位置。假设粒子的速度向量为V1i,V2i,V3i,Vdi ,粒子的位置向量为P1i,P2i,P3i,Pdi ,其中Vdi=Vd xi,Vd yi,Vd zi ,Pdi=Pd xi,Pd yi,Pd zi 。粒子的更新公式为Vi(t+1)=Vi(t)+c1r1(Pib e s t-Pi(t)+c2r2(Pgb e s t-Pi(t)Pi(t+1)=Pi(t)+Vi(t+1)(9)其中,为惯性权重,r1,r2为0到1之间的随机数,c1,c2分别表示粒子的个体学习因子和社会学习因子,t为迭代次数。2.2 I P S O算法参数设置为了平衡粒子的全局和局部探索能力,需动态设置惯性权重系数,惯性权重越大,全局探索能力越强,传统的粒子群算法常采用线性递减策略更新惯性权重,本文采用一种凹函数模型的动态惯性权重,惯性权重的更新公式为(t)=m a x-m i n 2 e x p-Ti t e rN(m a x-m i n)2 (1 0)其中,m a x为惯性权重最大值,m i n为惯性权重最小值,与惯性权重类似,学习因子的值也应随着迭代的次数而发生动态变化,动态更新公式为c1=1-Ti t e rNl n 2(1 1)c2=1+Ti t e rNl n 2(1 2)其中,Ti t e r为当前迭代次数,N表示总迭代次数。2.3 结合遗传算法与和声算法针对粒子群算法得到的粒子,首先通过轮盘赌法执行GA中的选择操作,在满足交叉概率的条件下将得到的个体进行交叉操作,即对任意两个粒子随机选择两组相同数量的航迹点,交换其位置坐标。同时对满足变异概率条件的粒子进行变异操作,即使用随机数替换该粒子随机选择的一个航迹点的位置坐标。重新计算每个粒子的适应度值,判断经过交叉变异操作后的粒子的适应度值,若比该粒子的个体最佳值更小1 9,则更新该粒子的个体最佳值,否则不更新。H S算法2 0通过生成随机数,并比较与记忆库取值概率HMC R以及微调概率P A R的大小,调整和声变量得到一个新的和声,比较新和声是否比最劣值要优,若是,则用新和声代替其最劣值,以此不断更新和声记忆库,直到达到迭代次数为止。本文将各粒子的历史最优值组成和声记忆库,根据H S算法原理不断更新记忆库,直到达到H S算法设定的终止条件。完成迭代后,判断和声记忆库中最优和声的适应度值,若优于全局最优值,则更新全局最优值,否则不更新。2.4 引入加速度引力搜索算法是基于万有引力定律提出的,其中任意一个粒子受到其他粒子的引力和,由此计算出粒子在d维空间产生的加速度adi(t)adi(t)=Fdi(t)Mi i(t)(1 3)其中,Fdi(t)表示该粒子在d维空间受到的合力大小,Mi i(t)表示第i个粒子的惯性重力大小,t表示迭代次数,将引力搜索算法中的加速度思想引入到P S O算法中,此时粒子的速度和位置更新公式为Vi(t+1)=bVi(t)+c1r1(Pib e s t-Pi(t)+c2r2(rgPgb e s t-Pi(t)+c3r3(Pkb e s t-Pit )+aPi(t+1)=Pi(t)+Vi(t+1)(1 4)95青 岛 大 学 学 报(自 然 科 学 版)第3 6卷其中,b表示压缩因子,a表示粒子的加速度,c3表示在dPc时,粒子的速度更新与除自身之外的其他任意第k个粒子的历史最优位置有关,d和r1,r2,r3表示0到1之间随机生成的数,这里Pc=0.3,Pib e s t为第i个粒子的历史最优位置,Pgb e s t为全体最优位置,Pkb e s t表示除了第i个粒子外的任一粒子的历史最优位置,当不满足dPc时,粒子的速度与位置的更新公式为 Vi(t+1)=bVi(t)+c1r1(Pib e s t-Pi(t)+c2r2(rgPgb e s t-Pi(t)+aPi(t+1)=Pi(t)+Vi(t+1)(1 5)综上所述,I P S O算法实现无人机航迹规划的步骤如下:S t e p 1 利用式(1)进行三维环境建模,并设置无人机飞行的起点与终点;S t e p 2 初始化参数以及粒子的速度与位置,评估适应度值,得到初始全局与个体最优位置,利用式(1 3)初始化各粒子的加速度;S t e p 3 由式(1 4)或式(1 5)更新粒子的速度以及位置,判断粒子是否飞出了设定的三维环境范围,若是则取边界值;S t e p 4 对粒子采取GA中的选择、交叉及变异操作,重新计算其适应度值,若经过交叉变异之后的粒子的位置比该粒子的历史最优位置更优,则更新该粒子的历史最优位置Pib e s t,否则不更新,同时比较此时粒子群当中是否存在比全局最佳位置更好的粒子,若存在则更新全局最优位置Pgb e s t,否则不更新;S t e p 5 重新计算各粒子的加速度值,并将各粒子的历史最优值组成和声记忆库,不断迭代产生新的和声向量,淘汰适应度值最劣的粒子,最终得到新的和声记忆库,通过适应度值判断此时和声记忆库中最优粒子的适应度值是否比全局最优值更小,若是则对全局最优值进行更新,否则不更新;S t e p 6 由式(1 0)(1 2)更新惯性权重和学习因子c1和c2;S t e p 7 更新粒子群全局最优适应度值后,判断全局最优值是否连续5代的差值小于0.0 1,若是则判定其陷入了局部最优,此时将式(1 4)的rg设置为0到1之间的随机数,对其进行一定的扰动,跳出局部最优;不断重复s t e p 36,直到达到设定的最大迭代次数。3 仿真实验及结果分析为了验证I P S O算法的有效性,实验所用平台为M a t l a b R 2 0 2 0 a,设置建模任务空间为1 0 01 0 01 0 0,起始点(0,0,0),终点(9 0,8 0,6 0),将I P S O算法分别与传统P S O、GA、P S O-GA算法以及B F O-GA-P S O算法进行比较。3.1 简单环境下I P S O算法高效性分析设置中间航迹处理点为5,对P S O、GA、P S O-GA、B F O-GA-P S O算法以及I P S O算法分别规划航迹并平滑处理。设置迭代次数为5 0次,统计各算法迭代5 0次后的适应度值大小,数据见表1,三维航迹俯视图如图1所示,迭代5 0次后的适应度值曲线如图2所示。表1 简单环境下迭代5 0次的适应度值大小算法P S OGAP S O-GAB F O-GA-P S OI P S O适应度值3 6 1.5 84 0 8.3 31 9 9.4 71 5 5.6 71 4 6.3 8由表1和图1可知,I P S O算法在简单环境下规划的路径近似于一条直线,最终的适应度值为1 4 6.3 8,与其他4种算法相比适应度值最小。从图2可以看出,I P S O算法在1 0代左右基本收敛到一个较优的适应度值,说明I P S O算法能够比较快速的收敛。B F O-GA-P S O算法由于引入了细菌觅食与遗传算法,在一定程度上帮助粒子跳出了局部最优,所以最终的适应度值达到了1 5 5.6 7,仅次于I P S O算法。而其他3种算法在不同程度上陷入了局部最优。GA的适应度值一直较差,迭代到5 0次时适应度值为4 0 8.3 3。而P S O尽管后期适应度值缓慢下降,但是已然陷入了局部最优,迭代到5 0次时适应度值为3 6 1.5 8,相比I P S O算法的1 4 6.3 8的适应度值明显大了许多,从图1中的三维俯视图也能看出其规划的路径质量较差。虽然P S O-GA规划的路径较前两种算法有所改进,但适应度值仍比I P S O算法的大许多,依旧在某种程度上陷入了局部最优。由此,I P S O算法在简单环境下的路径长度较其他4种算法具有显著的优势,收敛速度较快。06 第3期 唐文倩等:基于改进P S O混合算法的无人机三维路径规划研究图1 简单环境下三维航迹俯视图 图2 简单环境下迭代5 0次仿真适应度值曲线图3.2 复杂环境下I P S O算法高效性分析表 2 复杂环境下迭代5 0次的适应度值大小算法P S OGAP S O-GAB F O-GA-P S OI P S O适应度值4 6 9.0 53 6 8.8 51 8 9.5 91 5 8.5 21 4 9.9 2 为了进一步验证I P S O算法的有效性,加大环境的复杂度,增加山峰和圆柱体的个数。设置迭代次数为5 0次,表2统计了各算法迭代5 0次后的适应度值大小,三维航迹俯视图和迭代5 0次后的适应度值曲线如图3和图4所示。图3 复杂环境下三维航迹俯视图图4 复杂环境下迭代5 0次仿真适应度值曲线图从图4可以看出,I P S O算法在环境复杂度增加的情况下仍能快速收敛,且路径长度大大缩短,而传统的P S O算法和G A算法仍在很大程度上陷入局部最优,规划出的路径质量较差,从表2可知,经过5 0次迭代后的P S O和G A算法规划出的路径代价分别为4 6 9.0 5和3 6 8.8 5,适应度值均明显较大,而I P S O算法的路径代价值达到了1 4 9.9 2。传统的P S O与G A均容易陷入局部极值,故搜索出的路径长度一般较大。而I P S O算法糅合了其他的算法,增加了种群的多样性,在很大程度上帮助粒子跳出了局部最优解,同时I P S O算法引入了凹函数模型的惯性权重和动态更新的学习因子,使得粒子能够在搜索的前期注重全局搜索,后期则较为注重局部搜索,且相比线性递减策略,凹函数递减策略能够拥有更快的收敛速度。I P S O算法还将引力搜索算法中的加速度引入到速度更新中,使粒子在接近最优解时可以微调该粒子的速度,这就更好的平衡了粒子的探索与开发能力,因此I P S O算法无论是在简单环境还是复杂环境下都具有良好的性能优势。3.3 复杂环境下改进算法稳定性分析为了验证I P S O算法具有普遍性而不是偶然性,将上述5种算法进行2 5次仿真测试,每次的迭代次数设置为5 0次,各算法的平均适应度值、最优值、最劣值、标准差以及达到I P S O算法的适应度平均值所需的平均时间见表3,结果如图5所示。16青 岛 大 学 学 报(自 然 科 学 版)第3 6卷表3 各算法的适应度仿真结果统计算法平均值最优值最劣值标准差平均用时/sP S O8 3 1.7 11 4 4.5 21 7 3 8.4 24 5 2.0 51 1 6.4 7GA8 9 1.0 42 1 7.0 61 5 4 9.9 54 9 8.0 21 3 1.3 6P S O-GA2 5 7.6 41 4 7.2 96 7 1.2 11 5 3.7 19 5.4 2B F O-GA-P S O1 8 7.3 91 4 3.9 86 5 9.4 21 0 2.4 25 9.3 1I P S O1 5 8.1 91 4 2.4 61 8 2.9 81 0.75 1.5 3图5 2 5次仿真结果 从表3的适应度最优值可以看出,P S O算法虽然适应度最优值与I P S O算法的适应度最优值相近,但只是偶发现象,从图5可知,P S O算法仅有少数几次能达到适应度较优值,大多数的适应度值都比较大,最终适应度平均值达到了8 3 1.7 1,并且从适应度标准差 可知P S O算法尤其不稳定。从表3统计的适应度标准差数据可以看出,GA的适应度标准差为4 9 8.0 2,规划出路径的适应度值都较差,仿真2 5次后得到的适应度最优值为2 1 7.0 6,大于I P S O算法仿真2 5次得到的适应度最劣值,最终得到的适应度平均值达到了8 9 1.0 4。P S O-GA的适应度平均值相比P S O和GA算法有了很大的提高,但稳定性较差,最劣值达到了6 7 1.2 1。较于上述的3种算法,B F O-GA-P S O算法适应度平均值和稳定性均有很大的提高,虽然其适应度最劣值为6 5 9.4 2,但是从图5可以看出路径长度较差的情况只有2次,所以其适应度标准差较其他3种算法是最低的,仅次于I P S O算法。而I P S O算法运行2 5次之后适应度平均值最优于其他4种算法,接近于P S O与P S O-GA的适应度最优值。且I P S O算法的最劣值为1 8 2.9 8,适应度标准差为1 0.7,说明其适应度值波动较小,几乎每次都能规划出一条较优的路径,稳定性较高。由于I P S O算法糅合了其他算法且加入了其他的改进,导致计算量加大,运行同样的迭代次数,I P S O算法比P S O与GA算法消耗更多的时间,但能以更少的迭代次数达到适应度平均值,而P S O与GA算法想要达到I P S O算法的适应度平均值,则需要更多的迭代次数,如P S O和GA算法即使迭代5 0次也不一定能达到I P S O算法的适应度平均值,而从图4能看出I P S O算法在1 0代左右就能收敛到一个较好的适应度值,说明其收敛速度较快。I P S O算法由于收敛代数的大大减少,因而弥补了由于计算量增大造成时间成本的上升。故设置最大迭代次数为2 0 0次,I P S O算法在达到适应度平均值1 5 8.1 9所花费的时间只需5 1.5 3 s,较其他4种算法花费的时间最短。数据对比表明I P S O算法在路径长度,平均消耗时间,收敛速度和稳定性等方面都具有显著的优越性。4 结论本文提出的I P S O算法应用于无人机三维路径规划中,考虑路径长度代价、高度代价、碰撞代价、转弯角与爬升角代价等约束条件,I P S O算法将P S O与GA以及H S算法相结合,将引力搜索算法中的加速度思想引入到P S O算法中,并设置动态更新的学习因子与凹函数模型的动态惯性权重,当判断出粒子陷入局部极值无法跳出时,引入随机数对其进行扰动,帮助跳出局部最优。I P S O算法收敛速度快,稳定性好,平均寻优时间更短,适应度值更优。参考文献1 韩慧轩,周顺,周海波.障碍条件下串联机械手运动规划设计J.青岛大学学报(自然科学版),2 0 2 1,3 4(4):1 4 4-1 5 2.2WAN G Z,L I G F,R E N J.D y n a m i c p a t h p l a n n i n g f o r u n m a n n e d s u r f a c e v e h i c l e i n c o m p l e x o f f s h o r e a r e a s b a s e d o n h y b r i d a l g o r i t h mJ.C o m p u t e r C o mm u n i c a t i o n s,2 0 2 0,1 6 6:4 9-5 6.3C HA I Q S,WAN G Y J,HE Y,e t a l.I m p r o v e d P RM p a t h p l a n n i n g i n n a r r o w p a s s a g e s b a s e d o n P S OC/1 9 t h I E E E I n t e r n a t i o n a l C o n-f e r e n c e o n M e c h a t r o n i c s a n d A u t o m a t i o n.C h o n g q i n g,2 0 2 2:4 1-4 6.4 封建湖,张婷宇,封硕,等.面向机器人路径规划的改进粒子群算法J.机械设计与制造,2 0 2 1(9):2 9 1-2 9 4.26 第3期 唐文倩等:基于改进P S O混合算法的无人机三维路径规划研究5 陈洲宇.基于遗传粒子群混合算法的车辆路径问题研究D.成都:西南财经大学,2 0 2 2.6S ON G B Y,WANG Z D,Z OU L.A n i m p r o v e d P S O a l g o r i t h m f o r s m o o t h p a t h p l a n n i n g o f m o b i l e r o b o t s u s i n g c o n t i n u o u s h i g h-d e g r e e B e z i e r c u r v eJ.A p p l i e d S o f t C o m p u t i n g,2 0 2 1,1 0 0:1 0 6 9 6 0.7WAN G Z Y,CHE N Y C,D I N G S,e t a l.A n o v e l p a r t i c l e s w a r m o p t i m i z a t i o n a l g o r i t h m w i t h L v y f l i g h t a n d o r t h o g o n a l l e a r n i n gJ.S w a r m a n d E v o l u t i o n a r y C o m p u t a t i o n,2 0 2 2,7 5:1 0 1 2 0 7.8 巫茜,罗金彪,顾晓群,等.基于改进P S O的无人机三维航迹规划优化算法J.兵器装备工程学报,2 0 2 1,4 2(8):2 3 3-2 3 8.9 李丹,孙英华,王苗苗.基于双子群协作粒子群算法的双边匹配决策J.青岛大学学报(自然科学版),2 0 2 0,3 3(2):4 5-5 1.1 0 王蓉,刘遵仁,高阳.基于粒子群优化和邻域粗糙集的快速约简算法J.青岛大学学报(自然科学版),2 0 1 7,3 0(3):5 1-5 4.1 1 寇腾跃,于忠清,杨熙鑫.基于I P S O-G P R的HVA C送风温度预测模型J.青岛大学学报(自然科学版),2 0 2 1,3 4(2):2 9-3 7.1 2 A S MA A,S A D OK B.D y n a m i c d i s t r i b u t e d P S O j o i n t s e l i t e s i n m u l t i p l e r o b o t p a t h p l a n n i n g s y s t e m s:T h e o r e t i c a l a n d p r a c t i c a l r e v i e w o f n e w i d e a sC/2 1 s t I n t e r n a t i o n a l C o n f e r e n c e o n K n o w l e d g e-b a s e d a n d I n t e l l i g e n t I n f o r m a t i o n a n d E n g i n e e r i n g S y s t e m s(K E S).M a r s e i l l e,2 0 1 7:1 0 8 2-1 0 9 1.1 3 Z HON G J B,L I B Y,L I S X,e t a l.P a r t i c l e s w a r m o p t i m i z a t i o n w i t h o r i e n t a t i o n a n g l e-b a s e d g r o u p i n g f o r p r a c t i c a l u n m a n n e d s u r f a c e v e-h i c l e p a t h p l a n n i n gJ.A p p l i e d O c e a n R e s e a r c h,2 0 2 1,1 1 1:1 0 2 6 5 8.1 4 王宇,陈海涛,李海川.基于引力搜索算法的植保无人机三维路径规划方法J.农业机械学报,2 0 1 8,4 9(2):2 8-3 3+2 1.1 5 许诺.基于改进P S O算法的UAV三维路径规划研究J.电子测量技术,2 0 2 2,4 5(2):7 8-8 3.1 6 孙雪莹,易军凯.无人机三维路径规划的粒子群混合算法J/O L.电讯技术:1-1 22 0 2 3-0 3-0 2.h t t p:/k n s.c n k i.n e t/k c m s/d e t a i l/5 1.1 2 6 7.T N.2 0 2 2 0 3 0 7.1 8 3 7.0 0 4.h t m l.1 7 P HUN G M D,HA Q P.S a f e t y-e n h a n c e d UAV p a t h p l a n n i n g w i t h s p h e r i c a l v e c t o r-b a s e d p a r t i c l e s w a r m o p t i m i z a t i o nJ.A p p l i e d S o f t C o m p u t i n g,2 0 2 1,1 0 7:1 0 7 3 7 6.1 8 K E NN E D Y J,E B E RHA R T R.P a r t i c l e s w a r m o p t i m i z a t i o nC/I n t e r n a t i o n a l C o n f e r e n c e o n N e u r a l N e t w o r k s.P e r t h,1 9 9 5:1 9 4 2-1 9 4 8.1 9 F E N G H B,HU Q,Z HAO Z Y.AUV s w a r m p a t h p l a n n i n g b a s e d o n e l i t e f a m i l y g e n e t i c a l g o r i t h mJ.E n g i n e e r i n g a n d E l e c t r o n i c s,2 0 2 2,4 4:2 2 5 1-2 2 6 2.2 0 P ANG M Y,S HE N J N,WU L X.A d i s t r i b u t e d c o n g e s t i o n c o n t r o l s t r a t e g y u s i n g h a r m o n i c s e a r c h a l g o r i t h m i n i n t e r n e t o f v e h i c l e sJ.S c i e n t i f i c P r o g r a mm i n g,2 0 2 1(3):1-9.R e s e a r c h o n 3 D P a t h P l a n n i n g o f U A V B a s e d o n I m p r o v e d P S O H y b r i d A l g o r i t h mTANG W e n-q i a n,XU H a i-q i n,L I U Y a n g(C o l l e g e o f I n f o r m a t i o n S c i e n c e s a n d T e c h n o l o g y,D o n g h u a U n i v e r s i t y,S h a n g h a i 2 0 1 6 2 0,C h i n a)A b s t r a c t:A n i m p r o v e d P S O a l g o r i t h m w a s t e n d e r e d t o s o l v e t h e p r o b l e m o f p r e m a t u r e c o n v e r g e n c e o f p a r-t i c l e s w a r m o p t i m i z a t i o n(P S O)a l g o r i t h m i n UAV p a t h p l a n n i n g.B a s e d o n t h e c o s t o f p a t h l e n g t h,h e i g h t,c o l l i s i o n,t u r n i n g a n g l e a n d c l i m b i n g a n g l e,t h e f u n c t i o n o f f i t n e s s i s s t r u c t u r e d.T h e P S O a l g o-r i t h m i s c o m b i n e d w i t h g e n e t i c a l g o r i t h m(GA)a n d h a r m o n i c s e a r c h(H S)a l g o r i t h m,a n d t h e c o n c e p t o f a c c e l e r a t i o n w a s i n t r o d u c e d i n t h e g r a v i t y s e a r c h a l g o r i t h m.A n d D y n a m i c u p d a t i n g l e a r n i n g f a c t o r a n d d y-n a m i c i n e r t i a w e i g h t o f t h e c o n c a v e f u n c t i o n m o d e l a r e s e t.T h e s i m u l a t i o n r e s u l t s i n d i c a t e d t h a t c o m p a r e d w i t h t h e t r a d i t i o n a l w a y,t h e p r o g r e s s e d a l g o r i t h m h a d r e m a r k a b l e b e n e f i t s i n p a t h l e n g t h,c o n v e r g e n c e s p e e d,a v e r a g e c o n s u m p t i o n t i m e a n d s t a b i l i t y.K e y w o r d s:UAV;t h r e e-d i m e n s i o n a l p a t h p l a n n i n g;p a r t i c l e s w a r m h y b r i d o p t i m i z a t i o n a l g o r i t h m;f u n c-t i o n o f f i t n e s s36