2.2.4 A Unified View of the Search Methods

It is convenient to summarize the behavior of all search methods in terms of several basic steps. Variations of these steps will appear later for more complicated planning problems. For example, in Section 5.4, a large family of sampling-based motion planning algorithms can be viewed as an extension of the steps presented here. The extension in this case is made from a discrete state space to a continuous state space (called the configuration space). Each method incrementally constructs a search graph, ${\cal G}(V,E)$, which is the subgraph of the state transition graph that has been explored so far.

All of the planning methods from this section followed the same basic template:

1. Initialization: Let the search graph, ${\cal G}(V,E)$, be initialized with $E$ empty and $V$ containing some starting states. For forward search, $V = \{{x_{I}}\}$; for backward search, $V = \{{x_{G}}\}$. If bidirectional search is used, then $V = \{{x_{I}},{x_{G}}\}$. It is possible to grow more than two trees and merge them during the search process. In this case, more states can be initialized in $V$. The search graph will incrementally grow to reveal more and more of the state transition graph.
2. Select Vertex: Choose a vertex $n_{cur} \in V$ for expansion; this is usually accomplished by maintaining a priority queue. Let $x_{cur}$ denote the state associated with $n_{cur}$.
3. Apply an Action: In either a forward or backward direction, a new state, $x_{new}$, is obtained. This may arise from $x_{new} = f(x,u)$ for some $u \in U(x)$ (forward) or $x = f(x_{new},u)$ for some $u \in U(x_{new})$ (backward).
4. Insert a Directed Edge into the Graph: If certain algorithm-specific tests are passed, then generate an edge from $x$ to $x_{new}$ for the forward case, or an edge from $x_{new}$ to $x$ for the backward case. If $x_{new}$ is not yet in $V$, it will be inserted into $V$.^2.2
5. Check for Solution: Determine whether ${\cal G}$ encodes a path from ${x_{I}}$ to ${x_{G}}$. If there is a single search tree, then this is trivial. If there are two or more search trees, then this step could be expensive.
6. Return to Step 2: Iterate unless a solution has been found or an early termination condition is satisfied, in which case the algorithm reports failure.

Note that in this summary, several iterations may have to be made to generate one iteration in the previous formulations. The forward search algorithm in Figure 2.4 tries all actions for the first element of ${Q}$. If there are $k$ actions, this corresponds to $k$ iterations in the template above.