This installment of the notes covers graph search, Dijkstra's shortest path algorithm, A*, IDA*, and STRIPS planning. Examples are drawn from games such as the eight puzzle and Rubic's cube. Generalizations of these games are complete for nondeterministic polynomial space which, by Savich's theorem, is the same as (deterministic) PSPACE. These problems are all modeled well by STRIPS planning which is itself PSPACE complete. This installment of the notes emphasizes iterative deepening (IDA* is Iteratively Deepened A*). STRIPS planning is introduced as a generalization of graph search to the case of incomplete knowledge.
David McAllester, February, 1995