RRT Algorithm (Rapidly-exploring Random Tree)
RRT is a sampling-based method used often in high-dimensional spaces. It's particularly useful in cases where the exact representation of obstacles is unknown or hard to compute.
Problem Statement
A robotic arm with 10 joints needs to move from its start position to a goal position without hitting any obstacles. Each joint can move in many ways, creating an enormous number of possible positions. Finding a valid path through all these possibilities is extremely difficult and time-consuming.
Solution
The Rapidly-exploring Random Tree (RRT) algorithm solves this issue, randolmy generating paths until it intersects with the obstacle and a valid path is found.
Let's take the Robotic Arm with 10 joints for example:
Instead of checking every possible position of the 10 joints, the RRT algorithm explores the space by picking random points. It starts from the arm’s current position and grows small branches, each one moving a little closer to those random points. Over time, these branches spread out like a tree, reaching new areas of the space. When one of the branches gets close enough to the goal, the algorithm connects it, forming a complete path from start to goal without hitting any obstacles.
Basics of RRT
- Initialize the tree with a starting node.
- For a predetermined number of iterations:
- Select a random point in the space.
- Find the closest node in the tree to the random point.
- Add a new node to the tree that's a set distance towards the random point from the closest node.
- If the new node is close enough to the goal, connect it and terminate.
Demo
See this Jupyter notebook for an example of RRT in action:
