Stanford OnlineStanford AA274A Principles of Robotic Autonomy | Autumn 2019 | Motion Planning Sampling-Based
Stanford Online
Workspace And Configuration 0:06
Motion planning is posed in the workspace, but the search really happens in configuration space. A robot is shrunk to a point there, while obstacles are enlarged. With a triangular robot that only translates, this is easy to draw. If the point stays out of the forbidden region, the robot stays clear in the real world.
Sampling Based Methods 5:01
Once the robot can also rotate, the configuration space grows to three dimensions, and the obstacle shapes become much harder to build exactly. That is why sampling-based methods are used. They do not draw every obstacle in configuration space. They sample possible robot states, ask a collision checker whether each one is safe, and keep the safe ones to build a road map. These methods are simple, flexible, and useful beyond pure geometry, though they do not give a clean answer about how many samples are enough or whether no path exists.
Road maps and neighbors 18:31
Each sample is connected to nearby samples within a radius, not to every other point. A full graph would need too many collision checks, and each edge must be tested by breaking it into small steps in configuration space. The aim is a smaller radius that still gives enough neighbors without making the work too heavy.
Using the map 20:31
Once the road map is built, you attach the start and goal to the closest samples, checking that those links are collision free. Then you run a normal path search such as Dijkstra or A star on the graph. The result is simple to code when collision checking is available, but the map only represents free space implicitly through sampling.
Sampling and replanning 23:00
Uniform random sampling is only a baseline. In practice, you often sample more near the robot or goal, and people also use data-driven methods that learn a better sampling distribution from many solved planning problems. The path is then executed and recomputed in a receding-horizon way, usually every 200 milliseconds to a few seconds, so the plan can adapt to changes.
Collision checking in workspace 25:00
Collision checking is a geometric test in the workspace, not a full conversion of obstacles into configuration space. You move the robot into a pose, then use libraries such as Bullet to test whether the robot and obstacle shapes intersect. The hard translation is avoided because the configuration-space obstacle representation is too expensive to build directly.
Tree growth with RRT 31:03
RRT grows a tree from the start one sample at a time. Each new random configuration is checked for collision, connected to the nearest tree node, and extended only part of the way so branches stay short. The method is single-query and incremental, unlike PRM, which is built once as a batch road map.
Goal biasing 34:01
A plain random tree is unlikely to hit the goal exactly, so RRT usually samples the goal every so often, such as every 20 samples. This goal biasing pushes the tree toward the target and makes the method work much better. Many later variations change how far to extend or how to choose the sample, and one important variant is designed to become optimal as samples go to infinity.
Lazy roadmap building 37:01
Lazy PRM builds the graph without checking every edge right away. You run A* on the unverified graph, then check only the edges on the path it returns. If one edge is in collision, you drop it and run A* again. This saves work when you only need one start and goal, but not when you want many queries, where full PRM can be worth the cost.
Tree growth and bias 39:00
RRT is more incremental. It samples one node at a time and extends the tree, so it does not restart from the beginning. Its name comes from a Voronoi bias. Frontier nodes have larger Voronoi cells, so random samples are more likely to land in unexplored space. The speaker notes that this is only a conceptual picture, not something you compute in practice.
Limits and guarantees 42:00
These methods get expensive as dimensions rise, because coverage grows exponentially with dimension. They are usually practical in about three to eight dimensions, and nearest-neighbor search is a major bottleneck. The clean theory is only asymptotic. PRM and RRT are both guaranteed to find a feasible path as the number of samples goes to infinity, but plain RRT can give zigzag paths and may stay far from optimal.
Towards optimal variants 47:01
To get optimality, PRM uses a radius that shrinks like log n over n to the 1 over d power, which leaves about log n neighbors per sample. The speaker notes that the published proof needed correction, leading to a small change in the exponent to 1 over d plus one. RRT also has an optimal version, RRT star, which rewires edges to straighten the tree. FMT star tries to combine PRM’s path quality with RRT’s speed by lazily choosing low-cost connections and checking collisions only once per sample.
Collision and multi-robot limits 55:30
Collision checking is a major cost in sampling-based planning, and nearest-neighbor search is another bottleneck. For single robots, there is no collision between two feasible paths for the same robot because it takes one path or the other. With multiple robots, you must account for collisions between different trajectories, and the configuration space grows quickly. The same goes for sampling: non-uniform sampling is often used, sometimes to focus near the robot or near likely obstacles, and more recently by learning a sampling distribution from data.
Dynamics and reachable sets 58:01
For kinodynamic planning, you want paths that avoid obstacles and also respect the system dynamics, such as a car that cannot move sideways. One simple approach is forward propagation: sample a state, pick a control from the allowed set, choose a time horizon, and integrate the differential equation forward to grow the tree. A more informed approach is to solve a small trajectory optimization problem between samples. Then you collision check the resulting path afterward. Nearest neighbors also change: you use reachable sets, not simple balls, because some directions are easier to reach than others.
Low dispersion samples 1:14:00
Planning works best when the samples have low dispersion, so they cover the space well. The key result here is that deterministic sequences with asymptotically optimal dispersion are known, and their scaling goes like n to the minus one over d, where n is the number of samples.
PRM with determinism 1:15:00
For PRM, the sample placement and the connection radius are the two main choices. If you use low-dispersion samples and let the ball radius shrink no faster than n to the one over d, PRM is guaranteed to converge to the optimal path without random sampling.
Better results in practice 1:16:03
That means randomization is not the real reason PRM and RRT work. Careful deterministic sequences can perform better in tests across dimensions two to eight, and they also give convergence-rate guarantees and a path toward safety-critical use.
Next module and office hours 1:18:01
The class moves next to robotic perception, starting with sensors and then cameras, including how to model them, process camera data, extract features, and find semantic meaning. Office hours run until 1, and the midterm reminder follows.
AI-generated summary. It can be wrong or incomplete - check anything that matters against the original.
