2.2 Searching for Feasible Plans

The methods presented in this section are
just graph search algorithms, but with the understanding that the
state transition graph is revealed incrementally through the
application of actions, instead of being fully specified in advance.
The presentation in this section can therefore be considered as
visiting graph search algorithms from a planning perspective. An
important requirement for these or any search algorithms is to be *systematic*. If the graph is finite, this means that the algorithm
will visit every reachable state, which enables it to correctly
declare in finite time whether or not a solution exists. To be
systematic, the algorithm should keep track of states already visited;
otherwise, the search may run forever by cycling through the same
states. Ensuring that no redundant exploration occurs is sufficient
to make the search systematic.

If the graph is infinite, then we are willing to tolerate a weaker definition for being systematic. If a solution exists, then the search algorithm still must report it in finite time; however, if a solution does not exist, it is acceptable for the algorithm to search forever. This systematic requirement is achieved by ensuring that, in the limit, as the number of search iterations tends to infinity, every reachable vertex in the graph is explored. Since the number of vertices is assumed to be countable, this must always be possible.

As an example of this requirement, consider Example 2.1 on an infinite tile floor with no obstacles. If the search algorithm explores in only one direction, as depicted in Figure 2.3a, then in the limit most of the space will be left uncovered, even though no states are revisited. If instead the search proceeds outward from the origin in wavefronts, as depicted in Figure 2.3b, then it may be systematic. In practice, each search algorithm has to be carefully analyzed. A search algorithm could expand in multiple directions, or even in wavefronts, but still not be systematic. If the graph is finite, then it is much simpler: Virtually any search algorithm is systematic, provided that it marks visited states to avoid revisiting the same states indefinitely.