In the query phase, it is assumed that is sufficiently complete to answer many queries, each of which gives an initial configuration, , and a goal configuration, . First, the query phase pretends as if and were chosen from for connection to . This requires running two more iterations of the algorithm in Figure 5.25. If and are successfully connected to other vertices in , then a search is performed for a path that connects the vertex to the vertex . The path in the graph corresponds directly to a path in , 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, , 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