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].

Steven M LaValle 2012-04-20