Must an RDT use random samples?

No. The broader formulation permits deterministic dense sequences as well.

Does dense mean many cycles and connections?

No. Here it refers to coverage in configuration space; the structure is a tree.

Does connecting to the nearest point give a globally shortest route?

No. It is a local construction rule, as the worked example demonstrates.

AI Glossary / Graphs and symbolic AI / Intermediate

Rapidly exploring dense trees

Definition

Rapidly exploring dense trees, or RDTs, are incremental exploration structures that grow a tree through a configuration space using a dense sequence of target samples. The sequence may be deterministic or random. Rapidly exploring random trees, or RRTs, are the random-sampling case within this broader family in LaValle's formulation.

What it means

A configuration describes the state needed to locate a robot or another moving system, such as its position and joint angles. Exploring configuration space helps a planner discover routes between feasible configurations without constructing a complete geometric map of every possibility.
“Dense” means that, in the appropriate limiting construction, the tree can get arbitrarily close to points in the relevant space. It does not mean that the finite graph has almost every possible edge. An RDT remains a tree, with branching paths rather than a fully connected mesh. A finite sample budget produces only partial exploration, so a missed route is not proof that no route exists.

How it works

In the basic obstacle-free construction, begin at a root configuration. Take the next target from a dense sequence and find the nearest point on the space already reached by the tree. Connect that point toward the target. If the nearest point lies inside an existing edge, split that edge to create a branching vertex.
This exact nearest-point formulation includes the interiors of edges, not just stored vertices. Practical approximations can differ. With obstacles, a local connection must be checked and may stop before the target or add nothing. The geometry, distance measure, sampling sequence, and collision-checking procedure therefore form part of the method's specification.

Three practical examples

A motion-planning research prototype can compare deterministic dense sample sequences with random sequences while using the same exploration structure.
A robot simulator can grow a tree of collision-checked configurations to investigate whether a feasible route to a goal can be found.
An algorithm lesson can show how branching from an edge interior changes the explored geometry compared with selecting only existing vertices.

Think of it this way

Think of gradually extending a branching network of trails toward selected destinations. New trails can branch from somewhere along an existing trail rather than only at its endpoints. The analogy is limited because configuration-space distance may represent joint-angle differences, and a mathematically short connection may be physically infeasible for a real moving system.

Worked example

Consider an original obstacle-free example in a two-dimensional Euclidean space. The tree initially contains root O = (0, 0), vertex A = (4, 0), and the straight edge between them. The next target is B = (2, 3).
The nearest point on the existing tree is Q = (2, 0), the perpendicular projection onto the edge. Its distance to B is 3. Each endpoint is farther away: the distances from O and A to B are both sqrt(13), about 3.606. Therefore selecting only endpoints would produce a different connection from selecting the nearest point on the tree's full geometric trace.
The RDT construction splits O - A into O - Q and Q - A, then adds Q - B. The graph now has four vertices and three edges. It is still a tree: splitting an existing edge and attaching one new branch has not created a cycle.
The path from the root to B has length 2 + 3 = 5. The direct distance from O to B is about 3.606, so this construction has not produced a shortest root-to-target path. Local nearest connection and global path optimality are different properties.
If the next target is C = (5, 0), its nearest point is A, giving a new edge of length 1 and a tree with five vertices and four edges. These chosen targets illustrate individual updates; a short list is not itself an infinite dense sequence. Adding an obstacle across a proposed edge would require collision checking and could prevent that connection.

Illustrative case study

Fictional case: Spruce Robotics studies a planar planning problem in simulation. The researchers compare a deterministic sequence that increasingly covers the region with independent random samples. They hold the distance metric and collision tests constant so differences in exploration can be attributed more clearly to the sampling rule.
They record time to a feasible route, the explored tree, and cases where the allotted budget finds no solution. The fictional study does not claim that deterministic sampling is always superior, that the first route is shortest, or that a simulated route is ready to execute on hardware.

Common misconceptions and mistakes

Do not confuse spatial density with dense-graph terminology. A tree can cover a geometric space increasingly closely while having only one fewer edge than vertices. Do not assume every sampled target becomes a vertex when obstacles block local connections.
The limiting-density intuition is easiest in the stated obstacle-free setting. Planning guarantees require assumptions about free space, sampling, connection rules, and feasible paths. A continuous configuration space is not exhaustively searched by any finite collection of samples. Also, using a dense deterministic sequence is different from repeating a small fixed set of points, which may leave large regions permanently unexplored.

Business use

The business relevance lies mainly in robotics, simulation, and other systems needing feasible motion through complex spaces. RDTs provide a conceptual framework for comparing exploration strategies without tying the idea exclusively to random sampling.
For a practical evaluation, define the robot's configuration variables, geometric constraints, and local motion model before comparing planners. Assess route feasibility and computation separately from route quality. A shortest-looking line in a plot may violate constraints that the state representation omits. Retain enough information about the sample sequence and collision checks to explain why a route was accepted.

Check your understanding

Why does Q become a vertex when B is added?

Answer: Q is the nearest point on an existing edge. Splitting that edge makes Q an explicit branch point while preserving the tree structure.

Related terms

Rapidly exploring random tree
Configuration space
Nearest neighbor search
Motion planning
sampling-based planning
dense sequence
collision detection
local planner

Learn next

Replace target B with (1, 2). Its nearest point on O - A is (1, 0). The root-to-target tree path has length 3, while the direct distance is sqrt(5), about 2.236. Use this to distinguish local attachment from global route optimization.

Sources

Sources: LaValle, Planning Algorithms, Section 5.5, RDT family and dense sampling: https://msl.cs.illinois.edu/~lavalle/planning/node230.html . Section 5.5.1, nearest points on the tree, edge splitting and obstacles: https://msl.cs.illinois.edu/~lavalle/planning/node231.html .

Previous: Rao-Blackwellized particle filter Next: Rapidly exploring random tree