Rapidly-exploring Random Tree (RRT)
Discover the path planning algorithm that lets AGVs tackle high-dimensional spaces with speed and smarts. RRT conquers tough navigation in dynamic spots where old-school grid methods flop.
_hero.png)
Core Concepts
Random Sampling
It picks random spots in the configuration space, letting it scout unknown areas fast—no pre-mapped grid needed.
Nearest Neighbor
For each random sample, RRT grabs the closest node in the tree to grow from, keeping things smooth and connected.
Expansion Steps
The tree expands in fixed-length steps from that nearest neighbor toward the sample, so the robot never tries crazy long leaps.
Collision Checking
Before linking it up, it double-checks the new path segment dodges all static or moving obstacles.
Goal Biasing
To hustle toward the finish, it sometimes picks the actual Goal as the 'random' sample, nudging the tree that way.
Probabilistic Completeness
Math proves: if a path exists, RRT will find it eventually with enough samples and time.
How It Works
The Rapidly-exploring Random Tree builds a graph that fans out into the robot's free space step by step. Skip the grid like A* or Dijkstra—RRT thrives in continuous space.
It kicks off with one node at Start. Each loop samples a random point ($q_{rand}$), finds the nearest tree node ($q_{near}$), and steps a fixed distance toward it for a new candidate ($q_{new}$).
If the line from $q_{near}$ to $q_{new}$ is obstacle-free, boom—new node joins the tree. Rinse and repeat super fast, and the tree branches out like lightning until it hits the Goal.
_diagram.png)
Real-World Applications
Dynamic Warehousing
In busy warehouses with forklifts and people darting around, static maps go stale quick. RRT replans paths in milliseconds to dodge pop-up obstacles without slowing throughput.
Robotic Manipulators
For 6-DOF or 7-DOF arms, the config space is huge. RRT nails collision-free paths for pick-and-place in crowded setups.
Unstructured Environments
Outdoor ag bots or miners deal with bumpy, irregular ground—not neat grids. RRT handles unstructured chaos effortlessly.
Autonomous Parking
RRT shines in non-holonomic planning (think parallel parking), respecting steering limits and no-sideways moves.
Frequently Asked Questions
What makes RRT different from A* (A-Star)?
A* hunts the perfect shortest path on a grid but chokes in high-D or continuous spaces. RRT's random sampling flies through complex stuff, though paths aren't always shortest at first.
Does RRT guarantee the shortest path?
Nope, plain RRT just promises a path if one exists—not the optimal one. For that, grab RRT* (RRT-Star), which rewires the tree to get closer to shortest over time.
What is "Goal Bias" and why is it important?
Pure random sampling might wander into dead-end corners. 'Goal Bias' fixes that: say 5-10% of the time, it samples the Goal spot to steer growth toward victory and speed things up.
How does RRT handle dynamic obstacles?
Standard RRT plans globally for static maps. For movers, rerun it often (like every 100ms) or pair with local planners (TEB, DWA) for snap collision dodges.
Is RRT computationally expensive?
The core operations (sampling and nearest neighbor search) are relatively cheap, making RRT very fast for finding 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?
RRT paths often come out jerky and zig-zaggy from those random lines. Smoothing them post-process is key for smooth AGV rides and less motor strain.
Can RRT be used for non-holonomic robots (like cars)?
Yep. Basic RRT uses straight lines, but Kinodynamic RRT applies real steering/velocity controls to the robot model, so every tree edge is drivable for real.
What is the "step size" parameter?
Step size sets how far each extension goes. Too big? Skips tiny obstacles. Too small? Sloooow progress with tons of nodes.
How is path smoothing applied after RRT?
A go-to trick: on the final path, try shortcutting non-neighbors with straight lines. Clear? Ditch the middles. Then spline or Bezier curves to smooth the bends.
What hardware is required to run RRT?
Basic RRT is light—runs on embedded industrial PCs or even a Raspberry Pi 4 for 2D nav. For 3D arms or rapid replans, beefier CPUs help.
Is RRT deterministic?
Nah, it's stochastic—pure random. Run it twice on the same setup, get different paths. That's why seeding the randomizer matters for testing.
When should I choose RRT over Probabilistic Roadmaps (PRM)?
PRM shines in "multi-query" scenarios where the map stays put and you're planning tons of paths. RRT excels at "single-query" problems, like nailing one quick start-to-goal route or handling environments that change a lot.