一种偏向目标型地RRT算法实现

《一种偏向目标型地RRT算法实现》由会员分享，可在线阅读，更多相关《一种偏向目标型地RRT算法实现（11页珍藏版）》请在装配图网上搜索。

1、word一种偏向目标型的RRT算法实现摘要：本文针对根本快速扩展随机树(RRT)算法存在搜索过于平均、效率低下、用时较长的缺陷，提出了一种偏向目标型的改良型RRT算法。这种算法在生成随机点时以一定概率选择最终目标点作为局部目标点，使树的扩展有一个趋向于最终目标点的趋势，从而加快了算法的收敛速度，优化了规划路径。最后通过Matlab程序仿真，在二维平面上验证了改良型算法相对于根本算法的优越性。关键词：路径规划、RRT算法、偏向目标型一. 引言机器人学是当今科学技术研究的热点问题，它会聚了各个尖端学科最先进的研究成果。科学家们从上世纪40年代开始着手研制机器人到如今，机器人的开展主要经历了三次技术

2、变革。从最简单的第一代机器人到现在的第三代智能机器人，机器人从只会机械的执行命令逐渐演变成利用各种先进的传感器自动的学习环境，适应环境，并完成人类下达的任务。路径规划问题是机器人研究中的重要的组成局部，它的重点就是要使机器人自主并且安全的从起始位姿移动到目标位姿。机器人路径规划主要分为全局路径规划和局部路径规划两大方面。全局路径规划是一种利用环境全局信息的方法，它通常将周边环境信息存储在一地图中，并且利用这地图寻找可行路径。全局路径规划的优点是有利于找到全局可行解和最优解，但是它的运算时间长，不适用于快速变化的动态环境。常用的全局路径规划方法有栅格法、可视图法、拓扑法和自由空间法等。局部路径规

3、划只考虑机器人当前能探测到的环境信息，运算速度快、反响迅速，非常适用于动态环境。但其缺点是算法可能无法收敛，不能保证机器人一定能够到达目标点，而且找到的可行路径可能会偏离最短路径。常用的局部路径规划算法有人工势场法、模糊逻辑法、神经网络法和遗传算法等等。RRT算法是最近几年才开展起来的，并且应用比拟普遍的一种路径规划算法。它在处理非完整约束的路径规划问题时具有相当大的优势，因为它可以将各种约束集成到算法本身之中，因此对环境要求较低。而且该算法概率完备，在理论上肯定能找到可行路径。但其缺点是搜索过于平均，算法效率较低，而且规划出的路径往往偏离最短路径。本文针对RRT算法存在的缺陷，提出了一种改良

4、的偏向目标型的RRT算法，该算法有效的解决了搜索过于平均的问题，提高了算法效率，而且规划出的路径是更接近于最短路径的次优路径。二. RRT算法的根本原理RRT算法在路径规划时以状态空间中的一个初始点作为根节点，通过随机采样逐渐增加叶节点的方式，生成一个随机扩展树。当随机树中的叶节点中包含了目标点或目标区域时，便可在随机树中找到一条从根节点到目标点的路径。RRT的扩展方式如如下图1所示。图 1 RRT算法扩展过程图1中T表示当前存在的扩展树，表示随机点，表示离随机点最近的一个树节点，然后在和的连线上以步长step为单位截取一个新节点，如果没碰到障碍物，如此将参加到扩展树T中。重复以上步骤直到到达

5、目标区域如此算法完毕，此时可在树T中找到一条起点到目标点的路径。为了便于计算机编程实现，我们将RRT的构建过程归纳为以下两个表格。其中表1为各参数意义，表2为RRT构建流程。表 1 RRT算法中的各参数意义S所有空间无障碍空间有k个节点的随机树起始点目标点step步长Dis(q1,q2)S中两点之间的距离表 2 RRT算法构建流程1=2判断|-|step,假如是，转到步骤8，不是，转到步骤33生成随机点4找出使Dis(,)Dis(q,)5在和的连线上求使Dis(,)=step,并且，假如存在这样的，转到步骤6，假如不存在，转到步骤36在扩展树上增加节点，7判断|-|step,假如是，转到步骤8

6、，不是，转到步骤38完毕三. 改良的RRT算法虽然RRT算法概率完备，在理论上总能找出一条可行路径。但是由于其扩展新节点的方式是在全空间随机产生的，一方面造成扩展树在全空间分布过于平均，算法效率较低；另一方面规划的路径质量不高，通常偏离最短路径较大。针对以上缺陷，我们希望对根本的RRT算法进展改良。经过分析我们得知造成RRT算法上述缺陷的根源是在扩展新节点时，随机点是在全空间随机产生的。借鉴启发式算法的灵感，我们可以在确定随机点时让随机点以一定的概率等于目标点。这样树的扩展就有一个趋于目标点的趋势，而不是在全空间随机分布，从而提高了算法的搜索效率，而且由于树节点的扩展是趋向于目标点的，理论上规

7、划出来的路径也会更加接近于最短路径。还应注意的是改良后的算法在概率上依然是完备的。通过以上分析，我们知道改良的RRT算法流程和根本的RRT算法流程大致一样，只要把第二节中表2的第3个步骤进展如下的改写即可。（1） 生成随机点；（2） 给定一个0到1的偏置变量Bias，生成一个0到1的随机数rand；（3） 如果randBias,如此=；否如此， 不变。四. Matlab仿真实验本文仿真是在二维平面上进展的，将整个平面划分为了有障碍局部和无障碍物局部，如如下图2所示。图 2环境模型示意图地图尺寸为100*100，其中白色区域代表无障碍空间，机器人可以随意行走；黑色区域表示障碍物空间，机器人不能通

8、行。为了仿真的方便，这里的障碍物都选择为圆形，这不影响算法验证的可靠性。 分析可知扩展树的每个节点有三个必要要素，分别是节点的x，y坐标以与其父节点。因此我们定义节点的数据结构如下：其中表示节点在二维平面上的坐标，表示节点的父节点序号。考虑到起点作为根结点，其没有父节点，因此定义它的父节点序号为0。1分布障碍地图 起点5，80，终点90，70图 3 路径规划图，RRT算法(左)，改良RRT算法(右) 上图中蓝色的“*点表示扩展树的所有节点，红色的曲线表示规划得到的路径。通过图3的比照明显可以看出在分布障碍地图中，偏向目标型RRT算法得到的扩展树节点数更少，这说明算法的效率更高。观察路径曲线可以

9、看出偏向目标型RRT算法得到的路径更优。2狭窄通道地图 起点1，1，终点90，90图 4路径规划图，RRT算法(左)，改良RRT算法(右) 从图4中可以看出在狭窄通道地图中，我们可以明显的观察到根本RRT算法在搜索时表现出来的搜索过于平均，算法效率低下的缺陷，而且规划得到的路径也偏离最优路径较大。而改良后的偏向目标型RRT算法表现出了强烈的趋向于目标点趋势，而且规划得到的路径也非常接近于最优路径。3复杂随机地图起点1，1，终点90，90图 5路径规划图，RRT算法(左)，改良RRT算法(右) 通过图5，我们也可以看出改良后的RRT算法在复杂随机地图中也表现优异，证明了偏向目标型RRT算法的优越

10、性。五. 总结本文针对根本RRT算法存在搜索过于平均，算法效率低下，规划路径偏离最短路径较大的缺陷，分析其缺陷原因在于随机点确实定在全空间分布过于平均导致的。借鉴启发式算法的思想，我们提出了一种确定随机点的新方法，即让随机点以一定的概率等于目标点，这样就使随机树的扩展有一种趋向于目标点的趋势，从而解决了随机点分布过于平均的缺点。最后通过Matlab仿真对两种算法的结果比照分析得到，改良后的偏向目标型RRT算法相对于根本RRT算法，无论在算法效率还是路径质量，都表现出了很大的优越性。参考文献1王全.基于RRT的全局路径规划方法与其应用研究D.国防科学技术大学,2014. 2加东.基于RRT算法的

11、非完整移动机器人运动规划D.华东理工大学,2014. 3林,贾菁辉.基于比照优化的RRT路径规划改良算法J.计算机工程与应用,2011,47(3):210-213,228. 4贾菁辉.移动机器人的路径规划与安全导航D.理工大学,2009. 5周培培.未知环境下机器人路径规划算法的研究D.科技大学,2014. 6猛.基于智能优化与RRT算法的无人机任务规划方法研究D.航空航天大学,2012. 7王滨,金明河,宗武等.基于启发式的快速扩展随机树路径规划算法J.机械制造,2007,45(12):1-4. 8宋金泽,戴斌,单恩忠等.一种改良的RRT路径规划算法J.电子学报,2010,38(z1):22

12、5-228.9乔永兴.自主式移动机器人的路径规划D.某某大学,2003. 10磊,叶涛,谭民等.移动机器人技术研究现状与未来J.机器人,2002,24(5):475-480.11刚,林成.复杂环境下路径规划问题的遗传路径规划方法J.机器人,2001,23(1):40-44.附录本文中使用的Matlab程序%主程序function BiasGoal_RRTMap=CreateMap(1); %创建有障碍物的模拟地图，输入参数为不同的地图类型step=5; %步长startNode=1,1,0; %起点endNode=90,90,0; %终点tree=startNode; %根结点if(norm(

13、startNode(1,1:2)-endNode(1,1:2)=step)&(collision(startNode,endNode,Map)=0) path=startNode(1,1:2);endNode(1,1:2);else success=0; while success=0 tree,flag=extendTree(tree,endNode,step,Map); success=flag; endendpath=findPath(tree);plotmap(Map,path,tree);%创建地图，有三种不同类型的地图function Map=CreateMap(num)if nu

14、m=1 %分布障碍地图 Map.BarNum=3; Map.LLCd=0;0; %地图左下角坐标 Map.URCd=100;100; %地图右上角坐标 radius=20;15;20; %障碍物半径 barCenter=33,75;38,30;75,50; %障碍物中心点坐标 Map.radius(i)=radius(i); Map.cx(i)=barCenter(i,1); Map.cy(i)=barCenter(i,2); endendif num=2 %狭窄通道地图 Map.BarNum=2; Map.LLCd=0;0; Map.URCd=100;100; radius=23.75;23

15、.75; barCenter=50,76.25;50,23.75; Map.radius(i)=radius(i); Map.cx(i)=barCenter(i,1); Map.cy(i)=barCenter(i,2); endendif num=3 %复杂随机地图 Map.BarNum=100; Map.LLCd=0;0; Map.URCd=100;100; MaxRadius=2.5; Map.radius(i)=MaxRadius*rand;Map.cx(i)=Map.LLCd(1)+Map.radius(i)+(Map.URCd(1)-Map.LLCd(1)-2*Map.radius(

16、i)*rand;Map.cy(i)=Map.LLCd(2)+Map.radius(i)+(Map.URCd(2)-Map.LLCd(2)-2*Map.radius(i)*rand; endend%根本RRT算法程序function newTree,flagReach=extendTree(tree,endNode,step,Map)flag=1;while flag randPoint=(Map.URCd(1)-Map.LLCd(1)*rand,(Map.URCd(2)-Map.LLCd(2)*rand; distmp=tree(:,1:2)-ones(size(tree,1),1)*rand

17、Point; mindis,minnum = min(diag(distmp*distmp); pvector=randPoint-tree(minnum,1:2); newPoint=tree(minnum,1:2)+pvector/norm(pvector)*step; if collision(newPoint,tree(minnum,1:2),Map)=0 newNode=newPoint,minnum; newTree=tree;newNode; flag=0; endendif(norm(newPoint-endNode(1,1:2)=step)&(collision(newPoi

18、nt,endNode(1,1:2),Map)=0) flagReach=1;else flagReach=0;end%改良后的偏向目标型RRT算法程序function newTree,flagReach=BiasextendTree(tree,endNode,step,Map)flag=1;Bias=0.5;while flag randPoint=(Map.URCd(1)-Map.LLCd(1)*rand,(Map.URCd(2)-Map.LLCd(2)*rand; if randBias randPoint=endNode(1:2); end distmp=tree(:,1:2)-ones

19、(size(tree,1),1)*randPoint; mindis,minnum = min(diag(distmp*distmp); pvector=randPoint-tree(minnum,1:2); newPoint=tree(minnum,1:2)+pvector/norm(pvector)*step; if collision(newPoint,tree(minnum,1:2),Map)=0 newNode=newPoint,minnum; newTree=tree;newNode; flag=0; endendif(norm(newPoint-endNode(1,1:2)=st

20、ep)&(collision(newPoint,endNode(1,1:2),Map)=0) flagReach=1;else flagReach=0;end%检测新节点和每一个障碍物是否有碰撞，假如有如此返回1function collision_flag = collision(node, parent, Map);collision_flag = 0;for sigma = 0:.2:1, p = sigma*node(1:2) + (1-sigma)*parent(1:2); for i=1:Map.BarNum, if (norm(p(1);p(2)-Map.cx(i); Map.c

21、y(i)=Map.radius(i), collision_flag = 1; break; end endend%随机扩展树完成后，根据每个节点父节点的序号找出可行路径function path=findPath(tree)lastnodenum=size(tree,1);path=tree(lastnodenum,1:2);parentnodenum=tree(lastnodenum,3);while(parentnodenum=0) path=tree(parentnodenum,1:2);path; parentnodenum=tree(parentnodenum,3);end%画出地

22、图以与路径function plotmap(Map,path,tree)close all;th=0:2*pi/100:2*pi;axis(0,100,0,100);hold on X = Map.radius(i)*cos(th) + Map.cx(i); Y = Map.radius(i)*sin(th) + Map.cy(i); fill(X,Y,k); %障碍物 end plot(tree(:,1),tree(:,2),*); %所有节点 plot(path(:,1),path(:,2),r,linewidth,3); %路径课程论文评分标准表评价容具 体 要 求分值评分查阅、收集资料查阅一些相关资料，收集素材，进展参考。10选题、构思、主见选题新颖，构思全面，对问题有较深刻的认识，有一定独特见解。10逻辑结构结构合理，层次清楚，条理清晰，逻辑性强。10撰写质量格式规，语句通顺，语言准确，书写工整，达到论文要求的字数。20学过知识的运用结合学过的容，充分运用掌握的知识，充分表达自己的观点。20分析与阐述问题的能力所阐述问题清楚，突出重点，论文表现出对实际问题有较强的分析能力和概括能力，并所论述的事项有说服力。30总分11 / 11