Rapidly-exploring Random Tree (RRT)
Discover the path planning algorithm that empowers AGVs to navigate high-dimensional spaces with speed and flexibility. RRT solves complex navigation challenges in dynamic environments where traditional grid-based methods fail.
_hero.png)
Core Concepts
Random Sampling
The algorithm selects random coordinates within the configuration space, allowing it to explore unknown areas rapidly without requiring a pre-mapped grid.
Nearest Neighbor
For every random sample, RRT efficiently identifies the closest existing node in the tree to extend from, ensuring continuity in the path generation.
Expansion Steps
The tree grows by taking fixed-length steps from the nearest neighbor towards the random sample, preventing the robot from attempting impossible long-distance jumps.
Collision Checking
Before adding a new edge, the algorithm verifies that the path segment does not intersect with any known static or dynamic obstacles in the environment.
Goal Biasing
To speed up convergence, the algorithm occasionally chooses the actual Goal State as the "random" sample, pulling the tree intentionally towards the destination.
Probabilistic Completeness
A mathematical guarantee that if a viable path exists between the start and goal, RRT will eventually find it given enough time and samples.
How It Works
The Rapidly-exploring Random Tree algorithm works by iteratively building a graph that explores the free space of a robot's environment. Unlike A* or Dijkstra, which require a discretized grid, RRT operates in continuous space.
The process begins with a single node at the Start position. In each iteration, a random point ($q_{rand}$) is generated. The algorithm searches the existing tree for the nearest node ($q_{near}$). It then attempts to move from $q_{near}$ toward $q_{rand}$ by a fixed distance step, creating a new candidate node ($q_{new}$).
If the path between $q_{near}$ and $q_{new}$ is collision-free, the new node is added to the tree. This process repeats rapidly, causing the tree to spread like lightning, filling the empty spaces of the map until a branch reaches the Goal region.
_diagram.png)
Real-World Applications
Dynamic Warehousing
In facilities with constantly moving forklifts and personnel, static maps become obsolete quickly. RRT allows AGVs to re-plan paths in milliseconds to avoid sudden obstacles while maintaining high throughput.
Robotic Manipulators
For robotic arms with high degrees of freedom (6-DOF or 7-DOF), the configuration space is vast. RRT excels here, finding non-colliding paths for pick-and-place operations in complex cells.
Unstructured Environments
Unlike grid-based factories, agricultural or outdoor mining robots face irregular terrain. RRT navigates these unstructured environments without needing a perfect checkerboard grid.
Autonomous Parking
RRT is used in non-holonomic path planning (like car parking), where the vehicle cannot move sideways. It accounts for the kinematic constraints of the vehicle steering radius.
Frequently Asked Questions
What makes RRT different from A* (A-Star)?
A* searches a discretized graph or grid to find the mathematically optimal path, but it struggles in high-dimensional spaces or continuous environments. RRT relies on random sampling in continuous space, making it much faster for complex, high-dimensional problems, though the path it finds is rarely the shortest one initially.
Does RRT guarantee the shortest path?
No, standard RRT does not guarantee optimality; it only guarantees it will find a path if one exists. For optimized paths, a variant called RRT* (RRT-Star) is used, which rewires the tree as it grows to asymptotically approach the shortest path over time.
What is "Goal Bias" and why is it important?
If RRT only sampled purely randomly, it might explore corners of the room irrelevant to the destination. "Goal Bias" means that with a certain probability (e.g., 5-10%), the algorithm picks the Goal coordinate as the sample, gently pulling the tree growth toward the destination to speed up convergence.
How does RRT handle dynamic obstacles?
Standard RRT is a global planner for static maps. To handle moving obstacles, RRT is typically re-run at a high frequency (e.g., every 100ms) as the robot moves, or used in conjunction with a local planner (like TEB or DWA) that handles immediate collision avoidance.
Is RRT computationally expensive?
The core operations (sampling and nearest neighbor search) are relatively cheap, making RRT very fast for finding a feasible path. However, as the environment becomes cluttered or the number of nodes increases significantly, the nearest neighbor search can become a bottleneck without spatial indexing structures like KD-trees.
What are the downsides of using RRT?
The resulting paths are often "jerky" and jagged because they are formed by random straight-line connections. Post-processing (path smoothing) is almost always required to create drivable trajectories for AGVs to prevent wear and tear on motors.
Can RRT be used for non-holonomic robots (like cars)?
Yes. While basic RRT connects points with straight lines, Kinodynamic RRT extends the tree by applying valid control inputs (steering/velocity) to the robot model. This ensures that every edge in the tree is a path the robot can actually physically drive.
What is the "step size" parameter?
Step size determines how far the tree extends towards a sample in one iteration. If too large, the robot might jump over small obstacles (collision checking fails). If too small, the algorithm becomes slow and requires many nodes to cover the distance to the goal.
How is path smoothing applied after RRT?
A common technique is to take the final path and attempt to connect non-adjacent nodes with straight lines. If the shortcut is collision-free, the intermediate nodes are removed. Splines or Bezier curves are then used to round off the corners.
What hardware is required to run RRT?
Basic RRT is lightweight and can run on standard embedded industrial PCs or even stronger microcontrollers (like Raspberry Pi 4) for 2D navigation. However, for 3D manipulation or high-frequency replanning, more powerful CPUs are recommended.
Is RRT deterministic?
No, it is a stochastic (randomized) algorithm. If you run RRT twice on the exact same map with the same start and goal, you will get two different paths. This is why random seed control is important during debugging and testing.
When should I choose RRT over Probabilistic Roadmaps (PRM)?
PRM is better for "multi-query" scenarios where the map doesn't change and you need to plan many paths. RRT is superior for "single-query" problems where you need to solve one specific start-to-goal problem quickly, or when the environment changes frequently.