图书前言

FOr Lob, Gordon, Luck, George, and Isaac -- S.J.R.

J, d

FOr Kris, Isabella, and Juliet -- P.N.

Preface

Artificial intelligence (Al) is a big field, and this is a big book. We have tried to explore the

full breadth of the field, which encompasses logic, probability, and continuous mathematics;

....,.,l'~'l'l ~ v i c e s t o

perception, reasoning, learning, and action; and everything from microelectronic devices to

robotic planetary explorers. The book is also big because we go into some depth.

The subtitle of this book is ''A Modem Approach." The intended meaning of this rather

empty phrase is that we have tried to synthesize what is now known into a common 

framework, rather than trying to explain each subfield of Al in its own historical context. We

apologize to those whose subfields are, as a result, less recognizable.

New to this edition

This edition captures the changes in Al that have taken place since the last edition in 2003'

There have been important applications of Al technology, such as the widespread 

deploy.

ment of practical speech recognition, machine translation, autonomous vehicles, and 

household robottes. There have been algorithmic landmarks, such as the solution of the game of

checkers. And there has been a great deal of theoretical progress, particularly in areas such

as probabilistic reasoning, machine learning, and computer vision. Most important from our

point of view is the continued evolution in how we think about the field, and thus how we

.., 1 m'., c 11

organize the book. The major changes are as followst

. We place more emphasis on patially observable and nondeterministic environments,

. --,. phasis on patially observable and nondeterministic environments,

especially in the nonprobabilistic settings of search and planning. The concepts of

beliefstate (a set of possible worlds) and state estimation (maintaining the belief state)

are introduced in these settings; later in the book, we add probabilities.

. In addition to discussing the types of environments and types of agents, we now cover

.

.'',

in more depth the types of representations that an agent can use. We distinguish among

atomic representations (in which each state of the world is treated as a black box),

factored representations (in which a state is a set of attribute/value pairs), and structured

.

representations (in which the world consists of objects and relations between them).

. Our coverage of planning goes into more depth on contingent planning in partially

observable environments and includes a new approach to hierarchical planning.

. We have added new material on first-order probabilistic models, including OPen-universe

models for cases where there is uncertainty as to what objects exist.

. We have completely rewritten the introductory machine-learning chaptef, stressing a

wider variety of more modem learning algorithms and placing them on a firmer 

theoretical footing.

. We have expanded coverage of Web search and information extraction, and of 

tech. n 1. c 1 n 1 o fo

niques for learning from very large data sets.

. 20% of the citations in this edition are to works published after 2003'

. We estimate that about 20% of the material is brand new. The remaining 80% reflects

.

older work but has been largely rewritten to present a more unified picture of the field.

..

viI

... n n

vin Preface

Overview of the book

The main unifying theme is the idea of an intelligent agent. We define Al as the study of

ding theme is the idea of an intelligent agent. We define Al as the study of

,

agents that receive percepts from the environment and perform actions. Each such agent 

imments that receive percepts from the environment and perform actions. Each such agent 

im,

piements a function that maps percept sequences to actions, and we cover different ways to

represent these functions. such as reactive agents, real-time planners, and decision-theoretic

present these functions, such as reactive agents, real-time planners, and decision-theoretic

,

sVstems. We explain the role of leaminZ as extending the reach of the designer into unknown

J items. Wb explain the role of learning as extending the reach of the designer into unknown

.

environments, and we show how that role constrains agent design, favoring explicit 

knowly.

edge representation and reasoning. We treat robottes and vision not as independently defined

e presentation and reasoning. We treat robottes and vision not as independently defined

',,..

problems, but as occulting in the service of achieving goals. We stress the importance of the

-.. 

task environment in determining the appropriate agent design.

e ppropnate agent design.

Our primary aim is to convey the ideas that have emerged over the past fifty years of Al

',,

research and the past two millennia of related work. We have tried to avoid excessive 

formal..

ltV in the Dresentation of these ideas while retaining precision. We have included pseudocode

J in the presentation of these ideas while retaining precision. We have included pseudocode

1.

algorithms to make the key ideas concrete; our pseudocode is described in Appendix B.

o J ideas concrete; our pseudocode is described in Appendix B.

mk,. k 1,... 11..

fbis book is primarily intended for use in an undergraduate course or course sequence.

The book has 27 chapters, each requiring about a week's worth of lectures, so working

through the whole book requires a two-semester sequence. A one-semester course can use

, 1,. 1.

selected chapters to suit the interests of the instttictor and students. The book can also be

t

,.'.

used in a graduate-level course (perhaps with the addition of some of the primary sources

.laduate-level course (perhaps with the addition of some of the primary sources

I

suggested in the bibliographical notes). Sample syllabi are available at the book's Web site,

.gested in the bibliographical notes). Sample syllabi are available at the book's Web site,

.,, - - m,,...

- i rn- k 1-o7 q,1 ac 11,...

alma. cs. berkeley. edu. The onlV Prereouisite is familiaritV with basic conceDts of

y. edu. The only prerequisite is familiarity with basic concepts of

.

commuter science (algorithms, data structures, complexity) at a sophomore level. Freshman

puter science (algorithms, data structures, complexity) at a sophomore level. Freshman

1,, 1.,,

calculus and linear algebra are useful for some of the topics, the required mathematical 

backs pies, the required mathematical 

back,.,.,.''.'

ground is supplied in Appendix A.

Exercises are given at the end of each chapter. Exercises requiring significant 

pro..,..

gramming are marked with a keyboard icon. These exercises can best be solved by taking

advantage of the code repository at aima. cs. berkeley. edu. Some of them are large

1

enough to be considered term projects. A number of exercises require some investigation of

an to be considered term projects. A number of exercises require some investigation of

the literature, these are marked with a book icon.

ac k k k 1,..

Yhroughout the book, important Doints are marked with a DOintine icon. We have 

in.nout the book, important points are marked with a pointing icon. We have 

in1,'.. t n,

eluded an extensive index of around 6,000 items to make it easy to find things in the book.

Wherever a new term is first defined, it is also marked in the margin.

About the Web site

.,, -,

aima. c s. berke I eV. edu, the Web site for the book, contains

y. edu, the Web site for the book, contains

.,.

. implementations of the algorithms in the book in several programming languages,

t e Programming languages,

1.

. a list of over 1000 schools that have used the book, many with links to online course

..,

matenals and svilabi.

j llabi,

.

. an annotated list of over 800 links to sites around the Web with useful Al content,

',,

. a chaptenby-chapter list of supplementary material and links,

.. -..

. instructions on how to loin a discussion group for the book,

,oin a discussion group for the book,

Preface ix

..,

. instructions on how to contact the authors with questions or comments,

1 1

.. -.

. instructions on how to report errors in the book, in the likely event that some exist, and

t, in the likely event that some exist, and

,.,,

. slides and other materials for instructors.

About the cover

ac 1.

foe cover depicts the final position from the decisive game 6 of the 1997 match between

',.

chess champion Garry Kasparov and program DEEP BLUE. Kasparov, playing Black, was

forced to resign, making this the first time a computer had beaten a world champion in a

'

chess match. Kasparov is shown at the top. TO his left is the Asimo humanoid robot and

-..

to his right is Thomas Bayes (1702--1761), whose ideas about probability as a measure of

.nt is Thomas Bayes (1702--1761), whose ideas about probability as a measure of

belief underlie much of modem Al technology. Below that we see a Mars Exploration Rovef,

,

a robot that landed on Mars in 2004 and has been exploring the planet ever since. TO the

ploring the planet ever since. TO the

.,.

nght is Alan Turing (1912--1954), whose fundamental work defined the fields of computer

ant is Alan Turing (1912--1954), whose fundamental work defined the fields of computer

.. 1,.

science in general and artificial intelligence in particular At the bottom is Shakey 

(1966b b particular At the bottom is Shakey 

(19661972), the first robot to combine perception, world-modeling, planning, and learning. With

choked to riroiect leader Charles Rosen (1917--2002). At the bottom right is Aristotle (384

ohakeV is protect leader Charles Rosen (1917--2002). At the bottom right is Aristotle (384

y is prOJect leader Charles Rosen (1917--2002). At the bottom right is Aristotle (384

B .C.--322 B .C.), who pioneered the study of logic; his work was state of the art until the 19th

centurV (copy of a bust by Lysippos). At the bottom left, lightly screened behind the authors'

j (copy of a bust by Lysippos). At the bottom left, lightly screened behind the authors'

.,. 1.,

names, is a planning algorithm by Aristotle from De MOtu Animalium in the original Greek.

Behind the title is a portion of the CPSC Bayesian network for medical diagnosis (Pradhan

portion of the CPSC Bayesian network for medical diagnosis (Pradhan

et al., 1994). Behind the chess board is part of a Bayesian logic model for detecting nuclear

,. n... 1

explosions from seismic signals.

Creditsi Stan HondaiGettV (Kasparaov), Library of Congress (Bayes), NASA (Mars

J, paraov), Library of Congress (Bayes), NASA (Mars

' National Museum of Rome (Aristotle), Peter Norvig (book), Ian Parker (Berkeley

rover), National Museum of Rome (Aristotle), Peter Norvig (book), Ian Parker (Berkeley

,,. \ al

skVline), Shutterstock (Asimo, Chess pieces), Time Life/Getty (Shakey, Turing).

j ), ohutterstock (Asimo, Chess pieces), Time Life/Getty (Shakey, Turing).

Acknowledgments

ac. k 1 1 1 yi h. h .hi..

Yhis book would not have been possible without the many contributors whose names did not

,.,make it to the coveL Jitendra Malik and David ForsVth wrote Chanter 24 (computer vision)

J th wrote Chapter 24 (computer vision)

, q'.

and Sebastian Thrun wrote Chapter 25 (robottes). Vibhu Mittal wrote part of Chapter 22

(natural language). Nick Hay, Mehran Sahami, and Emest Davis wrote some of the exercises.

~ ac.

Zoran Duric (George Mason), Thomas C. Henderson (Utah), Leon Reznik (RIT), Michael

GourleV (Central Oklahoma) and Emest Davis (NYU) reviewed the manuscript and made

j

helpful suggestions. We thank Emie Davis in particular for his tireless ability to read multiple

drafts and help improve the book. Nick HaV whipped the bibliography into shape and on

p improve the book. Nick Hay whipped the bibliography into shape and on

deadline staVed uD to 5:30 AM writing code to make the book betted Jon Barron formatted

J p to 5f30 AM writing code to make the book betted Jon Barron formatted

and improved the diagrams in this edition, while Tim Huang, Mark Paskin, and Cynthia

Bruvns helDed with diagrams and algorithms in previous editions. Ravi Mohan and Ciaran

j ifs helped with diagrams and algorithms in previous editions. Ravi Mohan and Ciaran

O'Reillv wrote and maintain the Java code examDles on the Web site. John CannV wrote

J pies on the Web site. John Canny wrote

the robottes chapter for the first edition and Douglas Edwards researched the historical notes.

aam n.,vil ic $l l'.,

YracV Dunkelberger, Allison Michael, Scott Disanno, and Jane Bonned at Pearson tried their

, Dunkelberger, Allison Michael, Scott Disanno, and Jane Bonned at Pearson tried their

best to keep us on schedule and made many helpful suggestions. Most helpful of all has

x Preface

been June Sussman, P.P.A., who read every chapter and provided extensive improvements. In

.,.. 1, n,, 1,

previous editions we had proofreaders who would tell us when we left out a comma and said

which when we meant that; June told us when we left out a minus sign and said fi when we

meant x4. For every typo or confusing explanation that remains in the book, rest assured that

j. for every typo or confusing explanation that remains in the book, rest assured that

June has fixed at least five. She persevered even when a power failure forced her to work by

lantern light rather than LCD glow.

at,,~rt would like to thank his Dorents for their suDI

stuart would like to thank his parents for their support and encouragement and his

.

wife, Loy Sheflott, for her endless patience and boundless wisdom. He hopes that Gordon,

LucV, George, and Isaac will soon be reading this book after they have forgiven him for

J, b 1 and Isaac will soon be reading this book after they have forgiven him for

,.,. 

workinZ so long on it. RUGS (Russell's Unusual Group of Students) have been unusuallV

o ho long on it. RUGS (Russell's Unusual Group of Students) have been unusually

helpful, as always.

Peter would like to thank his parents (TOrsten and Gerda) for getting him started,

, l.. n

and his wife (Kris), children (Bella and Juliet), colleagues, and friends for encouraging and

-. -.

tolerating him through the long hours of writing and longer hours of rewriting.

b nim through the long hours of writing and longer hours of rewriting.

We both thank the librarians at Berkeley, Stanford, and NASA and the developers of

CiteSeef, Wikipedia, and Google, who have revolutionized the way we do research. We can't

,, 1,',, 1 1,.

acknowledge all the people who have used the book and made suggestions, but we would like

e people who have used the book and made suggestions, but we would like

-.,,.,

to note the especially helpful comments of Gagan Aggarwal, Eyal Amif, Ion 

Androutsopoulos, Krzysztof Apt, Warren Haley Armstrong, Ellery Aziel, Jeff Van Baalen, Darius Bacon,

Brian Bakef, Shumeet Baluja, Don Barkef, TOny Barrett, James Newton Bass, Don Beal,

Howard Beck, WOlf gang Bibel, John Binder, Larry Bookman, David R. Boxall, Ronen 

Brafx, n.

man, John Bresina, Gerhard Brewka, Selmer Bringsjord, Carla Brodley, Chris Brown, Emma

Brunskill, Wilhelm Burgef, Lauren Burka, Carlos Bustamante, Joao Cachopo, Murray 

Campbell, Norman Carvef, Emmanuel Castro, Anti Chakiavarthy, Dan Chisarick, Berthe Choueiry,

Roberto Cipolla, David Cohen, James Coleman, June Ann Comparini, Corinna Cones, Gary

Cottrell, Emest Davis, TOm Dean, Rina Dechtef, TOm Dietterich, Peter Drake, Chuck Dyef,

Doug Edwards, Robert Egginton, Asma'a EI-Budrawy, Barbara Engelhardt, Kutluhan Erol,

Oren Etzioni, Hana Filip, Douglas Fishef, Jeffrey Forbes, Ken Ford, Eric FosleFLussief,

John Foslef, Jeremy Frank, Alex Franz, Bob Futrelle, Marek Galecki, Stefan Gerberding,

Stuart Gill, Sabine Glesnef, Seth Golub, Gosta Grahne, Russ Greinef, Eric Grimson, Bac

bara Grosz, Larry Hall, Sieve Hanks, Othar Hansson, Emst Heinz, Jim Hendlef, Christoph

Herrmann, Paul Hilfingef, Robert Holte, Vasant Honavaf, Tim Huang, Seth Hutchinson, Joost

Jacob, Mark Jelasity, Magnus Johansson, Istvan Jonyer, Dan Jurafsky, Leslie Kaelbling, Keiji

Kanazawa, Surewha Kasibhatla, Simon Kasif, Henry Kautz, Gernot Kerschbaumer, Max

Khesin, Richard Kirby, Dan Klein, Kevin Knight, Roland Koenig, Sven Koenig, Daphne

Kollef, Rich Korf, Benjamin Kuipers, James Kurien, John Lafferty, John Laird, Gus 

Larsx, x X X n 1 T T

son, John Lazzaro, Jon LeBlanc, Jason Leatherman, Frank Lee, Jon Lehto, Edward Lim,

Phil Long, Pierre Louveaux, Don Loveland, Sridhar Mahadevan, TOny Mancill, Jim Martin,

Andy MaVer, John McCarthy, David McGrane, Jay Mendelsohn, Risto Miikkulanien, Brian

j. J, John McCarthy, David McGrane, Jay Mendelsohn, Risto Miikkulanien, Brian

Milch, Sieve Minion, Vibhu Mittal, Mehryar Mohri, Leora Morgenstem, Stephen Muggleton,

Kevin Mumhy, Ron Musick, Sung Myaeng, Eric Nadeau, Lee Naish, Pandu Nayak, Bernhard

phy, Ron Musick, Sung Myaeng, Eric Nadeau, Lee Naish, Pandu Nayak, Bernhard

Nebel, Stuart Nelson, XuanLong Nguyen, Nils Nilsson, Illah Nourbakhsh, Ah Noun, Arthur

Nunes-Harwitt, Sieve Omohundro, David Page, David Palmef, David Parkes, Ron Paff, Mark

Preface xi

Paskin, TOny Passera, Amit Patel, Michael Pazzani, Femando Pereira, Joseph Perla, Wim 

Pi. 1 x n' 1 t x

;is, Ira Pohl, Martha Pollack, David Poole, Bruce Portef, Malcolm Pradhan, Bill Pringle, Lob

Jls, Ira Pohl, Martha Pollack, David Poole, Bruce Portef, Malcolm Pradhan, Bill Pringle, Lob

. ac.

raine Prior, Greg Provan, William Rapaport, Deepak Ravichandran, Ioannis Refanidis, Philip

Resnik, Francesca Rossi, Sam Rowels, Richard Russell, Jonathan Schaeffer, Richard Scherl,

Hinrich Schuetze, Lars Schustef, Bart Selman, Sobed Shams, Stuart Shapiro, Jude 

Shavlik, YOram Singef, Satinder Singh, Daniel Sleatof, David Smith, Bryan So, Robert Sproull,

LVnn Stein, Larry Stephens, Andreas Stolcke, Paul Stradling, Devika Subramanian, Marek

j, Larry Stephens, Andreas Stolcke, Paul Stradling, Devika Subramanian, Marek

c'lchenek. Rich Sutton. Ionathan Tash, Austin Tate, Bas Terwljn, Olivier Teytaud, Michael

ouchenek, Rich Sutton, Jonathan Tash, Austin Tate, Bas Terwljn, Olivier Teytaud, Michael

ac' 'sober, William ThompQri q fustian Thrun, Eric Tiedemann, Mark TOrrance, Randall

Yhielscher, William Thompson, Sebastian Thrun, Eric Tiedemann, Mark TOrrance, Randall

Upham, Paul Utgoff, Peter van Beek, Hal Varian, Paulina Varshavskaya, Sunil Vemuri, Vandi

Verma, Ubbo Vissef, Jim Waldo, TOby Walsh, Bonnie Webbef, Dan Weld, Michael Wellman,

Kamin Whitehouse, Michael Dean White, Brian Williams, David WOlf e, Jason WOlf e, Bill

WOods, Alden Wright, Jay Yagnik, Mark Yasuda, Richard Yen, Eliezer Yudkowsky, Weixiong

=

Zhang, Ming Zhao, Shlomo Zilberstein, and our esteemed colleague Anonymous Reviewed

e, iding Zhao, Shlomo Zilberstein, and our esteemed colleague Anonymous Reviewed

About the Authors

Stuart Russell was born in 1962 in Portsmouth, England. He received his B.A. with 

firstclass honours in physics from Oxford University in 1982, and his Ph.D. in computer science

from Stanford in 1986. He then joined the faculty of the University of California at Berkeley,

where he is a professor of computer science, director of the Center for intelligent Systems,

and holder of the Smith--Zadeh Chair in Engineering. In 1990, he received the Presidential

Young investigator AWard of the National Science Foundation, and in 1995 he was cowinner

of the Computers and Thought AWard. He was a 1996 Miller Professor of the University of

puters and Thought AWard. He was a 1996 Miller Professor of the University of

California and was appointed to a Chancellor's Professorship in 2000. In 1998, he gave the

Forsythe Memorial Lectures at Stanford University. He is a Fellow and former Executive

Council member of the American Association for Artificial intelligence. He has published

over 100 papers on a wide range of topics in artificial intelligence. His other books include

The Use of Knowledge in Analogy and induction and (with Eric Wefald) Do the Right Thing:

Studies in Limited Rationalics

Peter Norvig is currently Director of Research at Google, Inc., and was the director 

responsible for the core Web search algorithms from 2002 to 2005. He is a Fellow of the American

Association for Artificial intelligence and the Association for Computing Machinery. 

PreviouslV, he was head of the Computational Sciences Division at NASA Ames Research Center,

J, ne was head of the Computational Sciences Division at NASA Ames Research Center,

where he oversaw NASA's research and development in artificial intelligence and robottes,

and chief scientist at Junglee, where he helped develop one of the first internet information

extraction services. He received a B.S. in applied mathematics from Brown University and

a Ph.D. in computer science from the University of California at Berkeley. He received the

Distinguished Alumni and Engineering innovation awards from Berkeley and the Exceptional

Achievement Medal from NASA. He has been a professor at the University of Southern 

California and a research faculty member at Berkeley. His other books are Paradigms ofAl

Programming: Case Studies in Common LisP and Verbmobil: A Translation Systemfor 

Faceto-Face Dialog and intelligent HelP Systems for UNIX.

..

xII