资源描述：
《移动机器人避障路径规划算法的研究.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、机器人技术中文核心期刊《微计算机信息》(嵌入式与SOC)2008年第24卷第2-2期文章编号:1008-0570(2008)02-2-0212-02移动机器人避障路径规划算法的研究Path-planningAlgorithmResearchofRobots(南京工业大学)张帆周庆敏ZHANGFANZHOUQINGMIN摘要:避障路径规划问题是在障碍物环境中,在满足与障碍物不相碰撞的前提条件下,规划一条从起点到达终点的路径。在此过程中,往往符合条件的路径不止一条,如何在其中找到最短路径则是我们关心的问题。本文以构建障碍物模型为基础,将路径规划问题转化为求解一条经过起点和终点的最短
2、路径,并在此基础上构建了算法程序。通过计算机仿真表明该方法具备良好的路径规划能力。关键词:路径规划;机器人;避障中图分类号:TP391文献标识码:AAbstract:Avoidanceobstaclepathplanningproblemisthatinobstacleenvironment,fromstartpointtodestinationpoint,researchacollisionfreepath.Thiskindofpathmaybeplenty,butthispaperfocusestofindtheshortestlengthofpath.Aprogramfo
3、rsearch-ingtheshortestlengthofpathispresented.Computersimulationexperimentshowsthat,themethodhasgoodpathplanningability.技Keywords:pathplanning,robots,avoidanceobstacle术表示为Distance(v[i],v[j])(简记为d[i][j])。定义cost[Obj_point]1引言[Obj_point]为图G的可视图矩阵,cost[i][j]=d([i][j])。创路径规划是移动机器人导航的最基本环节之一,机器人路3
4、构造可视图矩阵径规划是针对某个特定的问题状态出发,寻求一系列行为动作,新并建立一个操作集合,该集合具有时间上的序列关系直到目标顶点与顶点之间有两类关系,一类是同一障碍物的顶点间状态为止。路径规划的核心算法就是最短路径算法,它是计算机关系,一类是不同障碍物的顶点间关系。这两类关系都可以通科学与地理信息科学等领域研究的热点。最短路径算法有很多,过判断由顶点v[i],v[j]构成的路径与障碍物多边形Object[k](k=包括图论基本方法、启发式搜索方法、动态规划方法、神经网络1,2,3⋯)是否相交来解决。方法等。路径规划是移动机器人导航技术中不可缺少的重要组下面分两种情况计算cos
5、t.成部分,它反映了机器人在运动过程中与周围环境的交互能力,1)顶点v[i]v[j]∈Object[k](k=1,2,3⋯),计算边Distance(v[i],v是移动机器人完成任务的基础和安全保障。本文的研究目的在[j])可按下式计算(采用伪代码表示)于从有障碍物的环境中,从起始点到目标点之间规划出一条与if(v[i],v[j]是同一障碍物的顶点){环境障碍物无碰的最短路径。构造出可视图,在可视图的基础if(v[i],v[j]是相邻顶点)上规划出从起始点至目标点的最短避障路径。Distance(v[i],v[j])=sqrt((v[i].x-v[j].x)2+(v[i].y-
6、v[j].y)2)(1)elseDistance(v[i],v[j])=∞//∞用计算机中能表示的最大数代替2基本定义}定义2.1设vi=(xi,yi)(i=1,2,⋯,m),v1=vm+1是平面R2上2)若顶点v[i]∈Object[k],v[j]∈Object[s](k≠s),则计算过程相构成某多边形Pi的m个顶点,如果对任意i,j(i≠j),i,j=1,2,对复杂。倘若i,j两点间无障碍物,可按(1)式计算,否则就要判⋯,m,线段vivi+1与vjvj+1或是相邻且相交于一端点或不相断v[i],v[j]两点构成的路径v(i,j)与障碍物多边形顶点v[a],v[a+1]交,
7、则称多边形Pi为简单多边形。简单多边形集合记为P=组成的边界v(a,a+1)是否相交,根据相交结果来计算Distance(vi,{Pi
8、i=1,2,⋯K},K为简单多边形的个数;简单多边形Pi可表vj)的值。这里v[a],v[a+1]∈Object[l](l=1,2,⋯,a=1,2,⋯)。倘若相示为Pi={vj
9、j=1,2,⋯,m}。交,则将相应值置为∞。定义2.2障碍物多边形用Object[i]表示,i=1,2,3⋯且当且判断路径v(i,j)和边界v(a,a+1)有无交点,可以计算由v(i
