Stanford posts Pavone's motion planning lecture: RRT, PRM and FMT*

Stanford Online has put the seventh lecture of AA274A Principles of Robotic Autonomy, "Motion Planning II: Sampling-Based Methods," on YouTube. The recording dates from fall 2019. The lecturer is Marco Pavone, an adjunct professor in Stanford's Department of Aeronautics and Astronautics and Senior Director of Autonomous Vehicle Research at NVIDIA. Before joining the university, he worked at NASA's Jet Propulsion Laboratory. This is not a product release but teaching material, yet the topic directly determines how robots and self-driving cars plan trajectories. Stanford itself notes that the course structure, assignments and materials have changed since 2019, and that the links in the description lead to the current version.

Why a planner needs random points

Classical graph search (Dijkstra, A*) requires discretizing the configuration space. That is tolerable for a planar robot. For a manipulator with seven joints and a grid of 100 values per axis, you get 100 to the seventh power, or about 10^14 cells. Storing and traversing such a grid is impossible.

Sampling-based methods get around the problem differently. The planner draws random configurations, discards those that cause a collision, and connects the remaining ones with short feasible segments. It does not need an explicit map of obstacles in configuration space. All it needs is a function that answers whether a given point or segment is free.

Which algorithms belong to this block

The lecture description gives only a general topic title, but the standard set for sampling-based planning looks like this:

• PRM (Kavraki, Švestka, Latombe, Overmars, 1996): builds a graph from random points once and then answers many queries. It suits a static environment.
• RRT (LaValle, 1998): grows a tree from the start toward random points. It finds a path quickly in high-dimensional spaces and is more convenient than PRM for a single query.
• RRT* (Karaman, Frazzoli, 2011): adds tree rewiring and achieves asymptotic optimality. Path cost converges to the optimum as the number of samples grows.
• FMT* (Janson, Schmerling, Clark, Pavone, 2015): developed by Pavone's group. It traverses the samples in an order close to the fast marching method and often reaches a good path with fewer collision checks.
• Connection radius in PRM*: scales as (log n / n)^(1/d), where d is the dimension of the space. This estimate underlies the optimality proofs.

The key theoretical concept here is probabilistic completeness. If a path exists, the probability of finding it tends to one as the number of points grows. There are no time guarantees, and that is an important caveat.

Why the 2019 lectures have not gone out of date

Sampling-based planners have not gone anywhere. The OMPL library, which MoveIt uses for planning by default, includes implementations of PRM, RRT, RRT* and FMT. Modern directions build on this base: learned distributions for choosing points, parallel collision checking on GPUs, as in NVIDIA's cuRobo, and hybrids with trajectory optimization. The bottleneck is the same for all of them: collision checking usually eats most of the planning time.

The course has a free textbook, Principles of Robot Autonomy, at porabook.com and an open syllabus at stanfordasl.github.io/PoRA-I. For self-study, it is rare to find lectures, text and assignments all in one place.

How to use the material in practice

Start with the textbook, then watch the lecture. Implement RRT in a plane in roughly a hundred lines of code and count how many collision-check calls it takes to find one path. Then plug in OMPL and compare RRT, RRT and FMT on the same scene with a narrow passage. That is where the main weakness of these methods shows: the probability of sampling into a narrow corridor is small, and search time grows sharply.

Keep two limitations in mind. RRT paths come out jagged and almost always need smoothing. And for vehicles with dynamics, such as cars, geometry alone is not enough: you need kinodynamic variants and coordination with the controller. The 2019 lecture provides the foundation, but you will have to fill in the details from the current version of the course.