Automated Planning and Acting


This book is about methods and techniques that a computational agent can use for deliberative planning and acting, i.e., for deciding both which actions to perform and how to perform them, to achieve some objective. The study of deliberation has several scientific and engineering motivations.

Understanding deliberation is an objective for most cognitive sciences. In Artificial Intelligence research, this is done by modeling deliberation through computational approaches to both enable it and allow it to be explained. Furthermore, the investigated capabilities are better understood by mapping concepts and theories into designed systems and experiments, in order to test empirically, measure and qualify the proposed models.

The engineering motivation for studying deliberation is to build systems that exhibit deliberation capabilities and develop technologies that address socially useful needs. A technological system needs deliberation capabilities if it must autonomously perform a set of tasks that either are too diverse—or must be done in environments that are too diverse—to engineer those tasks into innate behaviors. Autonomy and diversity of tasks and environments is a critical feature in many applications, including robotics (e.g., service and personal robots, rescue and exploration robots, autonomous space stations, satellites, or vehicles), complex simulation systems (e.g., tutoring, training or entertainment), or complex infrastructure management (e.g., industrial or energy plants, transportation networks, urban facilities).

Motivation and Coverage

The coverage of this book derives from the view we advocated for in [234], which we will now briefly summarize.

Automated planning is a rich technical field, which benefits from the work of a very active and growing research community. Some areas in this field are extensively explored and correspond to a number of already mature techniques. However, there are other areas where further investigation is critically needed if automated planning is to have a wider impact on a broader set of applications. One of the most important such areas, in our view, the integration of planning and acting. The book covers several different kinds of models and approaches: deterministic, hierarchical, temporal, nondeterministic and probabilistic—and for each of them, we discuss not only the techniques themselves, but also how to use them in the integration of planning and acting.

The published literature on automated planning is very large, and it is not feasible to cover all of it in detail in a single book. Hence our choice of what to cover was motivated by putting the integration of planning and acting at the forefront. The bulk of research on automated planning is focused on a restricted form called classical planning, an understanding of which is prerequisite introductory material; and we cover it in part of Chapter 2. But we have devoted large parts of the book to extended classes of automated planning and acting that relax the various restrictions required by classical planning.

There are several other kind of deliberation functions, such as monitoring, reasoning about one's goals, reasoning about sensing and information-gathering actions, and learning and otherwise acquiring deliberation models. Although these are not our focus, we cover them briefly in (Chapter 7).

The technical material in this book is illustrated with examples inspired from concrete applications. However, most of the technical material is theoretical. Case-studies and application-oriented work would certainly enrich the integration of planning and acting view developed in here. We plan to devote a forthcoming volume to automated planning and acting applications.

Using this Book

This work started as a textbook project, to update the previous textbook in automated planning [235]. Our analysis of the state of the art led us very quickly to embrace the objective of covering planning and acting and their integration and, consequently, to face two obstacles:

This book can be used as a graduate-level textbook and as an information source for scientists and professionals in the field. We assume the reader to be familiar with the basic concepts of algorithms and data structures at the level that one might get in an undergraduate-level computer science curriculum. Prior knowledge of heuristic search techniques would also be helpful, but is not strictly necessary since the appendices provide overviews of needed tools.

A complete set of lecture slides for this book and other auxiliary materials are available online.


We are thankful to several friends and colleagues who gave us very valuable feedback on parts of this book. Among these are Hector Geffner, Patrick Haslum, Joerg Hoffmann, Felix Ingrand, Uger Kuter, Marco Pistore, Mak Roberts, and Vikas Shivashankar.

We also wish to acknowledge the support of our respective organizations who provided the support and facilities that helped to make this work possible: LAAS-CNRS in Toulouse, France, the University of Maryland in College Park, Maryland, and FBK, ICT-IRST in Trento, Italy.

Finally, we wish to acknowledge the support of our families, who remained patient during a project that consumed much more of our time and attention than we had originally anticipated.