Sampling-Based Planning
Imagine planning a path for a 6-axis robot arm. The configuration space is 6-dimensional (one per joint angle). To use a grid-based planner, you'd need to discretize each dimension — say, 10 grid points per joint.
That's 10^6 = 1 million grid cells. For a 7-axis arm, it's 10 million. For a robot arm mounted on a mobile base (9 dimensions), it's 1 billion cells.
Grids don't scale to high dimensions. We need a different approach.
The Big Idea: Random Sampling
Instead of discretizing the entire space, sample random configurations and check if they're collision-free. Build a graph connecting nearby collision-free samples. Search this graph for a path.
This is sampling-based planning. The two most famous algorithms:
- RRT (Rapidly-exploring Random Tree): Grows a tree from start toward goal
- PRM (Probabilistic Roadmap): Builds a reusable roadmap of the entire space
Let's dive into each.
RRT (Rapidly-exploring Random Tree)
RRT builds a tree of collision-free configurations, starting from the start pose and growing toward the goal.
The Algorithm
1. Start with a tree containing only the start configuration
2. Repeat N times:
a. Sample a random configuration in C-space
b. Find the nearest node in the tree to this sample
c. Try to extend the tree toward the sample by a small step
d. If the step is collision-free, add the new node to the tree
3. When the tree reaches the goal (or gets close), extract the path
Key insight: By sampling randomly across the space, RRT explores uniformly. The tree naturally "spreads out" to cover reachable areas.
Example (2D for visualization)
Imagine a 2D robot navigating around a wall:
Step 1: Start at S Step 5: Tree has spread
┌─────────────┐ ┌─────────────┐
│ │ │ · · │
│ S │ │ /│\· · │
│ │ │ │ S─┼─· · │
│ · ███ │ │ \│ · │
│ ███ G │ │ · ███ G │
│ ███ │ │ · ███ │
└─────────────┘ └──/────███────┘
After ~1000 samples, the tree has grown around the obstacle and reached the goal region. Now extract the path from the tree.
RRT is probabilistically complete — given infinite time, it will find a path if one exists. But it's not optimal: the path can be jagged and longer than necessary. Many variants (RRT*, RRT-Connect) improve speed and quality.
When to Use RRT
- High-dimensional spaces (robot arms, multi-robot systems)
- Single-query problems (plan once, execute once)
- Complex obstacles (narrow corridors, cluttered environments)
- Real-time constraints (RRT is fast for a single path)
Pros:
- Works in any dimension (tested up to 100+!)
- Simple to implement (~100 lines of code)
- Fast for single queries
Cons:
- Paths are often jerky and suboptimal
- No guarantee of shortest path
- Needs post-processing (smoothing) for real robots
PRM (Probabilistic Roadmap)
PRM takes a different approach: build a reusable roadmap of the entire space, then query it for paths.
The Algorithm
Preprocessing (build roadmap):
1. Sample N random collision-free configurations
2. For each sample, connect it to nearby samples (within distance d)
3. Store the resulting graph (the "roadmap")
Query (find path):
1. Connect start and goal to the roadmap
2. Run A* or Dijkstra on the roadmap graph
3. Return the path
Example
Preprocessing: Sample + connect Query: Connect start/goal, search
┌─────────────┐ ┌─────────────┐
│ ·─· ·─· │ │ S─· ·─· │
│ \│ / \ │ │ \│ / \ │
│ ·─· · │ │ ·─· · │
│ ███ │ │ │ ███ │
│ · ███ │ │ · ███─G │
│ /│\ ███ │ │ /│\ ███ │
│ · · · │ │ · · · │
└─────────────┘ └─────────────┘
Once the roadmap is built, queries are fast — just a graph search. This is great if you need to plan many paths in the same environment.
Think of PRM like pre-computing a highway system. Building the roadmap takes time, but once it exists, finding routes is instant. RRT is like driving off-road — you blaze a new trail every time, but you're free to go anywhere.
When to Use PRM
- Multi-query problems (plan many paths in the same environment)
- Static environments (the map doesn't change)
- Offline planning (you have time to preprocess)
Pros:
- Very fast queries after preprocessing
- Roadmap can be reused indefinitely
- Can optimize roadmap quality (more samples → better paths)
Cons:
- Slow preprocessing (sampling thousands of configs)
- Wastes computation on unreachable areas
- Doesn't adapt to dynamic obstacles
RRT vs. PRM: When to Use Each
| Scenario | Best Choice |
|---|---|
| Robot arm picks objects from a shelf | PRM (many queries, same environment) |
| Self-driving car navigates city | RRT (single route, changing traffic) |
| Drone explores unknown cave | RRT (map is unknown, single mission) |
| Warehouse robot patrols same routes | PRM (reuse roadmap) |
| Surgical robot in operating room | PRM (static environment, precise paths) |
Practical Improvements
Basic RRT and PRM are simple but naive. Production systems use enhanced versions:
RRT Variants
- RRT*: Rewires the tree to improve path quality (nearly optimal)
- RRT-Connect: Grows two trees (from start and goal) simultaneously (2x faster)
- Informed RRT*: Uses a heuristic to sample only in promising regions
PRM Variants
- Lazy PRM: Skip collision checks during preprocessing; check only when querying a path (faster build)
- Adaptive PRM: Add samples where needed (narrow passages) instead of uniformly
Smoothing
Both RRT and PRM produce jagged paths. Common post-processing:
- Shortcutting: Try to connect non-adjacent waypoints directly, skip intermediate points
- Spline fitting: Fit a smooth curve (Bezier, B-spline) through waypoints
- Gradient descent: Optimize the path to minimize length + smoothness cost
What's Next?
We've covered global planning — finding a high-level route from start to goal. But what happens when a person walks into your path, or the map is slightly wrong? Next, we'll explore local vs. global planning and how robots react to immediate obstacles.