改进的势场栅格法在机器人路径规划中的应用.pdf

第 19卷 第 1期长 春 大 学 学 报Vo.l 19 No.1 2009年 2月JOURNAL OF CHANGCHUN UN I VERSI TYFeb.2009 文章编号:1009-3907(2009)02-0038-05收稿日期:2008-11-18作者简介:雷艳敏(1976-),女,黑龙江省五常市人,长春大学电子信息工程学院讲师,博士生,主要从事多机器人系统的协作及智能控制方面的研究。改进的势场栅格法在机器人路径规划中的应用雷艳敏1,2,冯志彬3(11哈尔滨工程大学 自动化学院,黑龙江 哈尔滨 150001;21 长春大学 电子信息工程学院,吉林 长春 130022;31空军航空大学 航空救生系,吉林 长春 130021)摘 要:将势场法和栅格法结合,设计了一种改进的势场栅格法。该方法通过对栅格属性的设置来弥补势场法的缺点,并应用于移动机器人的静态全局路径规划中。在 V isual C+610中进行仿真,仿真结果表明该方法克服了单一的势场法和栅格法的缺点,利用该方法进行路径规划是可行的和有效的。关键词:势场法,栅格法,路径规划中图分类号:TP242 文献标识码:A0 引 言移动机器人的路径规划问题是机器人领域的核心问题之一,可定义为机器人在具有障碍物的工作空间中按照某种评价标准寻找一条安全无碰路径。根据机器人对工作空间环境信息的已知程度,路径规划问题可被分为静态路径规划和动态路径规划。针对路径规划问题,提出了许多算法,其中主要有人工势场法、栅格法、可视图法、神经网络法、模糊逻辑法、遗传算法、蚁群算法、粒子滤波法和滚动窗口法 1 3等。单一的任意一种路径规划方法都可以实现路径规划,但都存在着一定的缺点。所以可以考虑将两种或几种路径规划方法结合起来,充分利用各种方法的优点,使路径规划的性能(如安全性、光滑性)达到最优。路径规划主要涉及的问题有环境建模和搜索策略。环境建模的方法主要有栅格法和可视图法等,搜索策略有贪心算法、Dijkstra算法和 A*算法等。在静态路径规划中应用最多的是势场法和栅格法。势场法由 Khatib于 1986年首次被提出应用于机器人路径规划中。因其结构简单,计算量小,实时性好,得到了广泛的研究。但存在着 4个固有缺陷 4:(1)存在局部极小导致的陷阱区域;(2)在邻近的障碍物之间不能发现路径;(3)在障碍物出现时会震荡;(4)在狭窄通道中摆动。栅格法是由 W.E.Howden在 1968年提出的,是用大小相等的矩形栅格划分环境来区分环境中的自由空间与障碍物,它作为一种表示环境的有效方法越来越受到人们的重视,并有很好的应用前景。但是栅格法也存在着缺点,主要是由栅格的大小所引起的。栅格划分越小,障碍物的表示会越精确,但同时会占用大量的存储空间,算法的搜索范围将按指数增加。栅格的划分太大,规划的路径会很不精确。本文用栅格法来表示环境,采用 A*算法作为搜索策略,并用势场法中的斥力势函数和引力势函数来形成 A*算法中的启发函数,从而设计了一种改进的势场栅格法。通过对栅格地图的属性来做一些规定来弥补势场法的缺点,仿真结果表明该方法在进行移动机器人的静态路径规划时安全性和可靠性都比较高。1 势场栅格法111 栅格地图的建立及初始化栅格法将机器人路径规划的环境划分成二维网格,每格为一个单元,并假设障碍的位置和大小已知,且在机器人运动过程中不会发生变化。栅格法中的网格单元共有三种类型,即障碍网格、自由网格和机器人所在网格。目前常用的栅格表示方法有两种,即直角坐标法和序号法。这两种表示方法本质上是一样的,每个单元格都与(x,y)一一对应。本文采用序号法表示栅格,设栅格的中心点坐标为栅格的直角坐标,则每个栅格编号都与其直角坐标一一对应,地图中任意一点(x,y)与栅格编号 N 的映射关系为:N=INT(xGs)+xmaxGsINT(yGs),(1)式中,xm ax表示 x 轴的取值范围,Gs表示栅格尺寸的大小,I NT 函数表示取整,而栅格中心点的坐标为(xG,yG),它与栅格编号 N 之间的关系为:xG=(N%M)Gs+Gs/2,yG=I NT(N/M)Gs+Gs/2,(2)式中,M=xmax/Gs,符号%表示取余操作。栅格粒度的确定是栅格法中的主要问题。文献 5中根据障碍物的疏密来自动确定栅格粒度。本文中根据机器人的尺寸来确定栅格的粒度,假设一个栅格能容纳一个机器人,这里选择栅格的大小为 30c m 30cm 5。本文的仿真环境为 600c m 600c m,栅格号 N=0 399,机器人的初始位置为 Start(525,75),对应的栅格号为N=57,目标位置为 Goal(75,435),对应的栅格号为N=282。在 V isualC+610中进行仿真,仿真结果如图 1所示,黑色的图形代表障碍物栅格,小圆圈所代表的栅格为机器人的起始栅格和目标栅格,剩下的是自由栅格。在路径规划中机器人可以选择自由栅格作为它的路径点。图 1 栅格的序号表示法建立栅格后,对栅格进行初始化。设置变量 G _IsObstacle为 FALSE表示自由栅格,G _Is Obstacle为 TRUE表示自由栅格(包括机器人栅格)。112 栅格势场值的确立传统的人工势场法采用的是基于矢量合成的综合方法,它通过直观的规则即在源于障碍物的排斥力与源于目标点的吸引力的合力作用下规划机器人的运动。在只有局部信息的情况下,它的避障策略是十分有效的。但它的缺陷也是明显的。由于机器人运动的速度及方向取决于力矢量和的大小及方向,当合力为零时,机器人就无法运动了,这就是采用人工势场法易于陷入局部极小点的原因。而合力大小的变化也会使机器人的运动速度产生不必要的变化,降低了避障的效率,这里采用文献 6中的人工势场法,并加以改进。势场函数分为引力势函数和斥力势函数。势函数应该满足连续和可导的性质,同时需要满足机器人避障和到达目标点的要求。下面将分别给出引力势函数和斥力势函数。39第 1期 雷艳敏,等:改进的势场栅格法在机器人路径规划中的应用11211 引力势函数在机器人的路径规划中,目标点对机器人具有吸引力,距离目标点越远,引力势函数越大,反之越小。当距离为零时,机器人的引力势函数为零,此时机器人达到终点。通常目标势函数为Ug(X)=12kg(X-Xg)2,(3)式中,kg为位置增益系数,X-Xg为机器人 X 与目标点 Xg之间的距离。本文中 kg=2。11212 斥力势函数在势场中,障碍物产生的势场对机器人产生排斥作用,且距离越近,排斥作用越大,反之就越小。这里假设障碍物为不规则形状的障碍物,通常斥力势函数为:Urep(X)=12k0(1Q-1Q0)当 Q FQ00 当 Q:Q0,(4)式中,k0为位置增益系数,Q 为机器人 X 和障碍物之间的最短欧氏距离,Q0是一个常数,代表障碍物的影响距离。考虑到机器人处于合力为零的情况下,会使机器人处于局部最小点,而不能到达目标点。这里采用改进的斥力势函数,把机器人与目标点的距离考虑进去,同时在路径规划时,留一个安全距离 Q1,避免与障碍物相撞。所以斥力势函数为Urep(X)=12k0(1Q-Q1-1Q0-Q1)(X-Xg)n 当 Q F Q00当 Q:Q0,(5)总的势场函数为:U(X)=Ug(X)+Urep(X)=12kg(X-Xg)2+12k0(1Q-Q1-1Q0-Q1)(X-Xg)n 当 Q F Q12kg(X-Xg)2当 Q:Q0,(6)本文中选择参数为 Q0=200,Q1=30,为一个机器人的大小,k0=5,n=2。图 2 栅格地图的8个运动方向图113 栅格节点的选取在栅格地图中,一个节点栅格的前进方向有 8个,也就是机器人行进方向的右方、右后方、后方、左后方、左方、左前方、前方、右前方,中间的栅格为机器人所在的栅格,如图 2所示。路径节点的选取采用 A*(A-star)算法进行相邻节点的搜索,这里选取总的势函数作为启发函数。当距离障碍物越远时,Ure p(X)越小;当距离目标点越近时,Ug(X)越小,所以在启发函数下,机器人寻找 U(X)最小的栅格,逐渐的远离障碍物而趋向目标点。在图 2中,从当前栅格节点周围的 8个栅格中寻找一个启发函数值 U(X)最小的栅格节点,即:图 3 仿真图形n=m in8N=1(U(N),(7)N 为栅格序号,n为被选中的下一个路径节点,再以 n为当前节点搜索下一个节点,直到路径规划结束。根据本章中所设计的栅格势场法和相应给定的参数进行路径规划仿真,仿真图形如图 3所示。从图 3中可以看出,改进的栅格势场法能够进行静态环境的路径规划,但是路径不够平滑,如图 3中两个被椭圆线圈起来的地方,还没有考虑机器人工作环境的特殊性,下面将具体给出详细的分析和仿真。40长 春 大 学 学 报 第 19卷2 势场法的改进方法根据前述中所设计的势场栅格法可以实现移动机器人的静态路径规划,但是不能完全弥补势场法的缺陷,本文通过对栅格的属性进行适当的规定来弥补。211 局部最优点针对势场法中合力为零时,机器人会处于局部最优点,而无法到达目标点的现象,本文中通过在斥力场函数中引入机器人与目标点之间的距离来克服,见 11212。212 回溯问题回溯问题是指从栅格节点 n进入栅格节点 n+1时,可能会出现栅格节点 n+1周围除了栅格节点 n之外,都是障碍物的情况,这样机器人下一步又回到栅格节点 n+1处,依次类推,而机器人始终无法到达目标点。本文中通过把栅格节点 n+1设为障碍物节点来解决回溯问题,即机器人下次不会再选择栅格节点 n+1。这样机器人又回到栅格节点 n,重新选择路径到达目标点,仿真图形如图 4所示。(a)原来情况 (b)采用本文算法图 4 回溯问题仿真213 目标点在障碍物附近当目标点在障碍物附近时,障碍物斥力场的影响很大,使得机器人在栅格节点 n和 n+1之间来回移动,而始终无法到达目标点。这个缺陷可以通过对走过的路径栅格进行标记 Is_Path来克服。对于已经走过的路径节点下次再进行选择时,使它的势能值再低也不会被选上,而是选择其他的节点,但是这样的路径可能不是最优路径,但是却可以保证机器人到达目标点,即具有可达性。机器人的初始位置不变,把目标点位置改为 Goal(225,495),对应的栅格号为N=328,仿真图形如图 5所示。(a)原来情况 (b)标记 Is_Path图 5 目标点在障碍物附近214 狭窄通道中摆动通过仿真发现,当仿真环境中具有狭窄通道时,仿真参数对路径规划影响很大,图 3中就存在着这种情况。这是因为启发函数 U(X)中的 k0和 kg决定了斥力势函数大还是引力势函数大,在遇到狭窄通道的情况,应适当减少斥力作用或增加引力作用,即减小 k0或增大 kg,但 kg影响不太大。如图 6所示的仿真环境,机器人的初始点为 Start(315,45),对应的栅格为 N=30,目标点 Goal(315,495),对应的栅格为N=330。41第 1期 雷艳敏,等:改进的势场栅格法在机器人路径规划中的应用(a)k0=5,kg=2 (b)k0=3,kg=2图 6 狭窄通道中的摆动从图 6中可以看出通过适当减小 k0,可以克服狭窄通道中的摆动现象,使路径变的平滑。3 结 论从仿真结果可以看出,本文所提出的改进的势场栅格法,通过对栅格属性进行适当的规定可以很好地弥补势场法的缺陷,提高了路径规划的安全性、平滑性和可达性。下一步将该方法进行改进应用于动态路径规划和多机器人路径规划中。参考文献:1 王宗尧,司应涛,国海涛 1机器人路径规划方法的研究现状与展望 J.淮阴工学院学报,2007,16(3):49-51.2 刘华军,杨静宇.移动机器人运动规划研究综述 J.中国工程科学,2006,8(1):85-94.3 张纯钢,席裕庚.全局环境未知时基于滚动窗口的机器人路径规划 J.中国科学(E辑),2001,31(1):51-58.4 KorenY,Borenstein J.Potential fieldmethods and their inherent li mitations formobile robot navigation C M Proceedings ofthe 1991 IEEE InternationalConference on Robotics and Automation.Sacramento,California.1991:1398-1404.5 张美玉,黄翰,郝志峰,等.基于蚁群算法的机器人路径规划 J.计算机工程与应用,2005,41(9):34-37.6 金雷泽,杜振军,贾凯.基于势场法的移动机器人路径规划仿真研究 J.计算机工程与应用,2007,43(24):226-228.责任编辑:钟 声The application of the i mproved potentialgridmethod in robot path planningLEIYan-m in1,2,FENG Zh-i bin3(11College ofAutom ation,Harbin Engineering University,Harbin 150001,China;21College of E letronic Information Engineering,Changchun University,Changchun 130022,China;31Aviation L ifesaving Departmen,t Air ForceAviation University,Changchun 130021,China)Abstract:An i mproved potentialgridmethod is devised by combining potential fieldmethodwith gridmethod,which canmake up theshortcomings of potential fieldmethod through setting grid attribute and is applied to static global path planning of the mobile robot.Si mulation is carried outw ithV isualC+610.The results indicate that thismethod can overco me the shortco m ings of si mple potentialfiled and gridmethod,and it is feasible and effective in path planning.K ey words:potential field method;gridmethod;path planning42长 春 大 学 学 报 第 19卷