Heuristic search, either in the space of world states reached through progression or in the space of subgoals reached through regression, is a common and successful approach to classical planning. For example, at the recent 6th International Planning Competition (IPC-2008), the three best-performing satisficing planners and two of the three best-performing optimal planners in the sequential planning tracks followed this paradigm.

In this lecture we survey the principles and state of the art of heuristic-search domain-independent planning. Apart from the choice of search algorithm, the main feature that distinguishes heuristic planners is their heuristic estimator. Most current heuristic functions are based on one of the following four ideas: (1) delete relaxation, (2) critical paths, (3) abstractions, and (4) landmarks. While delete relaxation and heuristics based on it will be discussed in the lecture by Héctor Geffner, in this lecture we will present some of the core ideas underlying heuristics based on the other three paradigms, with a particular emphasis on admissible heuristics and abstractions.