Probabilistic Road Maps
Probabilistic Road Map (PRM) is the most popular multi-query algorithm. In the learning phase, free configurations are randomly sampled to become the nodes of a graph. Connections are made between the nodes to form the edges, representing feasible paths of the roadmap. Additional nodes are then created to expand the roadmap and improve its connectivity. In the query phase, the planner tries to find a path that connects start and goal configurations using the graph created in the learning phase.
Generate many samples in the space.
Instead of choosing points in the configuration space uniformly, we can choose them randomly, in the hope that we will choose a set of configurations that capture the underlying structure of the free space. We have probabilistic road maps but real worlds have a lot of dimensions.
In the previous chapter, we talked about configuration space. We talked about linking adjacent points in free space with edges, and then using this graph to plan pass through the space. This approach of discretizing the configuration space evenly on a grid, can work well when the dimension of the space is small, say two or three. But the number of samples required can grow to be frighteningly large as we increase the dimension of the space to five, six, eight, ten, or beyond.
Probabilistic Road Map Pseudocode
Repeat n times
Generate a random point in configuration space, x
If x is in freespace
Find the k closest points in the roadmap to x according to the Dist function
Try to connect the new random sample to each of the k neighbors using the LocalPlanner procedure. Each successful connection forms a new edge in the graph.
Issues
While these methods work very well in practice, they’re not strictly speaking complete. A complete path planning algorithm would find a path if one existed, and report failure if it didn’t.
In these cases, we might find success via denser samples.