RRT: 机器人路径规划RRT算法（1）

RRT应用案例

1 RRT 算法概述

RRT*算法是一种基于随机采样的路径规划方法，不仅具有概率完备性，还具有渐进优化能力。假设X=(0,1)^d代表d维构型空间，d \in N,d\geq 2

进一步假设X_{obs}代表障碍物空间，X_{obs}属于X.X_{free}表示自由空间，X_{free}+X_{obs}=X.对于机器人来说，初始构型和x_{init}和目标构型x_{goal}是X_{free}中的元素。由此可以将路径规划问题转化为以下形式

（X_{free},x_{init},x_{goal}）

假设函数\sigma:[0,1] \rightarrow R^4 ,\sigma 的全变差可以定义如下：

全变差

为了更好的理解算法，有必要实现熟悉三个定义：

定义一

\sigma的全变差TV(\sigma)<\infty,则称函数\sigma为区间[0,1]上的有界变差函数。

->\sigma是连续函数，则可以称\sigma为路径，

->\sigma是路径，且对所有\tau \in [0,1], \sigma(\tau) \in X_{free}.则\sigma 为碰撞路径；

->σ是无碰撞路径, 且\sigma(0)=x_{init}， \sigma(1)=x_{goal},则称\sigma 为可行路径。

由上述定义，路径的总变差可以理解为路径的长度。

定义二

（可行路径规划）给定一个路径规划问题（X_{free},x_{init},x_{goal}）,如果可行路径存在，则规划一条可行路径，如果路径不存在，则返回可行路径失败信息。

定义三

规划一条路径问题，（X_{free}, x_{init}, x_{goal}）,并定义价值函数c: \sum \rightarrow R \geq0 .\sum 是可行路径。如果最优路径存在，则会规划一条最优路径\sigma*且如果最优路径存在，则返回最优路径规划失败信息。

对于机器人的路径规划，从环境情况感知情况，可以将其分为以下两种：

• 环境已知路径规划
• 环境未知路径规划

2 RRT 算法的特点

RRT算法全称是快速扩展随机树，（RRT, Rapidly-exploring Random Trees）是最近十几年得到广泛发展与应用的基于概率采样的运动规划算法。由Steven M.LaValle教授在1998年提出。

RRT是采用一种特殊的增量方式进行构造，这种方式能迅速缩短一个随机状态点与树的期望距离。该方法的特点是能够快速有效搜索高维空间，通过状态空间的随机采样点，将搜索导向空白区域。从而得到一条从起始点到目标点的规划路径。它通过对状态空间中的采样点进行碰撞检测。避免了空间的建模，能够有效的解决高维空间和复杂约束的路径规划问题。

RRT算法适合解决多自由度机器人在复杂环境下和动态环境中的路径规划问题。

与其他的随机路径规划方法相比，RRT算法更适用于非完整约束和多自由度的系统中。

RRT 算法具有以下优势：

• RRT 在扩展过程中，倾向于扩展（探索）未知的空间；
• 该算法具有概率完备性，即随着迭代次数的增加，越来越多的未知空间被探索，当迭代次数趋于无穷大，所有的空间都能被探索，也就能保证目标构形一定能到达；
• 节点的分布与采样点的分布状况一致；
• 由于不用对障碍物进行精确建模，只用获得是否碰撞的信息，RRT 算法的避障规划效率高。

尽管RRT算法是一个相对高效率，同时可以较好的处理带有非完整约束的路径规划问题的算法，并且在很多方面有很大的优势，但是RRT算法并不能保证所得出的可行路径是相对优化的。因此许多关于RRT算法的改进也致力于解决路径优化的问题，RRT*算法就是其中一个。

RRT*算法的主要特征是能快速的找出初始路径，之后随着采样点的增加，不断地进行优化直到找到目标点或者达到设定的最大循环次数。RRT*算法是渐进优化的，也就是随着迭代次数的增加，得出的路径是越来越优化的，而且永远不可能在有限的时间中得出最优的路径。因此换句话说，要想得出相对满意的优化路径，是需要一定的运算时间的。所以RRT*算法的收敛时间是一个比较突出的研究问题。但不可否认的是，RRT*算法计算出的路径的代价相比RRT来说减小了不少。

Ref: 冗余机械臂运动学及避障路径规划研究