Artificial Intelligence: Foundations of Computational Agents is a book about the science of artificial intelligence (AI). The view we take is that AI is the study of the design of intelligent computational agents. The book is structured as a textbook but it is designed to be accessible to a wide audience.

We wrote this book because we are excited about the emergence of AI as an integrated science. As with any science worth its salt, AI has a coherent, formal theory and a rambunctious experimental wing. Here we balance theory and experiment and show how to link them intimately together. We develop the science of AI together with its engineering applications. We believe the adage, "There is nothing so practical as a good theory." The spirit of our approach is captured by the dictum, "Everything should be made as simple as possible, but not simpler." We must build the science on solid foundations; we present the foundations, but only sketch, and give some examples of, the complexity required to build useful intelligent systems. Although the resulting systems the will be complex, the foundations and the building blocks should be simple.

The book works as an introductory text on artificial intelligence for advanced undergraduate or graduate students in computer science or related disciplines such as computer engineering, philosophy, cognitive science, or psychology. It will appeal more to the technically minded; parts are technically challenging, focusing on learning by doing: designing, building, and implementing systems. Any curious scientifically oriented reader will benefit from studying the book. Previous experience with computational systems is desirable, but prior study of the foundations upon which we build, including logic, probability, calculus, and control theory, is not necessary, because we develop the concepts as required.

The serious student will gain valuable skills at several levels ranging from expertise in the specification and design of intelligent agents to skills for implementing, testing, and improving real software systems for several challenging application domains. The thrill of participating in the emergence of a new science of intelligent agents is one of the attractions of this approach. The practical skills of dealing with a world of ubiquitous, intelligent, embedded agents are now in great demand in the marketplace.

The focus is on an intelligent agent acting in an environment. We start with simple agents acting in simple, static environments and gradually increase the power of the agents to cope with more challenging worlds. We explore nine dimensions of complexity that allow us to introduce, gradually and with modularity, what makes building intelligent agents challenging. We have tried to structure the book so that the reader can understand each of the dimensions separately and we make this concrete by repeatedly illustrating the ideas with four different agent tasks: a delivery robot, a diagnostic assistant, a tutoring system, and a trading agent.

The agent we want the student to envision is a hierarchically designed agent that acts intelligently in a stochastic environment that it can only partially observe - one that reasons about individuals and relationships among them, has complex preferences, learns while acting, takes into account other agents, and acts appropriately given its own computational limitations. Of course, we can't start with such an agent; it is still a research question to build such agents. So we introduce the simplest agents and then show how to add each of these complexities in a modular way.

We have made a number of design choices that distinguish this book from competing books, including the earlier book by the same authors:

  • We have tried to give a coherent framework in which to understand AI. We have chosen not to present disconnected topics that do not fit together. For example, we do not present disconnected logical and probabilistic views of AI, but we have presented a multidimensional design space in which the students can understand the big picture, in which probabilistic and logical reasoning coexist.
  • We decided that it is better to clearly explain the foundations upon which more sophisticated techniques can be built, rather than present these more sophisticated techniques. This means that a larger gap exists between what is covered in this book and the frontier of science. It also means that the student will have a better foundation to understand current and future research.
  • One of the more difficult decisions we made was how to linearize the design space. Our previous book [Poole et al. (1998)] presented a relational language early and built the foundations in terms of this language. This approach made it difficult for the students to appreciate work that was not relational, for example, in reinforcement learning that is developed in terms of states. In this book, we have chosen a relations-late approach. This approach probably reflects better the research over the past few decades where there has been much progress in feature-based representations. It also allows the student to understand that probabilistic and logical reasoning are complementary. The book, however, is structured so that an instructor can present relations earlier.

This book uses examples from (, a collection of pedagogical applets that we have been involved in designing. To gain further experience in building intelligent systems, a student should also experiment with a high-level symbol-manipulation language, such as LISP or Prolog. We also provide implementations in AILog, a clean logic programming language related to Prolog, designed to demonstrate many of the issues in this book. This connection is not essential to an understanding or use of the ideas in this book.

Our approach, through the development of the power of the agent's capabilities and representation language, is both simpler and more powerful than the traditional approach of surveying and cataloging various applications of AI. However, as a consequence, some applications such as the details of computational vision or computational linguistics are not covered in this book.

We have chosen not to present an encyclopedic view of AI. Not every major idea that has been investigated is presented here. We have chosen some basic ideas upon which other, more sophisticated, techniques are based and have tried to explain the basic ideas in detail, sketching how these can be expanded.

Figure 0.1: Overview of chapters and dependencies

Figure 0.1 shows the topics covered in the book. The solid lines give prerequisites. Often the prerequisite structure does not include all sub-topics. Given the medium of a book, we have had to linearize the topics. However, the book is designed so that the topics can be taught in any order satisfying the prerequisite structure.

The references given at the end of each chapter are not meant to be comprehensive: we have referenced works that we have directly used and works that we think provide good overviews of the literature, by referencing both classic works and more recent surveys. We hope that no researchers feel slighted by their omission, and we are happy to have feedback where someone feels that an idea has been misattributed. Remember that this book is not a survey of AI research.

We invite you to join us in an intellectual adventure: building a science of intelligent agents.

David Poole
Alan Mackworth


Thanks to Randy Goebel for valuable input on this book. We also gratefully acknowledge the helpful comments on earlier drafts of this book received from Giuseppe Carenini, Cristina Conati, Mark Crowley, Pooyan Fazli, Holger Hoos, Manfred Jaeger, Mohammad Reza Khojasteh, Jacek Kisynski, Bob Kowalski, Kevin Leyton-Brown, Marian Mackworth, Gabriel Murray, Alessandro Provetti, Marco Valtorta, and the anonymous reviewers. Thanks to the students who pointed out many errors in the earlier drafts. Thanks to Jen Fernquist for the web site design, and to Tom Sgouros for hyperlatex fixes. We are grateful to James Falen for permission to quote his poem on constraints.

The quote at the beginning of Chapter 9 is reprinted with permission of Simon & Schuster, Inc. from THE CREATIVE HABIT: Learn it and Use It by Twyla Tharp with Mark Reiter. Copyright 2003 by W.A.T. Ltd.. All Rights Reserved.

Thanks to our editor Lauren Cowles and the staff at Cambridge University Press for all their support, encouragement and help. All the mistakes remaining are ours.