Rapidly-exploring Random Tree (RRT)

The Rapidly-exploring Random Tree (RRT) is a sampling-based path-planning algorithm that searches for a viable route from a starting point to a destination by continuously generating random sample points and branching a "tree" outward across the search space.

It adopts a fundamentally different approach compared to the familiar A* algorithm. While A* requires the search space to be pre-divided into a grid—much like navigating a precise map—RRT acts more like an explorer forging ahead through unknown or intricate terrain, making it exceptionally well-suited for high-dimensional environments with complex kinematic constraints.

💡 How It Works: How the Tree "Grows"

Think of RRT as planting a tree within a defined space, where it autonomously branches out to find a path:

1. Seeding: The starting point is defined as the "root" of the tree.

2. Random Sampling: A random sample point is generated within the planning space. This point can appear anywhere, even inside an obstacle.

3. Locating the Nearest "Branch": The algorithm identifies the closest existing node on the tree to this newly generated random point.

4. "Growing" toward the Target: From this nearest node, a new "branch" of fixed step size extends towards the random point to form a new node. If the random point falls within an obstacle, it is discarded; if it exceeds the step limit, an incremental point within that step size is generated along the vector.

5. Safety Check: The newly extended branch undergoes collision detection. If it does not collide with any obstacle, the new node is officially added to the tree.

6. Iterative Loop: Steps 2 to 5 are repeated iteratively until a branch reaches the destination threshold. Tracing back along the connected branches from the destination to the starting point yields a feasible, collision-free path.

The core strength of this approach lies in its ability to rapidly explore and cover an entire space, outperforming conventional grid-based algorithms particularly in environments densely packed with obstacles.

🚧 Challenges and Refinements: RRT Is Not Without Flaws

While RRT is highly capable in complex scenarios, it comes with notable limitations:

• Jagged, non-smooth paths: Because of its random branching nature, the resulting path is often a series of abrupt zig-zag segments, making it difficult for an autonomous vehicle to track smoothly in real-world driving conditions.

• Sub-optimal path length: It prioritises finding a viable path over finding the shortest one, meaning the algorithm offers no guarantee of global optimality.

• Search inefficiency in tight spaces: In intricate environments, it can generate numerous redundant search branches, leading to high computational overheads and slower convergence times.

Consequently, for real-world autonomous driving applications, engineers implement substantial enhancements to the baseline RRT algorithm. These include introducing goal-biasing strategies to steer tree growth towards the target, adopting Bidirectional RRT (expanding two trees simultaneously from both the origin and destination) to expedite search times, hybridising with algorithms like A*, and applying path pruning and smoothing techniques to enhance trajectory quality. Recent research highlights that such optimised RRT variants can cut computational overhead and path-planning duration by 64% to 78%.