机器人路径规划的快速扩展随机树算法综述

机器人路径规划的快速扩展随机树算法综述

陈秋莲，蒋环宇，郑以君

广西大学计算机与电子信息学院，南宁530004

摘

要：路径规划是移动机器人的重要研究内容。快速扩展随机树（Rapidly-ExploringRandomTree，RRT）算法因

在机器人路径规划中的成功应用，自提出以来就得到了极大的研究与发展。快速扩展随机树作为一种新颖的随机节点采样算法，相对传统路径规划算法，具有建模时间短、搜索能力强、方便添加非完整约束等优点。介绍了快速扩展随机树算法的基本原理与性质，并从单向随机树扩展、多向随机树扩展、其他改进等方面概括了算法的研究现状。最后，展望了算法未来的研究方向与挑战。

关键词：机器人路径规划；快速扩展随机树；随机采样算法；非完整约束文献标志码：A

中图分类号：TP242.6

doi：10.3778/j.issn.1002-8331.1905-0061

陈秋莲，蒋环宇，郑以君.机器人路径规划的快速扩展随机树算法综述.计算机工程与应用，2019，55（16）：10-17.CHENQiulian,JIANGHuanyu,ZHENGYijun.Summaryofrapidly-exploringrandomtreealgorithminrobotpathplan-ning.ComputerEngineeringandApplications,2019,55（16）：10-17.

SummaryofRapidly-ExploringRandomTreeAlgorithminRobotPathPlanning

CHENQiulian,JIANGHuanyu,ZHENGYijun

SchoolofComputerandElectronicalInformation,GuangxiUniversity,Nanning530004,China

Abstract：Pathplanningisavitalresearchcontentofmobilerobottechnology.Rapidly-ExploringRandomTree（RRT）algorithmhasbeenstudiedanddevelopedsinceitwasproposedbecauseofitssuccessfulapplicationinrobotpathplan-ning.Asanovelrandomnodesamplingalgorithm,comparedwithtraditionalalgorithms,therapidly-exploringrandomtreehasthecharacteristicsofshortmodelingtime,robustsearchabilityandconveniencetoaddnonholonomicconstraints.Thispaperintroducesthebasicprincipleandpropertiesoftherapidly-exploringrandomtreealgorithm,summarizestheresearchstatusofthealgorithmfromtheaspectsofsinglerandomtreeextension,multiplerandomtreeextensionandotherimprovements.Finally,thefutureresearchdirectionsandchallengesofthealgorithmareprospected.

Keywords：robotpathplanning;rapidly-exploringrandomtree;randomsamplingalgorithm;nonholonomicconstraint

1引言

法研究进展缓慢，难以满足复杂环境下的规划条件。如机器人路径规划旨在通过规划算法，在有障碍物的

基于网格分辨率完整性的启发式搜索算法，需要对全局工作环境内，规划出从起点到目标区域满足机器人自身环境进行完整的网格建模工作[3-4]，高维环境下的系统开约束条件的无碰撞路径[1]。在此基础上，通过某个或某销大；群智能算法适合整体环境优化，对问题搜索空间些准则（如规划路径最短，行走时间最短，能量消耗最少大小的敏感性强，也不适合高维复杂环境的机器人路径等）为机器人选择一条最优的运动路径[2]。

规划[5]。

机器人路径规划算法是移动机器人研究的核心内基于节点采样的快速扩展随机树（Rapidly-Exploring容之一，它起始于20世纪70年代，迄今已有大量的研究RandomTree，RRT）算法[6]，具有障碍物建模简单，既能成果，为机器人广泛应用做出重大贡献。但是随着工业用于完整系统的机械臂路径规划，也能添加约束条件用领域、社会需求的不断发展，传统的机器人路径规划算

于非完整系统的轮式机器人或无人机寻路等优点，为高

基金项目：国家自然科学基金（No.71371058，No.61363026）。

作者简介：陈秋莲（1974—），女，博士，副教授，研究领域为优化计算与CAD；蒋环宇（1995—），男，硕士研究生，研究领域为路径规

划与算法优化，E-mail：597650532@qq.com；郑以君（1994—），男，硕士研究生，研究领域为路径规划与算法优化。

收稿日期：2019-05-07

修回日期：2019-06-21

文章编号：1002-8331（2019）16-0010-08

CNKI网络出版：2019-06-28,http://kns.cnki.net/kcms/detail/11.2127.TP.20190626.1751.022.html

陈秋莲，等：机器人路径规划的快速扩展随机树算法综述2019，55（16）

11

维复杂环境的机器人路径规划开辟了一种新的解决方10.ifdis[Xnew,xgoal]ReturnT；

法在单向随机树扩展、多向随机树扩展以及其他改进方算法在第1~2行初始化随机树，满足最大迭代次数面的发展现状，列举了改进算法的优缺点，进而展望了下，进入循环。

算法未来的研究方向与面临的挑战。

第3~7行产生新节点，RANDOM函数在空闲区域中生成随机节点Xrand。NEAREST函数利用欧式距2RRT算法基本原理离选择树节点中离Xrand最近的节点Xnear。若Xnear与2.1问题描述

Xrand的连线上存在障碍物，则判断条件终止当前循环，

设X⊆ℝn为路径规划问题的有界工作空间，其中进入新一轮循环。NEW_STATE函数从Xnear与Xrandn表示工作空间维度，n∈ℕ且n≥2。Xobs⊂X为空

的连线方向上扩展固定步长u，得到新节点Xnew。节间中的障碍区域，空闲区域为Xfree，满足Xfree=X\\Xobs，点扩展过程如图1所示。

Xfree包含工作空间的所有状态点集合。给定路径的起

点xXinit∈Xfree，目标点xgoal∈Xfree，机器人路径由连续rand函数s:[0,1]→ℝn表示。如果对所有的τ∈[0,1]，有uXnews(τ)∈Xfree，且满足s(0)=xinit，s(1)=xgoal，则可规划出一

Xnear条从起点到目标点满足机器人自身约束条件的连续无碰撞路径作为问题的解。

xinit2.2原理介绍

RRT搜索类似于树不断生长、向四周扩散的过程。

算法以路径起点x图1

RRT算法扩展步骤

init作为随机树T的根节点，树中节点xi用集合V存储，

节点间的连接用边集E存储，所有节第8~9行将生成的新节点与新边添加至随机树。点满足xi∈Xfree。路径规划中，从空闲区域选取随机节第10~11行给出算法终止条件。若新节点与目标点引导树的生长方向。当树中的叶子节点扩散到目标点的欧式距离小于固定步长或者已经抵达目标点，则返点，完成整个搜索，返回该节点到根节点的树干路径连回随机树T。若达到最大迭代次数K，终止算法并退出。

线。算法伪代码如下：

返回随机树后，标记目标点与循环遍历得到的父节Build_RRT(xinit,xgoal,K)点，直到树根节点被标记。此时，算法从随机树中找到1.T.init(xinit)；一条由标记节点连接的起点至目标点间无碰撞的可行2.fork=1toKdo路径。

3.Xrand←RANDOM()；2.3性能分析

4.Xnear←NEAREST(Xrand,T)；

表1将RRT与常见的机器人路径规划算法进行比

5.ifOBS_NOT_FREE(Xnear,Xrand)

较[3-5]，分析算法存在的优缺点以及适用范围。

6.continue；

从表1可知，RRT适用范围广，节点随机性使算法7.Xnew←NEW_STATE(Xnear,Xrand,u)；在复杂环境中具有灵活的搜索能力。算法结构简单，容8.V←T.add_vertex(Xnew)；易添加非完整约束条件，可作为路径规划模块整合到各9.

E←T.add_edge(Xnear,Xnew)；

种规划系统中。随机树扩散规模类似Voronoi图，初期

表1

RRT与其他类型的机器人路径规划算法比较

算法优点

缺点

适用范围

参数少，结构简单，搜索能力强，易与RRT算法其他算法相结合，能解决高维空间与算法后期节点利用率低，计算量偏大，全局离线以及局部在线路径规划，复杂约束问题

路径不稳定

高维度、复杂环境下的路径规划概率路线图（PRM）

解决高维空间路径规划问题，路径重算法用性强

复杂环境下的搜索效率低

离线的全局路径规划，高维度环境下的路径规划A*算法搜索能力强，能收敛到全局最优路径计算复杂度依赖网格分辨率完整性，不适合高维环境路径规划

离线的全局路径规划粒子群（PSO）算法算法简洁，易于实现，具有记忆性，收容易陷入局部最优解，不适用于局部敛速度快

以及高维环境的路径规划离线的全局路径规划

神经网络算法

优秀的学习能力，鲁棒性强，易与其他算法结合

高度依赖学习环境，泛化能力差

经过离线训练后的全局路径规划

122019，55（16）ComputerEngineeringandApplications计算机工程与应用

尽量偏向环境四周，将环境分成较大的空闲区域再进行的父节点。若邻域内存在节点的权值大于当前Xnew的细分，对不同区域的随机采样点，总有树中的最近节点权值与到该节点的距离之和，以当前Xnew节点作为父节与之对应。此外，算法具备概率完备性，在时间允许条点，确保邻域内的节点权值总是当前最优。整体优化过件下，总能找到从起点到目标区域的可行路径。

程如图2所示。RRT*能收敛到全局最优解。但是当节点数量过于庞大时，算法的内存消耗与计算量会呈指数3算法发展综述

上升[10]，降低算法运行速度，不适用于实时性强的环RRT在路径规划领域取得较大的进展，但算法仍存

境。因此，提高优化路径的有效节点数量，降低节点内在节点利用率低、路径不稳定等不足。现有文献对RRT存消耗，是RRT*算法的主要改进方向。

的改进主要从单向随机树扩展、多向随机树扩展及其他方面展开。其中，单向随机树扩展作为一种数据结构，rr用于多向随机树扩展以及其他改进；提高整体计算效XrandXrand率，拓展算法应用范围，是改进算法的研究基础。

XnearXXnearnewXnew3.1单向随机树扩展

XminX单向随机树扩展以路径起点作为随机树根节点，整

min体结构简单，建模方便，解决了“维度爆炸”导致的空间xinitxinit路径规划难题，能良好地用于机械臂、四旋翼等高维度（a）重连Xmin

（b）优化邻域节点权值

完整约束的机器人路径规划。改进算法主要从节点采图2

RRT*节点扩展过程示意图

样优化与步长优化两方面提高路径质量，为后续算法的Nasir等人提出具有智能采样与路径优化功能的改进提供理论基础。

RRT*-smart[11]算法，解决RRT*收敛缓慢问题。算法初3.1.1节点采样优化

始路径由RRT*生成，删除冗余节点后，将当前路径上接Urmson等人提出具有节点偏置概率的hRRT（Heuris-近障碍物的节点设为信标点，在其周围偏置采样，优化ticallyRRT）算法[7]。该算法采用启发式搜索计算节点障碍物边缘路径，降低整体路径长度。定义偏置率B偏置概率，设定概率上限，符合条件的节点偏向目标扩偏向信标附近生成采样点，每当获得更小长度的新路径展。对满足启发式的多个节点不能选取最低成本节点时，再次优化路径并识别新信标。然而，智能采样注重扩展的缺陷，在hRRT算法基础上结合最近邻搜索，提出收敛速度而牺牲随机探索特性，可能会丢失更优解。而邻域节点扩展的IkRRT（Iterativek-NearestNeighbor且不同的环境下需人为地调整偏置率，算法自适应性需RRT）算法与最佳邻节点扩展的BkRRT（Bestofk-Nearest要提高。

Neighbors）算法。不同环境下的实验证明，BkRRT路径Arslan等人提出RRT#[12]解决RRT*收敛缓慢问题。平均长度更低，但相应的搜索时间更长，且容易陷于局该算法主要通过探测与利用两步骤完成路径优化。探测部最优。

过程完成随机树扩展。利用过程通过全局重规划选取Kalisiak等人提出RRT-blossom[8]算法，利用回归约随机树中低权值的节点，生成局部的最短路径段作为部束函数产生新节点，使随机树前期降低重复区域搜索概分全局路径。RRT#在每次迭代中都会更新低权值节点，率，尽可能探索未知环境，避免搜索空间的局部最优。按优先级对最短路径段排序，实现全局路径的快速收敛。

约束函数淘汰的节点被设为休眠状态，当随机树通过约Gammell等人提出直接采样的Informed-RRT*[13]。束函数形成稀疏的全局随机树后，若没找到目标区域，算法直接限制采样区间提高整体收敛速度。首先由此时休眠节点进行更小区域搜索，保证概率完整性。上RRT*求出初始路径长度，进而生成由椭圆性质定义的述算法通过偏置采样策略选取节点扩展，提高算法生成启发式有限椭圆采样子集。生成路径长度视作椭圆长路径质量，但算法的结构限制了节点的自适应扩展，虽轴，两端点直线距离视作短轴，从椭圆中选取采样节然保证了算法的高效性，却无法生成当前最优路径。

点。启发式椭圆采样子集面积随着路径长度降低而减对于RRT面临的不足，Frazzoli等人提出具有渐进小，经过多次路径优化后，能选取当前环境的最优路径。

最优性（最短距离）的RRT*[9]算法，在RRT节点扩展基3.1.2步长优化

础上添加随机几何图与剪枝优化理论，确保随机树的节刘成菊等人提出基于RRT的变步长搜索[14]。算法点都能收敛到当前最优值。RRT*标记每个节点到根节添加目标引力变量，随机树扩展受到随机节点与目标点点的距离，记为节点权值，在以Xnew为圆心，当前随机引力变量共同作用。调整引力系数获得不同长度的步树节点总数量决定半径R的邻域内，计算Xnew与邻域长，基于大步长快速扩展，小步长收敛路径的思想，提高内所有节点连接后的权值大小。删除Xnew与原父节点搜索效率。针对动态障碍物出现在生成路径中导致路Xnear的连线，找到使Xnew权值最小的节点Xmin作为新

径规划失败问题，文中设置路径缓存及重规划[15]，快速

陈秋莲，等：机器人路径规划的快速扩展随机树算法综述2019，55（16）13

生成避开障碍物的新路径，提高整体节点利用率。3.2.2多向随机树

Wang等人在无人机巡航[16]中采用变步长RRT生成初始Rodriguez等人在OB-RRT（ObstacleBasedRRT）[25]

路径，删除冗余节点后，结合三角不等式性质，优化后的中通过狭窄区域建立根节点，让随机树更快地寻找到可节点偏向障碍物顶点，获得当前最短的同伦路径。

行路径。刘多能结合主观意识，提出人工导引RRT[26]算3.2多向随机树扩展

法，在环境中人为设定多个随机树根节点，引导随机树多向随机树以单向随机树作为基本树结构进行扩

通过搜索困难的狭窄区域，优化节点连接过程。

展，在工作空间中构造多个随机树根节点，优化随机树Otte等人提出了C-FOREST（CoupledForestof之间的连接方式，提高路径规划效率。改进算法降低工RandomEngraftingSearchTrees）算法[27]，通过并行计作空间中细小区域搜索概率，减少采样节点数量，随机算寻找最优路径。算法在每个CPU上生成单随机树，搜索性能强，更适合狭窄区域或复杂环境下的路径规划。

并通过椭圆子集寻找单随机树最优解决方案。多棵随3.2.1双向随机树

机树通过T-CPU通信共享最优解决方案，选取比较后的Lavalle等人提出双向随机树（BidirectionalRRT，

不同位置的探索节点，满足多随机树扩展特性。算法以bi-RRT）[17]

用于高维度机械臂路径规划。算法以起点与当前最短路径为基础，进行新一轮的优化。并行多随机目标点为树根节点生成两棵树进行扩展，目标点随机树树在整体上降低了收敛至最优的时间。

以起点随机树生成的新节点为扩展方向，直到两棵树的3.3RRT其他方面改进

叶子节点互相连接。RRT-connect[18]在bi-RRT上引入贪RRT的改进方式具有多样性，除了对自身结构进行婪扩展思想，在目标点随机树中设置循环扩展，加快双优化外，也结合其他方面提高路径质量与整体收敛速随机树节点连接速度。Akgun等人在此基础上结合

度，生成满足非完整约束方程的机器人系统路径，扩展RRT*提出渐进最优的B-RRT*（BidirectionalRRT*）[19]

，算法的应用空间。

以RRT*代替RRT扩展起点随机树。找到初始路径后，3.3.1曲率平滑后处理

设定采样约束减少无效节点，用局部偏置优化路径上的平滑的可执行路径是非完整约束机器人路径规划节点至局部最优。但是，算法在连接节点时仍需执行的重要条件，RRT因计算高效、耗时少而在非完整约束RRT*全部操作，并在每次迭代时连接随机树，产生大量系统中得到广泛的应用。徐娜等人[28]结合非完整约束的计算开销。

方程与目标偏置的RRT算法，将欧式距离换成对角线距Jordan等人提出多种基于启发式技术的改进B-RRT*[20]

离，提高运算速度。对生成的初始路径进行曲率平滑算法。结合RRT-connect与启发式思想的快速收敛性，的后处理操作，产生满足约束的可行路径，使用车辆、降低节点扩展过程的计算量，提高总体收敛速度。但启平面板、单轮车等非完整约束模型进行模拟，验证了路发式在一定程度上限制了算法原有的探索、采样策略等径的可行性。杜明博等人提出连续曲率的RRT算法

性质。Qureshi与Ayaz提出智能双向搜索的最优算法

（ContinuousCurvatureRRT，CC-RRT）[29]

，考虑环境与IB-RRT*（IntelligentBidirectionalRRT*）[21]

，专用于复杂车辆最大曲率约束，通过剪枝函数与B样条曲线结合的环境搜索。算法使用智能样本插入的启发式技术，舍弃后处理方式，生成满足约束的可行路径。Yang等人提

RRT-connect的贪婪策略，通过随机节点邻域填充或者出无人机路径平滑算法SRRT（Smooth-PathRRT）[30]

，以最近节点权值排序选择扩展节点。王全等人[22]提出平随机树路径的夹角为连续曲率的唯一信息，通过三次滑路径的拼接算法，优化随机树间的连接方式。给定初B样条曲线生成满足无人机最小曲率半径约束的可行路径。

始方向及运动系统的最小半径等约束条件，生成的圆弧3.3.2引导域偏置采样

路径能满足非完整约束系统的路径规划。Burget等人与启发式的目标点偏置采样相比，引导域偏置采样提出满足任务约束的双向搜索算法BI-RRT*（Bidirec-需要提前生成优化随机树扩展的引导区域，再通过RRTtionalInformedRRT*）[23]。算法结合Informed-RRT*与进行路径扩展。GA-RRT（Guiding-AreaRRTBasedon

B-RRT*特点，使用双随机树生成初始路径，解决收敛速A*）[31]

以A*路径为引导域，先完成低分辨率下的A*路度慢的缺陷，为Informed-RRT*提供更多椭圆子集采样径规划，生成次优路径。在当前路径基础上，随机树以优化时间。结果表明，该算法比B-RRT*算法更高效。

一定概率选取当前路径周边节点，减少无效节点。实验Yi等人提出基于双向RRT*的同伦变体算法

证明，优化后的路径适合车辆运行且规划时间短。文HARRT*（HomotopyAwareRRT*）[24]

。算法通过人为献[32]将高斯分布模型作为引导区域，设定概率密度函干涉来规划从一个拓扑空间到另一个拓扑空间的路数偏向高斯曲线上的离散节点。仿真结果显示，通过径。这种方法解决了搜索和救援、军事中的人机互动的引导域扩展RRT在路径质量上相对于基本RRT算法规划问题。通过案例研究从理论上证明了所提方法的都有很大改进。此外，动态限制域的Informed-RRT*[13]、有效性。

IB-RRT[21]等，也是基于椭圆子集引导域偏置的采样算法。

142019，55（16）ComputerEngineeringandApplications计算机工程与应用

3.3.3结合智能算法采样3.3.5实时路径规划

RRT搜索过程中，后期节点扩展会产生大量的冗余实际工作的机器人在未知或动态环境中可能会面节点。因此，将RRT与智能算法结合，通过训练得到具临各种突发情况，导致规划路径不可用，而实时路径规有记忆性的节点，提高不同环境模型下的路径规划速划旨在重新规划可行路径，提高算法鲁棒性。张捍东等度。Cheng等人[33]用自学习方法提高节点质量来改善整人[43]将改进的RRT与滚动窗口模型结合，处理未知环境体路径，在RRT搜索过程中用扩展函数训练环境模型。的实时路径规划。机器人在基于传感器视距的窗口内设定节点环境约束标准，离障碍物远的节点约束性小，未发现障碍物时，按照窗口内的规划路径前进；发现障近的约束性大，删除约束性大的节点。随机树经过多次碍物后，选取合适的子目标点重新规划路径规避障碍搜索后，节点具有记忆性，路径规划质量更好，搜索速度物。刘新宇等人[44]在未知环境中采用聚类算法对可见更快。王全等人结合强化学习[34]，采用基于在线学习策区域内环境的复杂程度进行判别，生成自适应的局部略的Sarsa方法评价节点质量。根据评价值的变化设定规划区域。算法降低区域中障碍物数量与碰撞检测奖励或惩罚措施，提高节点对环境的感知度，确保新节的计算量，提高整体收敛速度，具有良好的环境适应能点扩展只与当前节点到树根节点的分支有关，减少整体力。Pimentel等人[45]提出有效探索未知环境的ID-RRT带来的影响。

（Information-DrivenRRT）算法。算法同时从多个可扩Shiarlis等人提出基于RRT*扩展的快速学习随机展节点中选取能探索更多未知区域信息的子目标点扩树算法（Rapidly-ExploringLearningTrees，RLT*）[35]。展，并记录环境信息。同时让机器人执行规划的子路径针对反向强化学习（InverseReinforcementLearning，IRL）段，防止环境更新影响子目标点位置。相对其他局部路中路径规划开销大、计算复杂的问题，定义缓存方案，降径规划，ID-RRT能对全局环境快速建模，避免产生局部低RLT*计算成本。Higueras等人利用完全卷积神经网

最优路径。Naderi等人[46]提出动态环境的实时路径规络（FullyConvolutionalNeuralNetworks，FCN）[36]

，以划算法RT-RRT*（RealTimeRRT*）。算法保留整棵随无监督学习方式学习路径规划任务，避免成本函数的显机树，能快速生成任何目标区域的可行路径，实时性式表达，训练后的FCN指导RRT*扩展完成实际的路径强。树根节点随着生成路径移动到目标区域而不删除搜索。实验显示，FCN-RRT*比RLT*取得了更好结果。原有节点，同时建立以根节点为圆心的移动邻域，增加Qureshi等人提出基于DNN的运动规划网络（Motion

邻域内的采样节点数量，重连随机树节点至当前最优，PlanningNetworks，MPNet）[37]

，以双向随机树扩展产生用来实时优化邻域内的可行路径，提高动态环境的避障的路径作为迭代对象。算法能较好地完成高维问题，解速度。

决神经网络在未知环境中泛化能力差的不足。Ichter等3.4改进算法小结

人[38]提出自学习的非均匀节点采样分布。先由离线学习表2对具有代表性的算法进行简要归纳，列举算法

得出可能存在的最优路径区域，再执行采样算法，将采采样方式，分析存在的优缺点以及适用场景。

样节点集中在该区域进行偏置采样，提高路径规划速度。

Melchior等人提出基于粒子节点搜索的RRT算法

4算法的研究方向与挑战

（ParticleRRT，PRRT）[39]

。随机树节点由粒子群组成，RRT经历长时间发展，取得了大量的研究成果。然

每个粒子模拟节点扩散，求出粒子群的平均扩散概率代而，优化后的路径与最优路径仍有一定差距。主要原因替单个节点扩散概率。此外，算法利用hRRT[7]的目标偏在于改进的RRT*算法需要不断调整步长以提高路径精向思想，提高路径质量，算法鲁棒性强。Viseras等人将度，生成最优路径所消耗的内存资源及计算时间呈指数RRT*与蚁群算法[40]结合，提出具备学习能力的启发式增长，不适于实际应用的机器人系统。此外，环境中的随机树框架。实验证明，具有启发式的随机树与蚁群算不规则障碍物区域采样、机器人的传感器精度、路面的法结合优于RRT*规划的效果。

凹凸性等因素也会影响路径质量。本文对目前算法面3.3.4优化数据结构

临的问题进行总结，并对未来研究方向提出几点建议。

RRT的树结构存储方式具有多种数据结构变体。（1）提高节点利用率

Yershova等人[41]提出动态KD-tree的存储结构，降低新RRT及RRT*生成大量节点避免产生局部最优路径节点搜索最近邻节点的计算量，解决RRT节点不断变化或搜索失败。算法通过均匀采样探索整个区域，树中大而重构KD-tree的低效性。动态KD-tree每次搜索产生部分探索节点离生成路径的优化区域远，优化路径的概对数时间开销，算法整体效率高。Sandstrem等人[42]使率小。此外，树的概率完整性使这些节点不断添加无效

用拓扑邻滤波对空间区域的邻节点集合进行处理，求得分支，增加计算时间。改进算法通过路径重规划[15，46-47]

，

显著减少的邻节点集。作为一种采样预处理方法，它可利用已有探索节点快速形成新路径；设定智能偏置采

与KD-tree、散列表等存储结构结合，提高算法规划速度。

样[11]、启发式采样[7，20]等约束条件，选取有利于路径优化

陈秋莲，等：机器人路径规划的快速扩展随机树算法综述

2019，55（16）15

表2

改进算法采样方式及优缺点

算法名称采样方式算法优点

存在的缺陷

算法适用场景

HRRT[7]

启发式采样选取启发式成本低的目标偏置节

牺牲计算时间，且容易陷入局点扩展

部最优

仿真环境的全局路径规划RRT_blossem[8]

约束偏置采样通过约束方程避免局部最优，提高约束方程单一，大空间的搜索仿真环境的局部及全局路径整体搜索速度

环境，效率低

规划

RRT*[9]

均匀采样

算法具备渐进最优性，在时间条件允许下，能收敛到最优路径节点计算量大，内存消耗大仿真环境的全局最优路径规划

定义信标点与偏置比的启发式算

收敛速度与路径质量不能同时RRT*-smart[11]

智能偏置采样

法实现智能采样搜索，加快算法的取得最优，不同环境需手动调仿真环境的全局最优路径规划

收敛速度

节偏置比，自适应性差引入全局重规划，排序选取最低权最低权值节点只能在生成新路RRT#

[12]

均匀采样

值节点，快速收敛至全局最优路径径时获得，未设置基于最低权机械臂、四旋翼等完整约束系值节点的启发式采样

统的全局最优路径规划使用椭圆区域限制节点采样范围，

Informed-RRT*[13]区域直接采样减少无效节点，提高最优路径收敛初始椭圆子集由RRT*全局搜仿真环境的全局最优路径规速度

索生成，整体时间花销大划，狭窄区域的最优路径规划RRT-connect[18]启发式采样通过贪婪搜索连接两棵随机树，降路径非最优，只适用于完整约机械臂、四旋翼等完整约束系低采样节点数量，提高收敛速度束下的机器人路径规划统的全局路径规划

改进B-RRT*[20]

启发式采样

使用多种启发式策略，能在不同条多种启发式采样提高整体计算件下提高双向RRT*的收敛速度量，限制算法自身的搜索特性仿真环境的全局最优路径规划结合RRT*和同伦算法，提出人机HARRT*[24]启发式采样

交互规划器，提高规避特定障碍物算法的计算效率与路径质量不仿真环境的全局同伦最优路径下同伦路径规划速度

能同时取得最优

规划

CC-RRT[29]均匀采样

使用B样条曲线优化生成路径，适当前算法只适用于低速运动车无人车、叉车等平面非完整约用于非完整约束的路径搜索辆的约束环境

束系统的全局路径规划使用少量参数生成可行路径，降低SRRT[30]均匀采样

计算复杂度，适合无人机等实时性未考虑传感器精度、风力、其他无人机、直升机、水下机器人、强的路径规划应用

未建模的因素影响

医疗机器人等复杂空间中非完整约束系统的全局路径规划利用IRL框架学习RRT*扩展过

RLT*

[35]

均匀采样程，设计缓存方案降低计算成本，IRL学习框架整体开销大，计工业机器人等稳定性要求高的收敛速度快

算复杂，需进一步优化最优路径规划，狭窄区域的最优路径规划

用粒子群的平均扩散概率代替节

PRRT[39]目标偏置采样点扩散概率，适合未知环境搜索，节点扩展取粒子群的平均扩散未知环境下崎岖路面或障碍物算法鲁棒性强

概率，实时性差

多的局部路径规划KD-RRT[41]均匀采样使用KD-tree数据结构存储RRT的KD-tree重构时间较长，需进一生成节点，减少最近邻搜索计算量步优化RRT的存储结构仿真环境的全局路径规划ID-RRT[45]均匀采样提高未知环境下信息采集速度与传感器精度要求高，单机器人未知环境下的移动机器人局部路径稳定性，避免局部最优路径在未知环境的信息采集速度慢路径规划

RT-RRT*[46]

均匀采样

实时路径规划性能强，适合动态环只能用于有界环境搜索，内存境的路径规划

消耗大

动态环境下的实时路径规划的节点进行扩展；利用直接采样[13，48]限制采样区间，确保列表[42]等高效的数据结构存储节点，优化最近邻节点的新的采样节点总在路径优化区域内。但是，现有改进算选取方式，避免通过欧式距离寻找邻节点而产生复杂的法中，路径重规划速度受到随机树节点数量限制，不同计算量。但是，改进的数据结构存在添加节点时间长，约束条件的采样算法需根据环境人为调节条件参数，自节点数量大导致资源消耗大，后期维护困难等不足。以适应能力不足。因此，进一步提高路径优化中节点利用后的研究中，在树结构的基础上使用其他技术生成更快率，生成更智能的算法，值得深入研究与讨论。

的搜索算法，降低最近邻节点连接成本，有助于进一步（2）改进最近邻搜索算法

提高算法收敛速度。

随机树经过均匀采样搜索，寻找最近邻节点的计算（3）优化狭窄区域采样

量会随着节点指数增长而增长，直接降低了算法收敛速RRT均匀采样性质降低了狭窄区域选取随机节点度。最近邻搜索算法作为限制RRT收敛速度的瓶颈，受的概率。作为采样算法的研究难点，很少有算法专门解到了研究者的高度重视。改进算法结合KD-tree[39]、散

决狭窄区域的最优路径。现有改进算法主要通过直接

162019，55（16）ComputerEngineeringandApplications计算机工程与应用

采样解决狭窄区域渐进收敛问题，如Informed-RRT*[13]flood-fillbehavior[C]//IEEEInternationalConferenceon与RABIT*[48]，通过不断减少采样区间，提高路径中的狭RoboticsandAutomation，2006：1237-1242.

窄区域采样概率。此外，在狭窄区间过多的环境中，受[9]KaramanS，FrazzoliE.Sampling-basedalgorithmsforopti-障碍物影响，算法容易生成当前同伦最优路径，导致最

malmotionplanning[J].TheInternationalJournalofRobot-终路径不唯一。使用深度学习[33，35，38]

离线训练，得到经

icsResearch，2011，30（7）：846-894.

过筛选的高回报值节点，能优化最终路径稳定性。现阶[10]AdiyatovO，VarolHA.Rapidly-exploringrandomtree

段应进一步提高上述算法性能，并着重研究实际机器人basedmemoryefficientmotionplanning[C]//2013IEEE系统在狭窄区域的优化过程。

InternationalConferenceonMechatronics&Automation，（4）优化非完整约束方程

2013：354-359.

非完整约束机器人的运动方程复杂，计算量大。常[11]NasirJ，IslamF，MalikU，etal.RRT*-smart：arapid

见的非完整约束机器人路径规划先通过RRT算法求得convergenceimplementationofRRT*[J].InternationalJour-nalofAdvancedRoboticSystems，2013，10（4）.可行路径，再采用曲率平滑后处理生成满足运动方程约[12]ArslanO，TsiotrasP.Useofrelaxationmethodsinsampling-束的路径

[28-30]

。然而，实际规划中路径目标更新快，后处

basedalgorithmsforoptimalmotionplanning[C]//2013理计算量大。非完整约束的运动方程需要考虑以下问IEEEInternationalConferenceonRoboticsandAuto-题：优化运动方程，减少方程计算量；平衡实时性强的非mation，2013：2421-2428.

完整约束机器人中曲线计算效率与路径精度；选取适合[13]GammellJD，SrinivasaSS，BarfootTD.Informed

狭窄区域的非完整约束机器人度量准则，提高狭窄区域RRT*：optimalsampling-basedpathplanningfocused下的路径稳定性。未来对非完整约束的研究应着重解viadirectsamplingofanadmissibleellipsoidalheuris-决实际的动力学问题，并进一步优化路径平滑度。

tic[C]//2014IEEE/RSJInternationalConferenceonIntelli-gentRobotsandSystems，2014：2997-3004.

5结束语

[14]刘成菊，韩俊强，安康.基于改进RRT算法的RoboCup机

RRT算法具有高效的随机扩展性，可快速生成可行

器人动态路径规划[J].机器人，2017，39（1）：8-15.路径，为高维且复杂的机器人路径规划问题提供了一种[15]FergusonD，KalraN，StentzA.ReplanningwithRRTs[C]//

新的解决方案，并取得了良好的进展。虽然改进的RRT2006IEEEInternationalConferenceonRoboticsand算法在路径质量、计算时间上取得显著的成果，但仍未Automation，2006：1243-1248.

[16]WangC，MengMQ.VariantstepsizeRRT：anefficient

达到理论上的最优结果。对RRT进一步探索，使其有更pathplannerforUAVincomplexenvironments[C]//2016广泛的应用空间，对机器人路径规划具有重要的研究IEEEInternationalConferenceonReal-TimeComputing意义。

andRobotics，AngkorWat，2016：555-560.

[17]LavalleSM，KuffnerJJJ.Randomizedkinodynamicplan-参考文献：

ning[J].InternationalJournalofRobotics&Research，[1]余卓平，李奕姗，熊璐.无人车运动规划算法综述[J].同济

1999，15（5）：378-400.

大学学报（自然科学版），2017，45（8）：1150-1159.

[18]KuffnerJJ，LavalleSM.RRT-connect：anefficientapproach

[2]李磊，叶涛，谭民，等.移动机器人技术研究现状与未来[J].

tosingle-querypathplanning[C]//2002IEEEInterna-机器人，2002，24（5）：475-480.

tionalConferenceonRoboticsandAutomation，2002：[3]冯来春.基于引导域的参数化RRT无人驾驶车辆运动规

995-1001.

划算法研究[D].合肥：中国科学技术大学，2017.

[19]AkgunB，StilmanM.Samplingheuristicsforoptimal

[4]张广林，胡小梅，柴剑飞，等.路径规划算法及其应用综述[J].

motionplanninginhighdimensions[C]//2011IEEE/RSJ现代机械，2011（5）：85-90.

InternationalConferenceonIntelligentRobotsandSys-[5]NoreenI，KhanA，HabibZ.Optimalpathplanningusing

tems，2011：2640-2645.

RRT*basedapproaches：asurveyandfuturedirections[J].[20]JordanM，PerezA.Optimalbidirectionalrapidly-exploring

InternationalJournalofAdvancedComputerScienceandrandomtrees：MIT-CSAIL-TR-2013-021[R].CSAILMIT，Applications，2016，7（11）：97-107.

2013.

[6]LavalleS.Rapidly-exploringrandomtrees：anewtoolfor

[21]QureshiAH，AyazY.Intelligentbidirectionalrapidly-pathplanning[R].IowaStateUniversity，1998.

exploringrandomtreesforoptimalmotionplanningin[7]UrmsonC，SimmonsR.Approachesforheuristicallybias-complexclutteredenvironments[J].RoboticsandAutono-ingRRTgrowth[C]//2003IEEE/RSJInternationalConfer-mousSystems，2015，68：1-11.

enceonIntelligentRobots&Systems，2003：1178-1183.[22]王全，王维，李焱，等.基于混合策略的轮式机器人路径规

[8]KalisiakM，PanneMVD.RRT-blossom：RRTwithalocal

划方法[J].计算机工程与应用，2014，50（4）：45-49.

陈秋莲，等：机器人路径规划的快速扩展随机树算法综述2019，55（16）17

[23]BurgetF，BennewitzM，BurgardW.BI2RRT*：aneffi-Automation，2018：1-6.

cientsampling-basedpathplanningframeworkfortask-[37]QureshiAH，SimeonovA，BencyMJ，etal.Motion

constrainedmobilemanipulation[C]//2016IEEE/RSJInter-planningnetworks[J].arXiv：1806.05767，2018.

nationalConferenceonIntelligentRobotsandSystems，[38]IchterB，HarrisonJ，PavoneM.Learningsamplingdistri-2016：3714-3721.

butionsforrobotmotionplanning[C]//2018IEEEInterna-[24]YiD，GoodrichMA，SeppiKD.Homotopy-awareRRT*：

tionalConferenceonRoboticsandAutomation，2018：towardhuman-robottopologicalpath-planning[C]//20167087-7094.

11thACM/IEEEInternationalConferenceonHuman-[39]MelchiorNA，SimmonsR.ParticleRRTforpathplan-RobotInteraction，2016：279-286.

ningwithuncertainty[C]//2007IEEEInternationalCon-[25]RodriguezS，TangX，LienJM，etal.Anobstacle-based

ferenceonRoboticsandAutomation，2007：1617-1624.rapidly-exploringrandomtree[C]//2006IEEEInterna-[40]ViserasA，LosadaRO，MerinoL.Planningwithants：

tionalConferenceonRoboticsandAutomation，2006：efficientpathplanningwithrapidlyexploringrandom895-900.

treesandantcolonyoptimization[J].InternationalJour-[26]刘多能.基于人机智能融合的移动机器人路径规划方法

nalofAdvancedRoboticSystems，2016，13（5）：1-16.研究[D].长沙：国防科学技术大学，2011.

[41]YershovaA，LaValleMS.Improvingmotion-planningalgo-[27]OtteM，CorrellN.C-FOREST：parallelshortestpath

rithmsbyefficientnearest-neighborsearching[J].IEEEplanningwithsuperlinearspeedup[J].IEEETransactionsTransactionsonRobotics，2007，23（1）：151-157.

onRobotics，2013，29（3）：798-806.

[42]SandstremR，BreggerA，SmithB，etal.Topologicalnearest-[28]徐娜，陈雄，孔庆生，等.非完整约束下的机器人运动规划

neighborfilteringforsampling-basedplanners[C]//2018算法[J].机器人，2011，33（6）：666-672.

IEEEInternationalConferenceonRoboticsandAuto-[29]杜明博，梅涛，陈佳佳，等.复杂环境下基于RRT的智能

mation，2018：3053-3060.

车辆运动规划算法[J].机器人，2015，37（4）：443-450.[43]张捍东，陈阳，吴玉秀，等.未知环境下移动机器人实时路

[30]YangK，SukkariehS.3Dsmoothpathplanningfora

径规划[J].计算机工程与应用，2018，54（19）：140-146.UAVinclutterednaturalenvironments[C]//2008IEEE/[44]刘新宇，谭力铭，杨春曦，等.未知环境下的蚁群-聚类自

RSJInternationalConferenceonIntelligentRobotsand适应动态路径规划[J].计算机科学与探索，2019，13（5）：Systems，Nice，2008：794-800.

846-857.

[31]冯来春，梁华为，杜明博，等.基于A*引导域的RRT智能

[45]PimentelJM，AlvimMS，CamposMFM，etal.Information-车辆路径规划算法[J].计算机系统应用，2017，26（8）：drivenrapidly-exploringrandomtreeforefficientenvi-127-133.

ronmentexploration[J].JournalofIntelligent&Robotic[32]宋晓琳，周南，黄正瑜，等.改进RRT在汽车避障局部路

Systems，2017，91（5）：1-19.

径规划中的应用[J].湖南大学学报（自然科学版），2017，[46]NaderiK，RajamäkiJ，HämäläinenP.RT-RRT*：areal-44（4）：30-37.

timepathplanningalgorithmbasedonRRT*[C]//8th[33]ChengP，LavalleSM.ReducingRRTmetricsensitivity

ACMSIGGRAPHConferenceonMotioninGames，formotionplanningwithdifferentialconstraints[D].2015：113-118.

IowaStateUniversity，2001.

[47]ZuckerM，KuffnerJ，BranickyM.MultipartiteRRTsfor

[34]王全.基于RRT的全局路径规划方法及其应用研究[D].

rapidreplanningindynamicenvironments[C]//2007IEEE长沙：国防科学技术大学，2014.

InternationalConferenceonRoboticsandAutomation，[35]ShiarlisK，MessiasJ，WhitesonS.Rapidlyexploringlearn-2007：1603-1609.

ingtrees[C]//2017IEEEInternationalConferenceon[48]ChoudhuryS，GammellJD，BarfootTD，etal.Region-RoboticsandAutomation，2017：1541-1548.

allyacceleratedbatchinformedtrees（RABIT*）：aframe-[36]Pérez-HiguerasN，CaballeroF，MerinoL.Learninghuman-worktointegratelocalinformationintooptimalpathawarepathplanningwithfullyconvolutionalnetworks[C]//planning[C]//2016IEEEInternationalConferenceon2018IEEEInternationalConferenceonRoboticsand

RoboticsandAutomation，2016：4207-4214.