基于改进智能算法的机器人路径规划.pdf

第 卷第期 年月武汉理工大学学报(交通科学与工程版)J o u r n a l o fWu h a nU n i v e r s i t yo fT e c h n o l o g y(T r a n s p o r t a t i o nS c i e n c e&E n g i n e e r i n g)V o l N o A u g 基于改进智能算法的机器人路径规划姜子棋)闫帅)周航)薛钰婷)蔡方儿)(南京航空航天大学民航学院)南京 )(北京计算机技术及应用研究所)北京 )摘要:文中提出一种改进蚁群算法求解路径规划问题建立路径距离与转弯总角度的多目标函数,提高规划路径的平滑性和安全性设计改进启发函数,引入障碍排除机制,提高优质节点的启发性考虑优质孙节点与目标点距离,提高蚁群算法的全局搜索能力引入防死锁机制,并记录临时不可选点,避免蚂蚁重复陷入障碍包围采用改进节点信息素更新规则,提高算法的运行效率通过不同密度随机障碍实验,证明提出改进蚁群算法的正确性和优越性结果表明:对比蚁群算法,改进算法在路径长度、转弯总角度上分别提高 和 关键词:障碍排除;防死锁;目标距离;节点信息素;蚁群算法中图法分类号:T P d o i:/j i s s n 收稿日期:第一作者:姜子棋(),女,硕士生,主要研究领域为交通运输、智能算法路径规划等引言机器人的自主能力主要体现在实现自主避障的路径规划,而路径规划的核心内容是算法目前,常用于路径规划的算法有人工势场法、A算法、遗传算法、粒子群算法、蚁群算法等 文献 通过A算法与最大最小蚂蚁系统结合,在启发信息中引入A算法评价函数和转弯抑制算子,引入退回机制解决死锁问题,改进算法收敛速度更快、全局路径更平滑文献 改进蚁群算法在考虑环境安全的情况下,利用当前最优路径和历史最优路径优化信息素分布,利用周围障碍信息改进状态转移概率,提高了算法搜索速度,避免了局部最优和死锁的情况文献 通过D i j k s t r a算法与蚁群算法相结合,利用D i j k s t r a算法先规划一条初始路径,再利用改进蚁群算法对路径进行优化,搜索效率更高、求解质量更好文献 通过贪婪算法与蚁群算法相结合,引入多目标加权的启发函数,建立时间最短目标函数规划路径文献 改进蚁群算法在转移概率中引入角度和障碍排除因子,在信息素更新规则中引入自适应机制,改进蚁群算法能够实现全局路径最优,路径规划具有较高的实时性和稳定性文献 提出了优势方位角的概念,算法求解过程中运用双向引导策略,大大提高了初始解及算法收敛速度,在大规 模 场 景 下 具 有 较 好 的 求 解 性 能文 献 综合考虑了安全因素、最优距离因素、高度因素影响改进蚁群算法启发函数,信息素更新原则同时 考 虑 最 优 节 点 信 息 素 值 和 最 优 适 应值,改进算法能够在简单及复杂环境中快速找到最优路径综上所述,现有蚁群算法对环境信息识别利用不足,没有对选择点周围的障碍加以判断对选择点、选择点的临近点与目标点之间的关系利用不充分,不能进行有效的全局规划在信息素更新上效率不高,需要建立各节点间的边对应关系针对上述问题,文中改进启发函数,设计障碍排除机制,增加对选择周围环境信息的利用引入选择点、选择点临近的优质节点与目标点的距离作为启发,提高优质节点的启发性以及算法的全局搜索能力设计防死锁机制,记录临时不可选点,避免重复陷入障碍物包围改进节点信息素更新机制,提高算法计算效率通过不同密度的随机障碍设置验证改进算法的有效性模型建立 应用环境建模栅格法是路径规划中常用的方法,是指将环境划分成一定数量的栅格,每个栅格代表一个可搜索的空间利用栅格法进行环境建模可以直接标记环境中的障碍物等环境信息,避免机器人在规划的路径中发生碰撞障碍物等情况栅格法构建的环境模型见图在栅格法构建环境模型的同时,利用二维数组存取环境信息,障碍、可行,从而提高计算机读取效率,减少空间转换,有利于蚁群算法对机器人应用环境的识别图栅格环境模型 机器人路径规划模型 目标函数设计由路径长度和转弯总角度组成的多目标函数该多目标函数旨在规划的路径距离最短,同时根据任务要求尽可能减小路径的整体转弯角度和次数多目标函数为f(x)nilin jj()式中:l为机器人第i段路径的欧氏距离;为机器人的第j个转弯角度;和分别为路径长度和转弯总角度的权重,和根据任务对机器人路径的转弯要求设置,若使路径转弯总角度较小,应设置较大 约束条件)最大转弯角是机器人在运行过程中需要满足的转弯角度约束,可以用两段路径之间的夹角进行计算,见图该角度的计算见式()aiaTi|ai|ai|c o s(i,n)()式中:ai为矢量;|ai|为矢量的长度)最大路径长度是指将机器人运行速度视为匀速时,允许其行驶的最长距离规划的路径长图最大转弯角示意图度需要小于或等于预设最大路径长度即iliLm a x(i,n)()式中:li为第i段路径的长度;Lm a x为预设最大路径长度算法设计 改进启发函数引入子节点障碍排除机制,子节点附近障碍越少启发性越好,避免蚂蚁陷入障碍物包围将子节点与目标点距离也作为启发之一引入启发函数,使蚁群更容易找到距目标点近的节点子节点的临近点(孙节点)与目标点之间的距离也应该考虑在内,提高蚁群算法的全局搜索能力,见图图孙节点启发示意图当不考虑孙节点时,两个子节点的启发性是相同的,但是最优路径距离相差较大这时考虑最优孙节点与目标点之间的距离作为启发,增加优质节点的启发性,从而提高蚁群算法的效率和求解质量改进启发函数见式()j(t)di jdj t可行节点临近节点db e s t k t()式中:di j为当前点i到子节点j之间的距离;dj t为子节点j到目标点t之间的距离,可行节点为子节点j临近标记是的节点,临近节点为子节点j临近的所有节点;db e s t k t为最优孙节点k到目标点t的距离 防死锁设计防死锁机制,采用路径节点退回的方法,武汉理工大学学报(交通科学与工程版)年第 卷退回上一节点,并记录当前点为临时不可选点,防止蚂蚁在当前迭代中再次选中死锁节点防死锁机制示意图见图图死锁示意图 状态转移概率蚁群算法中,下一节点的选择是算法运行的重要一环根据当前点筛选出临界的至多八个节点,然后对障碍节点进行删除,再对剩下的节点验证转弯角度约束,不符合最大转弯角度约束的节点也不在概率计算的范围内状态转移概率为pjj(t)j(t)sGa l l o w e d g r i ds(t)s(t)jGa l l o w e d g r i d其他()式中:j和j分别为栅格j的信息素函数和启发函数;和分别为信息素因子和启发函数因子;Ga l l o w e d g r i d为当前可以搜索的栅格 改进信息素更新蚁群算法的信息素存储结构共有两种,分别是边信息素和节点信息素为节省空间提高计算效率,采用二维数组方式存储环境信息,故使用节点信息素能够减少栅格之间的映射关系,进一步提高算法效率在利用节点信息素的蚁群算法时,一个节点可能会通过多条关联路径,每一条关联路径在该节点都会产生信息素并更新,这使该节点的信息素分布急剧增加为了避免节点信息素累积过快,应采取全局信息素更新的策略当采取全局信息素更新的策略时,可以适当的减缓节点信息素迅速累积的趋势,但是依然存在不稳定情况因此,考虑将迭代最优路径和当前迭代路径的信息素同时进行更新由此,该算法可以避免由于节点信息素的激增而陷入局部最优当每个时间为t时刻,信息素更新为j(t)j(t)()jb(t)b(t)()b()jmkkjbQ/Lb e s t当前最优路径经过节点b其他()kjQLk(LkLb e s tLb e s t)k蚂蚁经过节点j否则()式中:为信息素挥发因子;Q为信息素常量;Lb e s t为当前最优路径长度;Lk为蚂蚁k找到的路径长度 算法流程将最大转弯角约束设置在蚁群算法蚂蚁选择下一节点之前,避免选择节点无效,在一定程度上提高了算法效率改进蚁群算法流程图见图图改进蚁群算法流程仿真与分析 参数设置实验蚁群算法的参数值设置会影响算法运行时间和求解质量因此,先采用单一变量法对参数选取在 栅格环境下进行实验,选择实验结果均值较优的参数作为蚁群算法的输入初始值实验参数区间为,默认参数值为,实验结果见表,选取,第期姜子棋,等:基于改进智能算法的机器人路径规划,表主要参数实验结果参数参数设置值和实验结果路径长度均值/m 路径长度均值/m 路径长度均值/m 对多目标函数的权重设置实验结果见表距离最优的单目标函数转弯次数增加,总角度最优的单目标函数距离增加,多目标函数能够在一定程度上均衡距离和转弯角度根据任务需求调节权重,使路径规划更加符合实际需求表多目标函数实验结果实验结果目标函数距离最优总角度最优综合最优路径长度均值/m 转弯次数均值转弯总角度均值/()算法对比实验在 栅格环境中随机设置 和 个障碍点作为机器人应用的障碍环境对比蚁群算法、改进蚁群算法和本文改进蚁群算法,分别在不同障碍密度、分布情况下的路径质量,从路径距离、转弯总角度、转弯次数,以及运行时间四个方面进行评价)个障碍点三种算法的规划路径见图算法分别运行 次的平均实验结果见表对比改进蚁群算法,本文改进算法在转弯总角度和次数上也有明显提高,能够有效保障路径安全性和平滑性而由于本文改进算法考虑因素较多、计算量较大,在运行时间上并不占优势图算法路径)个障碍点三种算法的规划路径见表各算法仿真结果对比算法最短路径长度/m转弯总角度/()转弯次数最短路径长度对比减少/转弯总角度对比减少/运行时间/s蚁群算法 改进蚁群算法 本文算法 图算法分别运行 次的平均实验结果见表本文改进算法在高密度障碍环境下,最短路径求解效果更好同时,本文算法在路径距离、转弯总角度和转弯次数上均优于改进蚁群算法,规划的路径更加安全高效平滑,但在运行时间上较为欠缺,有待后续改进图算法路径表各算法仿真结果对比算法最短路径长度/m转弯总角度/()转弯次数最短路径长度对比减少/转弯总角度对比减少/运行时间/s蚁群算法 改进蚁群算法 本文算法 结论)利用二维数组存取环境信息,环境维度直接对应,有效提高算法对环境的读取效率)建立路径距离和转弯总角度的多目标函数,在保证路径距离最短的同时,减少路径转弯角度和次数,保证路径的平滑性和安全性)引入障碍排除机制,充分利用选择点周围环境信息,提高优质节点的启发性利用选择点、选择点临近优质节点与目标点之间的距离,提高算法的全局搜索能力和求解质量)改进节点信息素更新机制,降低算法空间复杂度,减少边对应关系,提高算法效率武汉理工大学学报(交通科学与工程版)年第 卷)随机设置不同密度的障碍环境,通过仿真对比算法实验,证明本文改进算法的高效性和正确性,在路径安全性上有较为明显的优势参 考 文 献白文彬固定翼无人飞行器航迹规划方法D哈尔滨:哈尔滨工程大学,丛玉华,赵宗豪,邢长达,等基于改进人工势场的无人机动 态 避 障 路 径 规 划 J兵 器 装 备 工 程 学 报,():殷绍伟,彭力,戴菲菲融合改进A蚁群和滚动窗口法的平滑路径规划J计算机科学与探索,():刘佳,秦小林固定翼无人机在线航迹规划方法J计算机应用,():宋俊福,徐炳辉,张岩,等基于改进自适应遗传算法的机器人路径规划J信息技术,():,袁福龙,朱建平基于改进蚁群算法的移动机器人最优路径规划J现代制造工程,():,D A IX,L ON G S,Z HAN G Z,e ta l M o b i l er o b o tp a t hp l a n n i n gb a s e do na n tc o l o n ya l g o r i t h m w i t hAh e u r i s t i cm e t h o dJ F r o n tN e u r o r o b o t,():T I AN W,YAN GZ HA G r i d m a p o r i e n t e dUAVf l i g h tp a t hp l a n n i n ga l g o r i t h m b a s e do n A C Oa l g o r i t h mJC o mm u n i c a t i o n s,S i g n a lP r o c e s s i n g,a n dS y s t e m s,L e c t u r e N o t e si n E l e c t r i c a lE n g i n e e r i n g,():Z HA O HL,N I E Z,Z HOU F B,e ta l A c o m p o u n dp a t hp l a n n i n ga l g o r i t h mf o rm o b i l e r o b o t sCI E E EI n t e r n a t i o n a lC o n f e r e n c eo nP o w e rE l e c t r o n i c s,N e wY o r k,L I J,X I ONG Y H,S HEJ HA ni m p r o v e da n tc o l o n yo p t i m i z a t i o nf o rp a t hp l a n n i n gw i t hm u l t i p l eUAV sCI 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 nM e c h a t r o n i c s,N e wY o r k,M I A OC W,CHE N GZ,YAN CL,e ta l P a t hp l a n n i n go p t i m i z a t i o no fi n d o o rm o b i l er o b o tb a s e do na d a p t i v ea n t c o l o n ya l g o r i t h mJ C o m p u t e r s&I n d u s t r i a lE n g i n e e r i n g,():邓向阳,张立民,方伟,等基于双向汇聚引导蚁群算法的机器人路径规划J系统仿真学报,():张钧轶基于智能算法的巡飞弹协同攻击策略研究D太原:中北大学,R o b o tP a t hP l a n n i n gB a s e do nI m p r o v e dI n t e l l i g e n tA l g o r i t h mJ I A N GZ i q i)Y A NS h u a i)Z H O UH a n g)X U EY u t i n g)C A IF a n g e r)(C o l l e g e o fc i v i l a v i a t i o n,N a n j i n gU n i v e r s i t yo fA e r o n a u t i c s a n dA s t r o n a u t i c s,N a n j i n g ,C h i n a)(B e i j i n gI n s t i t u t eo fC o m p u t e rT e c h n o l o g ya n dA p p l i c a t i o n s,B e i j i n g ,C h i n a)A b s t r a c t:A ni m p r o v e da n tc o l o n ya l g o r i t h m w a sp r o p o s e dt os o l v et h ep a t hp l a n n i n gp r o b l e mT h em u l t i o b j e c t i v ef u n c t i o no fp a t hd i s t a n c ea n dt o t a lt u r n i n ga n g l e w a se s t a b l i s h e dt oi m p r o v et h es m o o t h n e s sa n ds a f e t yo ft h ep l a n n e dp a t h S e c o n d l y,t h eh e u r i s t i cf u n c t i o nw a sd e s i g n e da n di m p r o v e d,a n dt h eo b s t a c l e e l i m i n a t i o nm e c h a n i s mw a s i n t r o d u c e d t o i m p r o v e t h eh e u r i s t i co f h i g h q u a l i t yn o d e s C o n s i d e r i n gt h ed i s t a n c eb e t w e e nh i g h q u a l i t yg r a n d s o nn o d e sa n dt a r g e tp o i n t s,t h eg l o b a ls e a r c ha b i l i t yo fa n tc o l o n ya l g o r i t h m w a s i m p r o v e d A n t i d e a d l o c km e c h a n i s m w a s i n t r o d u c e d,a n dt e m p o r a r yn o n o p t i o n a lp o i n t sw e r er e c o r d e dt op r e v e n ta n t sf r o mf a l l i n gi n t oo b s t a c l e sr e p e a t e d l y I m p r o v e dp h e r o m o n eu p d a t i n gr u l e sw e r ea d o p t e dt o i m p r o v e t h ee f f i c i e n c yo f t h ea l g o r i t h m F i n a l l y,t h ec o r r e c t n e s sa n ds u p e r i o r i t yo f t h e i m p r o v e da n t c o l o n ya l g o r i t h mw e r ep r o v e db yr a n d o mo b s t a c l ee x p e r i m e n t sw i t hd i f f e r e n td e n s i t i e s T h er e s u l t ss h o wt h a t c o m p a r e dw i t ht h ea n tc o l o n ya l g o r i t h m,t h e i m p r o v e da l g o r i t h mi m p r o v e s t h ep a t hl e n g t ha n dt h e t o t a l t u r n i n ga n g l eb y a n d r e s p e c t i v e l y K e yw o r d s:o b s t a c l ee l i m i n a t i o n;a n t i d e a d l o c k;t a r g e td i s t a n c e;n o d ep h e r o m o n e;A C O第期姜子棋,等:基于改进智能算法的机器人路径规划