Rapidly-Exploring Random Tree (RRT/RRT*)
A rapidly-exploring random tree, almost always called an RRT, is a method that finds a path by growing a branching tree outward from the robot's starting pose until a branch reaches the goal. It works in repeated little steps: pick a random target somewhere in the space of poses the robot could take, find the point already on the tree that sits closest to that target, and reach a short step from that point toward it — adding a new twig only if the motion stays collision-free. Because random targets land all over the space, the tree is pulled to grow fastest into the wide-open regions it has not yet explored, fanning out quickly to fill the free space, which is exactly where the name comes from.
An RRT is built for a single query in a possibly unknown or cluttered space: you grow one tree, from one start, until it touches the goal, then trace the branch back to read off the path. This makes it a natural fit for mobile robots and arms that must plan a fresh motion on the spot. The plain version is fast and good at finding some valid path, but it makes no promise the path is short — the route it returns is often jagged and roundabout, a first way through rather than a good one.
RRT* (said 'RRT-star') is the upgrade that fixes this. Each time it adds a new point, it also looks at the nearby points already in the tree and rewires their connections whenever routing through the new point would reach them more cheaply. Over many iterations this quiet rewiring keeps straightening and shortening the tree's paths, so RRT* is asymptotically optimal: the longer it runs, the closer its path creeps to the true shortest one. You trade extra computation for steadily better paths — plain RRT when you just need any safe path quickly, RRT* when you can afford to let it polish the route.
A drone must thread between trees to reach a clearing. Plain RRT sprouts a tree from its launch point that gropes outward until a branch pokes into the clearing — fast, but the flight path zig-zags. Run as RRT*, the same search keeps rewiring its branches as it goes, and the path it hands back gradually straightens into a near-direct glide.
Plain RRT finds a jagged path fast; RRT* keeps rewiring until the path is nearly optimal.
RRT and RRT* are single-query planners that grow one tree per request, unlike a PRM, which builds one reusable roadmap to answer many requests.