序  言

《人工智能：一种现代方法》（英文，第1版）是一部人工智能（AI）的优秀教材，1995年问世后在世界各地出版、发行，很快成为一部畅销书。在我国，英文影印本于2002年出版，也很受大众的欢迎。

事隔8年(2003年)，该书的第2版（作者Stuart Russell, Peter Norvig， Pearson Education出版集团出版）又出现在我们面前。作者是这样解释出版新书的原因，他说，自1995年该书第1版发行以来，AI有了很大的变化，它的技术更趋实用，因此新书的每一章都经过重写以反映该领域的最新成就，同时重新解释了原有的结果，使之更加符合新的发现。这充分反映了作者对新书的负责精神与严肃态度。

这部书的主要特点如下。

（1）在智能Agent（自主体，代理，行为者）的概念下，将AI中相互分离的领域统一起来，克服了以往AI教材中难以避免的内容零散且互不相关的现象，从而使AI变得更加理论化、系统化。

（2）理论与实际并重。作者在论述各个领域的原理与方法时，尽量运用数学（形式化）的语言，力图让它们建立在严格的理论基础之上。同时又介绍最新的实用算法，特别是能够解决现实世界问题的方法，尽量使AI从“玩具世界”中走向实用。

本书所具有的以上特点正好反映了AI当前发展的大趋势。大家知道，人工智能从上个世纪中叶诞生以来，一直未能形成系统的理论体系。因此，有的人把AI看成是一门“工程”，有的则认为是一门“技术”，也有的甚至认为只是一门“艺术”。大家也许记得，上个世纪80年代，以斯坦福大学的N. J. Nilsson为代表与以耶鲁大学 R. C. Schank为代表，曾经展开过一场关于AI究竟是一门“工程技术”，还是一门“艺术”的争论。当时存在这种争论是很自然的。在AI发展的初期，大多数研究者采取的研究方法是，首先凭借直觉或者启发式建立起AI的相关假设，然后在“玩具世界”中论证假设的合理性，由此建立起一套AI的理论与方法。为了克服数学方法的“局限性”，他们总是避免使用数学工具，尽量与传统的严格科学保持距离。但是，随着AI走向成熟，AI的“传统”发生了变化，它们逐步向科学靠拢，向实用靠近。一方面，尽量使用现代科学工具，使AI逐步变成一门科学。一方面，尽量面向现实世界，提出可行的算法，使AI走向实际应用。该书作者将这两大趋势及时地反映在教材中，从而形成自己的特色。

作者在前言中特别说明了本书与第1版的区别。我认为，第2版加强并进一步突出了以上两个特点。作者在重写过程中，对于理论部分尽量采用已有的、成熟的科学方法，如数学、心理学、计算机工程、神经科学等。在第2版中，还进一步强调了经济学中决策理论、运筹学，以及控制理论、控制论等与AI的关系，将AI与其它科学领域联系起来。在各个章节中都补充了新的内容，将这期间所取得的研究成果尽量纳入到新书中。

尽管本书已由清华大学计算机系姜哲等老师译为中文，并于2004年出版，为了使读者能够读到英文原书，我以为出版第2版的影印本还是有必要的。

中国科学院院士 清华大学教授

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; perception,

. 1. 1., 1.

reasoning, learning, and action; and everything from microelectronic devices to robotic planetary

e, learning, and action; and everything from microelectronic devices to robotic planetary

explorers. The book is also big because we go into some depth in presenting results, although we

.

strive to cover only the most central ideas in the main part of each chapter. Pointers are given to

J Lhe most central ideas in the main part of each chapter. Pointers are given to

fufther results in the biblioZraDhical notes at the end of each chaDter.

.laphical notes at the end of each chapter.

The subtitle of this book is ''A Modern 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 than they might otherwise have been.

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

;lug 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 implements a

function that maps percept sequences to actions, and we cover different ways to represent these 

func. 

nons, such as production systems, reactive agents, real-time conditional planners, neural networks,

and decision-theoretic systems. We eXDlain the role of learning as extending the reach of the designer

J plain 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

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

o presentation and reasoning. We treat robottes and vision not as independently dehned

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

.. -..

environment in determining the approDriate aZent desiZn.

u r propriate agent design.

Our primarV aim is to conveV the ideas that have emerged over the past fifty years of Al research

Primary aim is to convey the ideas that have emerged over the past fifty years of Al research

and the past two millenia of related work. We have tried to avoid excessive formality in the 

presen.

tation of these ideas while retaining precision. Wherever appropriate, we have included pseudocode

o precision. Wherever appropriate, we have included pseudocode

algorithms to make the ideas concrete, our pseudocode is described briefly in Appendix B. 

Implementations in several programming languages are available on the book's Web site, aima.cs.berkeley.edu.

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

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

suggested in the bibliographical notes). Because of its comprehensive coverage and large number of

detailed algorithms, it is useful as a primarV reference volume for Al Zraduate students and 

Drofeso primary reference volume for Al graduate students and 

profes.,. 1. 

sionals wishing to branch out beyond their own subfield. The only prerequisite is familiarity with

e to branch out beyond their own subfield. The only prerequisite is familiarity with

basic concepts of computer science (algorithms, data structures, complexity) at a sophomore level.

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

Freshman calculus is useful for understanding neural networks and statistical learning in detail. Some

o

of the required mathematical background is supplied in Appendix A.

Overview of the book

The book is divided into eight parts. Part i, Artificial llltelligellce, offers a view of the Al enterprise

o

based around the idea of intelligent agents--systems that can decide what to do and then do it. Part

5 6 y U

II, Problem Solving, concentrates on methods for deciding what to do when one needs to think ahead

several steps--for example in navigating across a country or playing chess. Part ill, Kllowledge and

Reasoning, discusses ways to represent knowledge about the world--how it works, what it is currently

like, and what one's actions might do--and how to reason logically with that knowledge. Part IVy

Planning, then discusses how to use these reasoning methods to decide what to do, particularly by

.

constructinZ mans. Part V Uncertain Knowledge and Reasoning, is analogous to Parts ill and IV,

o plans. Part V, Uncertain Knowledge and Reasoning, is analogous to Parts ill and IV,

but it concentrates on reasoninZ and decision making in the presence of uncertainty) about the world,

o 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.

o

TOgether, Parts II--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

..

VII

... n c

vin Preface

,

components. Part Vll, Communicating, Perceiving, and Acting, describes ways in which an 

intelligent agent can Derceive its environment so as to know what is going on, whether by vision, touch,

o o 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

1. 1 1,

robot motion or as natural language utterances. Finally, Part Vlll, Conclusions, analyzes the past and

euage utterances. Finally, Part Vlll, Conclusions, analyzes the past and

future of Al and the philosophical and ethical implications of artificial intelligence.

Changes from the first edition

Much has changed in Al since the publication of the first edition in 1995, and much has changed in this

e publication of the first edition in 1995, and much has changed in this

book. Every chaDter has been significantly rewritten to reflect the latest work in the field, to reinterpret

J pier has been significantly rewritten to reflect the latest work in the field, to reinterpret

1,,.

old work in a way that is more cohesive with new findings, and to improve the pedagogical flow of

J o.

., ~ 1 1 P. r, 1 1 1,,

ideas. Followers of Al should be encouraged that current techniques are much more practical than

.cd that current techniques are much more practical than

those of 1995; for example the planning algorithms in the first edition could generate plans of only

dozens of steps, while the algorithms in this edition scale up to tens of thousands of steps. Similar

, n.

orders-of-magnitude improvements are seen in probabilistic inference, language processing, and other

.nitude improvements are seen in probabilistic inference, language processing, and other

, n 1, al n 11., 1, 1.,,,

subfields. The following are the most notable changes in the book:

u

r n. 

. In Part i, we acknowledge the historical contyibutions of contfol theory, game theory, economics,

, o J, came theory, economics,

,. m'.,,,

and neuroscience. This helDs set the tone for a more integrated coverage of these ideas in

ps set the tone for a more integrated coverage of these ideas in

,

subsequent chapters.

r n. 

. In Part 11. online search algorithms are covered and a new chapter on constraint satisfaction has

, o pier on constraint satisfaction has

been added. The latter provides a natural connection to the material on logic.

r n 

. In Part ill, proDositional logic, which was presented as a stepping-stone to first-order logic in

, propositional logic, which was presented as a stepping-stone to first-order logic in

the first edition, is now presented as a useful representation language in its own right, with fast

.

inference alZorithms and circuit-based agent designs. The chapters on first-order logic have

o e .ifs. foe chapters on first-order logic have

been reorganized to present the material more clearly and we have added the internet shopping

.anned to present the material more clearly and we have added the internet shopping

domain as an example.

x nc 

. In Part IV, we include newer planning methods such as GRAPHPLAN and satisnability-based

, planning methods such as GRAPHPLAN and satisnability-based

,.,.n,1, .1. .1,.1 ., .11

planning, and we increase coverage of scheduling, conditional planning, hierarchical planning,

' 1.

and multiaZent DlanninZ

o planning.

x co

. In Part V, we have augmented the material on Bayesian networks with new algorithms, such

, o

., 1 1...,' x,

as variable elimination and Markov Chain Monte Carlo, and we have created a new chapter on

. 

uncertain temporal reasoning, covering hidden Markov models, Kalman filters, and dynamic

Bavesian networks. The coverage of Markov decision processes is deepened, and we add 

sect ac of Markov decision processes is deepened, and we add 

see.

nons on game theory and mechanism design.

came theory and mechanism design.

x n,

. In Part VI, we tie together work in statistical, symbolic, and neural learning and add sections on

, o 5 symbolic, and neural learning and add sections on

boosting algorithms, the EM algorithm, instance-based learning, and kernel methods (support

o algorithms, the EM algorithm, instance-based learning, and kernel methods (suppoft

I

vector machines).

x n.'

. In Part Vll. coverage of language processing adds sections on discourse processing and 

gram, o o

.,., 1,

mar induction, as well as a chapter on probabilistic language models, with applications to 

information retrieval and machine translation. The coverage of robottes stresses the integration of

.'

uncertain sensor data, and the chapter on vision has updated material on object recognition.

. In Part Vlll. we introduce a section on the ethical implications of Al.

l we introduce a section on the ethical implications of Al.

Using this bOOk

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. Alternatively, a course can be tailored to suit the 

interi luence. Alternatively, a course can be tailored to suit the 

interests of the instructor and student. Through its broad coverage, the book can be used to support such

Preface ix

,,

courses, whether they are short, introductory undergraduate courses or specialized graduate courses on

J, introductory undergraduate courses or specialized graduate courses on

,,.

advanced topics. Sample sVllabi from the more than 600 universities and colleges that have adopted

pies. Sample syllabi from the more than 600 universities and colleges that have adopted

the first edition are shown on the Web at aima.cs.berkeleV'edu. along with suggestions to help you find

J, along with suggestions to help you find

.

a sequence appropriate to your needs.

ac h 1,. 1,.J,RF. n.... .C

1 he book includes 385 exercises. Exercises requiring significant programming are marked with

,,,.

a keyboard icon. These exercises can best be solved by taldng advantage of the code repository at

J DOard icon. These exercises can best be solved by taldng advantage of the code repository at

., 1 1,

aima.cs.berkelev.edu. Some of them are larZe enouZh to be considered term Droiects. A number of

:.cdu. Some of them are large enough to be considered term projects. A number of

.....

exercises require some investigation of the literature; these are marked with a book icon.

aam. k

l hroughout the book, important points are marked with a pointing icon. We have included an

o

..

extensive index of around 10,000 items to make it easV to find things in the book. Wherever a new

J LO find things in the book. Wherever a new

NEWTERM term is first defined, it is also marked in the margin.

Using the Web site

At the aima.cs.berkelevedu Web site von will find:

,.edu Web site you will find:

.'.

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

plementations of the algorithms in the book in several programming languages,

1.

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

.

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

,,' 1.

. a chapter by chapter list of supplementary material and links,

...

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

,oin a discussion group for the book,

...

. Instructions on how to contact the authors with questions or comments.

luestions or comments,

..,

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

port errors in the book, in the likely event that some exist, and

.

n

. copies of the figures in the book, along with slides and other material for instructors.

.

Acknowledgments

Jitendra Malik wrote most of Chanter 24 (on vision). Most of Chapter 25 (on robottes) was written

pier 24 (on vision). Most of Chapter 25 (on robottes) was written

by Sebastian Thrun in this edition and by John Canny in the tirst edition. Doug Edwards researched

j oebastian Thrun in this edition and by John Canny in the first edition. Doug Edwards researched

the historical notes for the first edition. Tim Huang, Mark Paskin, and Cynthia Bruyns helped with

formatting of the diagrams and algorithms. Alan Apt, Sondra Chavez, Tom Holm, Jake Warde, Irwin

u

Zucker, and Camille Trentacoste at Prentice Hall tried their best to keep us on schedule and made

,, r 1.

manV helpful suggestions on the book's design and content.

J nelpful suggestions on the book's design and content.

q f' 1 o

'tllort would like to thank his p"rents for their continued sUDan

itual would like to thank his parents for their continued suppoft and encouragement and his

.

n r Q, o

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

., 1,'.

will soon be reading this. RUGS (Russell's Unusual Group of Students) have been unusually helpful.

o, p of Students) have been unusually helpful.

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

(axis), children, and friends for encouraging and tolerating him through the long hours of writing and

longer hours of rewriting.

o o.

We are indebted to the librarians at BerkeleV, Stanford, MIT, and NASA, and to the developers

J, otanford, MIT, and NASA, and to the developers

n

of CiteSeer and Google, who have revolutionized the way we do research.

ale, who have revolutionized the way we do research.

We can't thank all the people who have used the book and made suggestions, but we would

.

like to acknowledge the especially helpful comments of Eyal Amir, Xizysztof Apt, Ellery Aziel, Jeff

Van Baalen, Brian Baker, Don Barkef, TOny Barrett, James Newton Bass, Don Beal, Howard Beck,

Wolf gang Bibel, John Binder, Larry Bookman, David R. Boxall, Gerhard Brewka, Selmer Bringsjord,

bang Bibel, John Binder, Larry Bookman, David R. Boxall, Gerhard Brewka, Selmer Bringsjord,

Caria BrodleV, Chris Brown, Wilhelm Burgef, Lauren Burka, Joao Cachopo, Murray Campbell, 

Norm,, Mlhelm Burgef, Lauren Burka, Joao Cachopo, Murray Campbell, 

Norman Carver, Emmanuel Castro, Anti Chakiavarthy, Dan Chisarick, Roberto Cipolla, David Cohen,

James Coleman, June Ann Comparini, Gabs Cottrell, Ernest Davis, Rina Dechter, TOm Dietterich,

parini, Gary Cottrell, Ernest Davis, Rina Dechter, TOm Dietterich,

Chuck DVer, Barbara Engelhardt, Doug Edwards, Kutluhan Erol, Oren Etzioni, Hana Filip, Douglas

j, Barbara Engelhardt, Doug Edwards, Kutluhan Erol, Oren Etzioni, Hana Filip, Douglas

x Preface

Fisher, Jeffrey Forbes, Ken Ford, John Fosler, Alex Franz, Bob Futrelle, Marek Galecki, Stefan 

Germ I Ken Ford, John Fosler, Alex Franz, Bob Futrelle, Marek Galecki, Stefan 

Gerberding, Stuart Gill, Sabine Glesner, Seth Golub, Gosta Grahne, Russ Greiner, Eric Grimson, Barbara

b, stuart Gill, Sabine Glesner, Seth Golub, Gosta Grahne, Russ Greiner, Eric Grimson, Barbara

Grosz, Larry Hall, Sieve Hanks, Othar Hansson, Ernst Heinz, Jim Hendler, Christoph Herrmann, 

Vase, 

(asant Honavar, Tim Huang, Seth Hutchinson, Joost Jacob, Magnus Johansson, Dan JurafSky, Leslie

Kaelbling, Ken Kanazawa, Surekha Kasibhatla, Simon Kasif, Henry Kautz, Gernot Kerschbaumer,

&, nelji Kanazawa, Surekha Kasibhatla, Simon Kasif, Henry Kautz, Gernot Kerschbaumer,

Richard KirbV, Kevin Knight, Sven Koenig, Daphne Koller, Rich Korf, James Kurien, John Lafferty,

.

Gus Larsson, John Lazzaro, Jon LeBlanc, Jason Leatherman, Frank Lee, Edward Lim, Pierre 

Louds r 1, Q., 1 - -,, r.,

veaux, Don Loveland, Sridhar Mahadevan, Jim Martin, Andy Mayer, David McGrane, Jay 

Mendel, n.'

sohn, Brian Milch, Sieve Minion, Vibhu Mittal, Leora Morgenstern, Stephen Muggleton, Kevin 

Murk o x'. 1 Q,

phy, Ron Musick, Sung Myaeng, Lee Naish, Pandu Nayak, Bernhard Nebel, Stuart Nelson, XuanLong

Neuven. Illah Nourbakhsh, Sieve Omohundro, David Page, David Palmer, David Parkes, Ron Pare

ouyen, Illah Nourbakhsh, Sieve Omohundro, David Page, David Palmer, David Parkes, Ron Pare

Mark Paskin, Tony Passera, Michael Pazzani, Wim Pills, Ira Pohl, Martha Pollack, David Poole, Bruce

Porter, Malcolm Pradhan, Bill Pringle, Lorraine Prior, Greg Provan, William Rapaport, Philip Resnik,

Francesca Rossi, Jonathan Schaeffer, Richard Scherl, Lars Schuster, Sobed Shams, Stuart Shapiro,

plro,

Jude Shaviik, Satinder Singh, Daniel Sleator, David Smith, Bryan So, Robert Sproull, Lynn Stein,

Larry SteDhens. Andreas Stolcke. Paul Stradling, Devika Subramanian, Rich Sutton, Jonathan Tash,

J phens, Andreas Stolcke, Paul Stradling, Devika Subramanian, Rich Sutton, Jonathan Tash,

Austin Tate, Michael Thielscher, William Thompson, Sebastian Thrun, Eric Tiedemann, Mark 

TOrrance, Randall Upham, Paul Utgoff, Peter van Beek, Hal Varian, Sunil Vemuri, Jim Waldo, Bonnie

Webber, Dan Weld, Michael Wellman, Michael Dean White, Kamin Whitehouse, Brian Williams,

David WOlf e, Bill Woods, Alden Wright, Richard Yen, Weixiong Zhang, Shlomo Zilberstein, and the

.., 1, n

anonymous reviewers Drovided bV Prentice Hall.

J provided by Prentice Hall.

About the Cover

The cover image was designed by the authors and executed by Lisa Marie Sardegna and Maryann

e .ned by the authors and executed by Lisa Marie Sardegna and Maryann

Simmons using SGI Inventor and Adobe PhotoshoD. The cover deDicts the following items

u p. she cover depicts the following items

from the historV of Al f

J of Al f

1. Aristotle's planning algorithm from De Motu Animalium (c. 400 B .C .).

ry ac n T 1 l,

2. Ramon Lull's concept generator from Ars Magna (c. 1300 A.D.).

ac

3. Charles Babbage's Difference Engine, a prototype for the hrst universal computer (1848).

e &me, a prototype for the hrst universal computer (1848).

4. Gottlob Frege's notation for first-order logic (1789).

6 olc (1789).

5. Lewis Carroll's diagrams for logical reasoning (1886).

o o o L1886).

6. Sewall Wright's probabilistic network notation (1921).

o probabilistic network notation (1921 ).

~', ~.

7. Alan Turing (1912--1954).

5 (1912~1954).

8. ShakeV the Robot (1969--1973).

J

9. A modern diagnostic expert system (1993).

&nostic expert system (1993).

About the Authors

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

hon.'.

ours 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

J J 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 Sixth--Zadeh

.

Chair in Engineering. In 1990, he received the Presidential YOung investigator Award of the National

.ineenng. 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 California and was appointed to a Chancellor's 

ProfessorJ ppointed 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

u Knowledge in Analogy and induction and (with Eric Wefald) Do the Right Thing: Studies

in Limited Rationalics

.

Peter Norvig is director of Search Quality at Google, Inc. He is a Fellow and Executive Council

member of the American Association for Artificial intelligence. Previously, he 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. Before that he served as chief scientist at 

June

glee, where he helped develop one of the first internet information extraction services, and as a senior

scientist at Sun MicrosVstems Laboratories working on intelligent information retrieval. He received

y items Laboratories working on intelligent information retrieval. He received

a B.S. in applied mathematics from Brown University and a Ph.D. in computer science from the 

UniI

versitV of California at Berkeley. He has been a Drofessor at the University of Southern California and

j j. He has been a professor at the University of Southern California and

a research faculty member at BerkeleV' He has over 50 publications in comDuter science includinZ

j Inember at Berkeley. He has over 50 publications in computer science including

the books Paradigms ofAl Programming: Case Studies in COmmon LisP, Verbmobil: A Translation

Systemfor Face-to-Face Dialog, and intelligent HelP Systems for UNIX.

.

xI