RRT Mechanics

Imagine you are trying to find the best path through a dense, dark forest without a map. You randomly pick a direction, walk a short distance, and then stop to see if you hit a tree or found a path. This simple process of trial and error is exactly how a robot explores a new space using a specific tool called Rapidly-exploring Random Tree. Robots often face environments that are too complex for traditional math to solve in one go. Instead of calculating every possible turn, they build a map as they move. By building this map, the robot slowly reveals a safe route toward its final destination.

The Mechanics of Tree Expansion

When a robot begins its journey, it starts at a single point known as the root of the tree. The robot picks a random point within the environment to act as a target for its next move. It then searches its current tree to find the node that sits closest to this new random point. Once it identifies that closest node, the robot attempts to extend a new branch toward the random target. If the path to that target is clear of obstacles, the robot adds a new node to its growing tree. This process repeats hundreds of times per second to build a complex web of reachable paths.

Key term: Node — a specific point in the environment that the robot has already verified as safe and reachable.

Think of this like a climber throwing a rope to find a secure anchor point on a cliff. The climber does not know exactly where the best holds are located on the rock face. They throw the rope in a random direction to see if it catches on something solid. If the rope catches, they pull themselves toward that point and prepare for the next toss. The robot does the same thing by testing random directions and keeping the branches that do not collide with obstacles. This allows the robot to explore large areas without needing a perfect model of the room.

Building the Path to the Goal

After the tree has grown enough, the robot must shift its focus from random exploration to reaching the actual destination. The robot periodically forces the random point to be the goal location instead of a random coordinate. This action pulls the tree branches toward the target, which helps the robot find a way through tight corners or hallways. If the tree successfully connects to the goal, the robot traces the nodes backward to find the exact path it took. This sequence of nodes becomes the reliable map the robot follows to reach the finish line safely.

The following steps describe how the robot makes decisions during each cycle of the tree expansion:

1. Generate a random coordinate within the workspace to determine a potential direction for movement.
2. Locate the nearest existing node in the current tree to serve as the starting point for growth.
3. Calculate a straight line from that nearest node toward the random coordinate to plan the path.
4. Check for obstacles along that specific line to ensure the robot does not hit any solid objects.
5. Add the new node to the tree if the path is clear so the robot can continue moving.

By following these steps, the robot ensures that it constantly expands its reach while avoiding dangerous collisions. This method is incredibly efficient because it does not waste time calculating parts of the room that the robot will never visit. It only focuses on the space that helps it get closer to the goal. As the tree grows denser, the robot finds smoother and more direct routes between its current position and the objective. This simple loop of random sampling and path checking provides a robust way for machines to navigate unknown spaces without human help.

---

Rapidly-exploring Random Tree algorithms allow robots to navigate complex spaces by iteratively sampling random points and connecting them to a growing map of safe paths.

But what does it look like in practice when the robot encounters a dynamic obstacle that moves while the tree is growing?