Probabilistic Roadmap

A planning algorithm that first scatters random points into space and connects them into a road network, then searches it for a path.

The probabilistic roadmap is a sampling-based motion planning algorithm generally credited to a 1996 paper by Lydia Kavraki and colleagues. It works in two phases: a construction phase that randomly samples collision-free points in configuration space (the space of all possible robot poses) and connects nearby points that can be joined by a straight, collision-free line, forming a graph — the ‘roadmap’; and a query phase that connects the start and goal into this graph and searches it with Dijkstra or A*. Its strength is that the roadmap, once built, can be queried repeatedly (multi-query), which suits settings where the environment stays largely fixed and planning happens often; its weakness is that narrow passages are hard to sample into. It has probabilistic completeness: given enough samples, the probability of finding an existing path approaches 1. RRT, by contrast, grows a single tree from the start each time and suits one-off queries better.

ExampleFor a fixed workstation arm, a PRM roadmap is built once in joint space ahead of time; every time the pick-and-place targets change, only the new start and goal need to be connected into the existing network and searched, without replanning from scratch.

Also called

PRM, PRM Planner

Related

Rapidly-exploring Random Tree · Sampling-Based Planning · Probabilistic Completeness · Configuration Space (C-Space) · Path Planning · A* Search

Sources

Wikipedia: Probabilistic roadmap
Lynch & Park, Modern Robotics（§10.5.2 The PRM Algorithm）