Probabilistic Roadmap (PRM)

A probabilistic roadmap, usually shortened to PRM, is a reusable 'road network' of safe positions that a robot builds once and then drives across many times. Think of how a city's road map is surveyed and drawn up just once, after which any driver can plan a trip between any two addresses on it. A PRM does the same for a robot: in a first, slower phase it scatters many random poses across the space of everything the robot could do, keeps only the collision-free ones, and joins nearby safe poses with short links that are also checked to be collision-free. The result is a graph — dots (safe poses) joined by edges (safe motions) — that captures the navigable shape of the free space.

Once that roadmap exists, answering a planning request is fast. To go from some start pose to some goal pose, the planner simply connects each of them to the nearest dots already on the roadmap, then runs an ordinary graph search such as Dijkstra's algorithm or A* over the network to find a route. Because the expensive work of sampling and collision-checking was done up front, each new query is cheap — which is why a PRM is called a multi-query planner: build the map once, reuse it for many different start-and-goal pairs.

This pays off precisely when the world holds still and the robot must make many trips through it — a robot arm picking from fixed bins all day, or a mobile robot patrolling an unchanging building. The drawback is the mirror image of that strength: if the obstacles move, the roadmap's edges may no longer be collision-free and much of it must be rebuilt. For one-off plans through a changing or unknown space, a single-shot method like the rapidly-exploring random tree is usually the better fit.