基于改进狼群算法的AGV路径规划.pdf

随着社会经济发展和工业智能信息化的深入,智能化物流逐渐成为商业和工业领域必不可少的基础设施,这使得自动引导小车(a u t o m a t e dg u i d e dv e h i c l e,AGV)得到越来越广泛的应用,同时也促进了对AGV关键技术的深入研究.路径规划作为该领域核心技术之一,具有非常广泛的应用场合,比如手机导航、无人驾驶车辆的避障和规划路径、智能物流等.针对路径规划问题,国内外学者做了大量的深入研究,提出了很多解决方法,其中包括遗传算法、蚁群算法、粒子群算法和神经网络等.其中,文献 基于狼群捕猎过程中的分工协作提出了狼群算法(w o l fp a c ka l g o r i t h m,WP A),该算法将狼群的捕猎活动抽象为游走、召唤、围攻种行为,并引入“胜者为王”的头狼选择机制和“适者生存”的更新机制.狼群算法的提出引起了国内外学者的广泛关注.文献 将狼群算法成功应用于无人机航迹规划;文献 在原始狼群算法的基础上引入次头狼召唤和围攻的更新策略,提高了算法的全局寻优能力,并将其应用于空战目标火力分配问题上;文献 提出了根据游走次数的奇偶性改变探狼搜索方向的方法,并且引入自适应调节搜索步长的策略,提高了算法的求解精度.狼群算法作为群体智能算法的一种,具有广泛的应用领域,同样也适用于AGV最优路径求解问题.本文针对狼群算法易陷入局部最优、搜索效率低等问题,提出了一种改进狼群算法(i m p r o v e dw o l f p a c ka l g o r i t h m,I WP A),并将其应用于AGV路径规划.本文介绍了AGV运动空间的环境建模以及改进的狼群算法,比较了I WP A和WP A在函数优化问题上的求解效果,并对种算法分别进行了AGV路径规划仿真实验和结果分析.A GV路径规划问题 环境建模在AGV路径规划研究中,描述环境的建模方法有很多种,常用的有可视图法、自由空间法、拓扑法和栅格法等 .本文采用栅格法进行环境建模,将运动环境映射成大小相同的网格矩阵,每块栅格的边长都为,AGV视作地图中的一个质点.一个的栅格环境如图所示,以栅格左下角为坐标原点,横向为X轴,竖向为Y轴,则栅格j的坐标为(aj,bj).对地图中的栅格采用实数编码,则在MM的栅格环境中,栅格坐标与编号N的对应关系为:a m o d(N,M),bf i x(N)/M)()其中:m o d为取余运算;f i x为向靠近取整的运算.带障碍物的栅格地图如图所示,AGV路径规划即要求在图中白色的可行区域内规划出一条从起始点到目标点的最优路径.图带障碍物的栅格地图 适应度函数的建立利用狼群算法进行路径规划时,种群中的每匹狼都代表一条潜在的可行路径,适应度函数则是评价这条路径优劣程度的唯一标准.本文适应度函数采用路径长度、平滑度以及安全度作为评价指标.)路径长度评价函数f.计算公式为:ft j(aj aj)(bj bj)()其中:a、b为当前路径中所经过栅格的位置坐标;t为路径节点个数.)路径平滑度评价函数f.采用相邻路段之间夹角之和的大小作为评价平滑度的指标,即ft j (ljlj,lj lj)()其中,(ljlj,ljlj)为相邻条路段ljlj和ljlj的夹角.f值越小,路径越平滑.)路径惩罚函数f.路径与障碍物相交的次数越多则函数值就越大,越容易在迭代过程中被淘汰.fmjC m()其中:m为与障碍物相交的次数;C为一个取值较大的正常数.将f和f进行归一化处理后,AGV路径规划的适应度评价函数为:ff/dp a t hf/(Nn u m)f()其中:dp a t h为起点和终点与它们之间垂直交叉点的距离之和;Nn u m为路径的拐点总数;、为权值,且.故AGV的最优路径规划即为求解使适应度函数f最小的坐标集.改进的狼群算法 狼群算法基本原理狼群算法的基本过程主要包括以下步骤:合肥工业大学学报(自然科学版)第 卷)狼群初始化.在D维空间中随机初始化n匹人工狼的位置,则第i匹人工狼的位置可表示为Xi(xi,xi,xi D),i,n.)选取距离猎物最近的人工狼为头狼,并将除头狼外最优的Sn u m匹狼选取为探狼,Sn u m随机取n/(),n/中的整数,为探狼比例因子,并执行游走搜索行为,向四周h个方向以步长Sa搜寻猎物.探狼i向第p(p,h)个方向游走后,在第d维空间位置更新为:xpi dxi ds i n(p/h)Sda()若探狼搜索到距离猎物更近的位置,则更新其当前位置,并重复游走行为,直到某人工狼搜索到优于头狼的位置时,该探狼将代替头狼发起召唤或直到游走达到最大游走次数Tm a x.)将头狼和探狼以外的其余狼作为猛狼,在头狼发起召唤后,猛狼以步长Sb向头狼移动,猛狼i在第k次迭代后,其在第d维空间位置更新为:xk i dxki dSdb(gkdxki d)/|gkdxki d|()其中,gkd为第k代头狼在第d维空间中的位置.在奔袭的过程中,若猛狼所处位置优于头狼,则该猛狼将代替头狼发起召唤行为;否则猛狼将继续奔袭,直到与头狼的距离小于dn e a r时,对猎物发起围攻.判定距离dn e a r的计算公式为:dn e a rD Dd|dm a xdm i n|()其中:为距离判定因子;dm a x、dm i n为狼群在第d维空间位置坐标的最大值和最小值.)当猛狼与猎物的距离小于dn e a r时,便联合探狼以步长Sc对猎物进行围攻,以期捕获.狼群位置更新公式为:xk i dxki d Sdc|gkdxki d|()其中,为,间均匀分布的随机数.若进行围攻之后人工狼离猎物更近,则更新位置;否则保持原位置不变.种 搜 索 步 长 在 第d维 空 间 中 存 在 如 下关系:SdaSdb/Sdc|dm a xdm i n|/S()其中,S为步长因子.)狼群的更新机制.根据适者生存的更新策略,淘汰适应度最差的R匹狼,然后随机生成R匹狼.R为随机整数,取值在n/(),n/之间,其中为比例因子.狼群算法的改进针对传统狼群算法初始种群多样性不足,探狼游走方向固定,易陷入局部最优,迭代后期搜索效率低等缺陷,本文从如下个方面进行了改进,以进一步提高算法的寻优效率.改进的S i n e混沌映射优化初始种群狼群算法中种群的初始位置和狼群的更新机制均采用随机生成的方式,这种方式容易导致种群分布不均匀、多样性不足,影响后期的迭代寻优效率.而混沌映射具有遍历性、规律性、随机性等特点,可以有效避免这些缺陷.产生混沌变量的S i n e混沌模型映射公式为:zk s i n(zk)()其中:zk为迭代序列,kN,z(,;为控制参数,越接近时混沌性能越好.当取,迭代 次后,S i n e混沌映射序列分布图如图、图所示,可以发现序列的分布并不十分均匀,在,和,区间内出现的频率较高.图S i n e映射分布直方图图S i n e映射分布图依据文献 所提方法对S i n e混沌映射进行改进,如式()所示,并利用式()将序列映射到狼群空间位置上.第期程俊,等:基于改进狼群算法的AGV路径规划ck s i n(ck),ek s i n(ek),yk(ck ek)m o d()xi ddm i nyi d(dm a xdm i n)()其中:y,为混沌迭代序列;为控制参数.改进后的S i n e映射分布图如图、图所示.从图、图可以看出,混沌值分布更加均匀,出现的概率更加相近.因此采用改进的S i n e映射进行狼群初始化和更新,有利于提高种群多样性,进而提高算法的寻优效率.图改进的S i n e映射分布直方图图改进的S i n e映射分布图 探狼随机游走策略在传统的狼群算法中,探狼游走行为由式()决定,这使得探狼i不论迭代搜索多少次,方向只有h个,搜索方向固定,且每代之间的搜索方向都是平行的,削弱了算法的随机性.文献 提出根据游走次数的奇偶性改变搜索方向的方法,文献 在游走行为中引入相位因子,以提高探狼搜索的灵活性.为了进一步丰富搜索方向,本文对探狼游走公式进行了改进,公式如下:XpiXi(v/|v|)Sa()其中,v为随机方向向量,计算公式为:vV(:,p)T,Vr a n d(D,h)()其中,r a n d为生成随机数的运算.这样探狼在每次游走时,会随机选择h个方向进行搜索,方向不固定,增强了搜索的随机性,从而提高了算法的全局寻优能力.头狼选择引入M e t r o p o l i s准则原始算法中总是选择适应度最好的人工狼作为头狼,执行召唤行为.在迭代后期,种群多样性降低时,易使种群陷入局部最优,降低算法的全局搜索能力.针对该问题,在探狼游走搜索后,对头狼的选择方式上引入M e t r o p o l i s准则 使得算法具有概率突跳的能力.本文以种群迭代次数k来表示M e t r o p o l i s准则中的温度,改进公式为:Pe x p k/Km a x()()其中,Km a x为种群最大迭代次数.当探狼i搜索到优于头狼的位置时,探狼i取代当前头狼发起召唤;当所有探狼搜索至最大游走次数依然未搜索到优于头狼的位置时,按式()概率接受非最优人工狼作为当前种群的头狼,随着迭代次数的增加,算法接受非最优人工狼作为头狼的概率逐渐减小.猛狼奔袭策略的改进在原始算法中头狼发起召唤之后,猛狼需要不停奔袭直至与猎物的距离小于dn e a r时,才能转入围攻行为.该策略在算法后期容易导致猛狼在头狼附近不停奔袭搜索而难以进入围攻行为,从而影响算法的寻优效率.为此,本文采用猛狼奔袭次就转入围攻的召唤策略.同时,取消围攻步长Sdc,消除其与游走步长之间的耦合关系,提高算法局部开采能力,则人工狼在围攻之后的位置更新方式为:xk i dxki d(gkdxki d)()其中,为,内的随机数.改进狼群算法步骤)采用栅格法对AGV运动环境进行建模,对栅格进行编码,并获取障碍物信息.)采用实数编码,对狼群进行初始化.利用 节所述方法构造人工狼初始位置,则第i匹人工狼位置为Xi(xi,xi,xi D),i,n,每匹人工狼代表一条潜在的可行路径;初始化算法的迭代次数Km a x、探狼比例、狼群更新比例、游走步长Sa、奔袭的步长Sb等.)按照式()计算每匹狼的适应度f(Xi),将适合肥工业大学学报(自然科学版)第 卷应度最好的人工狼暂定为头狼,除头狼外适应度最好的前Sn u m匹狼作为探狼.按照式()执行游走搜索,若f(Xi)f(Xg),则人工狼i将代替头狼;若探狼在游走搜索之后,未发现更优位置,且满足Pqr a n d,其中qr a n d为之间的随机数,则取任意一匹探狼代替当前头狼发起召唤行为;否则不更新当前头狼.)猛狼按式()向头狼奔袭,若途中发现适应度优于头狼,则将取代头狼发起召唤.)猛狼联合探狼按式()执行围攻行为.)更新头狼位置,并淘汰掉适应度最差的R匹狼,按改进的S i n e混沌映射规则重新生成R匹狼.)判断是否满足终止条件,若满足,则算法结束;否则转至步骤)继续进行搜索.仿真实验 函数测试与分析为了验证本文所提的I WP A的有效性和可行性,本文选择了在函数优化中广泛使用的个标准测试函数进行测试,并与WP A进行实验对比.测试函数的基本信息见表所列,表中:U表示此函数为单峰;M表示多峰;S表示可分;N表示不可分.实验设置最大迭代次数为 ,种群数量为 ,探狼比例因子,狼群更新比例因子,S ,其他参数参考文献 设置,分别进行 次的独立实验.实验结果见表所列,若结果小于 E,则视为.表个标准测试函数编号函数表达式维数特征取值范围最优值E a s o mf(x)c o sxc o sxe x p(x)(x)UN ,M a t y a sf(x)(xx)xxUN,S i xH u m pC a m e lB a c kf(x)x xxxxxxMN,S p h e r ef(x)Dixi U S,B o o t hf(x)(xx)(xx)M S ,R a s t r i g i nf(x)Dixi c o s(xi)M S,E g g c r a t ef(x)xx(s i nxs i nx)MN ,S u m s q u a r e sf(x)Dii xi U S,表函数优化结果对比编号函数算法平均值最优值标准差平均耗时/sE a s o mI WP A WP A E M a t y a sI WP A WP A E E E S i xH u m pC a m e lB a c kI WP A WP A S p h e r eI WP A E E E WP A E E E B o o t hI WP A WP A E E E R a s t r i g i nI WP A E WP A E g g c r a t eI WP A WP A E E E S u m s q u a r e sI WP A E E E WP A E 由表可知,首先在平均值与最佳值的对比上,I WP A比WP A寻优能力更强,收敛精度更高.对E a s o n、M a t y a s单峰函数寻优接近理论最优值,体现了I WP A具有较强的开采能力,这得益于种群的多样性以及猛狼良好的围攻行为;对R a s t r i g i n、S u m s q u a r e s等多峰函数具有较好的优第期程俊,等:基于改进狼群算法的AGV路径规划化效果,体现了I WP A跳出局部极值的能力,这得益于对头狼的选择上引入了M e t r o p o l i s准则,使得算法具有概率突跳的能力.从标准差的对比可以看出I WP A具有更好的鲁棒性,在平均耗时上I WP A与WP A处于同一级别,说明I WP A在提升性能的基础上并没有明显增加运行时间.为了更直观地说明I WP A的优越性,给出了R a s t r i g i n、E g g c r a t e、S u m s q u a r e s个函数的收敛曲线,如图所示.从图可以看出,I WP A在收敛速度和求解精度上均有优势.图个函数的收敛曲线 路径规划仿真实验为了验证改进的狼群算法在AGV路径规划问题上的可行性,本文进行了仿真实验.仿真环境为 的栅格地图,起始坐标为(,),终点坐标为(,),种群维数为,种群个数N ,最大迭代次数K ,探狼比例因子,狼群更新比例因子,最大游走次数T,步长因子s,/.在相同的条件下,将I WP A和WP A种算法各自运行 次,路径规划的数据统计结果见表所列,各自规划的最优路径如图、图所示.表种算法运行 次的数据比较算法I WP AWP A最优路径长度/m 平均路径长度/m 最优路径转角度数/()平均转角度数/()路径长度方差/m 时间/s 图WP A的最优路径规划图 I WP A的最优路径规划合肥工业大学学报(自然科学版)第 卷从表可以看出,在仿真环境中,I WP A规划的最优路径距离比WP A的短 m左右,总转角度数小 ,从平均值和方差上可以看出I WP A寻优更加稳定、鲁棒性更好.从图和图可以看出I WP A规划的路径更加平滑,充分说明了I WP A在AGV路径规划上的有效性和稳定性.结论本文在栅格法环境建模的基础上,针对A G V路径规划问题,提出了一种改进的狼群算法.该算法利用改进的S i n e混沌映射进行种群的初始化和更新,提高了种群的多样性;探狼的随机游走策略,增强了算法搜索的随机性;在头狼的选择上引入M e t r o p o l i s准则,提高了算法跳出局部最优解的能力;猛狼奔袭策略的改进有利于加快算法收敛.仿真实验表明,在A G V路径规划的问题上,I W P A比W P A更加有效,具备一定的实用价值.参考文献魏彤,龙琛基于改进遗传算法的移动机器人路径规划J北京航空航天大学学报,():鲁飞基于改进蚁群算法的机械臂路径规划研究D合肥:合肥工业大学,王东风,孟丽粒子群优化算法的性能分析和参数选择J自动化学报,():L IH,YAN GSX,S E T O M L N e u r a l n e t w o r k b a s e dp a t hp l a n n i n g f o r am u l t i r o b o t s y s t e mw i t hm o v i n go b s t a c l e sJI E E ET r a n s a c t i o n so nS y s t e m s,M a n,a n dC y b e r n e t i c s,P a r tC:A p p l i c a t i o n sa n dR e v i e w s,():吴虎胜,张凤鸣,吴庐山一种新的群体智能算法狼群算法J系统工程与电子技术,():刘永兰,李为民,吴虎胜,等基于狼群算法的无人机航迹规划J系统仿真学报,():陈杰,薛雅丽,叶金泽基于改进狼群算法的多机协同目标分配研究J吉林大学学报(信息科学版),():郭立婷基于自适应和变游走方向的改进狼群算法J浙江大学学报(理学版),():刘恺文,曹政才基于改进灰狼优化算法的自动化立体仓库作业能量优化调度J计算机集成制造系统,():Z HUX,C HE NL,T AN GB,e ta l D y n a m i cp a t hp l a n n i n gf o r a u t o n o m o u sd r i v i n go nv a r i o u s r o a d sw i t ha v o i d a n c eo fs t a t i ca n d m o v i n go b s t a c l e sJ M e c h a n i c a lS y s t e m s&S i g n a lP r o c e s s i n g,:严周莉 A GV的路径规划及运动控制研究D武汉:武汉工程大学,刘金源,葛继科,唐籍涛一种基于改进型S i n e映射的快速混沌图像加密算法J重庆科技学院学报(自然科学版),():惠晓滨,郭庆,吴娉娉,等一种改进的狼群算法J控制与决策,():何庆,吴意乐,徐同伟改进遗传模拟退火算法在T S P优化中的应用J控制与决策,():(责任编辑李凯)(上接第 页)通过B样条轨迹规划算法实验验证了混联机器人在工作空间内具有较好的灵活性和各个关节运动的柔顺性.实验研究表明,本文对于柔索驱动混联机器人的设计和广泛应用具有一定的参考和推动作用.参考文献张波,战红春,赵明扬,等柔索驱动三自由度球面并联机构运动 学 与 静 力 学 研 究 J机 器 人,():,赵宏宇一种串并混联机械臂结构设计及运动学研究D成都:成都理工大学,陈伟海,游贤强,崔翔,等绳驱动拟人臂机器人的动力学建模及张力分析J北京航空航天大学学报,():李艳文,黄真,王鲁敏,等新型自由度并联机器人运动学分析J机械工程学报,():,沈寂一种球面并联机构的动力学性能分析及仿真D南昌:华东交通大学,曾宪菁,黄田,曾子平,等基于三自由度球面并联机构数控回转台 的 机 械 设 计 J机 器 人 技 术 与 应 用,():王杰六自由度机器人本体设计及轨迹规划与虚拟仿真D合肥:合肥工业大学,T U R S Y N B E KI,S H I N T EM I R O VA I n f i n i t e r o t a t i o n a lm o t i o ng e n e r a t i o na n da n a l y s i so fas p h e r i c a lp a r a l l e lm a n i p u l a t o rw i t hc o a x i a l i n p u t a x e sJ M e c h a t r o n i c s:T h eS c i e n c eo f I n t e l l i g e n tM a c h i n e s,():李国洪,王远亮基于B样条和改进遗传算法的机器人时间最优轨迹规划J计算机应用与软件,():,李朋阳,高建设,顾昌利一种串并混联的上肢康复机器人轨迹 规 划 研 究 J机 械 设 计 与 制 造,():,赵东捷,杜兆才,刘李明一种柔索驱动超冗余度机器人结构及驱动机构设计J装备制造技术,():,(责任编辑胡亚敏)第期程俊,等:基于改进狼群算法的AGV路径规划