Researchers in the field of artificial intelligence (AI) have long studied automated planning, and there is a vast body of literature related to AI planning, ranging from journal and conference research papers, to several edited collections of papers and books describing approaches or systems, or case studies of applications. Textbooks that compile the accumulated knowledge and experience into a form suitable for teaching a course, however, have been lacking. This book is intended to fill this gap.

There are five major divisions to this book, together covering most of the field. A sixth section presents applications of planning in selected domains. A brief survey of other planning-related research, and appendices on search, first-order logic, and model checking, round out the book.

The section on classical planning (chapters 2 through 5) discusses much of the early basic research in planning, including representations for planning problems, complexity analysis, and planning as search in state space and plan space. It focuses on abstracting and presenting methods and lessons from early planning systems, rather than on describing the systems themselves. This is followed by a section on subsequent “neo-classical” work, consisting of graph-based planning (GRAPHPLAN), propositional satisfiability, and constraint satisfaction techniques. The third major division (chapters 9 through 12) collects relatively short discussions of heuristics and control rules, along with situation calculus and deductive logic, and includes a fairly detailed chapter on hierarchical task network planning, under the title of heuristics and control strategies. Parts 4 and 5 discuss advanced topics: temporal reasoning in planning, scheduling, and planning under uncertainty of different kinds. Part 6 describes applications: planning spacecraft scientific experiments (in particular, the National Aeronautics and Space Administration’s (NASA’s) Deep Space One mission), path and motion planning for robots, manufacturability analysis, emergency planning, and planning in the game of bridge. The single chapter on other research (chapter 24) is a collection of very brief surveys of several planning-related areas, such as multi-agent planning, learning for planning, case based planning, and linear and integer programming, useful primarily for letting the student know that these related areas exist. Exercises are provided for chapters in Parts 1 through 5, consisting of theoretical or other paper-and-pencil problems, and some programming and practical exercises with implementations of planning techniques. A comprehensive bibliography is provided, with partial citations in a few places.

This is an ambitious book, which has attempted a large task, and the authors have done a good job. The writing is clear, and the coverage usually strikes the right balance between breadth and depth, and formality and exposition. Parts 1 and 2 are excellent presentations of classical and neo-classical planning. The description of hierarchical task network planning in Part 3 is instructive, as is much of the exposition of planning under uncertainty in Part 5, and of time- and resource-related planning in Part 4. I would have liked to see more discussion of scheduling and resource allocation problems (chapter 15); scheduling is, as the authors remark, an important, broad, and well-developed area in its own right. The case studies in Part 6 are interesting, and would be even more so with additional discussion of how the theory and approaches described in the preceding sections do (or do not) apply to these implementations. The case study of robot path and motion planning (chapter 20) might also have gone into more detail; navigation and path planning is one of the more mature applications of planning, even if it involves a significant amount of domain-specific representational knowledge (data structures for specialized representations of space, and trafficability of areas).

In some places, a little more background material might help; for example, the chapter on constraint satisfaction techniques would be improved, particularly for a practitioner who might not have the necessary AI background, by the addition of an illustration and explanation of constraint satisfaction, before the formal definition of constraint satisfaction problems. However, students who have taken an introductory course in AI should have no problems. This book is eminently suitable for a graduate course in planning, and would be a good secondary text for an advanced graduate course on artificial intelligence in general.

The book is intended primarily as a graduate-level textbook, and some prior coursework in artificial intelligence, or other exposure to concepts, such as search algorithms, computational complexity, and logic, is necessary in order to understand much of the material.

This book will be a useful pedagogical resource for students and teachers. It will also serve as a useful reference for researchers in other areas overlapping the field of AI planning, and for practitioners designing systems with an AI planning component.