机器人RRT快速扩展随机树路径规划算法(快速扩展随机树)

1、 1994-2010 china academic journal electronic publishing house. all rights reserved. http:/脚以酬喇编辐基于启发式的快速扩展随机树路径规划算法“口王滨口金明河口谢宗武口刘宏哈尔滨工业大学机器人研究所哈尔滨巧摘要针对基于随机采样的路径规划缺乏确定性的问题,提出一种具有启发式的多自由度机器人路径规划算法。该葬法在快速扩展随机树葬法的基抽上,引入了启发式佑价函数,使扩展随机树有利于朝目标东方向进行生长。仿 真结果表明,提高了复杂环境下机器人路径规划的效率,保证了规划的路径接近于最姐路径,对同一任务的规划具有一定的

2、可重复性。关妞词机器人路径规划快速扩展随机树启发式函数中圈分类号代文献标识码文章编号以,一侧刃一“通,己一亨朋叱“朋比即一,而即助边己曰二目比心助丫入邓一鸣址公如目加路径规划是智能机器人研究领域的一个重要方向,主要解决在有津碍的环境中,机器人如何自主寻找一条从给定起点到终点适当的运动路径,使其能在运动过程中安全、无碰地绕过障碍物。传统的路径规划有多边形拟合法、遗传算法、栅格法、人工势能法等。但这些方法都需要在一个确定性空间内对障碍物进行确定的建棋和描述,计算复杂度与机器人自由度呈指数关系,不适合于解决多自由度机器人在复杂环境中的规划,一,一。与传统方法不同,基于采样的运动规划方法通过对状态空间

3、中的采样点进行碰撞检测来获取障碍物信息,避免了对空间的建模,能够有效解决高维空间和复杂约束的运动规划问题。快速扩展随机树是目前应用比较广泛的墓于采样的单查询运动规划方法“,。该方法特点是能够快速有效地搜索高维空间,通过状态空间 的随机采样点,把搜索导向空白区域,从而寻找到一条从起始点到目标点的规划路径,适合于解决多自由度机器人在复杂环境下和变化场景中的运动规划。但是算法也存在问题。由于利用随机采样生成扩展树,这将导致对同一任务重复规划会产生不同的路径,使机器人在完成同一任务时,可重 复性比较差。同时用于寻找路径的扩展树由随机采样点生成,所以规划出的路径经常远离最短路径。本文根据算法中估价函数的

4、思想,提出一种改进的具有启发式的算法,简称一算法。该算法以算法为基础,在生成国家“肠”计划项目编号以巧收稿日期年月扩展树时,根据多次随机采样点到目标点的估计代价,选择最优节点加人扩展树,使扩展树的生长 方式按采样点估价函数值最小的方向生长,直到目标点。通过加人具有启发性的估价函数,该算法克服了机器人使用算法完成同一任务时重复性差的缺点,同时可以保证规划的路径是接近最短路径的次优路径。算法的基本原理是一种在多维空间中有效率的规划算法。每次规划是以状态空间中的一个初始点作为根节点,通过随机采样,逐渐增加叶节点的方式,生成一个随机扩展树。当随机树的叶节点中包含了目标点或目标区域中的点,便可在随机树中

5、找到一条以树节点组成的从初始点到目标点的规划路径。对机器人环境建模,设是环境中一个刚体或系统的状态空间,且。侧。在的工作空 间,其中包括机器人的位里坐标和方向角度。快速扩展随机树的构建过程如图所示,兀为一个拥有无个节点扩展树,二为乳的节点,且兀。口剐,。为与障碍物无碰撞的机器人自由状态空间。同时定义 耘为初 始状态起点,州为目标状态终点,二州为目标区域。令二为空 间中一个随机选取的位姿状态,且漏。在兀中找出距离 耘“最近的节点忘,设、。俪,令及,妇代表两个位姿状态间的几何距离,则。与、的关系可表示为、二,续刀,二,。在。与的连线上求丸二,、,必 须满足、加且,、,的条件,其中,为生长的最小单位

6、长度,称为步长。如果存在翻肠机械制造卷第期,国 1994-2010 china academic journal electronic publishing house. all rights reserved. http:/蕊嘛舔辑黯嘿凡,则兀增加一个新节点。令兀,表示新的,则乳,兀、。否 则 重新选取耘“,重复以上过程。算 法的羞 本步骤如下二,二州二一图的构建迁一二二拍加二,二浏峨花二二朋心,浏杨二户场,二创一二心,盆二,江护曰二曰,“二一州”山卜旧比的二娜州妇其中函数是表示扩展树的叶节点,它有个返回值丫代表没有找到新的叶节点,代表找到新的 叶节点二,代表到达目标节点二州。当扩展树到达目

7、标节点后,返回找到的路径二二州。在中,函数。心表示随机选取采样点二函数,表示在扩展树中寻找距二最近的叶节点函数。成,叮,完成从二到二的方向上以固定的步长计算出新的叶节点,计算公式为二二一二一“二。一 二一“其中“代表欧拉范数定义的两点间的距离。改进的下算法由于算法中扩展树生 长 时,是以规划起点二作为树的根节点,在自 由空 间中随机采样二,根据式来确定新的叶节点二,直到树的叶节点包含了二州为止。二选取的任惫性,导致了扩展树的生长形状具有 随机性,从而导致从树的根节点二到 叶节点二浏规划的路径有时接近最短路径,有时远离最短路径,也存在随机性。并且对同一任务的规划缺乏可重复性。为减少路径规划的随机

8、性,使扩展树具有向目标点生长的特性,本文在算法的基础上,根据搜索算法中寻找最短路径的思想,在构建扩展树时引人了启发式估价函数。使扩展树构建时即可绕过障碍物,又可朝着目标点方向生长。在路径规划中 引人启发信息能提高搜索的效率,有利 于减少扩展树生长的随机性,并使规划出路径接近最短路径。奋算法是一种启发式搜索算法,是计算网络路径最有效的算法,它通过选择合适的估价函数使其寻找最优路径。其核心思想是在路径中 的任何一个节点,都有一个估价函数,可表示为以司,其中是节点从初始点到目标点的估价函数,到是在状态空间中从初始节点到节点的实际代价,是从到目标节点最佳路径的估计代价。,算法的搜索是沿着到目标节点估计

9、值八最小的方向进行扩展。估价函数中的选取形响求解最优路径的效率和结果。为保证找到最短路径 最优解的条件,对于环境来说,一般取两节点 间欧几理德距离直线距离做为估价值,即八。二一。二一。犷一一叮。对算法中扩展树增加叶节点二时,引人了启发函数,通过计算每个节点到目标点的估价值来选取新增的叶节点。即在扩展树的生长时,选取一定的随机采样点二,并分别计算出新的临时节点,。计算公式为二一二,动万,二劣一劣式中二一为上次采样刚加人扩展树的新叶节点,为的父节点。选取到目标点估价值最小的节点作为加人扩展树中。由于中创表示从初始节点节点的实际代价,生成扩展树时,班司为一二一劣一一劣一名一“式中盯一代表父节点的实际

10、代价。由于步长为定值,所有备选节点的实际代价值相同,所以中估价函数中可 省略 盯,即司司。这样以启发因子为扩展树生长的启发因子,削弱了选取叶节点二的随机性,保证了扩展树具有向着目标节点生长的特性。但是由于算法中在扩展树生长时,融人了导向目标节点的启发因子,新的叶节点 总是选取离目标最近的节点,这会使路径寻找过程中遇到局部极小值问题。本文利用文献【提出的节点取消复原的方法来解决局部极小问题。其思想是探索以前到达过的状态空间是无用的,而且经常容易陷人局部最小。解决的方回,。机械制造,卷第,期出哈 1994-2010 china academic journal electronic publish

11、ing house. all rights reserved. http:/烫粗娜斟撼姗森初始位置耘。和目标位里知山规划可行的路径。在实验中,起始点杯设为,目标点孙设为,设定步长 为。图为算 法规划的路径,其中细线为构造的扩展随机树,粗线为在扩展随机树上搜索到的路径。由于的随机采样,在 叶节点到达目标点前,探索了很多空旷的区域。图采样点为个,规划的路径长度 为。图采样点 为个,规划的路径长度为。丁二峨二一一不,一,、甲”一。气,城了三。二,城一卜卜。飞犷件,户卜。,止,艺艺卜尹义,、一。厂厂日咧卜、卜盆,犷口记厂汽一,匕二匕二二二二一乙一 一一一二一一一一一峨洲路径长度路径长度一图算法规划的路

12、径径图为算法在与图同样的场景情况下规划的路径。在扩展树增加新的叶节点 时,由于加人了启发函数,可以保证扩展树朝着目标的方向生长,使搜索到的路径接近于最短路径,使机器人每次完成同样任务都具有相对的重 复性 并且在遇到障碍物时,采取取消复原节点,可以使扩展树的生长很快绕开障碍物。图的采样点为,规划的路径长度为图的采样点为,规划的路径长度为。、。二,二,护冬门、, ,扮,、法是如果新的临时节点二,与其父节点一的距离小于二,与扩展树上节点的最近距离,即川肠一,、川、二,此临时节点将被保留否则,将被取消。其中二二为扩展树上距离二,最近的叶节点。这样有利于扩展树的叶节点向着空 旷未探索过的地带发展,使规划

13、的路径既可向着目标点方向进行探索,同时又可绕开障碍物,避免局部极小值问题的发生。算法对中函数进行了改进,具体步骤如下附了二二二朋心脚川二二。心创“石。,二一二期 ”,二,二二二峋江户山山二以坛江一名,山泊目】”械侧记尹,名州,二动一二二肠,甘二一,二一,二,比花叮其中函数,二表示根据随机采样点按式计算出临时节点二函数花界肠一,表示根据取消复原条件对进行筛选,并产生新的叶节点的备选节点组二。函数,表示按二中各节点的估价值,确定出新的叶节点“,并加人扩展树中。该扩展树从根节点二“逐渐生长,直到其叶节点包含了目标点二州或目标区域中的点后,便可找到一条从泊到二州的规划路径。仿真实验本节以点状机器人和自

14、由度机器人为例,通过与算法进行比较,来验证所提出的算法。实验在,内存的计算机上进行。点状机器声的规划这里设定点状机器人没有方向,它的状态空间 即是机器人在场景中的位里二,刃。状态 空间为,其中随机设里个大小任意的障碍物。任惫给定。路径长度路径长度一图叮算法规划的路径图是两种算法在任意的场景环境中的规划路径。实验中,在的状态空 间内,随机设定了个任意 障碍物,起始点为设为,目标点二,设为,设定步长为。图为算法搜索到的路径,长度为,采样点 为。图为算法搜索到 的路径,长度为,采样点为。从实验结果可以看出,算法对同一任务规划的存在随机性,由于随机采样经常导致规划的路径远离优化的最短路径。算法保留 了

15、算法中向空 旷地带探索的特性,可以快速绕过障碍物找到可行的路径 并且对同一任务具有相对的可重复性,减少了每次规划的随机性,满足机器人在复杂环境下的路山肠机械制造卷第”期,国 1994-2010 china academic journal electronic publishing house. all rights reserved. http:/娜姗悲欺易哪衰趾机人平均采样点和规划时阅算算法法平均采样点点平均规划时间减口口狱径规划。表给出 了两种算法在图和图的条件下进行次实验,所完成路径规划的平均采样点 和平均规划时间。从表中数据可以看出,算法由于采样时受到启发函数的引导,在规划效率上有一

16、定的提高。衰点状机人平均采样点和舰划时间算算法法平均采样点点平均规划时间多自 由度机器人的规划在多自 由度机器人的路径规划 实验中,本文对自由度机器人和多指灵巧手进行拉抽屉的操作规划,取位姿空 间为机器人的状态空间。由于机器人有个自由度,状态空间为,氏,氏,氏,各关节角度在一下,司中随机采样。利 用公司的建立仿真场景,调用脚】大学开发的“】函数库来实现场景的碰扭检侧。执行拉抽屉的操作任务分两步骤从初始位里接近抽屉拉开抽屉。当分别给定机器人的初始位二和目标位浏 后,利用和算法各进行次实验。图为机器人和灵巧手 在算法一规划下,完成拉开抽屉的仿真场景。表为机器人在两种算法下的平均采样点和规划 时间。从表中可以粉出,算法保留了算法适 合在 高维空间规划的特性,同时在启发函数的引导下翼嚣要 霆 霭盆图,算法在仿真二对拉抽屉的路径规划减少可以快速地规一一一一囚划出可行的路径。结论本文针对复杂环境下多自由度机器人的路径规划问题,提出了一种较为通用的解决方法。该方法在快速扩展随机树算法墓础上,结合算法中的启发式估价函数,可实现多自由度机器人的在线路径规划。改进的算法使扩展树在启发函数的引导下可快速地向目标扩展,减少了采样点的数目,提高了规划的效率同时减少了路径