Dagothar's Den

Rapidly-Growing Random Tree (RRT) path planning algorithm 

There are things that are easy to do for humans, and really hard to do for robots. One of such things is the problem of path planning - how to find a path between the start and the goal, and avoid the obstacles in between?

There is a wide range of methods employed precisely to solve this problem. There are path planners basing on potential field methods, Wavefront planners, roadmap algorithms, and so on. Each of them has its specific advantages and shortcomings.

RRT algorithm is one of such planners. It’s based on a randomized approach, making it only probabilistically-complete. The idea is to grow (extend() method) two trees at start and goal locations, and try to find a connection (connect() method) between them, as the trees continue to explore the space.

The RRT algorithm was introduced in the paper Rapidly-Growing Random Tree (RRT) path planning algorithm by James Kuffner and Stevan LaValle. The whole idea is explained there in detail.

Path planning allows you to find a path between obstacles in a configuration space. It doesn’t have to be a 2 dimensional one, or even 3 dimensional. It can consists of many dimensions: the generalized coordinates (like robot arm joint angles, speed, even temperature). The method can also be a subject of various modifications.

I tried to make a simple explanation of Extend() and Connect() in the first two gifs. In Connect() method, you may have to perform a lot more steps before you find the connection.