未知环境下改进的基于RRT算法的移动机器人路径规划.pdf

未知环境下改进的基于RRT算法的移动机器人路径规划.pdf

《未知环境下改进的基于RRT算法的移动机器人路径规划.pdf》由会员分享，可在线阅读，更多相关《未知环境下改进的基于RRT算法的移动机器人路径规划.pdf（9页珍藏版）》请在冰点文库上搜索。

第22卷第3期2009年6月模式识别与人工智能PR&AIV0122JunNo32009未知环境下改进的基于RRT算法的移动机器人路径规划康亮赵春霞郭剑辉（南京理工大学计算机科学与技术学院南京210094）摘要将快速扩展随机树（RRT）算法与基于滚动窗口的路径规划相结合，提出一种改进的移动机器人路径规划算法该方法利用机器人实时测得的局部环境信息，以滚动方式进行在线规划，克服了RRT算法通常只能在已知环境中进行移动机器人路径规划的限制，拓展了应用范围规划时只考虑窗口环境地图，不必计算障碍物边线的解析式，节省了存储空间，算法实时性得以保证在此基础上，算法引入启发式估价函数，使得随机树易于朝目标点方向生长同时，运用回归分析生成新节点，避免了可能产生的局部极小，增强了算法搜索未知空问的能力最后仿真实验验证了该方法的有效性关键词移动机器人，路径规划，滚动规划，快速扩展随机树（RRT）中图法分类号TP24ImprovedPathPlanningBasedonRapidly-ExploringRandomTreeforMobileRobotinUnknownEnvironmentKANGLiang，ZHAOChunXia，GUOJianHui（CollegeofComputerScienceandTechnology，Na研ngUniversityofScienceandTechnology，Nanjing210094）ABSTRACTAnimprovedpathplanningalgorithmisproposedbycombiningrapidlyexploringrandomtree（RRT）androllingpathplanningInthisalgorithm，thereal-timelocalenvironmentinformationdetectedbytherobotisfullyusedandtheon-lineplanningisperformedinarollingstyleTherefore，theRRTalgorithmcallbeusedinbothknownandunknownenvironmentOnlythelocalenvironmentalmapiscalculatedintheplanningtoimprovetheplanningefficiency，andthustheplanninginrealtimeisguaranteedThecalculationofanalyticalexpressionsoftheobstaclecanbeignoredHence，thememoryissavedgreatlyBasedonthealgorithmofrapidly-exploringrandom，theheuristicevaluationfunctionisintroducedintotheimprovedalgorithm，80thattheexploringrandomtreecangrowinthedirectionoftargetpointTheregressionanalysis，whichavoidslocalminimum，enhancesthecapabilityofsearchingunknownspaceThesimulationresultsverifytheeffectivenessoftheimprovedalgorithmKeyWordsMobileRobot，PathPlanning，RollingPlan，RapidlyExploringRandomTree（RRT）国家863计划资助项目（No2006AA042238）收稿n期：

20080714；修回日期：

20081l一10作者简介康亮，男，1980年生，博士研究生，主要研究方向为智能机器人、优化算法、路径规划E-mail：

kangliang0912yahoocornca赵春霞，女，1964年生，教授博士生导师，主要研究方向为智能机器人、虚拟现实、仿真系统郭剑辉，男，1983年生，博士，主要研究方向为模式识别、机器人导航、信息融合万方数据338模式识别与人工智能22卷1引言移动枧器入技术是近年来发展起来的一门综合学科，集中了机械、电子、计算机、自动控制以及人工智能等多学科最新研究成果，代表了机电一体化的最高成就J在移动机器入榻关技术的硒究中，导航技术是其核心，而路径规划是导航研究的一个重要环节和课题所谓路径规划是指移动机器人按照某一性能指标（妇距离、时闻、能量等）搜索一条跌起始状态到目标状态的最优或次优路径珏】传统的路径规划方法主要有，人工势场法、模糊觏刚法、遗传算法、久工享孛经网络、模羧退灭算法、蚊群优化算法、粒子群算法等+这些方法在解决一般的路径规划问题时有一定的优越性，但要应用于非完整性约束规划闼遂还存在很多闻瑟。

巍菲完整缝巍划和运动动力学规划恰恰又是机器人学及其他成用的一个重要领域同时这些方法大都需要在一个确定佳空闯内对藩褥物进行确定酶建模秘描述，计算复杂度与机器人自由度呈指数关系，不适合解决多自由度机器人在复杂环境巾的规划快速扩展隧槐树（RapidlyExploringRandomTree，RRT）算法旧。

41是近几年发展起来的基于采样的单凌询路径规划方法，目前应用较广泛。

基予采样的单查询路径规妫方法通过对状态空闻的随枫采样，把搜索导向空白区域RRT算法因为避免丫对空间的建模，与其他方法棚比有独特的优势该算法高效的搜索特性，使其适合解决高维空间多富幽度机器人的复杂约束下的运幼规划问题，能直接应用到非宠整性约束或非完整性动力学约束规划中这种基于隧视采样的运动规翊方法由于其箨法的随机性，所以具有概率完备性在有解的前掇下，算法获得露行筋有保证。

但该算法的固有规划方式限制了其进一步应用：

1）隧机搜索均匀一致在全局空间，导致算法无谓耗费代价较大；2）先全局搜索构建隧枧树，再一次性规划路径，导致算法通常只能应用在已知环境中，实时戚用性较差；3）路径的搜索树Elj随机采样点生成，导致规划出的路径经常不是最优路径。

借鉴文献5中的滚动规划思想，本文采用反复的局部路径规划代替一次性的全局路径规划结果，实瑷了RRT算法在未知环境下移动枧器人路径规划中的应用利用滚动规划概念，无需对障碍物进行确定的建模，将随机采样限制在滚动窗口，避免全局采撵，大大减少瓣刘时阁，提高算法的实时性根据舄发式函数生成滚动密蠢子瓣标点，保诞窥划路径的最优性为避免产生局部极小，利用回归分析扩展随机树毅萤点，算法搜索未知空间的能力因此大大增强。

2基本的快速扩散随机树算法21随机树构建阶段欲初始绞姿（状态）点名瓣；出发构建隧槐树F。

如图1所示钿一7图1基本的RRT构建过程Fig1ConstructionofbasicRRT在位姿空间中随枧选择一个位姿（状态）点茁。

m遍历r，找到r上离石。

最近距离的节点菇。

，然后在控制输入集U里选择输入UEU（如转向角、速度等）作耀在茗一上，枧器入溅着菇一到戈。

矗。

蔹照状态转换方程产生满足全局约束的候选路径集合，经历时间，到达个新状态构成戈。

集合选择使褥茗。

到达并。

胡距离最近懿控制输入U作为最佳控制输入依次产生新状态，直至到达爵标状态，随机树构建结束2+2路径产生阶段从目标状态点出发，找到父节点，依次进行，直歪到达起始状态点，即树根这样就规划出从起始状态点到达目标获态点满足全弱积微分约束酶路径以及在每一时刻的控制输入参数因为在搜索的生成过程中充分考虑了机器人客观存在的微分约束（如菲完整约束、动力学约束、运动凌力学约束等），因而算法规划出来的轨迹合理性较好，但算法的随机性导致其只能概率完备隧税算法泼损失完备性为代价来提离挽行效率，适合解决高自由度机器人在复杂环境中的运动规划，合理1生较好。

万方数据3期康亮等：

未知环境下改进的基于RRT算法的移动机器人路径规划3393滚动规划移动机器人在运动过程中能探知其传感范围内有限区域的环境信息，这部分信息必须充分利用因此解决这一问题的指导思想是，采用反复进行的局部优化规划代替一次性全局优化的结果，并在每次局部优化规划中充分利用该时刻最新的局部环境信息滚动规划算法卜141的基本原理如下1）环境信息预测在滚动的每一步，机器人根据探测到的视野内的信息或所有已知的环境信息，建立环境模型，包括设置已知区域内的节点类型信息等2）局部滚动优化将上述环境信息模型看成一个优化窗口，在此基础上，根据目标点的位置和特定的优化策略计算出下一步的最优子目标，然后根据子目标和环境信息模型，选择局部规划算法，确定向子目标行进的局部路径，并实施当前策略，即依所规划的局部路径行进若干步，窗口相应向前滚动3）反馈信息校正根据局部最优路径，驱动机器人行走一段路径后，机器人会探测到新的未知信息，此时可根据机器人在行走过程探测到的新信息补充或校正原来的环境模型，用于滚动后下一步的局部规划局部子目标是在滚动窗口中寻找一个全局目标的映射，它必须避开障碍物，且满足某种优化指标子目标的选择方法反映了全局优化的要求与局部有限信息约束的折衷，是在给定信息环境下企图实现全局优化的自然选择基于滚动窗13的路径规划算法依靠实时探测到的局部环境信息，以滚动方式进行在线规划在滚动的每一步，根据探测到的局部信息，用启发式方法生成优化子目标，在当前滚动窗口内进行局部路径规划，然后实施当前策略（依局部规划路径移动一步），随滚动窗口推进，不断取得新的环境信息，从而在滚动中实现优化与反馈的结合由于规划问题压缩到滚动窗口内，与全局规划相比其计算量大大下降4启发滚动快速扩散随机树算法41位姿空间建模设在工作区域分布着一个或多个障碍物，将移动机器人模型化为点状机器人，同时工作区域中障碍物根据机器人的实际尺寸进行相应的膨化处理机器人无全局环境信息，令c代表位姿空间，是所有机器人可能位姿的集合令C。

h=PCrob（p）nobs，表示C空间障碍物Ch。

=CC表示自由空间C。

h与Ch。

均为C的子集，具有相同的边界因此机器人路径问题的几何约束条件可表示成T（p；，P。

）机器人路径规划就是找到一条从初始状态P，C。

到一个目标状态P。

C仟。

的一条路径一条轨迹就是被定义为一个时间参数化的连续路径丁：

0，T一ch。

设环境中包含静态障碍物，一个碰撞检测算法能够有效检测一个给定的位姿状态是否在障碍物中42构造滚动窗口在实际应用中，环境对于机器人来说往往只是部分已知甚至是完全未知的不完整环境信息下的机器人导航通常是基于传感器数据的本文只考虑二维平面的运动规划问题机器人由于车轮滑动等因素造成的运动误差不予考虑以周期方式驱动，在滚动的每一步，定义以机器人当前位置为中心的区域为优化窗口而Win（p月（t）=PPC，a（p，PR（t）r称为机器人在P。

（t）处的视野域，亦即该点的滚动窗口，其中r为机器人传感器的探测半径在构造滚动窗口时，只利用传感器的读数进行路径规划，不必计算障碍物边线的解析式这样可节省存储空间，提高计算速度局部子目标最优点Di由收敛标准评价函数决定，在下一节中将说明选择标准的评价函数子目标收敛标准的选择反映了全局优化的要求与局部有限信息约束的折衷，是在给定信息环境下企图实现全局优化的自然选择该区域的环境模型，一方面是全局环境信息向该区域的映射，另一方面还补充了传感器系统检测到的原来未知的障碍物以当前点为起点，根据全局先验信息确定该窗口区域的局部目标，根据窗口内信息所提供的场景预测进行规划，找出适当的局部路径，机器人依此路径移动，直到下一周期43随机采样规划滚动窗口随机树以当前路径点P。

（t）为起始点名。

，构建以探测半径为窗口半径范围内的随机树该随机树表示为瓦，是一个最多有K节点的RRT，且TkCh。

戈为瓦的节点，石死，xii。

为瓦的根节点如图1，令并酬为滚动窗口C空间中一个随机选取的位姿状态，且x。

dEC慨由于节点戈训选取的任意性，导致了随机树的生长形状具有随机性，从而导致规划的路径优化性也存在随机性万方数据模式识别与人工智能22卷为减少路径规翅的随机性，使隧耄氇树有向毯标点生长的特性，本文在RRT算法的撼础上，根据最短路径思想，在构建随机树时引入启发式估价躏数。

使随机树构建时既町绕过障碍物，又可赣着目标点方向生长在路径规划中引入启发信息能提高搜索的效率，有利于减少随机树生长的隧枧性，并使规划出的路径接近最短路径。

令Road（髫。

，戈：

）代表随机树中两个位姿节点间的路径代价，Dis（戈；，茁：

）代表随机树中两个位姿节点间的欧几里德距离类似于A算法，本文为随机树中每个节点定义一个估价函数；厂（省）=g（并）+毳（茗）。

其中g（x）=Road（x，茗嘲）是随机节点菇浏到树中节点茹所需的路径代价h（髫）为启发估价函数，这照取随机节点x。

到目标终点聋酬的平腼距离为饿价值，h（x）I-Dis（x。

崩，舅吲）。

因此艇茗）表示从节点z经随机节点石。

到目标节点菇州的路径估计值遍历滚动窗口内随机树r，取估价函数最小值的节点菇一，有尺菇）=min（f（髫）。

这使暑随撬耩沿着到目标节点估价值只盏）最小的方向进行扩展。

在控制输入集己，里选择输入M威U（如转向角、速度等）作焉在菇上，在点菇一与茹一之闻求点菇。

髫。

必须满足菇。

Ch。

且Dis（戈。

，Xnear）=p的条件，其中p0为RRT生长的最小单位长度，称为步长。

如果存在茗，劂氛增加一个新节点。

令瓦+表示新的RRT，则瓦=瓦+。

+髫。

否则重新选取髫。

州，重复以上过程调用隧视树扩展函数添加薪节点时，可麓会骞3种情况：

1）新节点戈。

与随机节点搿刊间的距离小于步长，则茗就是茗刊；2）可以找到新节点名将其加入RRT，但搿。

不是随枧节点茗训；3）所计算的新节点石位于c。

h，则重新选择扩展随机树扇子在随机树生长中弓|入导向翻标的启发佑狯因子，叶节点菇。

，总是选择离目标最近的节点，这可能会使随机树遇到局部极小值问题因此随机树生长的新节点茗。

必须要克服这个问题，引导随枫树更好地探索未翔空间本文利用统计学中回归分析纠舷成新节点，将RRT算法探索未知空阚的能力进一步增强以避免因启发估价因子导致的局部极小其思想是探索以前到过的空间是无用的，而且容易陷入局部极小引进网麴分橱RegressionAnalysis）是考察蓑节点与其他节点之间关系，利用回归函数约束，使得随机树不探索以前到过的空间，因此避免局部极小凝节点生成方法是遍历隧掇楗，如果茗。

与其父节点茗的距离小于并。

与扩展树上其它任意节点的距离，刚选择该蒂点为随枫树薪生节点。

圈2解释了新节点的选择过程（a）一个节点的可能扩展（b）树中节点的所有扩展（魏）Possibleexpansionsforanode（b）Allexpansionsintree巨2薪节蠢懿选择Fig2Selectionofnewnode在图2中，实心点表示树审淼骞节点，空心点表示树中节点可能的扩展新节点线段表示随机树中连接各节点的边图2（a）表示一个节点在随机树生成薪节点嚣寸昀可能扩旋。

撼圈霞起的空心节点表示不符合回归函数约束，剩下唯一一个空心节点到其父节点的距离小于该节点到随机树上任意节点的距离，因茈选择该节点作为随机树扩展静新节点。

图2（b）表示随机树上节点的所有可能扩展可以看出，本文的随机树具有强烈探索未知空间的倾向，这祥使得规鲻路径能绕开障碍物和走出局部极小，继续向着目标点方向进行探索，利于随机树的叶节点向着空旷未探索过的地带发展。

综上新述，滚动窗瑟内随槐树构建的具体步骤如下stepI对滚动镦嚣随机树r初始化，r开始只包含初始节点名step2滚动窗口Ck空间中随机选择一个状态舅酬。

step3根据最短路径思怒寻找树r中和x酬距离最近的节点戈一，step4选择输入狂，使机器人状态由戈到Xnwstep5网到step4，确定戈一是否符合回归分析，不符合则step6将z作为随机树r的一个新节点，雎则被记录在连接节点搿。

和z一的边上滚动窗弱状态空阚进行X次采样后，遍历隧槐树，根据启发估价思想寻找滚动窗口子目标茗。

根据子目标收敛标准评价函数，j鬣瓦l灭菇。

b）=rain苁菇）万方数据3期康亮等：

未知环境下改进的基于RRT算法的移动机器人路径规划这里的八髫）=g（髫）+h（戈）其中g（髫）=Road（x训。

，茗）为随机树从初始节点戈。

到节点名的路径代价，h（菇）为随机树节点菇到目标终点的估价值，估价函数中h（石）的选取影响求解最优路径的效率和结果为保证找到最短路径（最优解的）条件，对于2D环境来说，一般取两节点间欧几里德距离（直线距离）Dis（z，x酬）作为估价值滚动窗口的状态空间采样次数和窗口大小相关，按不同应用场合，配置不同参数确定滚动窗口内的子目标后，搜索滚动窗口随机树，规划窗口内从起始节点到子目标节点的路径，机器人滚动前进到子目标点，进行下一轮的滚动规划RRT机器人这样不断滚动前进，直至到达目标终点44收敛性和最优性证明在未遇到障碍物时，子目标节点启发式估价函数是单调递减的，因而此情况下的路径长度是有限的在遇到障碍物时，总是选择估价函数最小值节点为规划路径下一节点，因而此情况下的每一步路径长度也是有限的因此，算法最终会在一个有限长度的路径上停止如果目标终点可以到达，那么规划路径收敛到目标终点的可能性就会得到保证首先定义机器人路径是由一连串的节点组成起点5，目标终点G假设机器人工作在一个有限的几何空间中，环境空间中的每个障碍物都是有限周长，因此有以下结论1）在无障碍环境中，移动机器人的路径节点必定会终止在目标点G2）在未遇到障碍物时，移动机器人的规划路径长度必定是有限长度3）移动机器人绕开障碍物的路径长度将是有限长度下面给出算法的收敛性证明如果移动机器人可以到达目标，那么成功规划的路径长度必定是有限长度证明机器人的路径长度等于未遇到障碍物情况下和避障情况下的规划路径长度之和由结论2），在未遇到障碍物情况下，机器人路径长度必定是有限长度因为机器人工作在一个有限的几何空间中，所以障碍物的个数也必定是有限的而每一个障碍物又都是有限周长，所以在避障情况下，机器人的路径长度也必定是有限长度由结论3），机器人绕开障碍物的路径长度也必将是有限长度因此，算法成功规划的路径长度必定是有限长度下面再给出算法的最优性证明只要移动机器人可以到达目标，那么算法规划的路径长度将是最优证明由上面的收敛性证明可知，如果移动机器人可以到达目标，那么成功规划的路径长度必定是有限长度根据随机树节点启发估价函数定义，每一个子目标节点的选择一定是距离目标终点最近的节点因此，算法成功规划的路径长度必定最优5仿真实验实验环境是用Matlab开发的，运行于PC机，CPU主频512MB环境为30m30m下的矩形区域，障碍物随机设置，大小任意，碰撞半径04m起点设置坐标为（0，0），终点坐标设置为（30，30）图3是基本RRT算法在已知环境下机器人的路径规划可以看到RRT搜索树是随机均匀一致分布的这适用于对地图环境先验已知，然后再实现路径规划对于未知环境下机器人实时路径规划则不适用但也清楚证明了基于RRT的路径规划算法对未知状态空间有强烈的搜索倾向根据这一特点，本文提出滚动RRT，对未知环境下移动机器人实时路径规划进行研究图3基本RRT算法的路径规划Fig3PathplanningofbasicRRT图4滚动RRT算法的路径规划Fig4PathplanningofwilingRRT万方数据342模式识别与人工智能22卷图4是运用滚动RRT算法遴行路径规翘。

由于是滚动探测规划前进，适用于未知环境下的移动机器入路径规划，同时可以看到随机树相比予基本RRT算法，其叶节点数量大大降低此时，扩展树分支有3519个叶节点，路径长度53m，运行时闻369s。

面圈3环境下的RRT搜索树的卧节点为8426个，运行时闻581瓢图4中路径规划是单纯的滚动窗口和RR个结合，没有任何崩发思想弓|黪，随枧搜索到达目标。

图5中同时利用本文提出的启发估价函数来确定滚动窗口内随机树的最近叶节点和目标节点此时，搜索树分支有648个时节点，路径长度44m，运行时闻116s图5癌发滚动RRT算法的路经规划Fig5PathplanningofheuristicwilingRRT因为启发馈份选择距离最小的叶节点进行RRT树扩展，可能会导致局部极小，使得无法完成路径规划，如图6所示为了解决这个增生问题，本文剥髑回归分析来筛选新节点，成功避免了这问题，如图7所示图6癌发滚动RRT算法的鼹郝最，j、Fig6Localminimumofheuristi