1、Artificial IntelligenceA Modern ApproachStuart J. Russell and Peter NorvigContributing writers:John F. Canny, Jitendra M. Malik, Douglas D. EdwardsPrentice Hall, Englewood Cliffs, New Jersey 07632Library of Congress Cataloging-in-Publication DataRussell, Stuart J. (Stuart Jonathan)Artificial intelli
2、gence : a modern approach/ Stuart Russell, Peter Norvig.p. cm.Includes bibliographical references and index.ISBN 0-13-103805-21. Artificial intelligence I. Norvig, Peter. II. Title.Q335.R86 1995006.3-dc20 94-36444CIPPublisher: Alan AptProduction Editor: Mona PompiliDevelopmental Editor: Sondra Chave
3、zCover Designers: Stuart Russell and Peter NorvigProduction Coordinator: Lori BulwinEditorial Assistant: Shirley McGuire 1995 by Prentice-Hall, Inc.A Simon it also introduces a new kind of component, the neural network,and its associated learning procedures. Part VII, “Communicating, Perceiving, and
4、 Acting,“describes ways in which an intelligent agent can perceive its environment so as to know what isgoing on, whether by vision, touch, hearing, or understanding language; and ways in which it canturn its plans into real actions, either as robot motion or as natural language utterances. Finally,
5、Part VIII, “Conclusions,“ analyses the past and future of AI, and provides some light amusementby discussing what AI really is and why it has already succeeded to some degree, and airing theviews of those philosophers who believe that AI can never succeed at all.PrefaceUsing this bookThis is a big b
6、ook; covering all the chapters and the projects would take two semesters. You willnotice that the book is divided into 27 chapters, which makes it easy to select the appropriatematerial for any chosen course of study. Each chapter can be covered in approximately one week.Some reasonable choices for
7、a variety of quarter and semester courses are as follows: One-quarter general introductory course:Chapters 1, 2, 3, 6, 7, 9, 11, 14, 15, 18, 22. One-semester general introductory course:Chapters 1, 2, 3, 4, 6, 7, 9, 11, 13, 14, 15, 18, 19, 22, 24, 26, 27. One-quarter course with concentration on sea
8、rch and planning:Chapters 1, 2, 3, 4, 5, 6, 7, 9, 11, 12,13. One-quarter course with concentration on reasoning and expert systems:Chapters 1,2, 3, 6, 7, 8,9, 10,11,14, 15,16. One-quarter course with concentration on natural language:Chapters 1, 2, 3, 6, 7, 8, 9, 14, 15, 22, 23, 26, 27. One-semester
9、 course with concentration on learning and neural networks:Chapters 1, 2, 3, 4, 6, 7, 9, 14, 15, 16, 17,18, 19, 20, 21. One-semester course with concentration on vision and robotics:Chapters 1, 2, 3, 4, 6, 7, 11, 13, 14, 15, 16, 17, 24, 25, 20.These sequences could be used for both undergraduate and
10、 graduate courses. The relevant partsof the book could also be used to provide the first phase of graduate specialty courses. Forexample, Part VI could be used in conjunction with readings from the literature in a course onmachine learning.We have decided not to designate certain sections as “option
11、al“ or certain exercises as“difficult,“ as individual tastes and backgrounds vary widely. Exercises requiring significantprogramming are marked with a keyboard icon, and those requiring some investigation of theliterature are marked with a book icon. Altogether, over 300 exercises are included. Some
12、 ofthem are large enough to be considered term projects. Many of the exercises can best be solvedby taking advantage of the code repository, which is described in Appendix B. Throughout thebook, important points are marked with a pointing icon.If you have any comments on the book, wed like to hear f
13、rom you. Appendix B includesinformation on how to contact us.AcknowledgementsJitendra Malik wrote most of Chapter 24 (Vision) and John Canny wrote most of Chapter25 (Robotics). Doug Edwards researched the Historical Notes sections for all chapters and wrotemuch of them. Tim Huang helped with formatt
14、ing of the diagrams and algorithms. MaryannSimmons prepared the 3-D model from which the cover illustration was produced, and LisaMarie Sardegna did the postprocessing for the final image. Alan Apt, Mona Pompili, and SondraChavez at Prentice Hall tried their best to keep us on schedule and made many
15、 helpful suggestionson design and content.PrefaceStuart would like to thank his parents, brother, and sister for their encouragement and theirpatience at his extended absence. He hopes to be home for Christmas. He would also like tothank Loy Sheflott for her patience and support. He hopes to be home
16、 some time tomorrowafternoon. His intellectual debt to his Ph.D. advisor, Michael Genesereth, is evident throughoutthe book. RUGS (Russells Unusual Group of Students) have been unusually helpful.Peter would like to thank his parents (Torsten and Gerda) for getting him started, his advisor(Bob Wilens
17、ky), supervisors (Bill Woods and Bob Sproull) and employer (Sun Microsystems)for supporting his work in AI, and his wife (Kris) and friends for encouraging and tolerating himthrough the long hours of writing.Before publication, drafts of this book were used in 26 courses by about 1000 students.Both
18、of us deeply appreciate the many comments of these students and instructors (and otherreviewers). We cant thank them all individually, but we would like to acknowledge the especiallyhelpful comments of these people:Tony Barrett, Howard Beck, John Binder, Larry Bookman, Chris Brown, LaurenBurka, Murr
19、ay Campbell, Anil Chakravarthy, Roberto Cipolla, Doug Edwards, Kut-luhan Erol, Jeffrey Forbes, John Fosler, Bob Futrelle, Sabine Glesner, Barbara Grosz,Steve Hanks, Othar Hansson, Jim Hendler, Tim Huang, Seth Hutchinson, Dan Ju-rafsky, Leslie Pack Kaelbling, Keiji Kanazawa, Surekha Kasibhatla, Simon
20、 Kasif,Daphne Roller, Rich Korf, James Kurien, John Lazzaro, Jason Leatherman, JonLeBlanc, Jim Martin, Andy Mayer, Steve Minton, Leora Morgenstern, Ron Musick,Stuart Nelson, Steve Omohundro, Ron Parr, Tony Passera, Michael Pazzani, IraPohl, Martha Pollack, Bruce Porter, Malcolm Pradhan, Lorraine Pri
21、or, Greg Provan,Philip Resnik, Richard Scherl, Daniel Sleator, Robert Sproull, Lynn Stein, DevikaSubramanian, Rich Sutton, Jonathan Tash, Austin Tate, Mark Torrance, RandallUpham, Jim Waldo, Bonnie Webber, Michael Wellman, Dan Weld, Richard Yen,Shlomo Zilberstein.Summary of ContentsiiiinIVArtificial
22、 Intelligence 11 Introduction. 32 Intelligent Agents. 31Problem-solving 533 Solving Problems by Searching . 554 Informed Search Methods . 925 Game Playing. 122Knowledge and reasoning 1496 Agents that Reason Logically. 1517 First-Order Logic. 1858 Building a Knowledge Base . 2179 Inference in First-O
23、rder Logic. 26510 Logical Reasoning Systems. 297Acting logically 33511 Planning. 33712 Practical Planning . 36713 Planning and Acting. 392Uncertain knowledge and reasoning 41314 Uncertainty. 41515 Probabilistic Reasoning Systems. 43616 Making Simple Decisions . 47117 Making Complex Decisions . 498Le
24、arning 52318 Learning from Observations. 52519 Learning in Neural and Belief Networks. 56320 Reinforcement Learning. 59821 Knowledge in Learning. 625Communicating, perceiving, and acting 64922 Agents that Communicate . 65123 Practical Natural Language Processing . 69124 Perception . 72425 Robotics.
25、773VIII Conclusions 81526 Philosophical Foundations . 81727 AI: Present and Future . 842A Complexity analysis and O() notation. 851B Notes on Languages and Algorithms. 854Bibliography 859Index 905VIVIIContentsI Artificial Intelligence 11 Introduction 31.1 What is AI? . 4Acting humanly: The Turing Te
26、st approach . 5Thinking humanly: The cognitive modelling approach . 6Thinking rationally: The laws of thought approach . 6Acting rationally: The rational agent approach . 71.2 The Foundations of Artificial Intelligence . 8Philosophy (428 B.C.-present) . 8Mathematics (c. 800-present) . 11Psychology (
27、1879-present) . 12Computer engineering (1940-present) . 14Linguistics (1957-present) . 151.3 The History of Artificial Intelligence . 16The gestation of artificial intelligence (1943-1956). . 16Early enthusiasm, great expectations (1952-1969) . 17A dose of reality (1966-1974) . 20Knowledge-based sys
28、tems: The key to power? (1969-1979). . 22AI becomes an industry (1980-1988) . 24The return of neural networks (1986-present) . 24Recent events (1987-present) . 251.4 The State of the Art . 261.5 Summary . 27Bibliographical and Historical Notes . 28Exercises . 282 Intelligent Agents 312.1 Introductio
29、n . 312.2 How Agents Should Act . 31The ideal mapping from percept sequences to actions . 34Autonomy . 352.3 Structure of Intelligent Agents . 35Agent programs . 37Why not just look up the answers? . 38An example . 39Simple reflex agents . 40Agents that keep track of the world . 41Goal-based agents
30、. 42Utility-based agents . 442.4 Environments . 45XIV ContentsProperties of environments . 46Environment programs . 472.5 Summary . 49Bibliographical and Historical Notes . 50Exercises . 50II Problem-solving 533 Solving Problems by Searching 553.1 Problem-Solving Agents . 553.2 Formulating Problems
31、. 57Knowledge and problem types . 58Well-defined problems and solutions . 60Measuring problem-solving performance . 61Choosing states and actions . 613.3 Example Problems . 63Toy problems . 63Real-world problems . 683.4 Searching for Solutions . 70Generating action sequences . 70Data structures for
32、search trees . 723.5 Search Strategies . 73Breadth-first search . 74Uniform cost search . 75Depth-first search . 77Depth-limited search . 78Iterative deepening search . 78Bidirectional search . 80Comparing search strategies . 813.6 Avoiding Repeated States . 823.7 Constraint Satisfaction Search . 83
33、3.8 Summary . 85Bibliographical and Historical Notes . 86Exercises . 874 Informed Search Methods 924.1 Best-First Search . 92Minimize estimated cost to reach a goal: Greedy search . 93Minimizing the total path cost: A* search . 964.2 Heuristic Functions . 101The effect of heuristic accuracy on perfo
34、rmance . 102Inventing heuristic functions . 103Heuristics for constraint satisfaction problems . 1044.3 Memory Bounded Search . 106Contents_xvIterative deepening A* search (IDA*) . 106SMA* search . 1074.4 Iterative Improvement Algorithms .111Hill-climbing search .111Simulated annealing .113Applicati
35、ons in constraint satisfaction problems .1144.5 Summary . 115Bibliographical and Historical Notes . 115Exercises . 1185 Game Playing 1225.1 Introduction: Games as Search Problems . 1225.2 Perfect Decisions in Two-Person Games . 1235.3 Imperfect Decisions . 126Evaluation functions . 127Cutting off se
36、arch . 1295.4 Alpha-Beta Pruning . 129Effectiveness of alpha-beta pruning . 1315.5 Games That Include an Element of Chance . 133Position evaluation in games with chance nodes . 135Complexity of expectiminimax . 1355.6 State-of-the-Art Game Programs . 136Chess . 137Checkers or Draughts . 138Othello .
