Query phase

In the query phase, it is assumed that ${\cal G}$ is sufficiently complete to answer many queries, each of which gives an initial configuration, ${q_{I}}$, and a goal configuration, ${q_{G}}$. First, the query phase pretends as if ${q_{I}}$ and ${q_{G}}$ were chosen from ${\alpha }$ for connection to ${\cal G}$. This requires running two more iterations of the algorithm in Figure 5.25. If ${q_{I}}$ and ${q_{G}}$ are successfully connected to other vertices in ${\cal G}$, then a search is performed for a path that connects the vertex ${q_{I}}$ to the vertex ${q_{G}}$. The path in the graph corresponds directly to a path in ${\cal C}_{free}$, which is a solution to the query. Unfortunately, if this method fails, it cannot be determined conclusively whether a solution exists. If the dispersion is known for a sample sequence, ${\alpha }$, then it is at least possible to conclude that no solution exists for the resolution of the planner. In other words, if a solution does exist, it would require the path to travel through a corridor no wider than the radius of the largest empty ball [600].