The International Planning Competition (IPC), which started in 1998, has subsequently been held biennially, and has provided a focus for much recent work in planning. One major outcome from the competitions has been the provision of a substantial number of planning problems that can serve as benchmarks for planning systems. Planning is known to be a hard problem, and so it is also of interest to have some way of determining the complexity of a planning problem that is more discriminating than polynomial time (P) or nondeterministic polynomial time (NP). One of the two major intellectual contributions to planning theory that this book makes is an exhaustive discussion of the complexity of the problems from the IPCs. This occupies the first part of the book. The second contribution is a description of the author’s fast-downward planner, with an integration of the discussion into the framework established for planning problems in the first part of the book.

For the first discussion, the author groups the problems from the planning competitions into three types: transport, which includes problems such as the logistics problem from the IPC; route, which includes the grid problem in which a robot has to navigate through a grid where keys are required to unlock some portions of the grid; and other, containing, among others, the problem of scheduling satellite observations. By abstracting each of these categories, the author is able to establish a collection of complexity results for each of the problems. It should be noted that these results assume that P and NP are distinct. A technique that is used repeatedly is to relate the problems to known hard problems. Thus, grid is related to the minimum set cover problem, and the card game FreeCell is related to three literals satisfiability (3SAT). Along the way, the original IPC specifications of the problems--in planning domain definition language (PDDL)--are clarified. Characteristic results for transport and route are that plan existence is polynomial if fuel is unrestricted and NP otherwise; further bounded plan existence is always NP complete.

The fast-downward planner differs from most previous planning systems in that it allows state variables that are not binary (as opposed to the propositional nature of Stanford Research Institute Problem Solver (STRIPS) variables). A major benefit of this is that the structure of the causal graph associated with a task is more likely to be acyclic. Informally, this causal graph contains a vertex for each state variable, and arcs from variables that occur in preconditions to variables that occur in the post condition of the same operator. If the causal graph contains a cycle, then it is not possible to obtain a hierarchical decomposition of the problem.

Fast downward works in three phases. In the first, translation, the problem is compiled into what the author calls a multi-valued planning task (MPT), in which the variables are no longer restricted to being binary. This phase is followed by a knowledge compilation phase that builds the data structures that store the causal graph. Eliminating cycles in the graph requires that the problem be relaxed (a form of abstraction often used in planning and problem solving). In this phase, the system builds an efficient mechanism for determining the successor states of any given state. The third and final phase is the search for the solution. Central to this phase is the causal-graph heuristic that estimates the cost of reaching the goal from a given state, but other heuristics are involved as well.

Helmert applied fast downward to each of the problems from the IPC list. Performance figures are given in terms of the number of unsolved tasks for each problem type. The author concludes that fast downward is competitive with the state of the art. One particular heuristic mix is identified as a clear winner among the choices for the search phase of fast downward.

The level of detail in the book is somewhat uneven. In general, in the first part, where the IPC problems are considered, there is plenty of detail with full proofs given. The second part of the book, related to fast downward, has somewhat less detail: the author is quite open about the fact that much of this is an overview. However, the ideas for the main algorithms in the reductions are clearly explained. The reader interested in implementing fast downward will still have a lot to do, but the outlines are there. The book is an important contribution to planning. By showing how a problem can be recast as an MPT, with a corresponding simplification of the causal graph, the author has made a significant addition to the planner’s armory.