对Rapidly-exploring Random Trees(RRT)路径规划方法的理解

首飞

分类：学习笔记

个人专栏：路径规划

发布时间 2022.07.17阅读数 2778 评论数 0

RRT与PRM一样，也是概率完备且不最优的。概率完备是指只要解存在就一定能在某一时刻找到。但解不一定是最优的。RRT与PRM相比，有一个优势就是，它在构建图的过程中就在寻找路径。

RRT的主要算法流程

在这里插入图片描述

这份基于matlab的代码很好的展示了RRT的算法流程:

https://github.com/emreozanalkan/RRT

RRT的优劣分析

优势：

相对于PRM更具有目标导向，它在构建图的过程中就在寻找路径。
无需对系统进行建模，无需对搜索区域进行几何划分，在搜索空间的覆盖率高，搜索的范围广，可以尽可能的探索未知区域。

劣势：

RRT得到的路径往往不是最优的。有比较大的优化空间。
RRT是在整个地图空间中随机采样点，这样全范围的采样往往效率不高。可以考虑启发式的采样，让采样的点更具有目标导向。
在狭窄的通道里不易获得采样点。所以有时无法通过狭窄通道。

在RRT上的改进

Bidirectional-RRT/RRT-Connect

算法流程：
在这里插入图片描述

在这里插入图片描述

关于双向RRT的介绍来源于：https://www.cnblogs.com/21207-iHome/p/7210543.html

RRT*

RRT_ 完全继承了RRT的特性，并在其基础上扩展了两个新的特性。正是由于新特性的加入，RRT_ 可以生成更优的路径。同时由于算法步骤的增加和collision check的增加，计算消耗也增加了。
下面是RRT* 的算法流程：
在这里插入图片描述

其实整个RRT* 算法可以分为三个大的部分。第一部分是继承至RRT的。这一部分和RRT是一样的，就是寻找到z_{new}和z_{nearest}。这一过程就是伪代码中的4，5，6步骤。
在这里插入图片描述

near neighbor search
在这一步骤中，我们要为新得到的z_{new}找一个合适的父节点。思路是，以z_{new}为圆心，以固定的半径r画圆。落在该圆范围内的节点就是z_{new}潜在的父节点。我们将z_{new}与每个邻近的节点相连（如下图节点a、b），计算z_{new}通过哪个邻近节点到达z_{init}的cost最小。注意，这里的cost一般是指路径长度。
在这里插入图片描述
最终我们会发现，z_{new}通过z_{nearest}到达z_{init}路径最短。这时z_{nearest}就会设置成z_{new}的父节点。

rewiring tree operations
到这一步时，z_{new}已经和z_{nearest}建立了连接，形成了一条新的边。这时我们要考虑a节点和b节点通过z_{new}到达z_{init}路径会短一点吗？从我画的图直观来看a节点和b节点原来的连接似乎使得路径更短。所以可以保留其原来的连接，不进行更改。
在这里插入图片描述
为了说明这一步骤的功能，我们做一个假设。我认为b节点通过z_{new}到达z_{init}路径会短一点，即红色路径比黑色路径短。这时会发生什么? a节点和b节点间的连接会断开，b节点会将自己的父节点改为z_{new}。

通过不断迭代上述步骤，RRT*会逐渐生成越来越短的路径。

https://player.bilibili.com/player.html?aid=96583530

https://blog.csdn.net/ljq31446/article/details/78867011

A Comparison of RRT, RRT_ and RRT_-Smart Path Planning Algorithms

Informed RRT*

在寻找到第一条可行的路径前，Informed RRT_ 所做的工作与RRT_ 是一样的。不同之处在于，Informed RRT* 使用初始路径的长度来画一个以起始点和终止点为焦点的椭圆。
在这里插入图片描述
随着迭代的进行，路径会越来越短。椭圆的面积也越来越小。因为采样点的区域被限定了，采样效率更高。收敛到最优路径花的时间也更少。