Probabilistic roadmap

The Probabilistic Roadmap (PRM) method 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 basic idea behind PRM is to take random samples from the configuration space of the robot, testing them for whether they are in the free space, and use a local planner to attempt to connect these configurations to other nearby configurations. 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.

PRM is provably probabilistically complete, meaning that as the number of sampled points increases without bound, the probability that the algorithm won't find a path if one exists approaches zero.

The probabilistic roadmap method consists of two phases: a construction and a query phase. In the construction phase, a roadmap (graph) is built, approximating the motions that can be made in the environment. First, a random configuration is created. Then, it is connected to some useful neighbors. A neighbor is useful if its distance to the new configuration is less than a predetermined constant. Configurations and connections are added to the graph until the roadmap is dense enough. In the query phase, the start and goal configurations are connected to the graph. The path is obtained by a Dijkstra's shortest path query. See e.g. for a more extensive elaboration of the PRM method.