基于改进传统RRT算法的机器人路径规划研究

买智强，辛舟，张雪琪

(兰州理工大学 机电工程学院，甘肃 兰州 730050)

近年来，机器人技术的快速发展使得许多与机器人相关的研究变得热门起来，路径规划就是其中之一。为了使机器人安全无障碍地从起始点平稳运行到目标点，给机器人规划一条无障碍路径就是路径规划的主要内容。在此基础上，随着国内外学者的不断研究，逐渐对路径规划提出了新的要求，如最短、最优、最快等。为了达到这些更高的要求，不同学者提出了不同的解决方法。

快速扩展随机树RRT算法(rapidly-exploring random tree)是其中比较典型的一种算法，由LAVALLE S M于1998年提出[1]。这是一种典型的树状结构搜索算法，以初始状态作为根节点，通过在状态空间中进行随机采样，不断扩展，逐步覆盖状态空间的自由区域，并最终覆盖整个状态空间，从而获得一条从初始状态到目标状态的路径。RRT算法结构简单，不需要对障碍物进行精确的建模，不仅适用于二维空间，三维空间同样可以[2]。其缺点在于得到的路径并非最优且由于是随机规划，效率也并不高。FRAZZOLI E等针对RRT算法规划出的路径不是最优解，提出RRT*算法，通过对新节点至根节点的权值比较，找出最优解[3]，也有学者提出过删除低性能节点规划高纬机器人路径[4]，或者是将局部优化引入，进而提高效率[5]。虽然在一定程度上提高了路径的平滑性，但却使得效率大大降低。LAVALLE S M等则提出双向随机树(bidirectional RRT，bi-RRT)用来规划高纬度路径[6]。bi-RRT采用起始点和目标点分别生成一颗自己的随机树，直到二者相遇即得路径。这种方法虽然缩短了时间，但却未能得到最优路径。

近年来，随着智能算法的兴起，结合强化学习，CABALLERO F[7]等提出基于RRT*扩展的快速学习随机树法(rapidly-exploring learning trees，RLT*)。对于RRT算法的随机性，很多人选择引入人工势场法来进行改善，且取得了不错的效果[8-9]。但对于密集障碍物附近的路径仍不能做到动态调整以达到最优。本文则基于人工势场引入障碍物对目标点的斥力函数，动态调整RRT算法在经过障碍物附近时的步长，以此来改善路径。

RRT算法基本原理如下：首先扫描全局地图，获取起始点Po、目标点Pg及障碍物等相关信息，然后以Po为树的根节点，在地图内随机选取一个点Prand，比较随机点Prand与每一个树节点(包括根节点)的距离，选择距离最短的那个。此时最短距离所对应的那个树节点作为该随机点Prand的父节点Pnear，沿Pnear到Prand方向以步长q为间隔选取一个新点Pnew，判断Pnear到Pnew是否经过障碍物。若是则重新选取随机点，再比较再判断；
若未经过障碍物，则将Pnew加入到树节点，作为新的树节点。不断重复这个过程，直到找到目标点Pg，或者达到最大迭代次数[10]。原理图如图1所示。

图1 原理图

从图1中可以看到，传统RRT算法在规划路径时扩展步长是不变的，这样在一定程度上大大简化了算法，但其规划出的路径效果并不好。步长大小完全取决于使用者，长步长一般适用于那些路径长且障碍物情况简单的场合，短步长一般适用于路径较短但路况复杂，需要躲避的障碍物多的情况，但实际应用中碰到的情况往往是以上二者混合的。对于一段长且复杂的路径，既希望能以长步长迅速接近目标，又希望在经过复杂障碍物的时候步长能变短一些，好让得出的轨迹在障碍物附近相对平稳。为解决这个问题，结合人工势场中有关于障碍物斥力场及斥力函数的想法，本文提出在传统RRT算法中引入斥力场及斥力函数。

人工势场法是一种虚拟力法，多用于机器人路径规划，其基本原理是在障碍物和目标点附近构建势力场，通过对机器人位置的势场强度求负梯度后得到势场力。其中，目标点产生引力，障碍物产生斥力，二者的合力方向为机器人运动方向[11]。本文不涉及引力势及引力函数，对其不做介绍。目前常用的斥力函数如下：

(1)

式中：Ur(X)表示在X点处的斥力场；
η是斥力度因子；
ρ0是障碍物的影响范围；
X0表示障碍物位置；
ρ(X,X0)表示位置点X与障碍物之间的最短距离。当距离>ρ0时，机器人的运动不受障碍物的影响。斥力场产生的斥力为斥力场的负梯度，其表达式为

Fr=-∇[Ur(X)]=

(2)

式中：Fr表示斥力；
∇ρ(X,X0)表示障碍物位置指向X位置的单位向量。

当机器人距离障碍物较远时，采用长步长迅速靠近以减少时间，一旦进入障碍物影响范围ρ0，斥力函数启动，减小步长。具体变化如下：

(3)

式中：S为改进后的步长；
k为步长系数；
|Fr|为斥力Fr取标量。当ρ≥ρ0，即未进入障碍物影响范围时，步长固定为q；
当ρ<ρ0机器人进入障碍物影响范围时，动态步长启动，距离障碍物越近，斥力Fr越大，步长S越小。

1)Matlab仿真平台

图2、图3分别是是由Matlab搭建的两张地图。地图规模均是[500，500]，方框即为地图边界，黑色区域代表障碍物，路径规划的起始点为[1，1]，目标点为[490，490]，固定步长q=30，障碍物影响范围ρ0取50。

图2 仿真地图1

图3 仿真地图2

2)传统RRT算法与改进算法

传统RRT算法路径规划结果如图4、图5所示。图中，与目标点相连的黑色细线表示最终路径。为了便于观察，程序设定在每一次打点后都停顿1 s，最终图4用时40.230 s，图5用时37.560 s。观察图中传统RRT算法所得路径，可以明显看出，在路径经过障碍物附近时平滑性大大降低，尤其是在地图2这种障碍物空间复杂的情况下，路径点转折更大。

图4 地图1规划结果

图5 地图2规划结果

改进后的RRT算法规划路径如图6、图7所示。为了获取更加准确的距离信息，包络障碍物边缘，加入动态步长后，路径点在障碍物附近的路径平滑程度大大提高。地图1用时48.532 s，地图2用时52.548 s。从时间上看，图6相比于图4，改进后算法多用时25.58%，图7相比于图5多用时22.4%。

图6 地图1规划结果

图7 地图2规划结果

3)曲线拟合比较

由于RRT算法得出的轨迹是一条折线段，机器人在经过拐角时会出现运动不平稳的现象。为了解决这个问题，选择对路径进行光滑处理。贝塞尔曲线是于1962年由法国工程师皮埃尔·贝塞尔(Pierre Bézier)所发表，用贝塞尔曲线来为汽车的主体进行设计。后经人不断改良[12]，广泛应用于二维平面。本文采用该方法进行路径曲线的拟合。图8、图9为经过光滑处理后的最终路径。显然，改进后的RRT算法得到的路径在经过障碍物附近时更为光滑。

图8 RRT算法拟合

图9 改进RRT算法拟合

本文完成了对传统RRT算法的改进，基于人工势场法中的斥力场及斥力函数，加入了动态步长，对RRT算法经过障碍物附近时的路径进行优化，再对得到的路径进行贝塞尔曲线拟合，使得改进后的算法在经过障碍物附近时路径的平滑程度大大提高，缺点是在一定程度上延长了规划时间。后续的研究将会更加注重规划时间的缩短。

猜你喜欢势场步长障碍物中心差商公式变步长算法的计算终止条件肇庆学院学报(2022年5期)2022-09-29基于Armijo搜索步长的BFGS与DFP拟牛顿法的比较研究成都信息工程大学学报(2021年5期)2021-12-30基于Frenet和改进人工势场的在轨规避路径自主规划北京航空航天大学学报(2021年4期)2021-11-24融合前车轨迹预测的改进人工势场轨迹规划研究汽车工程(2021年12期)2021-03-08基于改进型人工势场的无人车局部避障湖北汽车工业学院学报(2020年4期)2020-12-31基于随机森林回归的智能手机用步长估计模型中国惯性技术学报(2020年2期)2020-07-24高低翻越动漫界·幼教365(中班)(2020年3期)2020-04-20SelTrac®CBTC系统中非通信障碍物的设计和处理铁道通信信号(2020年9期)2020-02-06赶飞机创新作文(1-2年级)(2019年4期)2019-10-15基于势场搜索的无人车动态避障路径规划算法研究北京汽车(2019年4期)2019-09-17

推荐访问:机器人 算法 路径