5.6 Roadmap Methods for Multiple Queries

Previously, it was assumed that a single initial-goal pair was given
to the planning algorithm. Suppose now that numerous initial-goal
queries will be given to the algorithm, while keeping the robot model and
obstacles fixed. This leads to a *multiple-query* version of the motion planning problem. In this case, it makes
sense to invest substantial time to preprocess the models so that
future queries can be answered efficiently. The goal is to construct
a topological graph called a *roadmap*, which efficiently solves
multiple initial-goal queries. Intuitively, the paths on the roadmap
should be easy to reach from each of and , and the
graph can be quickly searched for a solution. The general framework
presented here was mainly introduced in [516] under
the name *probabilistic roadmaps (PRMs)*. The probabilistic
aspect, however, is not important to the method. Therefore, we call
this family of methods *sampling-based roadmaps*. This
distinguishes them from *combinatorial roadmaps*, which will
appear in Chapter 6.