Skip to content
Tutorials Center
My learning

Topics

Lesson 23 of 38 ยท Path Planning

Sampling-Based Planning: PRM and RRT

Plan paths in high-dimensional spaces with random sampling. Build a Probabilistic Roadmap and an RRT in Python, and learn RRT*, bias and completeness.

Grid search dies in high dimensions. A robot arm with seven joints would need an astronomical grid, and you rarely need every cell anyway. Sampling-based planners take a different approach: instead of covering the space, they throw random configurations at it, keep the free ones, and connect them into a graph or tree. You never build the obstacles explicitly. You only need a function that answers "is this configuration (or this short motion) collision free?"

Two algorithms dominate: PRM, a map for many queries, and RRT, a fast tree for a single query. Both fit in a few dozen lines, and you will run each below.

The two building blocks

Every sampling-based planner relies on two primitives from the collision checker:

  1. is_free(q): is this configuration free of collisions?
  2. edge_free(q1, q2): is the straight segment between two configurations free? (Usually checked by testing points every small step along it.)

Everything else is bookkeeping. This design is why these planners scale to arms with many joints: the collision checker works in the workspace, and the planner never sees an obstacle's shape in C-space.

Sampling-based planning

Sample Draw random configurations.
Check Keep only collision-free ones.
Connect Join them with safe straight edges.
Search Find a path in the resulting graph.
1 / 2

Probabilistic Roadmap (PRM)

PRM works in two phases.

  1. Learning phase. Sample N free configurations (nodes). For each node, try to connect it to its k nearest neighbors with straight edges; keep the edges that are collision free.
  2. Query phase. Connect the start and goal to the roadmap, then run a graph search (A* or Dijkstra) on it.

The roadmap is reusable as long as the obstacles do not move, which suits a factory arm that repeats many tasks in a fixed cell.

Python PRM in a 2D world

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

If PRM returns no path, the roadmap is disconnected; the fix is simply more samples or a larger K. That is the probabilistic completeness property: as the number of samples grows, the probability of finding an existing path approaches 1.

Rapidly-exploring Random Trees (RRT)

For a single query, building a full roadmap is wasteful. RRT grows a tree from the start and aims it at random targets:

  1. Sample a random configuration q_rand (every so often, use the goal itself: a goal bias of about 5 to 10 percent).
  2. Find the tree node q_near closest to q_rand.
  3. Move from q_near toward q_rand by at most a fixed step size to get q_new.
  4. If the segment is collision free, add q_new to the tree with q_near as its parent.
  5. Stop when a node lands close enough to the goal, then follow parents back to the start.

The nearest-node rule gives the tree a Voronoi bias: nodes at the frontier have large empty regions around them, so they get picked more often. The tree therefore sprints into unexplored space.

Python RRT with goal bias

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The path is valid but wiggly. RRT cares about finding a route quickly, not about its quality.

RRT*, smoothing and other improvements

  • RRT* adds two steps after creating q_new: pick the best parent among nearby nodes (the one that gives the lowest cost), then rewire neighbors through q_new when that is cheaper. It is asymptotically optimal: with more samples the path converges toward the shortest one.
  • RRT-Connect grows two trees, one from the start and one from the goal, and tries to join them. It is often the fastest for arms.
  • Path shortcutting. After any planner returns, try joining non-adjacent waypoints with straight, collision-free edges and delete the detours. A few hundred random attempts clean most of the zigzag.
  • Lazy collision checking and informed sampling (sampling only inside the ellipse of better paths once a solution exists) save time.

Planning libraries such as OMPL (used inside MoveIt for robot arms) implement all of these. Choose RRT-Connect for a quick first solution, then shortcut or run RRT* for a better one.

Strengths and limits

Strength Weakness
Dimensionality Handles 6 to 20+ dimensions Needs many samples in tough cases
Obstacles Only needs a collision checker No explicit map of C-space
Narrow passages Probabilistic guarantee Slow to find tight gaps; special samplers help
Path quality RRT*, shortcutting improve it Plain RRT paths are jagged and random
Repeatability PRM reuses its roadmap RRT results vary between runs (fix the seed to compare)

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why do sampling-based planners work well for robot arms with many joints?

    Sampling avoids the exponential cost of grids: it only asks whether sampled configurations and short edges are free.
  2. 2. What is the main difference between PRM and RRT?

    PRM has a learning phase producing a roadmap for many queries. RRT grows a tree from the start for a single query.
  3. 3. What does goal bias do in RRT?

    Sampling the goal now and then (5 to 10 percent) speeds up convergence without losing the exploration of random samples.
  4. 4. What does RRT* add to RRT?

    RRT* chooses low-cost parents and rewires neighbors, making it asymptotically optimal.

Summary

  • Sampling-based planners sample random configurations and need only is_free and edge_free checks.
  • PRM builds a roadmap once and answers many queries with graph search.
  • RRT grows a tree from the start, biased by frontier nodes and optionally the goal.
  • They are probabilistically complete; RRT* is asymptotically optimal.
  • Shortcutting and RRT-Connect make results shorter and faster in practice.

Next: Trajectory Generation and Smoothing