基于改进PSO混合算法的无人机三维路径规划研究.pdf
《基于改进PSO混合算法的无人机三维路径规划研究.pdf》由会员分享,可在线阅读,更多相关《基于改进PSO混合算法的无人机三维路径规划研究.pdf(7页珍藏版)》请在咨信网上搜索。
1、 第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、洋(东华大学信息科学与技术学院,上海 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算法在考虑路径长度代价、高度代价、碰撞代价以及转弯角与爬升角代价的基础上构建适应度函数,将粒子群算法与遗传算法以及和声搜索算法相结合,同时引入引力搜索算法中的加速度思想
3、,设置动态更新的学习因子与凹函数模型的动态惯性权重。仿真结果表明,对比传统的方法,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
4、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
5、 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
6、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
7、 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 环境建模无人机航迹规划前,首先进行环境建模,为了模拟无人机飞行的实际场景,本文采用山峰函数作为无人机飞行的基本地形,三维建模时使用圆柱体模仿无人机飞行时遇到的树木
8、、房屋之类的威胁物体。山峰函数青 岛 大 学 学 报(自 然 科 学 版)第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
9、表示航迹代价,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,
10、坐 标 位 置 为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 碰撞代价 当无人机所在高度低于山峰和圆柱
11、体的高度,且航迹上的点到圆柱体中心的距离小于圆柱体半径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在水平面上的投
12、影为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 传统粒子群算法粒子群算法
13、主要是通过鸟群觅食的行为找到全局最优解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分别表示粒子的
14、个体学习因子和社会学习因子,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
15、2(1 2)其中,Ti t e r为当前迭代次数,N表示总迭代次数。2.3 结合遗传算法与和声算法针对粒子群算法得到的粒子,首先通过轮盘赌法执行GA中的选择操作,在满足交叉概率的条件下将得到的个体进行交叉操作,即对任意两个粒子随机选择两组相同数量的航迹点,交换其位置坐标。同时对满足变异概率条件的粒子进行变异操作,即使用随机数替换该粒子随机选择的一个航迹点的位置坐标。重新计算每个粒子的适应度值,判断经过交叉变异操作后的粒子的适应度值,若比该粒子的个体最佳值更小1 9,则更新该粒子的个体最佳值,否则不更新。H S算法2 0通过生成随机数,并比较与记忆库取值概率HMC R以及微调概率P A R的大小
16、,调整和声变量得到一个新的和声,比较新和声是否比最劣值要优,若是,则用新和声代替其最劣值,以此不断更新和声记忆库,直到达到迭代次数为止。本文将各粒子的历史最优值组成和声记忆库,根据H S算法原理不断更新记忆库,直到达到H S算法设定的终止条件。完成迭代后,判断和声记忆库中最优和声的适应度值,若优于全局最优值,则更新全局最优值,否则不更新。2.4 引入加速度引力搜索算法是基于万有引力定律提出的,其中任意一个粒子受到其他粒子的引力和,由此计算出粒子在d维空间产生的加速度adi(t)adi(t)=Fdi(t)Mi i(t)(1 3)其中,Fdi(t)表示该粒子在d维空间受到的合力大小,Mi i(t)
17、表示第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
18、 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
19、 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 重新计算各粒子的加速度值,并将各粒子的历史最优值组成和声记忆库,不断迭代产生新的和声向量,淘汰适应度值最劣的粒子,最终
20、得到新的和声记忆库,通过适应度值判断此时和声记忆库中最优粒子的适应度值是否比全局最优值更小,若是则对全局最优值进行更新,否则不更新;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,设
21、置建模任务空间为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 O
22、GAP 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种
23、算法在不同程度上陷入了局部最优。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混合算法的无人机
24、三维路径规划研究图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 复杂环境下三维航迹
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基于 改进 PSO 混合 算法 无人机 三维 路径 规划 研究
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。