Preface

One motivation for studying automated planning is very practical: the need for information processing tools that provide affordable and efficient planning resources. Such tools are needed for use in complex and changing tasks that involve demanding safety and/or efficiency requirements. They are needed for integrating more autonomy and intelligent control capabilities in complex artifacts. Automated planning technology is already capable enough to be useful in a variety of demanding applications, in areas ranging from controlling space vehicles and robots to deploying emergency operations and playing the game of bridge.

Another motivation for automated planning is more theoretical. Planning is an important component of rational behavior. If one purpose of Artificial Intelligence (AI) is to grasp the computational aspects of intelligence, then certainly planning, as the reasoning side of acting, is a key element in such a purpose.

These two motivations create the potential for synergy between theory and practice in automated planning. By observing what works well in practice, it is possible to develop better theories of planning. These better theories will in turn lead to better planning systems for practical applications.

The intent of this textbook is to give readers an understanding of automated planning theory and automated planning practice and how they relate to each other. The book contains a set of theoretical chapters to introduce the theory of automated planning and a set of case-study chapters to illustrate how to adapt and combine automated planning techniques in a variety of application domains.

Material Covered

The published literature related to automated planning is quite large, and it is not feasible in a single book to give detailed discussions of all of it. Our choice of what to cover was motivated by the following considerations.

The bulk of research on automated planning focuses on a restricted form called classical planning. We feel strongly that for the field of automated planning to realize its full potential, it needs to move beyond classical planning. For that reason, while covering classical planning as prerequisite introductory material, we have devoted large parts of the book to extended classes of automated planning that relax the various restrictions required by classical planning.

We also devoted a large part of the book to descriptions of application-oriented work. These chapters are mainly illustrative case studies. From the application point of view, the field of planning is still in an early stage. It has not yet developed a mature engineering methodology to enable us to present a comprehensive mapping from the features of an application domain to the planning techniques that best address these features. We do hope that this book can contribute to the development of such a mature technology.

Using This Book

This book may be used both as a graduate-level textbook and as an information source for professionals in the field. We assume that readers already know the basic concepts of search algorithms, data structures, computational complexity, and programming languages at the level that one might get in an undergraduate computer science curriculum. Prior knowledge of heuristic search and first-order logic would also be helpful but probably is not strictly necessary since Appendices A and B provide overviews of those topics.

The book is composed of twenty-four chapters, which are organized into seven parts, and three appendices. Parts I and II cover a restricted model of planning problems and algorithms for planning within that model. Part III deals with heuristics and control strategies for planning; and Parts III to V discuss several extended models and planning algorithms. Part VI is devoted to five case studies and applications. In Part VII, the last chapter discusses brie§y other problems and techniques related to planning, e.g., planning and acting or planning and learning, to which it was not possible to devote a full chapter.

Figure (1) shows which chapters depend on which others. The required precedence relationship is indicated by solid lines. The figure shows that one may proceed along several possible paths when studying the book. In particular, several of the application-oriented chapters can be tackled quite early. The book contains more material than can fit into a single semester. The precedence relationship between chapters can help teachers decide which chapters to cover.

As an example of what can be covered in a single semester, a recent course on planning at the University of Maryland covered the following chapters: 1, 2 (skipping set-theoretic representation), 3, 4, 5, 6, a quick overview of 7, most of 9, 10, 11, 14, 15, most of 16, most of 17, 20, 22, and 23. The course also included term projects in which the students, in groups of two or three people, proposed and carried out research projects on topics related to automated planning.

Web Site

At http://www.laas.fr/planning is a web site for additional material related to this book. It contains links to related work; links to planning programs that may be downloaded; copies of slides that have been used in lectures based on this book; and additional illustrations, examples, and exercises as may be appropriate.

Acknowledgments

We wish to acknowledge the feedback from students who took courses based on various rough drafts of this book, in particular the students at the universities of Maryland, Toulouse, and Trento and the ESSLLI 2002 summer school participants. Much thanks to our reviewers; their comments
resulted in significant improvements. We are thankful to several friends who gave us very valuable feedback on parts of this book; among these are

Suzanne Biundo, University of Ulm,
Steve Chien, Jet Propulsion Laboratory,
Kutluhan Erol, Mindlore Inc,
Maria Fox, University of Strathclyde,
Froduald Kabanza, University of Sherbrooke,
Jana Koehler, IBM Zurich Research Laboratory,
J. P. Laumond, LAAS,
Derek Long, University of Strathclyde,
Amnon Lotem, Skybox Security,
Héctor Muñoz-Avila, Lehigh University,
Marco Pistore, IRST,
Alex Pogel, New Mexico State University,
Stephen J.J. Smith, Great Game Products,
Sylvie Thiebaux, The Australian National University,
David Wilkins, SRI International,
Qiang Yang, Simon Fraser University.

Thanks to M. Herrb and R. Prajoux, who helped us set up the distributed CVS server and Latex environment. We also wish to acknowledge the support of our respective workplaces, which provided facilities that helped make this work possible: LAAS-CNRS in Toulouse, France, the University of Maryland in College Park, Maryland, and ITC-IRST in Trento, Italy.