2.2.1 General Forward Search

Figure 2.4: A general template for forward search.

Figure 2.4 gives a general template of search algorithms, expressed using the state-space representation. At any point during the search, there will be three kinds of states:

1. Unvisited: States that have not been visited yet. Initially, this is every state except ${x_{I}}$.
2. Dead: States that have been visited, and for which every possible next state has also been visited. A next state of $x$ is a state $x'$ for which there exists a $u \in U(x)$ such that $x' = f(x,u)$. In a sense, these states are dead because there is nothing more that they can contribute to the search; there are no new leads that could help in finding a feasible plan. Section 2.3.3 discusses a variant in which dead states can become alive again in an effort to obtain optimal plans.
3. Alive: States that have been encountered, but possibly have unvisited next states. These are considered alive. Initially, the only alive state is ${x_{I}}$.

The set of alive states is stored in a priority queue, ${Q}$, for which a priority function must be specified. The only significant difference between various search algorithms is the particular function used to sort ${Q}$. Many variations will be described later, but for the time being, it might be helpful to pick one. Therefore, assume for now that ${Q}$ is a common FIFO (First-In First-Out) queue; whichever state has been waiting the longest will be chosen when ${Q}.GetFirst()$ is called. The rest of the general search algorithm is quite simple. Initially, ${Q}$ contains the initial state ${x_{I}}$. A while loop is then executed, which terminates only when ${Q}$ is empty. This will only occur when the entire graph has been explored without finding any goal states, which results in a FAILURE (unless the reachable portion of $X$ is infinite, in which case the algorithm should never terminate). In each while iteration, the highest ranked element, $x$, of ${Q}$ is removed. If $x$ lies in ${X_{G}}$, then it reports SUCCESS and terminates; otherwise, the algorithm tries applying every possible action, $u \in U(x)$. For each next state, $x' = f(x,u)$, it must determine whether $x'$ is being encountered for the first time. If it is unvisited, then it is inserted into ${Q}$; otherwise, there is no need to consider it because it must be either dead or already in ${Q}$.

The algorithm description in Figure 2.4 omits several details that often become important in practice. For example, how efficient is the test to determine whether $x \in {X_{G}}$ in line 4? This depends, of course, on the size of the state space and on the particular representations chosen for $x$ and ${X_{G}}$. At this level, we do not specify a particular method because the representations are not given.

One important detail is that the existing algorithm only indicates whether a solution exists, but does not seem to produce a plan, which is a sequence of actions that achieves the goal. This can be fixed by inserting a line after line 7 that associates with $x'$ its parent, $x$. If this is performed each time, one can simply trace the pointers from the final state to the initial state to recover the plan. For convenience, one might also store which action was taken, in addition to the pointer from $x'$ to $x$.

Lines 8 and 9 are conceptually simple, but how can one tell whether $x'$ has been visited? For some problems the state transition graph might actually be a tree, which means that there are no repeated states. Although this does not occur frequently, it is wonderful when it does because there is no need to check whether states have been visited. If the states in $X$ all lie on a grid, one can simply make a lookup table that can be accessed in constant time to determine whether a state has been visited. In general, however, it might be quite difficult because the state $x'$ must be compared with every other state in ${Q}$ and with all of the dead states. If the representation of each state is long, as is sometimes the case, this will be very costly. A good hashing scheme or another clever data structure can greatly alleviate this cost, but in many applications the computation time will remain high. One alternative is to simply allow repeated states, but this could lead to an increase in computational cost that far outweighs the benefits. Even if the graph is very small, search algorithms could run in time exponential in the size of the state transition graph, or the search may not terminate at all, even if the graph is finite.

One final detail is that some search algorithms will require a cost to be computed and associated with every state. If the same state is reached multiple times, the cost may have to be updated, which is performed in line 12, if the particular search algorithm requires it. Such costs may be used in some way to sort the priority queue, or they may enable the recovery of the plan on completion of the algorithm. Instead of storing pointers, as mentioned previously, the optimal cost to return to the initial state could be stored with each state. This cost alone is sufficient to determine the action sequence that leads to any visited state. Starting at a visited state, the path back to ${x_{I}}$ can be obtained by traversing the state transition graph backward in a way that decreases the cost as quickly as possible in each step. For this to succeed, the costs must have a certain monotonicity property, which is obtained by Dijkstra's algorithm and $A^*$ search, and will be introduced in Section 2.2.2. More generally, the costs must form a navigation function, which is considered in Section 8.2.2 as feedback is incorporated into discrete planning.