Why use random samples?

They provide a way to explore a large space without listing every possible configuration in advance.

Is an RRT the same as a random walk?

No. It grows a branching structure and can extend from different existing states.

Does RRT learn a movement policy?

Basic RRT is a planning procedure; constructing its tree does not by itself train a learned policy.

AI Glossary / Graphs and symbolic AI / Intermediate

Rapidly exploring random tree

Definition

A rapidly exploring random tree, or RRT, is a sampling-based planning structure that grows a branching tree through a state or configuration space. It repeatedly samples a target and attempts to extend the existing tree toward that target. In motion planning, accepted extensions must satisfy the applicable movement and collision constraints.

What it means

A robot's configuration can include several joint angles rather than a simple map location. Enumerating every possible configuration is often impractical. An RRT explores selected portions of that space and records how newly reached configurations connect to earlier ones.
The randomness concerns the exploration targets. It does not mean executing arbitrary physical movements without checking them. A planner can build and test the tree in a model before a controller attempts a route. The tree records candidate connections; the accuracy of the environment model and the validity checks determine what those connections establish.

How it works

A common implementation selects a random target, finds the nearest stored tree state, and moves a limited distance from that state toward the target. If the local motion passes validity checks, it adds the new state with a parent connection. Repetition creates branches. Some iterations may deliberately target the goal.
States bordering less explored regions tend to attract more targets because they are nearest to a larger portion of the sampling space. This encourages outward exploration. The distance metric, extension limit, sampling distribution, and local movement model all influence the result. Nearest-vertex implementations should be distinguished from idealized constructions that find the nearest point anywhere along existing edges.

Three practical examples

A robotic-arm simulator can seek a collision-free sequence of joint configurations for moving a gripper between fixtures.
A mobile-robot planning demonstration can explore routes around obstacles while comparing several random seeds and extension lengths.
A virtual assembly tool can investigate whether a component can move through a constrained space, provided its geometry and permitted motions are represented adequately.

Think of it this way

Think of growing a branching set of trails toward randomly selected landmarks. Each new trail begins from a nearby established junction. The analogy is limited: a robot's configuration space may have many dimensions, and closeness in the planner's metric does not by itself establish that the connecting movement is feasible.

Worked example

Consider an original two-dimensional, obstacle-free demonstration with straight-line motion, Euclidean distance, and maximum extension length 1. Start with O = (0, 0). We stipulate the next targets to make the calculation reproducible; this is a trace illustrating the update rule, not evidence of random coverage.
For target T1 = (3, 0), the nearest vertex is O. Move one unit toward T1 and add A = (1, 0), with parent O. The target is not itself added because it lies beyond the extension limit.
For T2 = (1, 2), distances from O and A are sqrt(5) and 2. Select A and add B = (1, 1). For T3 = (2, 1), B is nearest at distance 1, so add C = (2, 1), with parent B.
The recorded route O - A - B - C has length 3. The direct distance O - C is sqrt(5), about 2.236, showing that this construction does not automatically return a shortest route. If a later attempted segment crosses a forbidden region, rejecting that entire extension is one possible implementation policy. Valid endpoints alone would not justify accepting the segment.

Illustrative case study

In a fictional case, Bramble Robotics tests a virtual gripper transfer between two workstations. An RRT finds a route for one fixture arrangement but times out for another. The team labels the first result a candidate feasible path and the second an unresolved planning attempt.
Engineers replay the candidate against their collision model, inspect clearances, and test whether the motion controller can follow the resulting trajectory. They also record planning time across repeated seeds. This separates finding a geometric path from demonstrating a reliable physical operation. No real company outcome or performance improvement is implied.

Common misconceptions and mistakes

A timeout does not prove that no path exists. A found path is not automatically globally shortest. Theoretical probabilistic-completeness statements require assumptions and do not promise success within a chosen finite budget.
Checking only sampled endpoints can miss collisions between them. A straight-line connector in joint space also need not satisfy a system's dynamic constraints. RRT, RRT-Connect, and RRT* are related but distinct methods; guarantees or implementation details should not be transferred between their names without checking the specific algorithm.

Business use

Business teams evaluating robotic automation can use RRT-based planning as one component of a feasibility workflow. Useful measurements include solution rate over repeated trials, planning latency, path length, clearance, and the cost of validating motions.
Document the robot model, obstacle geometry, sampling settings, stopping rule, and definition of success. A fast demonstration on an empty scene says little about performance in a cluttered production layout. Compare planners on representative tasks and retain failed trials in the evaluation record.

Check your understanding

Why is A = (1, 0), rather than T1 = (3, 0), the first added vertex?

Answer: The stipulated extension limit is 1, so the planner advances only one unit from O toward that target.

Related terms

Rapidly exploring dense trees
Configuration space
Motion planning
Nearest neighbor search
collision detection
sampling-based planning
RRT-Connect
RRT*

Learn next

Repeat the first extension with a limit of 2. The added point becomes (2, 0). Then introduce an obstacle intersecting the proposed segment and explain why changing the step limit cannot replace checking the complete motion.

Sources

Sources: OMPL, geometric RRT class documentation, sampling, nearest-state expansion, goal bias and range: https://ompl.kavrakilab.org/classompl_1_1geometric_1_1RRT.html . LaValle, Planning Algorithms, RDT/RRT family and geometric construction: https://msl.cs.illinois.edu/~lavalle/planning/node230.html and https://msl.cs.illinois.edu/~lavalle/planning/node231.html .

Previous: Rapidly exploring dense trees Next: Rare events