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 ${q_{I}}$ and ${q_{G}}$, 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.