Artificial Intelligence
A Modern Approach
Stuart J. Russell and Peter Norvig
Contributing writers:
John F. Canny, Jitendra M. Malik, Douglas D. Edwards
Prentice Hall, Englewood Cliffs, New Jersey 07632
,Library of Congress Cataloging-in-Publication Data
Russell, Stuart J. (Stuart Jonathan)
Artificial intelligence : a modern approach/ Stuart Russell, Peter Norvig.
p. cm.
Includes bibliographical references and index.
ISBN 0-13-103805-2
1. Artificial intelligence I. Norvig, Peter. II. Title.
Q335.R86 1995
006.3-dc20 94-36444
CIP
Publisher: Alan Apt
Production Editor: Mona Pompili
Developmental Editor: Sondra Chavez
Cover Designers: Stuart Russell and Peter Norvig
Production Coordinator: Lori Bulwin
Editorial Assistant: Shirley McGuire
© 1995 by Prentice-Hall, Inc.
A Simon & Schuster Company
Englewood Cliffs, New Jersey 07632
The author and publisher of this book have used their best efforts in preparing this book. These efforts
include the development, research, and testing of the theories and programs to determine their
effectiveness. The author and publisher shall not be liable in any event for incidental or consequential
damages in connection with, or arising out of, the furnishing, performance, or use of these programs.
All rights reserved. No part of this book may be
reproduced, in any form or by any means,
without permission in writing from the publisher.
Printed in the United States of America
10 9 8 7 6 5 4 3 2 1
ISBN D-IH-IQBSOS-E
Prentice-Hall International (UK) Limited, London
Prentice-Hall of Australia Pty. Limited, Sydney
Prentice-Hall Canada, Inc., Toronto
Prentice-Hall Hispanoamericana, S.A., Mexico
Prentice-Hall of India Private Limited, New Delhi
Prentice-Hall of Japan, Inc., Tokyo
Simon & Schuster Asia Pte. Ltd., Singapore
Editora Prentice-Hall do Brasil, Ltda., Rio de Janeiro
,Preface
There are many textbooks that offer an introduction to artificial intelligence (AI). This text has
five principal features that together distinguish it from other texts.
1. Unified presentation of the field.
Some texts are organized from a historical perspective, describing each of the major
problems and solutions that have been uncovered in 40 years of AI research. Although
there is value to this perspective, the result is to give the impression of a dozen or so barely
related subfields, each with its own techniques and problems. We have chosen to present
AI as a unified field, working on a common problem in various guises. This has entailed
some reinterpretation of past research, showing how it fits within a common framework
and how it relates to other work that was historically separate. It has also led us to include
material not normally covered in AI texts.
2. Intelligent agent design.
The unifying theme of the book is the concept of an intelligent agent. In this view, the
problem of AI is to describe and build agents that receive percepts from the environment
and perform actions. Each such agent is implemented by a function that maps percepts
to actions, and we cover different ways to represent these functions, such as production
systems, reactive agents, logical planners, neural networks, and decision-theoretic systems.
We explain the role of learning as extending the reach of the designer into unknown environ-
ments, and show how it constrains agent design, favoring explicit knowledge representation
and reasoning. We treat robotics and vision not as independently defined problems, but
as occurring in the service of goal achievement. We stress the importance of the task
environment characteristics in determining the appropriate agent design.
3. Comprehensive and up-to-date coverage.
We cover areas that are sometimes underemphasized, including reasoning under uncer-
tainty, learning, neural networks, natural language, vision, robotics, and philosophical
foundations. We cover many of the more recent ideas in the field, including simulated
annealing, memory-bounded search, global ontologies, dynamic and adaptive probabilistic
(Bayesian) networks, computational learning theory, and reinforcement learning. We also
provide extensive notes and references on the historical sources and current literature for
the main ideas in each chapter.
4. Equal emphasis on theory and practice.
Theory and practice are given equal emphasis. All material is grounded in first principles
with rigorous theoretical analysis where appropriate, but the point of the theory is to get the
concepts across and explain how they are used in actual, fielded systems. The reader of this
book will come away with an appreciation for the basic concepts and mathematical methods
of AI, and also with an idea of what can and cannot be done with today's technology, at
what cost, and using what techniques.
5. Understanding through implementation.
The principles of intelligent agent design are clarified by using them to actually build agents.
Chapter 2 provides an overview of agent design, including a basic agent and environment
vii
, Vlll Preface
project. Subsequent chapters include programming exercises that ask the student to add >.
capabilities to the agent, making it behave more and more interestingly and (we hope)
intelligently. Algorithms are presented at three levels of detail: prose descriptions and !
pseudo-code in the text, and complete Common Lisp programs available on the Internet or
on floppy disk. All the agent programs are interoperable and work in a uniform framework
for simulated environments.
This book is primarily intended for use in an undergraduate course or course sequence. It
can also be used in a graduate-level course (perhaps with the addition of some of the primary
sources suggested in the bibliographical notes). Because of its comprehensive coverage and the
large number of detailed algorithms, it is useful as a primary reference volume for AI graduate
students and professionals wishing to branch out beyond their own subfield. We also hope that
AI researchers could benefit from thinking about the unifying approach we advocate.
The only prerequisite is familiarity with basic concepts of computer science (algorithms,
data structures, complexity) at a sophomore level. Freshman calculus is useful for understanding
neural networks and adaptive probabilistic networks in detail. Some experience with nonnumeric
programming is desirable, but can be picked up in a few weeks study. We provide implementations
of all algorithms in Common Lisp (see Appendix B), but other languages such as Scheme, Prolog,
Smalltalk, C++, or ML could be used instead.
Overview of the book
The book is divided into eight parts. Part 1, "Artificial Intelligence," sets the stage for all the others,
and offers a view of the AI enterprise based around the idea of intelligent agents—systems that
can decide what to do and do it. Part II, "Problem Solving," concentrates on methods for deciding
what to do when one needs to think ahead several steps, for example in navigating across country
or playing chess. Part III, "Knowledge and Reasoning," discusses ways to represent knowledge
about the world—how it works, what it is currently like, what one's actions might do—and how
to reason logically with that knowledge. Part IV, "Acting Logically," then discusses how to
use these reasoning methods to decide what to do, particularly by constructing plans. Part V,
"Uncertain Knowledge and Reasoning," is analogous to Parts III and IV, but it concentrates on
reasoning and decision-making in the presence of uncertainty about the world, as might be faced,
for example, by a system for medical diagnosis and treatment.
Together, Parts II to V describe that part of the intelligent agent responsible for reaching
decisions. Part VI, "Learning," describes methods for generating the knowledge required by these
decision-making components; it also introduces a new kind of component, the neural network,
and its associated learning procedures. Part VII, "Communicating, Perceiving, and Acting,"
describes ways in which an intelligent agent can perceive its environment so as to know what is
going on, whether by vision, touch, hearing, or understanding language; and ways in which it can
turn its plans into real actions, either as robot motion or as natural language utterances. Finally,
Part VIII, "Conclusions," analyses the past and future of AI, and provides some light amusement
by discussing what AI really is and why it has already succeeded to some degree, and airing the
views of those philosophers who believe that AI can never succeed at all.
A Modern Approach
Stuart J. Russell and Peter Norvig
Contributing writers:
John F. Canny, Jitendra M. Malik, Douglas D. Edwards
Prentice Hall, Englewood Cliffs, New Jersey 07632
,Library of Congress Cataloging-in-Publication Data
Russell, Stuart J. (Stuart Jonathan)
Artificial intelligence : a modern approach/ Stuart Russell, Peter Norvig.
p. cm.
Includes bibliographical references and index.
ISBN 0-13-103805-2
1. Artificial intelligence I. Norvig, Peter. II. Title.
Q335.R86 1995
006.3-dc20 94-36444
CIP
Publisher: Alan Apt
Production Editor: Mona Pompili
Developmental Editor: Sondra Chavez
Cover Designers: Stuart Russell and Peter Norvig
Production Coordinator: Lori Bulwin
Editorial Assistant: Shirley McGuire
© 1995 by Prentice-Hall, Inc.
A Simon & Schuster Company
Englewood Cliffs, New Jersey 07632
The author and publisher of this book have used their best efforts in preparing this book. These efforts
include the development, research, and testing of the theories and programs to determine their
effectiveness. The author and publisher shall not be liable in any event for incidental or consequential
damages in connection with, or arising out of, the furnishing, performance, or use of these programs.
All rights reserved. No part of this book may be
reproduced, in any form or by any means,
without permission in writing from the publisher.
Printed in the United States of America
10 9 8 7 6 5 4 3 2 1
ISBN D-IH-IQBSOS-E
Prentice-Hall International (UK) Limited, London
Prentice-Hall of Australia Pty. Limited, Sydney
Prentice-Hall Canada, Inc., Toronto
Prentice-Hall Hispanoamericana, S.A., Mexico
Prentice-Hall of India Private Limited, New Delhi
Prentice-Hall of Japan, Inc., Tokyo
Simon & Schuster Asia Pte. Ltd., Singapore
Editora Prentice-Hall do Brasil, Ltda., Rio de Janeiro
,Preface
There are many textbooks that offer an introduction to artificial intelligence (AI). This text has
five principal features that together distinguish it from other texts.
1. Unified presentation of the field.
Some texts are organized from a historical perspective, describing each of the major
problems and solutions that have been uncovered in 40 years of AI research. Although
there is value to this perspective, the result is to give the impression of a dozen or so barely
related subfields, each with its own techniques and problems. We have chosen to present
AI as a unified field, working on a common problem in various guises. This has entailed
some reinterpretation of past research, showing how it fits within a common framework
and how it relates to other work that was historically separate. It has also led us to include
material not normally covered in AI texts.
2. Intelligent agent design.
The unifying theme of the book is the concept of an intelligent agent. In this view, the
problem of AI is to describe and build agents that receive percepts from the environment
and perform actions. Each such agent is implemented by a function that maps percepts
to actions, and we cover different ways to represent these functions, such as production
systems, reactive agents, logical planners, neural networks, and decision-theoretic systems.
We explain the role of learning as extending the reach of the designer into unknown environ-
ments, and show how it constrains agent design, favoring explicit knowledge representation
and reasoning. We treat robotics and vision not as independently defined problems, but
as occurring in the service of goal achievement. We stress the importance of the task
environment characteristics in determining the appropriate agent design.
3. Comprehensive and up-to-date coverage.
We cover areas that are sometimes underemphasized, including reasoning under uncer-
tainty, learning, neural networks, natural language, vision, robotics, and philosophical
foundations. We cover many of the more recent ideas in the field, including simulated
annealing, memory-bounded search, global ontologies, dynamic and adaptive probabilistic
(Bayesian) networks, computational learning theory, and reinforcement learning. We also
provide extensive notes and references on the historical sources and current literature for
the main ideas in each chapter.
4. Equal emphasis on theory and practice.
Theory and practice are given equal emphasis. All material is grounded in first principles
with rigorous theoretical analysis where appropriate, but the point of the theory is to get the
concepts across and explain how they are used in actual, fielded systems. The reader of this
book will come away with an appreciation for the basic concepts and mathematical methods
of AI, and also with an idea of what can and cannot be done with today's technology, at
what cost, and using what techniques.
5. Understanding through implementation.
The principles of intelligent agent design are clarified by using them to actually build agents.
Chapter 2 provides an overview of agent design, including a basic agent and environment
vii
, Vlll Preface
project. Subsequent chapters include programming exercises that ask the student to add >.
capabilities to the agent, making it behave more and more interestingly and (we hope)
intelligently. Algorithms are presented at three levels of detail: prose descriptions and !
pseudo-code in the text, and complete Common Lisp programs available on the Internet or
on floppy disk. All the agent programs are interoperable and work in a uniform framework
for simulated environments.
This book is primarily intended for use in an undergraduate course or course sequence. It
can also be used in a graduate-level course (perhaps with the addition of some of the primary
sources suggested in the bibliographical notes). Because of its comprehensive coverage and the
large number of detailed algorithms, it is useful as a primary reference volume for AI graduate
students and professionals wishing to branch out beyond their own subfield. We also hope that
AI researchers could benefit from thinking about the unifying approach we advocate.
The only prerequisite is familiarity with basic concepts of computer science (algorithms,
data structures, complexity) at a sophomore level. Freshman calculus is useful for understanding
neural networks and adaptive probabilistic networks in detail. Some experience with nonnumeric
programming is desirable, but can be picked up in a few weeks study. We provide implementations
of all algorithms in Common Lisp (see Appendix B), but other languages such as Scheme, Prolog,
Smalltalk, C++, or ML could be used instead.
Overview of the book
The book is divided into eight parts. Part 1, "Artificial Intelligence," sets the stage for all the others,
and offers a view of the AI enterprise based around the idea of intelligent agents—systems that
can decide what to do and do it. Part II, "Problem Solving," concentrates on methods for deciding
what to do when one needs to think ahead several steps, for example in navigating across country
or playing chess. Part III, "Knowledge and Reasoning," discusses ways to represent knowledge
about the world—how it works, what it is currently like, what one's actions might do—and how
to reason logically with that knowledge. Part IV, "Acting Logically," then discusses how to
use these reasoning methods to decide what to do, particularly by constructing plans. Part V,
"Uncertain Knowledge and Reasoning," is analogous to Parts III and IV, but it concentrates on
reasoning and decision-making in the presence of uncertainty about the world, as might be faced,
for example, by a system for medical diagnosis and treatment.
Together, Parts II to V describe that part of the intelligent agent responsible for reaching
decisions. Part VI, "Learning," describes methods for generating the knowledge required by these
decision-making components; it also introduces a new kind of component, the neural network,
and its associated learning procedures. Part VII, "Communicating, Perceiving, and Acting,"
describes ways in which an intelligent agent can perceive its environment so as to know what is
going on, whether by vision, touch, hearing, or understanding language; and ways in which it can
turn its plans into real actions, either as robot motion or as natural language utterances. Finally,
Part VIII, "Conclusions," analyses the past and future of AI, and provides some light amusement
by discussing what AI really is and why it has already succeeded to some degree, and airing the
views of those philosophers who believe that AI can never succeed at all.
