Understanding of rapid exploring random trees (RRT) path planning method

RRT And PRM equally , It is also probability complete and not optimal . Probability completeness means that as long as the solution exists, it can be found at some time . But the solution is not necessarily optimal .RRT And PRM comparison , One advantage is , In the process of building the diagram, it is looking for a path .

RRT The main algorithm flow of

This is based on matlab The code of shows RRT Algorithm flow of :

https://github.com/emreozanalkan/RRT

RRT Analysis of advantages and disadvantages of

advantage ：

• be relative to PRM More goal oriented , In the process of building the diagram, it is looking for a path .
• There is no need to model the system , There is no need to divide the search area geometrically , High coverage in search space , Search for a wide range , You can explore unknown areas as much as possible .

Inferiority ：

• RRT The resulting path is often not optimal . There is more room for optimization .
• RRT Is a random sampling point in the whole map space , In this way, the efficiency of full range sampling is often not high . Consider heuristic sampling , Make the sampled points more target oriented .
• It is not easy to obtain sampling points in a narrow channel . So sometimes you can't get through the narrow passage .

stay RRT Improvements on

Bidirectional-RRT/RRT-Connect

Algorithm flow ：

About two-way RRT The introduction comes from ：https://www.cnblogs.com/21207-iHome/p/7210543.html

RRT*

RRT Completely inherited RRT Characteristics of , Based on it, two new features are extended . Thanks to the addition of new features ,RRT Better paths can be generated . At the same time, due to the increase of algorithm steps and collision check An increase in , Computing costs have also increased .

Here is RRT* Algorithm flow of ：

In fact the whole RRT* The algorithm can be divided into three major parts . The first part is to inherit to RRT Of . This part and RRT It's the same , Is to find $z{new}$ and $z{nearest}$. This process is in the pseudo code 4,5,6 step .

near neighbor search

In this step , We're going to pay for the new $z{new}$ Find a suitable parent node . The train of thought is , With $z{new}$ For the center of a circle , With a fixed radius $r$ A circle . The node falling within the circle is $z{new}$ Potential parent nodes . We will $z{new}$ Connect to each adjacent node （ As shown in the following figure $a$、$b$）, Calculation $z{new}$ Through which adjacent node to arrive $z{init}$ Of cost Minimum . Be careful , there cost Generally refers to the path length .

Eventually we will find ,$z{new}$ adopt $z{nearest}$ arrive $z{init}$ The shortest path . At this time $z{nearest}$ It will be set to $z_{new}$ Parent node .

rewiring tree operations

At this point ,$z{new}$ Has been and $z{nearest}$ It establishes the connection , Formed a new edge . At this time, we should consider a Nodes and b Node passing $z{new}$ arrive $z{init}$ Will the path be shorter ？ From the picture I drew a Nodes and b The original connection of nodes seems to make the path shorter . So you can keep its original connection , No changes .

To illustrate the function of this step , Let's make one hypothesis . In my submission b Node passing $z{new}$ arrive $z{init}$ The path will be shorter , That is, the red path is shorter than the black path . What will happen then ? a Nodes and b The connection between nodes will be broken ,b The node will change its parent node to $z_{new}$.

By iterating through the above steps ,RRT* Will gradually generate shorter and shorter paths .

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*

Before finding the first feasible path ,Informed RRT Work done with RRT It's the same . The difference is ,Informed RRT* Use the length of the initial path to draw an ellipse focusing on the starting and ending points .

As the iteration goes on , The path will be shorter and shorter . The area of the ellipse is getting smaller and smaller . Because the area of the sampling point is limited , Higher sampling efficiency . It takes less time to converge to the optimal path .

The picture below is RRT and Informed RRT Effect diagram . You can see Informed RRT Optimize the path only within a defined ellipse . When the path is optimized to the same cost when ,RRT Than Informed RRT* More flowers 8 Times more time .

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

The paper :

Informed RRT*: Optimal sampling-based path planning focused via direct sampling of an admissible ell