Rapidly-exploring random tree
Path-planning algorithms for robotic applications need to find the optimal route through possible regions of the space at each step. One of the simplest path-planning algorithms to find a route is the rapidly-exploring random tree (RRT) which was proposed by Steven LaValle [1]. RRT uses a greedy heuristic to span the entire space which makes it really efficient. There is a variant, RRT*, which can find the optimal route [2].
The fundamental steps of constructing a RRT is as follows:
- Random node — Pick a node at random and check that it is collision-free
- Nearest neighbor — Get the nearest node to the given random node
- Interpolated node — Add a new node at a certain distance from the nearest node in the direction of the random node
An example of the RRT spanning a 2-D space is given in Figure 1 with the code posted in Github.
There are several desirable properties of RRT which make it a widely used path-planning algorithm:
- Convergence — RRT converges quickly due to the only operations being distance measure with respect to the random node.
- No assumptions about the state space — It can be used in non-convex high dimensional space.
- Constrained-Can be utilized for different kind of constraints governing physical systems.
- Bias towards unexplored space — Biased by large Voronoi regions to choose the largest unexplored regions.
I want to plug Steve LaValle’s original RRT webpage.
[1] LaValle, S. M. (1998). Rapidly-exploring random trees: A new tool for path planning.
[2] Karaman, S., & Frazzoli, E. (2011). Sampling-based algorithms for optimal motion planning. The international journal of robotics research, 30(7), 846–894.
