Probabilistic Roadmaps (PRM)

A probabilistic roadmap builds a graph of free space by random sampling. It throws down random points, keeps those that are collision-free, and links each to its nearby neighbors with straight, collision-free edges. Once built, the same roadmap can answer many start-goal queries quickly.

Number of samples Neighbors to connect

Drag the start and goal.

Build once, query many times

Build: sample $n$ random configurations, keep those in $\mathcal{C}_{\text{free}}$, and connect each to its $k$ nearest neighbors if the straight segment between them is free. Query: connect the start and goal to the roadmap the same way, then run Dijkstra or A*.

$$P(\text{path found}) \to 1 \text{ as } n \to \infty \quad \text{(probabilistic completeness)}$$

What to notice

With few samples the roadmap often misses the narrow gap in the middle wall, so the path takes the long way around, or no path is found. Narrow passages are the classic weakness of uniform sampling, since few random samples land inside them. More samples or more neighbors fix it, at the cost of more collision checks. PRMs suit robots that plan many times in the same space, like an arm in a fixed work cell.