Probabilistic roadmap

The probabilistic roadmap[1] planner is a motion planning algorithm in robotics, which solves the problem of determining a path between a starting configuration of the robot and a goal configuration while avoiding collisions.

The starting and goal configurations are added in, and a graph search algorithm is applied to the resulting graph to determine a path between the starting and goal configurations.

In the construction phase, a roadmap (graph) is built, approximating the motions that can be made in the environment.

Configurations and connections are added to the graph until the roadmap is dense enough.

Given certain relatively weak conditions on the shape of the free space, PRM is provably probabilistically complete, meaning that as the number of sampled points increases without bound, the probability that the algorithm will not find a path if one exists approaches zero.