In an earlier video, we learned that path planning based on a true roadmap representation of free C-space is complete, meaning that the planner will find a path if one exists. Since it is difficult to analytically calculate a true roadmap, we look for methods to approximately construct a roadmap. One type of approximate roadmap is the probabilistic roadmap, or PRM for short. The PRM is constructed from a set of configurations sampled from the C-space, and it can be called a probabilistic roadmap because, as the number of samples tends to infinity, the likelihood that the graph is a true roadmap goes to 100 percent. An advantage of a PRM graph over a grid-based graph is that the structure of the free C-space is generally captured by the PRM with many fewer nodes than with a grid graph. PRMs have been used to solve complex motion planning problems in high-dimensional C-spaces.

This figure shows a PRM for a two-dimensional C-space.

To construct a PRM, we can use this algorithm. In the first phase, we generate N samples of the free C-space. These free configurations can be generated by uniformly randomly sampling the C-space and only keeping the sample if it is collision-free, but non-uniform sampling strategies can also be used to increase the likelihood that the PRM is able to represent narrow passageways in the C-space with a smaller number of samples.

The N free-space configurations generated in the first phase of the algorithm are the nodes of the graph. The second phase of the algorithm tries to connect the nodes with edges. For each node, we find a set of k nearby nodes. Then, for each of these neighbor nodes, we try to find a path from the original node to the neighbor. To do this, we use a very simple and fast local path planner which does not attempt to avoid obstacles. For example, the planner could just choose a straight line between the original node and the neighbor. We then check whether this path is collision free, and if so, we add an edge between the two nodes. At the end of this second phase of the PRM construction algorithm, we have a graph that should approximately represent the free space, depending on our choice of the number of samples N, the number of neighbors k, the sampling algorithm, and the local path planner. The choice of the sampling algorithm and the local path planner provides a lot of flexibility to customize the basic algorithm.

Once we have preprocessed the C-space by generating the PRM, we can solve different path planning problems by connecting different start and goal configurations to the PRM, as you see here, and using A-star search to find a good path through the PRM. Thus the PRM planner is usually thought of as a multiple-query planner: we invest time to generate a good representation of the free C-space so we can then efficiently solve several motion planning problems.

In the next video we'll see a different sampling-based motion planner typically used for single queries.