1、收稿日期:基金项目:吉林省教育厅重点项目(J KH K J)作者简介:宋宇(),男,汉族,吉林长春人,长春工业大学教授,硕士,主要从事嵌入式系统设计与研究,E m a i l:s o n g y uc c u t e d u c n 通信作者:张浩(),男,汉族,河南安阳人,长春工业大学硕士研究生,主要从事路径规划算法方向研究,E m a i l:q q c o m第 卷 第期 长 春 工 业 大 学 学 报 V o l N o 年 月 J o u r n a l o fC h a n g c h u nU n i v e r s i t yo fT e c h n o l o g y A p
2、 r D O I:/j c n k i c n /t 基于改进A算法的物流机器人算法研究宋宇,张浩,程超(长春工业大学 计算机科学与工程学院,吉林 长春 )摘要:针对传统A算法实现过程中存在转弯次数过多、路径搜索长度过长等缺点,提出一种改进A算法.通过对启发函数的计算方式进行改进,提高了路径搜索质量,同时引入转弯惩罚来降低规划过程中转弯次数,最后删除路径中冗余节点,得到一条最优路径.通过M a t l a b进行验证,改进算法相对于传统算法在路径长度上缩短了,在转弯次数和转弯总角度上分别提高 和.关键词:路径规划;A算法;路径平滑中图分类号:T P 文献标志码:A文章编号:()R e s e
3、a r c ho na l g o r i t h mo f l o g i s t i c s r o b o t b a s e do ni m p r o v e dAa l g o r i t h mS ON GY u,Z HAN G H a o,CHE NGC h a o(S c h o o l o fC o m p u t e rS c i e n c e&E n g i n e e r i n g,C h a n g c h u nU n i v e r s i t yo fT e c h n o l o g y,C h a n g c h u n ,C h i n a)A b
4、s t r a c t:I nv i e wo ft h es h o r t c o m i n g so ft r a d i t i o n a lAa l g o r i t h m,s u c ha st o om a n yt u r n sa n dt o ol o n gp a t hs e a r c h t i m e,a n i m p r o v e dAa l g o r i t h mi sp r o p o s e d B y i m p r o v i n g t h e c a l c u l a t i o nm e t h o do ft h eh e u
5、 r i s t i cf u n c t i o n,t h es e a r c h q u a l i t yo ft h ep a t hi si m p r o v e d,a n dt h et u r n i n g p e n a l t yi si n t r o d u c e dt or e d u c e t h en u m b e ro f t u r n s i nt h ep l a n n i n gp r o c e s s F i n a l l y,t h e r e d u n d a n tn o d e s i nt h ep a t ha r e
6、d e l e t e d t oo b t a i na no p t i m a l p a t h T h r o u g hM a t l a bv e r i f i c a t i o n,c o m p a r e dw i t h t h e t r a d i t i o n a la 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 ms h o r t s t h ep a t h l e n g t hb y,a n d i n c r e a s e s t h en u m b e r o f t u r n
7、sa n dt h e t o t a lA 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:p a t hp l a n n i n g;As t a ra l g o r i t h m;p a t hs m o o t h i n g 引言路径规划作为智能驾驶的一部分,在物流机器人中具有举足轻重的作用.路径规划指在给定的随机地图中规划出一条最优路径.常见的路径规划算法包括蚁群算法、遗传算法、人工势场法等.这些寻优算法都无法跳出局部最优解,且算法运行时间长.A算法是一种经典的路径规划算法,它可以有效地得到一条从起点到终点的无障
8、碍路径,但在大规模地图中会出现搜索效率低、转弯次数过多等缺点.为此,文献 针对复杂场景地图引入安全因子,使路径经过危险区域更少;文献 利用跳点搜索来代替A算法,减少了算法执行过程中搜索节点的数目,以此来提高算法执行效率;文献 将搜索的八个节点扩展到从起点到当前节点的整个支路上,缩短了路径的长度;文献 采用双向寻路策略,并且吸取人工势场法的思想可以得到一条较优路径;文献 提出基于动态窗口的双向A算法.综合以上分析,提出了一种改进A算法,分析不同距离计算方式的优缺点,对启发函数进行重新定义,并引入转弯惩罚,使规划过程中避免出现过多转角,最后删除路径中的冗余节点,得到最优路径.环境建模常见的路径规划
9、环境建模包括构型空间法、自由空间法、栅格法、拓扑图法等.为了清晰表述改进算法,文中采用二维栅格法对物流机器人的环境空间进行建模.假设每个栅格的边长为,二维栅格区域可以分为可行区域和障碍物区域,可行区域用白色表示,障碍物区域用黑色表示,考虑到物流机器人的安全,将不足一个栅格大小的障碍物作为一个障碍物来表示.为了准确记录所走路径点,文中规定栅格序号从左至右、从上到下、从依次递增.栅格序号图如图所示.图栅格序号图假设栅格地图由R行C列构成,栅格序号N与其坐标N(x,y)的对应关系为xa m o d(N,C)a,yaRac e i lNR,()式中:a每个栅格的边长;m o d取余函数;c e i l
10、返回值的最小整数.算法原理A算法通过计算开放列表中每个节点的代价估价函数f(n),选取最小的代价估价函数作为父节点加入关闭列表中,并将父节点周围可行节点加入开放列表中,重复以上操作,直到父节点为指定的目标节点,算法结束.其中代价估价函数为f(n)g(n)h(n),()式中:g(n)当前节点n到起始点的欧氏距离;h(n)当前节点n到目标点的曼哈顿距离.g(n)s q r t(s_xn_x)(s_yn_y),h(n)a b s(n_xe_x)a b s(n_ye_y),()式中:s_x起点的横坐标;s_y起点的纵坐标;n_x当前节点的横坐标;n_y当前节点的纵坐标;e_x目标点的横坐标;e_y目标
11、点的纵坐标.改进算法启发函数启发函数的大小直接影响A算法搜索效率.当启发函数小于当前节点到目标点的实际距离时,算法搜索节点过多,算法执行效率低;当启发函数大于当前点到目标点的距离时,算法得到的不是最优路径;当启发函数等于当前点到目标点的实际距离时,算法搜索效率最高,但由于障碍物的存在,这种情况很难实现.为此,选用合适的启发函数显得极为重要.常见的距离计算方式包括曼哈顿距离、对角线距离、欧式距离等.A点到B点三种距离定义图如图所示.从图中可得,使用曼哈顿距离作启发函数虽然可以减少算法的运算量,但规划出的路径效果不是最优的;使用欧氏距离可以得到最优路径,但存在计算复杂,导致算法运行过慢;而使用对角
12、线距离可以综合以上两种距离的优点.为此选用对角线距离作启发函数,则启发函数为Xm i n(a b s(exnx),a b s(eyny),()长 春 工 业 大 学 学 报 第 卷Ya b s(exnx)a b s(eyny),()h(n)aXa(YX),()式中:a每个栅格的边长.图三种距离定义图转弯惩罚项在传统A算法中,会出现牺牲路径平滑度的情况得到最短路径,在实际物流机器人行驶过程中会降低机器人的工作效率,同时也会缩短物流机器人的使用寿命.因此,提出了转弯惩罚项,在计算当前节点的代价估价函数f(n)时,会考虑起点s与终点e形成的向量s e和终点e与当前节点n形成的向量n e这两个向量所围
13、成的平行四边形的面积,即两个向量的叉积作为转弯惩罚项.向量s e和n e的叉积为p u na b s(d xd yd xd y)K,()其中:d xa b s(exnx),()d ya b s(eyny),()d xa b s(exsx),()d ya b s(eysy),()式中:K一个大于且小于的常数.为此,当前节点n的代价估价函数为f(n)g(n)h(n)p u n.()路径平滑在传统A算法与改进A算法中会出现冗余转折点,这会导致物流机器人在行进过程中出现过大的转弯角度,从而降低物流机器人的工作效率.因此,提出了路径再优化策略.路径再优化示意图如图所示.)将路径中的转折点、起点和终点放入
14、数组中.则数组中存放着p、p、p、p节点.)删除冗余节点.遍历数组中的节点,判断任一节点前后两个节点相连是否通过障碍物,若没有通过,则删除中间节点.图中实线为路径规划结果,虚线为路径平滑处理后的结果.图路径再优化示意图改进算法流程改进算法流程如图所示.仿真实验为了验证改进A算法的有效性,文 中在C o r e i UC P U GH z的W i n d o w 操作系统下的M a t l a b软件上进行仿真对比.首先随机生成一个 的地图,对比传统A算法以及改进A算法的结果如图所示.由图可得,传统A算法与改进A算法路径规划的长度、转弯次数以及转弯总角度见表.表A算法对比表指标传统A算法改进A算
15、法路径长度 转弯次数 总转弯角度/()由表可得,改进算法相对于传统算法而言,在路径长度上缩短,在转弯次数和转弯总角度上分别提高 和,虽然在路径长度第期宋宇,等:基于改进A算法的物流机器人算法研究上没有明显提高,但在路径平滑度上有很大的提升.图改进算法流程(a)传统A算法(b)改进A算法图A算法规划图结语通过改进A算法的物流机器人算法,改进算法的搜索方式,并对实际代价以及启发函数进行改进,最后对路径进行再优化,通过M a t l a b进行仿真,实验结果表明,改进算法可以得到更优路径.参考文献:张志文,张鹏,毛虎平,等改进A算法的机器人路径规划研究J电光与控制,():田海波,李陆军,畅科剑,等用
16、于无人车路径规划的改进A算法J现代制造工程,():,刘加奇,王泰华,董征基于改进蚁群算法的移动机器人路径规划J传感器与微系统,():冯豪博,胡桥,赵振轶基于精英族系遗传算法的AUV集群路径规划J/O L()系统工程与电子技术,:牛秦玉,李美凡,赵勇改进人工势场法的A G V路径规划算法研究J机床与液压,():宋宇,王志明改进A星算法移动机器人路径规划J长春工业大学学报,():崔宝侠,王淼弛,段勇基于可搜索 邻域的A算法路径规划J沈阳工业大学学报,():Z h a n gH M,L iML,Y a n gL S a f ep a t hp l a n n i n go fm o b i l er o b o tb a s e do ni m p r o v e d Aa l g o r i t h mi nc o m p l e xt e r r a i n sJ A l g o r i t h m s,():赵晓,王铮,黄程侃,等基于改进A算法的移动机器人路径规划J机器人,():李晓露,熊禾根,陶永,等基于改进A算法的移动机器 人 全 局 最 优 路 径 规 划 J高 技 术 通 讯,
