Why a grid stops working
In an earlier rung we planned by carving the world into a grid and running Dijkstra's algorithm or A* over the cells. That works beautifully for a robot rolling across a flat floor, where the configuration space — the set of all poses the robot can take — has just two or three dimensions. But picture a robot arm with seven joints. Its configuration is a list of seven angles, so its configuration space is seven-dimensional.
Suppose we chop each joint angle into a modest 100 slices. A two-dimensional grid would have 100 x 100 = 10,000 cells — easy. A seven-dimensional grid has 100 to the seventh power: one hundred trillion cells. No computer can build, store, or search that. This explosion of cells as the number of dimensions grows is often called the curse of dimensionality.
The shared trick: sample, check, connect
Sampling-based planning sidesteps the grid entirely. Instead of visiting every cell, it throws darts: it picks random configurations, keeps the good ones, and stitches them together. The same three-step engine drives both planners in this guide.
- Sample. Draw a random configuration — say, a random setting for all seven joint angles. This is one dart landing somewhere in the configuration space.
- Check. Run a collision check: does the robot in that pose hit an obstacle, the wall, or itself? Keep only samples that land in free space and discard the ones that fall into obstacle space.
- Connect. Try to link each surviving sample to nearby ones with a short, straight motion. If the robot can slide between them without colliding, that link becomes an edge you can travel along.
Notice we never enumerate the whole space — we only ever ask the collision checker about the handful of poses our darts happen to hit. The samples concentrate effort where it matters, and the planner gets better the longer it runs.
PRM: a reusable web of roads
The probabilistic roadmap, or PRM, runs the three steps in two phases. First comes a build phase: scatter many samples across the whole free space and connect each to its neighbors, growing a web of safe roads — the roadmap. This phase ignores where the robot starts or where it needs to go.
Then comes the query phase: to plan a specific motion, connect the start pose and the goal pose into the existing web, then run plain A* over the roadmap to find a route. The payoff is reuse — once the web is built for a fixed scene, you can answer thousands of start-to-goal queries cheaply.
RRT: one tree reaching outward
Sometimes you do not want to pre-build a whole map — you just need one path, right now, in a scene you may never revisit. That is the job of the rapidly-exploring random tree, or RRT. Instead of a web, it grows a single tree rooted at the start pose, reaching outward toward unexplored corners of the free space.
- Draw a random sample somewhere in the configuration space.
- Find the tree node nearest to that sample, and grow a short branch from it a small step toward the sample.
- If a collision check clears that little branch, add it to the tree. Repeat until a branch reaches the goal.
Because random samples tend to fall in the large empty regions the tree has not yet reached, RRT naturally pulls itself into open space and explores fast — hence the name. A plain RRT stops the moment it touches the goal, so the resulting path is often a single quick, ragged route.
Its popular variant RRT* ("RRT-star") goes further. Each time it adds a node, it rewires nearby branches to use cheaper connections, so the more samples it draws, the shorter and straighter its path becomes — converging toward the optimal route given enough time, rather than settling for the first one found.
The honest tradeoff
Sampling buys speed in high dimensions, but it gives up two comforts a grid gave us. First, the raw output is jagged: a chain of straight segments with abrupt corners that no real motor wants to track. Planners usually hand this path to a smoothing or trajectory optimization stage before the robot ever moves.
Second, these methods are only probabilistically complete: if a path exists, the chance of finding it climbs toward certainty as you draw more samples — but at any finite moment, failing to find one does not prove none exists. A grid search, by contrast, can declare with certainty that no path is possible.
In practice, the choice is about queries. PRM amortizes a slow build over many trips through a fixed scene; RRT and RRT* are the go-to when you need one path fast in a fresh or changing world. Both usually serve as the global planner, with a local controller handling the moment-to-moment dodging.