Prune-PRM: Faster Roadmap Planning by Batch Collision Pruning

Python, OMPL, NumPy, Moon Lab

2026 · built as a real OMPL planner

A PRM variant written as a real OMPL planner in Python. Classic PRM checks for collisions while it wires the graph. Prune-PRM builds the roadmap without any collision checks, then removes colliding nodes and edges in one batch using the exact obstacle geometry. A locality bound, R_eff, proves that most edges cannot collide, so they are kept without any test.

Problem

The test world

A point robot in a 60×60 box must go from (10, 10) to (50, 50) around four circular obstacles. The same world is shared by the demo, the benchmark and the plots, so every result lines up.

Prune-PRM path from start to goal around four grey circular obstacles — A Prune-PRM solution: 23 waypoints from start to goal.

Idea

Build blind, prune once

Four batch steps: sample random points anywhere, even inside obstacles; build a skeleton by joining each point to its k nearest neighbours, ignoring obstacles; prune points inside a circle and edges that cross one; then search the result with Dijkstra for the shortest path.

Animation of Dijkstra searching the pruned roadmap from start to goal

R_eff

The locality bound

R_eff = r + inflation + max edge length. Any edge that hits a circle must have an endpoint inside that circle’s R_eff ring: its closest point to the centre is within r + inflation, and each endpoint is at most one edge length from that point. So an edge with both ends outside every ring is provably safe and is kept with zero tests. Tested on the same skeleton, the localised prune does about 3–5× fewer edge-vs-circle tests than the naive one, and an assertion checks that both give the identical roadmap.

Three charts: prune time of naive vs R_eff pruning over neighbours per node, max edge length and number of samples — Naive (orange) vs R_eff pruning (blue). The gain is steady with more neighbours or samples, and shrinks as edges get longer.

OMPL

A real OMPL planner

Prune-PRM subclasses ob.Planner and overrides solve(). A nanobind trampoline lets OMPL’s C++ core call the Python method, so it plugs into SimpleSetup and ompl.tools.Benchmark exactly like PRM or RRT. It uses OMPL for the state space, the sampler, start and goal, and the output path. It bypasses OMPL’s yes/no validity checker, because R_eff needs the real obstacle shapes.

Benchmark

Against PRM, PRM* and FMT*

10 runs, 1 s budget. All planners solve the world. Prune-PRM takes about 14 ms (prune + search, with the roadmap assumed built), PRM about 25 ms, FMT* about 12 ms, and PRM* uses its full budget for the shortest path. The time column is not like-for-like (Python with analytic circles vs C++ with a collision callback); path length is a fair comparison.

Bar charts of planning time (log scale) and path length for PrunePRM, PRM, PRM* and FMT*

What I learnt

OMPL architecture: state spaces, validity checkers, samplers, problem definitions and the planner lifecycle.
Custom planners: subclassing ob.Planner from Python, and how the nanobind trampoline connects it to the C++ core.
Proof-driven speed-ups: turning a geometric bound into skipped work, and checking with an assertion that the result does not change.
Fair benchmarking: ablations on the same input, and saying clearly which numbers are and are not like-for-like.
Debugging: a ROS libompl shadowing the pip install through LD_LIBRARY_PATH, and a double-free crash from freeing OMPL states by hand.

Try it

Tutorial notebook in Colab: runs in the browser, installs OMPL by itself.
Talk slides: Prune-PRM & OMPL
Full write-up (PDF): method, R_eff proof, OMPL integration and benchmark method.