IPRENTICE HALL SERIESIN ARTIFICIAL INTELLIGENCEStuart Russell and Peter Norvig, EditorsFORSYTH&PONCEGRAHAMJURAFSKY& MARTINNEAPOLITANRUSSELL&NORVIGComputer Vision: A Modern ApproachANSI Common LispSpeech and Language ProcessingLearning Bayesian NetworksArtificial Intelligence: A Modern ApproachArtificial IntelligenceA Modern ApproachSecond EditionStuart. .J.Russell and Peter NorvigContributing writers:John F. CannyDouglas D. EdwardsJitendra M. MalikSebastian Thrun.J.'.I; Pearson Education lnternational
u purchased this book within the United States or Canada you should be aware that ir has been wrongfully imported:mt the approval of the publisher or the Author. President and Editorial Director, ECS: Marcia J. HortonIlisher: Alan R. Aptociate Editor: Toni Dianne Holmtorial Assistant: Patrick Lindnere President and Director of Praduction and Manufacturing, ESM: David W. Riccardi:cutive Managing Editor: Vince ü'Brien;istant Managing Editor: Camille Trentacoste,duction Editor: Irwin Zuckernufacturing Manager: Trudy Pisciottinufacturing Buyer: Lisa McDowell·ector, Creative Services: Paul Belfanti:ative Director: Carole Anson· Editor: Greg Dulles: Director: Heather Scottsistant to Art Director: Geoffrey Cassarver Designers: Stuart Russell and Peter Norvigver lrnage Creation: Stuart Russell and Peter Norvig; Tamara Newnam and Patrice Van Ackererior Designer: Stuart Russell and Peter Norvigrrketing Manager: Pamela Shafferrrketing Assistant: Barrie ReinholdFor Loy, Gordon, and Lucy For Kris, Isabella, and Juliet -112003. ]995 by Pearson Educarian. lnc.Pearson Education, lnc.Upper Saddle River, New Jersey 07458 II rights reserved. No part of this book rnay be reproduced, in any form or by any means,ithout permission in writing fram the publisher.le author and publisher of this book have used their best efforts in preparing this book. These effortsc1ude the development, research, and testing of the theories and prograrn; to determine their effectiveness. e author and publisher make no warranty of any kind, express or implied, with regard to tbese programs· the documentation contained in this book. The author and publisher shall not be liable in any event forcidental ar consequential damages in connection with, or arising out of, the furnishing, performance,· use of these programs.rinted in the United States of America09876543:SBN arson)earson)earson)earsonEducation Ltd., LondonEducarion Australia Pty. Lld . SydneyEducation Singapore, Pte. Ltd.Education North Asia Lld., Hang KangEducation Canada, Inc., TorontoEducación de Mexico, S.A. de c.v.Education-Japan,TokyoEducation Malaysia, Pte. Ltd.Education, lnc., Upper Saddle River, New Jersey';',"S.J.R.P.N.
PrefaceArtificial Intelligence (AI) is a big field, and this is a big book. We have tried to explore the fullbreadth of the field, which encompasses logic, probability, and continuous mathematics; perception,reasoning, learning, and action; and everything from microelectronic devices to robotic planetaryexplorers. The book is also big because we go into some depth in presenting results, although westrive to cover only the most central ideas in the main part of each chapter. Pointers are given tofurther results in the bibliographical notes at the end of each chapter.The subtitle of this book is "A Modern Approach." The intended meaning of this rather emptyphrase is that we have tried to synthesize what is now known into a common framework, rather thantrying to explain each subfield of AI in its own historical context. We apologize to those whosesubfields 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 AI as the study ofagents that receive percepts from the environment and perform actions. Each such agent implements afunction that maps percept sequences to actions, and we cover different ways to represent these func- .tions, such as production systems, reactive agents, real-time conditional planners, neural networks,and decision-theoretic systems. We explain the role of learning as extending the reach of the designeriuto unknown environments, and we show how that role constrains agent design, favoring explicitknowledge representation and reasoning. We treat robotics and vision not as independently definedproblems, but as occurring in the service of achieving goals. We stress the importance of the taskenvironment in determining the appropriate agent designoOur primary aim is to convey the ideas that have emerged over the past fifty years of AI researchand the past two millenia of related work. We have tried to avoid excessive formality in the presentation of these ideas while retaining precision. Wherever appropriate, we have included pseudocodealgorithms 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 canalso be used in a graduate-Ievel course (perhaps with the addition of some of the primary sourcessuggested in the bibliographical notes). Because of its comprehensive coverage and large number ofdetailed algorithms, it is useful as a primary reference volume for AI graduate students and professionals wishing to branch out beyond their own subfield. The only prerequisite is familiarity withbasic concepts of computer science (algorithms, data structures, complexity) at a sophomore leveI.Freshman ca1culus is useful for understanding neural networks and statisticallearning in detail. Someof the required mathematical background is supplied in Appendix A.Overview of the book'.:;."The book is divided into eight parts. Part I, Artificial Intelligence, offers a view of the AI enterprisebased around the idea of intelligent agents-systemsthat can decide what to do and then do it. PartlI, Problem Solying, concentrates on methods for deciding what to do when one needs to think abeadseveral steps-for example in navigating across a country or playing chess. Part III, Knowledge andReasoning, discusses ways to represent knowledge about the world-how it works, what it is currentlylike, and what one's actions might do-and how to reason logically with that knowledge. Part IV,Planning, then discusses how to use these reasoning methods to decide what to do, particularly byconstructing 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 lI-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-makingvii
Prefaceviiicomponents. Part VII, Communicating, Perceiving, and Acting, describes ways in which an intelligent agem 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 imo real actions, either asrobot motion or as naturallanguage utterances. Finally, Part VIII, Conclusions, analyzes the past andfuture of AI and the philosophical and ethical implications of artificial intelligence.courses, whether they are short, introductory undergraduate eourses or specialized graduate courses onadvaneed topies. Sample syllabi from the more than 600 universities and eolleges that have adoptedthe first edition are shown on the Web at aima.cs.berkeley.edu, along with suggestions to help you find1 ! Changes from the first editionMuch has changed in AI since the publication of the first edition in 1995, and much has changed in thisbook. Every chapter has been signifieantly rewritten to refleet the latest work in the field, to reinterpretold work in a way that is more eohesive with new findings, and to improve the pedagogical flow ofideas. Followers of AI should be encouraged that eurrent teehniques are much more praetical thanthose of 1995; for example the planning algorithms in the first edition could generate plans of onlydozens of steps, while the algorithms in this edition seale up to tens of thousands of steps. Similarorders-of-magnitude improvements are seen in probabilistie inference, language proeessing, and othersubfields. The following are the most notable ehanges in the book:o In Part I, we acknow ledge the historical eontributions of control theory, game theory, economics,and neuroscience. This helps set the tone for a more integrated coverage of these ideas insubsequent ehapters.o In Part lI, online seareh algorithms are covered and a new chapter on constraint satisfaction hasbeen added. The latter provides a natural conneetion to the material on logic.o In Part III, propositionallogic, which was presented as a stepping-stone to first-order logic inthe first edition, is now presemed as a useful representation language in its own right, with fastinference algorithms and circuit-based agent designs. The chapters on first-order logie havebeen reorganized to present the material more clearly and we have added the Internet shoppingdomain as an example.o In Part IV, we include newer planning methods such as GRA HPLAN and satisfiability-basedplanning, and we increase eoverage of scheduling, conditional planning, hierarehieal planning,and multiagent planning.o In Part V, we have augmented th material on Bayes,ian networks with new algorithms, suehas variable elimination and Markov Chain Monte Carlo, and we have ereated a new chapter onuncertain temporal reasoning, covering hidden Markov models, Kalman filters, and dynamicBayesian networks. The eoverage of Markov decision processes is deepened, and we add sections on game theory and meehanism designoo In Part VI, we tie together work in statistical, symbolie, and neurallearning and add sections onboosting algorithms, the EM algorithm, instance-based learning, and kernel methods (supportvector maehines).o In Part VII, eoverage of language processing adds sections on diseourse processing and grammar induetion, as well as a ehapter on probabilistic language models, with applications to information retrieval and maehine translation. The coy,erage \lf roboties stresses the integration ofuncertain sensor data, and the ehapter on vision has úpdated material on objeet recognition.o In Part VIII, we introduce a section on the ethical implicatioris"Of AI.Using this bookThe book has 27 chapters, each requiring about a week's worth of leetures, so working through thewhole book requires a two-semester sequence. Alternatively, a eourse ean be tailored to suit the interests of the instructor and student. Through its broad coverage, the book can be used to support suchixPreface NEWTERMa sequenee appropriate to your needs.The book includes 385 exereises. Exercises requiring significant programming are marked witha keyboard icon. These exercises can best be solved by taking advantage of the code repository ataima.cs.berkeley.edu. Some of them are large enough to be considered term projects. A number ofexercises require some investigation of the literature; these are marked with a book icon.Throughout the book, important points are marked with a pointing icon. We have included anextensive index of around 10,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.Using the Web si teAt the aima.cs.berkeley.eduWeb site you will find:o implementatións of the algorithms in the book in several programming languages,o a list of over 600 schools that have used the book, many with links to online eourse materiais,o an annotated list of over 800 links to sites around the web with useful AI content,o a ehapter by chapter'list of supplementary material and links,o instructions on how to join a diseussion group for the book,o instructions on how to contaet the authors with questions or cornrnents,o instructions on how to report errors in the book, in the likely event that some exist, ando eopies of the figures in the book, along with slides and other material for instructors.AcknowledgmentsJitendra Malik wrote most of Chapter 24 (on vision). Most of Chapter 25 (on roboties) was writtenby Sebastian Thrun in this edition and by John Canny in the first edition. Doug Edwards researehedthe historieal notes for the first edition. Tim Huang, Mark Paskin, and Cynthia Bruyns helped withformatting of the diagrams and algorithms. Alan Apt, Sondra Chavez, Toni Holm, Jake Warde, IrwinZucker, and Camille Trentacoste at Prentice Hall tried their best to keep us on schedule and mademany helpful suggestions on the book's design and content.Stuart would like to thank his parents for their continued support and encouragement and hiswife, Loy Sheflott, for her endless patience and boundless wisdom. He hopes that Gordon and Lucywill soon be reading this. RUGS (Russell's Unusual Group of Students) have been unusually helpful.Peter would like to thank his parents (Torsten and Gerda) for getting him started, and his wife(Kris), ehildren, and friends for eneouraging and tolerating him through the long hours of writing andlonger hours of rewriting.We are itidebted to the librarians at Berkeley, Stanford, MIT, and NASA, and to the developersof CiteSeer and Google, who have revolutionized the way we do researeh.We can't thank ali the people who have used the book and made suggestions, but we wouldlike to acknowledge the especially heJpful cornrnents of Eyal Amit, Krzysztof Apt, Ellery Aziel, JeffVan Baalen, Brian Baker, Don Barker, Tony Barrett, James Newton Bass, Don Beal, Howard Beck,Wolfgang Bibel, John Binder, Larry Bookman, David R. Boxall, Gerhard Brewka, Selmer Bringsjord,Carla Brodley, Chris Brown, Wilhelm Burger, Lauren Burka, Joao Cachopo, Murray Campbell, Norman Carver, Emmanuel Castro, Anil Chakravarthy, Dan Chisarick, Roberto Cipolla, David Cohen,James Coleman, Julie Ann Comparini, Gary Cottrell, Ernest Davis, Rina Deehter, Tom Dietterich,Chuck Dyer, Barbara Engelhardt, Doug Edwards, Kutluhan Erol, Oren Etzioni, Hana Filip, Douglas
PrefacexFisher, Jeffrey Forbes, Ken Ford, John Fosler, Alex Franz, Bob Futrelle, Marek Galecki, Stefan Gerberding, Stuart Gill, Sabine Glesner, Seth Golub, Gosta Grahne, Russ Greiner, Eric Grimson, BarbaraGrosz, Larry Hall, Steve Hanks, Othar Hansson, Ernst Heinz, Jim Hendler, Christoph Herrmann, Vasant Honavar, Tim Huang, Seth Hutchinson, Joost Jacob, !vlagnus Johansson, Dan Jurafsky, LeslieKaelbling, Keiji Kanazawa, Surekha Kasibhatla, Simon Kasif, Henry Kautz, Gernot Kerschbaumer,Richard Kirby, 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 Louveaux, Don Loveland, SridharMahadevan, Jim Martin, Andy !vlayer, David !vlcGrane, Jay !vlendelsohn, Brian !vli1ch,Steve Minton, Vibhu Mittal, Leora Morgenstem, Stephen Muggleton, Kevin Murphy, Ron Musick, Sung Myaeng, Lee Naish, Pandu Nayak, Bernhard Nebel, Stuart Nelson, XuanLongNguyen, Illah Nourbakhsh, Steve Omohundro, David Page, David Palmer, David Parkes, Ron Parr,Mark Paskin, Tony Passera, Michael Pazzani, Wim Pijls, Ira Pohl, Martha Pollack, David Poole, BrucePorter, Ma1colm Pradhan, Bill Pringle, Lorraine Prior, Greg Provan, William Rapaport, Philip Resnik,Francesca Rossi, Jonathan Schaeffer, Richard Scherl, Lars Schuster, Soheil Shams, Stuart Shapiro,Jude Shavlik, Satinder Singh, Daniel Sleator, David Smith, Bryan So, Robert Sproull, Lynn Stein,., Larry Stephens, Andreas Sto1cke, Paul Stradling, Devika Subramanian, Rich Sutton, Jonathan Tash,," Austin Tate, !vlichael Thielscher, William Thompson, Sebastian Thrun, Eric Tiedemann, !vlark Torrance, Randall Upham, Paul Utgoff, Peter van Beek, Hal Varian, Sunil Vemuri, Jim Waldo, BonnieWebber, Dan Weld, !vlichael Wellman, Michael Dean White, Kamin Whitehouse, Brian Williams,David Wolfe, Bill Woods, Alden Wright, Richard Yen, Weixiong Zhang, Shlomo Zilberstein, and theanonymous reviewers provided by Prentice Hall.About the CoverThe cover image was designed by the authors and executed by Lisa Marie Sardegna and MaryannSimmons using SGI Inventor and Adobe PhotoshopTrvI The cover depicts the following itemsfrom the history of AI:About the AuthorsStuart Russell was bom in 1962 in Portsmouth, England. He received his B.A. with first-class honours in physics from Oxford University in 1982, and bis Ph.D. in computer science from Stanford in1986. He then joined the faculty of the University of California at Berkeley, where he is a professorof computer science, director of the Center for Intelligent Systems, and holder of the Smith-ZadehChair in Engineering. In 1990, he received the Presidential Young Investigator Award of the NationalScience Foundation, and in 1995 he was cowinner of the Computers and Thought Award. He was a1996 Miller Professor of the University of Califomia and was appointed to a Chancellor's Professorship in 2000. In 1998, he gave the Forsythe Memoria1 Lectures at Stanford University. He is a Fellowand former Executive Council member of the American Association for Artificial Intelligence. He haspublished over 100 papers on a wide range of topics in artificial intelligence. His other books includeThe Use of Knowledge in Analogy and Indllction and (with Eric Wefald) Do the Right Thing: Stlldiesin Limited Rationality.Peter Norvig is director of Search Quality at Google, Inc. He is a Fellow and EXifutive Councilmember of the American Association for Artificial Intelligence. Previous1y, he was head of the Computational Sciences Division at NASA Ames Research Center, where he oversaw NASA's researchand development in artificial intelligence and robotics. Before that he served as chief scientist at Junglee, where he helped develop one of the first Internet information extraction services, and as a seniorscientist at Sun Microsystems Laboratories working on intelligent information retrieval. He receiveda B.S. in applied mathematics from Brown University and a Ph.D. in computer science from the University of Califomia at Berkeley. He has been a professor at the University of Southem Califomia anda research faculty member at Berkeley. He has over 50 publications in computer science includingthe books Paradigms of AI Programming: Case Stlldies in Common Lisp, Verbmobil: A TranslationSystemfor Face-to-Face Dialog, and Intelligent Help Systems for UNIX.1. Aristotle's planning algorithm from De Motll Animalillm (c. 400 B.C.).2. Ramon Lull's concept generator fromArs Magna (c. 1300 A.D.).3. Charles Babbage's Difference Engíne, a prototype for the first universal computer (1848).4. Gottlob Frege's notation for first-order logic (1789).5. Lewis Carroll's diagrams for logical reasoning (1886).6. Sewall Wright's probabilistic network notation (1921).7. Alan Turing (1912-1954).8. Shakey the Robot (1969-1973).9. A modern diagnôstic expert system (1993).;.xi
Summary af CantentsIArtificial InteIligenceII1Introduction2Intelligent AgentsSolving Problems by Searching . . . .Informed Search and ExplorationConstraint Satisfaction Problems . .Adversarial.Search. 5994137161Knowledge and reasoning78910IV132Problem-solving3456III. . Logical AgentsFirst-Order Logic . Inference in First-Order LogicKnowledge Representation194240272320Planning11 Planning12 Planning and Acting in the Real World . . . . .VUncertain knowledge and reasoning1314151617VIUncertainty . . . . .
IN ARTIFICIAL INTELLIGENCE Stuart Russell and Peter Norvig, Editors _I FORSYTH & PONCE GRAHAM JURAFSKY & MARTIN NEAPOLITAN RUSSELL & NORVIG Computer Vision: A Modern Approach ANSI Common Lisp .
and artificial intelligence expert, joined Ernst & Young as the person in charge of its global innovative artificial intelligence team. In recent years, many countries have been competing to carry out research and application of artificial intelli-gence, and the call for he use of artificial
BCS Foundation Certificate in Artificial Intelligence V1.1 Oct 2020 Syllabus Learning Objectives 1. Ethical and Sustainable Human and Artificial Intelligence (20%) Candidates will be able to: 1.1. Recall the general definition of Human and Artificial Intelligence (AI). 1.1.1. Describe the concept of intelligent agents. 1.1.2. Describe a modern .
IN ARTIFICIAL INTELLIGENCE Stuart Russell and Peter Norvig, Editors FORSYTH & PONCE Computer Vision: A Modern Approach GRAHAM ANSI Common Lisp JURAFSKY & MARTIN Speech and Language Processing, 2nd ed. NEAPOLITAN Learning Bayesian Networks RUSSELL & NORVIG Artiﬁcial Intelligence: A Modern Approach, 3rd ed. Artiﬁcial Intelligence A Modern Approach Third Edition Stuart J. Russell and Peter .
Peter Norvig Prentice Hall, 2003 This is the book that ties in most closely with the module Artificial Intelligence (2nd ed.) Elaine Rich & Kevin Knight McGraw Hill, 1991 Quite old now, but still a good second book Artificial Intelligence: A New Synthesis Nils Nilsson Morgan Kaufmann, 1998 A good modern book Artificial Intelligence (3rd ed.) Patrick Winston Addison Wesley, 1992 A classic, but .
BCS Essentials Certificate in Artificial Intelligence Syllabus V1.0 BCS 2018 Page 10 of 16 Recommended Reading List Artificial Intelligence and Consciousness Title Artificial Intelligence, A Modern Approach, 3rd Edition Author Stuart Russell and Peter Norvig, Publication Date 2016, ISBN 10 1292153962
PA R T 1 Introduction to Artificial Intelligence 1 Chapter 1 A Brief History of Artificial Intelligence 3 1.1 Introduction 3 1.2 What Is Artificial Intelligence? 4 1.3 Strong Methods and Weak Methods 5 1.4 From Aristotle to Babbage 6 1.5 Alan Turing and the 1950s 7 1.6 The 1960s to the 1990s 9 1.7 Philosophy 10 1.8 Linguistics 11
Artificial Intelligence, Machine Learning, and Deep Learning (AI/ML/DL) F(x) Deep Learning Artificial Intelligence Machine Learning Artificial Intelligence Technique where computer can mimic human behavior Machine Learning Subset of AI techniques which use algorithms to enable machines to learn from data Deep Learning
Artificial Intelligence and Its Military Implications China Arms Control and Disarmament Association July 2019 What Is Artificial Intelligence? Artificial intelligence (AI) refers to the research and development of the theories, methods, technologies, and application systems for