路径规划之RRT *算法

系列文章目录

路径规划之Dijkstra算法
路径规划之Best-First Search算法
路径规划之A *算法
路径规划之D *算法
路径规划之PRM算法
路径规划之RRT算法
路径规划之RRT *算法

---

---

前言

之前提到过RRT算法，现在简单提一下它的改进算法RRT*。

一、RRT算法

1.起源

RRT*是由Steven M. LaValle于2006年首次提出。

2.改进

之前RRT算法的流程已经提过了，说一下RRT算法做出的改进，RRT算法相比于RRT算法做了两点改进，分别是重新选择父节点和重布线。

2.1 重新选择父节点

RRT算法每次迭代都会得出一个新节点p_new，再将p_new与最近的节点相连接p_near相连接。
而RRT *算法第一个改进就是为p_new选择新的父节点（RRT算法选择的父节点就是p_near，即最近节点），而RRT *算法则是以p_new为圆心，在指定的搜索半径内找到从起点到p_new路径代价最小的点。

2.2 重新布线

在第一步改进完成后，继续在p_new的搜索范围内进行搜索，计算该范围内的节点在将p_new修改成自己的父节点后，从起点到它的路径代价是否减少，若减少则更新路径。

3.对比RRT

内容	RRT	RRT *
实现	相对简单	相对复杂
收敛性	RRT在有限时间内可以找到一条可行路径，但不一定是最优的	在理论上具有渐近最优的性质，即在不断迭代的过程中，生成的路径趋向于全局最优
适用场景	适用于实时路径规划问题，尤其是在高维和复杂环境中	更适用于强调全局最优性能的问题，即使在计算开销较高的情况下也能找到更优的路径

4.结果