Princeton Intro to Robotics (Fall 2026) | Lecture 3: Rapidly Exploring Randomized Trees (RRTs)

Overview

Geometric motion planning must account for a robot’s shape, but discretizing its configuration space grows exponentially with dimension. Rapidly-exploring random trees (RRTs) avoid that upfront grid by incrementally sampling configurations, extending a tree toward them, and using collision checks to keep valid branches; RRT* adds rewiring to improve path length, while RRTs are probabilistically complete under practical conditions.

Key takeaways

A uniform configuration-space grid with B bins per dimension requires B^d cells, which makes graph search impractical for robots with many degrees of freedom.
RRTs avoid explicitly constructing the often-complicated obstacle set C_obs by checking collisions only for configurations and edges encountered as the tree grows.
In each RRT iteration, a random configuration selects a direction, the nearest tree vertex supplies the extension point, and collision checking decides whether the new branch is retained.
Checking only the endpoints of an RRT edge is unsafe: the motion between two collision-free configurations can still intersect an obstacle.
RRT* improves a feasible route through local tree rewiring and can be stopped after any available computation budget; its objective still needs to reflect practical goals, not just geometric path length.
RRTs are probabilistically complete under practical assumptions, but unlike complete graph-search algorithms, they may not terminate when no feasible route exists.

Chapters

0:00 From Grid Search to Planning for Robots with Shape

The motion-planning problem is to move a robot from configuration A to configuration B without collisions, given a geometric environment model.
The preceding lecture covered discrete graph search, including breadth-first search, Dijkstra’s algorithm, and A*.
Treating a robot as a point simplifies planning but ignores its geometry; this lecture develops a way to address that limitation.

5:50 Minkowski Sums Inflate Obstacles Around a Circular Robot

A simple workaround is to enclose the robot in a circle, inflate each obstacle by the circle’s radius, and plan for a point.
The inflation is a Minkowski sum: place the robot’s circle at every point of an obstacle and take the union.
The circle approximation can be overly conservative: a feasible path for a planar quadrotor may disappear in a cluttered environment.

8:00 Configuration Space Turns Robot Geometry into Point Planning

A planar quadrotor has three degrees of freedom: x and y position plus orientation θ, giving configuration space SE(2).
The free space C_free contains collision-free configurations; its complement, C_obs, contains configurations where the robot collides.
A path through C_free represents a valid sequence of configurations for the robot, accounting for both robot and obstacle geometry.

14:00 Why Configuration-Space Grids Hit the Curse of Dimensionality

If a robot has d degrees of freedom and each dimension is divided into B bins, a uniform grid has B^d cells.
A seven-degree-of-freedom robot arm already makes dense discretization expensive; humanoids may have 30–40 or more degrees of freedom.
Explicitly enumerating grid cells and testing each for collision makes both representing C_obs and searching it impractical in high dimensions.

17:30 RRTs Avoid Upfront Discretization and Explicit C_obs Models

The rapidly-exploring random tree (RRT), developed around 1998–1999, builds a search structure directly in continuous configuration space.
Instead of constructing C_obs, an RRT queries whether particular configurations or motions collide with the environment.
Fast collision-checking methods such as GJK—Gilbert–Johnson–Keerthi—help make these repeated queries practical, particularly for convex shapes.

22:00 RRT Iterations Sample Configurations and Extend the Nearest Vertex

Initialize the tree with the start configuration, sample a random configuration Q_rand, and find the nearest existing tree vertex Q_near.
Extend from Q_near toward Q_rand by a chosen step size, producing a candidate configuration Q_s.
The random sample ignores obstacles; the extension step is where collision checking determines whether the candidate can join the tree.

26:00 Collision Checks Reject Invalid Extensions and Grow Branches

If Q_s is in collision, discard it; otherwise, add it to the tree with an edge from Q_near.
The nearest vertex can be any existing tree vertex, not just the most recently added one, which creates branches rather than a single chain.
Each accepted vertex has one parent, so the structure remains a tree without cycles and can later be traversed back toward the start.

35:00 RRT Termination Uses a Goal Tolerance and Parent Pointers

The basic algorithm stops when an accepted Q_s enters an ε-ball around the goal configuration Q_B.
Store each new vertex’s parent Q_near; recover the route by following parent pointers backward from the goal-side vertex to Q_A.
To reach an exact goal, one option is to attempt a collision-checked connection from a nearby tree vertex to Q_B.

41:00 Random Sampling Explores Large Unvisited Voronoi Regions

In obstacle-free examples, the tree spreads outward and progressively fills more of configuration space.
The tree’s vertices induce Voronoi regions; random sampling makes larger, less-explored regions more likely to attract growth.
In obstacle-filled examples, the tree may reach a goal region quickly, but its first feasible route can be jagged and inefficient.

46:00 Validate the Whole RRT Edge, Not Just Its Endpoints

Collision-free endpoints Q_near and Q_s do not guarantee that the segment between them is collision-free.
Check the entire edge using methods such as sampling points along it or, where available, an efficient specialized segment test.
A small extension step and conservative obstacle inflation can reduce the risk of missing collisions between sampled configurations.

52:00 RRT Demonstrations: Six-Degree-of-Freedom Piano and Drone Planning

The piano-movers example plans for a rigid object in 3D with six degrees of freedom: three translations and three rotations.
A drone-planning demonstration shows an RRT-based route executed at speeds reaching about 8 meters per second in MIT’s Stata Center.
The demonstrations concern geometric paths; real drone execution also requires accounting for dynamics, model uncertainty, feedback, and state estimation.

56:00 RRT* Rewires the Tree to Improve Path Length

Basic RRT seeks a feasible collision-free path, not an optimal one, and can produce unnecessary detours.
RRT* adds a rewiring step that locally replaces existing connections when a shorter route is found.
RRT* is anytime: after it finds a feasible path, more computation can improve path length while preserving feasibility.

1:03:00 Probabilistic Completeness: RRTs Find Paths Given Enough Iterations

Classical completeness requires finding a path whenever one exists and terminating with failure when none exists.
RRTs are not classically complete: when no solution exists, the basic algorithm may run indefinitely.
Under practical environment assumptions, RRTs are probabilistically complete: if a path exists, the probability of finding one approaches 1 as iterations increase.

1:09:00 Choosing a Useful Objective for Motion-Planning Optimality

RRT* needs an objective such as path length, but a mathematically shorter route is not automatically the best route for a robot.
Vehicle planning may balance travel time, speed limits, energy use, and passenger comfort rather than minimizing a single quantity.
Poorly chosen or weighted objectives can produce unintended behavior, so defining what “optimal” means is part of the planning problem.

Summary, takeaways, and chapters were generated by AI from the video's transcript and may contain errors. The video belongs to its creator, Introduction to Robotics @ Princeton.