Sampling-based planning: PRM

Grid search like A* doesn't scale past 4 or 5 dimensions — the curse of dimensionality kills it. For arms with 6+ DOF, you need sampling-based planning. PRM (Probabilistic Roadmap) is the canonical solution: build a graph of random valid configurations, search the graph. Built once, queried many times. Old (1996) but still the right answer for some problems.

The two-phase recipe

Phase 1: Build the roadmap (offline)

1. Sample N random configurations from C-space. Reject any that collide with obstacles.
2. For each sample, find the K nearest neighbors. Try connecting each pair with a straight-line path. If the path is collision-free, add an edge.
3. The result: a graph of valid configurations connected by valid local paths.

For a 6-DOF arm: ~5000 nodes, ~50,000 edges, ~10–60 seconds to build.

Phase 2: Query (online)

1. Connect start and goal configurations to the nearest k roadmap nodes.
2. Run A* (or Dijkstra) on the augmented graph.
3. Smooth the resulting path.

Query time: typically <100 ms. Cheap because the hard work is in phase 1.

The right problem fit

PRM shines when:

• Same environment, many queries: pick-and-place from many starts to many goals on a fixed shelf.
• High-DOF, single-query is acceptable to wait for: build the roadmap once, reuse forever.
• The C-space is mostly free: high free-space ratio means random samples are usually valid.

PRM is the wrong tool when:

• The environment changes: rebuild the roadmap on every change. RRT or trajectory optimization is faster.
• The free space is narrow: random samples rarely connect across narrow passages. Need sample biasing.
• You only ever plan one path: amortized cost of building the roadmap doesn't pay off.

The narrow-passage problem

PRM struggles to connect samples through narrow corridors in C-space. Examples: an arm threading through a small hole in a wall; a peg inserting into a barely-large-enough socket.

Modern variants address this:

• Gaussian sampling: sample pairs near obstacles; one valid + one invalid samples likely separated by a narrow passage.
• Bridge test: sample a midpoint between two close samples; if midpoint is collision-free but endpoints aren't, you've found a passage.
• Visibility-PRM: limit samples to mutually-visible nodes; reduces graph size while preserving connectivity.

Performance considerations

• Collision checking dominates: 90% of phase 1's time is in collision checks (each candidate edge requires checking many points along it). Optimize the collision-checker.
• k-d trees for nearest-neighbor: brute-force NN is O(N) per query; k-d tree is O(log N). Significant for large roadmaps.
• Roadmap caching: serialize the roadmap to disk; reload across robot restarts.

The 2026 production landscape

PRM in pure form is rare in 2026 production. Three replacements absorbed its niche:

• RRT-Connect: faster for single-query problems. Default for most arm planning.
• Trajectory optimization (CHOMP, STOMP): smoother paths; better for arms.
• Learning-based planners: neural-network roadmaps (Motion Planning Networks). Fast inference; brittle generalization.

PRM still appears in:

• Multi-query industrial setups (warehouse arm picking from a shelf 1000 times/day).
• Graph-based reasoning over feasible trajectories (TAMP, where each PRM node is a candidate sub-goal).
• Educational settings (PRM is the cleanest introduction to sampling-based planning).

Implementation in 30 lines

import numpy as np
from scipy.spatial import KDTree

def build_prm(n_samples=5000, k=10, dof=6):
    samples = []
    while len(samples) < n_samples:
        q = np.random.uniform(joint_low, joint_high, dof)
        if not in_collision(q):
            samples.append(q)
    samples = np.array(samples)
    tree = KDTree(samples)

    edges = []
    for i, q in enumerate(samples):
        _, neighbors = tree.query(q, k+1)
        for j in neighbors[1:]:  # skip self
            if collision_free_path(samples[i], samples[j]):
                edges.append((i, j))
    return samples, edges

def query_prm(samples, edges, start, goal):
    # Connect start and goal to roadmap, A*, smooth
    ...

The hard parts (in_collision, collision_free_path) come from your collision checker (FCL, Bullet, MoveIt's built-in). The PRM logic itself is simple.

The OMPL connection

OMPL (Open Motion Planning Library) ships PRM, RRT, RRT*, and ~20 other sampling-based planners with consistent APIs. MoveIt uses OMPL under the hood. For practical arm planning, you don't write PRM from scratch — you call OMPL.

// C++ via OMPL
auto si = std::make_shared<ob::SpaceInformation>(joint_space);
si->setStateValidityChecker([&](const ob::State *s) {
    return !in_collision(s);
});
auto prm = std::make_shared<og::PRM>(si);
prm->setProblemDefinition(pdef);
prm->growRoadmap(60.0);  // 60 seconds
ob::PlannerStatus solved = prm->solve(5.0);  // 5 seconds query timeout

Exercise

For a 2-DOF planar arm in a 2D world with obstacles, implement PRM in Python (~80 lines). Build a roadmap; query 100 different start/goal pairs. Then perturb one obstacle slightly; observe how many edges become invalid. The fraction tells you when to rebuild vs. update incrementally.

Next

RRT and RRT* — the go-to planners for single-query problems. Faster than PRM when you only need one path.