移动机器人避障路径规划算法的研究-

1、技术创新中文核心期刊微计算机信息(嵌入式与SOC 2008年第24卷第2-2期360元/年邮局订阅号:82-946现场总线技术应用200例机器人技术移动机器人避障路径规划算法的研究Path -planning Algorithm Research of Robots(南京工业大学张帆周庆敏ZHANG FAN ZHOU QINGMIN摘要:避障路径规划问题是在障碍物环境中,在满足与障碍物不相碰撞的前提条件下,规划一条从起点到达终点的路径。在此过程中,往往符合条件的路径不止一条,如何在其中找到最短路径则是我们关心的问题。本文以构建障碍物模型为基础,将路径规划问题转化为求解一条经过起点和终点的最短路

2、径,并在此基础上构建了算法程序。通过计算机仿真表明该方法具备良好的路径规划能力。关键词:路径规划;机器人;避障中图分类号:TP391文献标识码:AAbstract:Avoidance obstacle path planning problem is that in obstacle environment,from start point to destination point,research a collision free path.This kind of path maybe plenty,but this paper focuses to find the shortest l

3、ength of path.A program for search-ing the shortest length of path is presented.Computer simulation experiment shows that,the method has good path planning ability.Key words:path planning,robots,avoidance obstacle文章编号:1008-0570(200802-2-0212-021引言路径规划是移动机器人导航的最基本环节之一,机器人路径规划是针对某个特定的问题状态出发,寻求一系列行为动作,

4、并建立一个操作集合,该集合具有时间上的序列关系直到目标状态为止。路径规划的核心算法就是最短路径算法,它是计算机科学与地理信息科学等领域研究的热点。最短路径算法有很多,包括图论基本方法、启发式搜索方法、动态规划方法、神经网络方法等。路径规划是移动机器人导航技术中不可缺少的重要组成部分,它反映了机器人在运动过程中与周围环境的交互能力,是移动机器人完成任务的基础和安全保障。本文的研究目的在于从有障碍物的环境中,从起始点到目标点之间规划出一条与环境障碍物无碰的最短路径。构造出可视图,在可视图的基础上规划出从起始点至目标点的最短避障路径。2基本定义定义2.1设vi=(xi,yi(i=1,2,m,v1=v

5、m+1是平面R 2上构成某多边形Pi 的m 个顶点,如果对任意i,j (i j,i,j=1,2,m ,线段vivi+1与vjvj+1或是相邻且相交于一端点或不相交,则称多边形Pi 为简单多边形。简单多边形集合记为P=Pi|i=1,2,K,K 为简单多边形的个数;简单多边形Pi 可表示为Pi=vj|j=1,2,m。定义2.2障碍物多边形用Objecti表示,i=1,2,3且当且i j 时,ObjectiObjectj=,其中i,j=1,2,。定义2.3S,G 在平面R 2上,分别代表起始点和目标点。定义2.4全体障碍物顶点用vi表示,i=1,2,3.全体障碍物顶点数用Obj_point 储存,且

6、用v0表示起点S ,用vObj_point表示终点。定义2.5在有障碍物的平面R 2上,定义G 是顶点vi(i=1,2,3.构成的有权图。边的权值定义为vi集两顶点间的距离,表示为Distance(vi,vj(简记为dij。定义costObj_pointObj_point为图G 的可视图矩阵,costij=d(ij。3构造可视图矩阵顶点与顶点之间有两类关系,一类是同一障碍物的顶点间关系,一类是不同障碍物的顶点间关系。这两类关系都可以通过判断由顶点vi,vj构成的路径与障碍物多边形Objectk(k=1,2,3是否相交来解决。下面分两种情况计算cost.1顶点vivjObjectk(k=1,2,

7、3,计算边Distance(vi,v j可按下式计算(采用伪代码表示if (vi,vj是同一障碍物的顶点if(vi,vj是相邻顶点Distance(vi,vj=sqrt(vi.x-vj.x2+(vi.y-vj.y2(1else Distance(vi,vj=/用计算机中能表示的最大数代替2若顶点viObjectk,vjObjects(k s,则计算过程相对复杂。倘若i ,j 两点间无障碍物,可按(1式计算,否则就要判断vi,vj两点构成的路径v(i,j与障碍物多边形顶点va,va+1组成的边界v(a,a+1是否相交,根据相交结果来计算Distance(vi,vj的值。这里va,va+1Obje

8、ctl(l=1,2,a=1,2,。倘若相交,则将相应值置为。判断路径v(i,j和边界v(a,a+1有无交点,可以计算由v(i,j,v(a,a+1组成的矢量表达式的值:(viva×(va+1-va*(v a+1-va×(vj-va。若该表达式的值大于或等于0,表示有交点,注意,此处符号*和×并非一般意义上的四则运算符号,而是矢量运算符号。4用传统Dijkstra 算法计算避障路径Dijkstra 算法使用“贪婪”策略分阶段解决问题。每个阶段选择距离起点路径最短的顶点,“贪婪”表示该策略试图最大化短张帆:硕士研究生212- 邮局订阅号:82-946360元/年技术创新

9、机器人技术PLC 技术应用200例您的论文得到两院院士关注期收益,即使发现新的结点之后需要改变原有决策时也是如此。算法的主要思想是:分步求出最短路径,每一步产生一个到达新目的顶点的最短路径。下一步所能达到的目的顶点通过如下贪婪准则选取:在未产生最短路径的顶点中,选择路径最短的目的顶点。设置顶点集合S 并不断作贪心选择来扩充这个集合。当且仅当顶点到该顶点的最短路径已知时该顶点属于集合S 。初始时S 中只含起点。设u 为G 中一顶点,我们把从源点到u 且中间仅经过集合S 中的顶点的路称为从源到u 特殊路径,并把这个特殊路径记录下来(例如程序中的disti ,j。每次从V-S 选出具有最短特殊路径长

10、度的顶点u ,将u 添加到S 中,同时对特殊路径长度进行必要的修改。一旦V=S ,就得到从源到其他所有顶点的最短路径,也就得到问题的解。4.1对Dijkstra 算法的优化策略传统Dijkstra 算法仅给出了最短路径,无法得到路径上的中间结点,为了获得中间结点,可以把Dijkstra 算法中用于记录起始点到每一顶点的路径长度的dist 数组扩充成结构体,增加prev 域。扩充后的dist 数组元素的结构如下:struct dist_vbool traget ;/表示点是否被选入最短路径的标志位,初始化为falseint prev ;/表示该点的前驱结点有了这样的dist_v 数组,当搜索到规

11、划终点之后,就可以利用直接前驱信息,向前追踪到规划起点,从而可以绘制出规划所得的路径。同时,在搜寻过程中,还可以将当前点周围的邻接矩阵值进行简单排序,依次压入堆栈,这将大大减少每次计算下一条最短路径的时间。最后,在从起点搜寻目标点的过程中,还可以同时从目标点向起点搜寻,分别用两个数组存储两端搜寻到的顶点。每次循环过后进行检查,若发现相同的顶点序列号则表示两条搜索路径出现“对接”,可结束搜索,这个改进也使算法具备了一定的并行性。4.2算法实现障碍物信息可以用以下纪录表示:int Total_um ;/记录障碍物多边形的顶点数;point p maxnum;/数组p 记录障碍物多边形顶点的X ,Y

12、轴坐标;ObjectObjects_nums;/Objects_nums 记录障碍物的总数;构造可视图流程图:图1可视图构造流程5算法实验结果根据上述障碍物模型表示和算法设计框架,在VC6.0环境下编制了程序并构建了大量环境模型进行算法实验。图2显示是其中两次实验的结果,图中的多边形区域表示虚拟的不同地物的障碍物多边形,穿过整个场景的红色线段是所计算得到的最短路径,可以看出,该算法能够计算得出最短的避障路径。(实验a(实验b图2两组实验结果6小结本文详细描述了机器人路径规划的原理,背景,并且实现了在不同障碍物模型下的最短路径计算,第4节给出了算法流程和算法实现细节。目前,空间存储问题已不再是算

13、法要考虑的主要问题,因此有必要根据工程的实际情况对已有的算法进行必要的改进,必要时应该用空间换时间来提高最短路径算法的效率,用对算法的合理改进来使程序运行更快速。可以证明,本算法总是可以获得正确的最短路径。本文作者创新点:构建出障碍物多边形的抽象模型,在此模型基础上设计出一套切实可行的求解最短路径的优化算法。参考文献1黄玉清,梁靓.机器人导航系统中的路径规划算法J.微计算机信息.2006.7:259-2612T.Lozano-Perez,M.Wesley.An Algorithm for Planning Colli-sion-free Paths AmongPolyhedral Obstacles.Communications of theACM,1979,22(5:4364503黄刘生,唐策善.数据结构第二版M.合肥:中国科学技术大学出版社作者简介:张帆,男,汉族,1981年11月生,南京工业大学信息科学与工程学院计算机应用专业硕士研究生,研究方向为机器人最短路径规划,遗传算法;南京工业大学信息科学与工程学院硕士生导师,周庆敏教授。Biography:Zhang fan,College of Information Science and En-gineering,Nanjing University of Technology,Nanjing Jian