Rapidly-exploring Random Tree (RRT)

The algorithm guarantees that the probability of finding a feasible path, if one exists, approaches 1.0 as the number of samples goes to infinity. Unlike resolution-complete grid-based planners, RRT does not suffer from discretization bias in high-dimensional spaces. The Voronoi bias ensures the tree is rapidly pulled toward unexplored regions of the Configuration Space (C-Space).

RRT nodes are selected with a probability proportional to the volume of their Voronoi region. Larger Voronoi cells correspond to unexplored frontiers, so the tree is statistically 'pulled' into empty space. This emergent property eliminates the need for explicit exploration heuristics and is the primary reason RRT efficiently covers high-dimensional C-Space without exponential complexity.

RRT does not require an explicit geometric model of obstacles. It relies solely on a collision-checking oracle—a black-box function that returns whether a configuration is valid. This makes it agnostic to obstacle complexity: it handles point clouds, meshes, and voxel grids identically. The algorithm works directly in the robot's Degrees of Freedom (DOF) space without preprocessing.

Unlike the Probabilistic Roadmap (PRM), which precomputes a reusable graph for multi-query scenarios, RRT is a single-query planner. It builds a tree from the start state toward the goal for each new planning problem. This is advantageous in dynamic environments where precomputed roadmaps become invalid due to moving obstacles or changing task constraints.

The standard RRT finds a feasible path but does not optimize for path length or smoothness. The RRT* variant adds a rewiring step: when a new node is added, nearby nodes are reconnected if doing so reduces their cost-to-come. This guarantees asymptotic convergence to the shortest path as sampling time increases, making it a cornerstone for Trajectory Optimization pipelines.

RRT can be extended to Kinodynamic Planning by replacing the straight-line steering function with a forward simulation of the robot's dynamics. Instead of connecting configurations with a linear segment, the tree expands by applying random control inputs over a short time horizon. This ensures every edge in the tree respects velocity, acceleration, and Nonholonomic Constraints, producing directly executable trajectories.