RRT路径规划算法

汽车学堂，www.auto-mooc.com

隶属清华大学苏州汽车研究院旗下清研车联

专注汽车新技术人才培养

"

基于快速扩展随机树（RRT / rapidly exploring random tree）的路径规划算法，通过对状态空间中的采样点进行碰撞检测，避免了对空间的建模，能够有效地解决高维空间和复杂约束的路径规划问题。

"

RRT方法的特点是能够快速有效地搜索高维空间，通过状态空间的随机采样点，把搜索导向空白区域，从而寻找到一条从起始点到目标点的规划路径，适合解决多自由度机器人在复杂环境下和动态环境中的路径规划。

RRT算法

快速搜索随机树（RRT）算法是一种增量式采样的搜索方法，该方法在应用中不需要任何参数整定，具备良好的使用性能。它利用增量式方法构建搜索树，以逐渐提高分辨能力，而无须设置任何分辨率参数。在极限情况，该搜索树将稠密的布满整个空间，此时搜索树由很多较短曲线或路经构成，以实现充满整个空间的目的。增量式方法构建的搜索树其导向取决于稠密采样序列，当该序列为随机序列时，该搜索树称为快速搜索随机树（Rapidly Exploring Random Tree，RRT），而不论该序列为随机还是确定性序列，都被称为快速搜索稠密树（Rapidly Exploring Dense Trees，RDTs），这种规划方法可处理微分等多种约束。

算法步骤

考虑二维和三维工作空间，环境中包含静态障碍物。初始化快速随机搜索树T，只包括根节点，即初始状态S。在自由空间中随机选取一个状态点，遍历当前的快速随机搜索树T，找到T上距离最近的节点，考虑机器人的动力学约束从控制输入集中选择输入，从状态开始作用，经过一个控制周期到达新的状态。满足与的控制输入为最佳控制量。将新状态添加到快速随机搜索树T中。按照这样得到方法不断产生新状态，直到到达目标状态G。完成搜索树构建后，从目标点开始，逐次找到父节点直到到达初始状态，即搜索树的根节点。

随机树构建过程

由于在搜索过程中考虑了机器人的动力学约束，因此生成的路径的可行性很好。但是算法的随机性导致其只具备概率完备性。

改进算法

LaValle等人的工作奠定了RRT方法的基础。在采样策略方面，RRTGoalBiaS方法在控制机器人随机运动的同时，以一定概率向最终目标运动；RRTGoalZoom方法分别在整个空间和目标点周围的空间进行采样；RRTCon方法则通过加大随机步长改进规划速度。双向规划思想也被采用，衍生出RRTExtExt，RRTExtCon，RRTConCon等多种算法。

基本RRT算法收敛到终点位姿的速度可能比较慢。为了提高算法的效率和性能，需不断对该算法进行改进。如为了提高搜索效率采用双向随机搜索树(Bi~RRT)，从起始点和目标点并行生成两棵RRT，直至两棵树相遇，算法收敛。由于这个算法相比于原始RRT有更好的收敛性，因此在目前路径规划中是很常见的。NikAMelchior提出的粒子RRT算法，考虑了地形的不确定性，保证了在不确定性环境下搜索树的扩展。

Kuffner和Lavane又提出RRT-connectlv，使得节点的扩展效率大大提高。运动规划中，距离的定义非常复杂，Pengcheng研究了在RRT生长过程中距离函数不断学习的算法以降低距离函数对环境的敏感性。考虑到基本RRT规划器得到的路径长度一般是最优路径的1.3~1.5倍，英国的J.desmithl研究了变分法技术使其达到最优。Amna A引入KD树作为二级数据结构加速查找距离从环境中取出的随机点最近的叶节点，降低了搜索成本。该算法在动态障碍物、高维状态空间和存在运动学、动力学等微分约束的环境中的运动规划已经得到广泛的应用。