Artificial Intelligence

Stuart Russell was born in 1962 in Portsmouth, England. He received his B.A. with first-class 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 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 Rationality.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. 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 robotics, 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 of AI Programming: Case Studies in Common Lisp and Verbmobil: A Translation System for Faceto-Face Dialog and Intelligent Help Systems for UNIX.

• I. Artificial Intelligence1. Introduction1.1 What is AI?1.2 The Foundations of Artificial Intelligence1.3 The History of Artificial Intelligence1.4 The State of the Art1.5 Summary, Bibliographical and Historical Notes, Exercises2. Intelligent Agents2.1 Agents and Environments2.2 Good Behavior: The Concept of Rationality2.3 The Nature of Environments2.4 The Structure of Agents2.5 Summary, Bibliographical and Historical Notes, ExercisesII. Problem-solving3. Solving Problems by Searching3.1 Problem-Solving Agents3.2 Example Problems3.3 Searching for Solutions3.4 Uninformed Search Strategies3.5 Informed (Heuristic) Search Strategies3.6 Heuristic Functions3.7 Summary, Bibliographical and Historical Notes, Exercises4. Beyond Classical Search4.1 Local Search Algorithms and Optimization Problems4.2 Local Search in Continuous Spaces4.3 Searching with Nondeterministic Actions4.4 Searching with Partial Observations4.5 Online Search Agents and Unknown Environments4.6 Summary, Bibliographical and Historical Notes, Exercises5. Adversarial Search5.1 Games5.2 Optimal Decisions in Games5.3 Alpha—Beta Pruning5.4 Imperfect Real-Time Decisions5.5 Stochastic Games5.6 Partially Observable Games5.7 State-of-the-Art Game Programs5.8 Alternative Approaches5.9 Summary, Bibliographical and Historical Notes, Exercises6. Constraint Satisfaction Problems6.1 Defining Constraint Satisfaction Problems6.2 Constraint Propagation: Inference in CSPs6.3 Backtracking Search for CSPs6.4 Local Search for CSPs6.5 The Structure of Problems6.6 Summary, Bibliographical and Historical Notes, ExercisesIII. Knowledge, Reasoning, and Planning7. Logical Agents7.1 Knowledge-Based Agents7.2 The Wumpus World7.3 Logic7.4 Propositional Logic: A Very Simple Logic7.5 Propositional Theorem Proving7.6 Effective Propositional Model Checking7.7 Agents Based on Propositional Logic7.8 Summary, Bibliographical and Historical Notes, Exercises8. First-Order Logic8.1 Representation Revisited8.2 Syntax and Semantics of First-Order Logic8.3 Using First-Order Logic8.4 Knowledge Engineering in First-Order Logic8.5 Summary, Bibliographical and Historical Notes, Exercises9. Inference in First-Order Logic9.1 Propositional vs. First-Order Inference9.2 Unification and Lifting9.3 Forward Chaining9.4 Backward Chaining9.5 Resolution9.6 Summary, Bibliographical and Historical Notes, Exercises10. Classical Planning10.1 Definition of Classical Planning10.2 Algorithms for Planning as State-Space Search10.3 Planning Graphs10.4 Other Classical Planning Approaches10.5 Analysis of Planning Approaches10.6 Summary, Bibliographical and Historical Notes, Exercises11. Planning and Acting in the Real World11.1 Time, Schedules, and Resources11.2 Hierarchical Planning11.3 Planning and Acting in Nondeterministic Domains11.4 Multiagent Planning11.5 Summary, Bibliographical and Historical Notes, Exercises12 Knowledge Representation12.1 Ontological Engineering12.2 Categories and Objects12.3 Events12.4 Mental Events and Mental Objects12.5 Reasoning Systems for Categories12.6 Reasoning with Default Information12.7 The Internet Shopping World12.8 Summary, Bibliographical and Historical Notes, ExercisesIV. Uncertain Knowledge and Reasoning13. Quantifying Uncertainty13.1 Acting under Uncertainty13.2 Basic Probability Notation13.3 Inference Using Full Joint Distributions13.4 Independence13.5 Bayes’ Rule and Its Use13.6 The Wumpus World Revisited13.7 Summary, Bibliographical and Historical Notes, Exercises14. Probabilistic Reasoning14.1 Representing Knowledge in an Uncertain Domain14.2 The Semantics of Bayesian Networks14.3 Efficient Representation of Conditional Distributions14.4 Exact Inference in Bayesian Networks14.5 Approximate Inference in Bayesian Networks14.6 Relational and First-Order Probability Models14.7 Other Approaches to Uncertain Reasoning14.8 Summary, Bibliographical and Historical Notes, Exercises15. Probabilistic Reasoning over Time15.1 Time and Uncertainty15.2 Inference in Temporal Models15.3 Hidden Markov Models15.4 Kalman Filters15.5 Dynamic Bayesian Networks15.6 Keeping Track of Many Objects15.7 Summary, Bibliographical and Historical Notes, Exercises16. Making Simple Decisions16.1 Combining Beliefs and Desires under Uncertainty16.2 The Basis of Utility Theory16.3 Utility Functions16.4 Multiattribute Utility Functions16.5 Decision Networks16.6 The Value of Information16.7 Decision-Theoretic Expert Systems16.8 Summary, Bibliographical and Historical Notes, Exercises17. Making Complex Decisions17.1 Sequential Decision Problems17.2 Value Iteration17.3 Policy Iteration17.4 Partially Observable MDPs17.5 Decisions with Multiple Agents: Game Theory17.6 Mechanism Design17.7 Summary, Bibliographical and Historical Notes, ExercisesV. Learning18. Learning from Examples18.1 Forms of Learning18.2 Supervised Learning18.3 Learning Decision Trees18.4 Evaluating and Choosing the Best Hypothesis18.5 The Theory of Learning18.6 Regression and Classification with Linear Models18.7 Artificial Neural Networks18.8 Nonparametric Models18.9 Support Vector Machines18.10 Ensemble Learning18.11 Practical Machine Learning18.12 Summary, Bibliographical and Historical Notes, Exercises19. Knowledge in Learning19.1 A Logical Formulation of Learning19.2 Knowledge in Learning19.3 Explanation-Based Learning19.4 Learning Using Relevance Information19.5 Inductive Logic Programming19.6 Summary, Bibliographical and Historical Notes, Exercises20. Learning Probabilistic Models20.1 Statistical Learning20.2 Learning with Complete Data20.3 Learning with Hidden Variables: The EM Algorithm20.4 Summary, Bibliographical and Historical Notes, Exercises21. Reinforcement Learning21.1 Introduction21.2 Passive Reinforcement Learning21.3 Active Reinforcement Learning21.4 Generalization in Reinforcement Learning21.5 Policy Search21.6 Applications of Reinforcement Learning21.7 Summary, Bibliographical and Historical Notes, ExercisesVI. Communicating, Perceiving, and Acting22. Natural Language Processing22.1 Language Models22.2 Text Classification22.3 Information Retrieval22.4 Information Extraction22.5 Summary, Bibliographical and Historical Notes, Exercises23. Natural Language for Communication23.1 Phrase Structure Grammars23.2 Syntactic Analysis (Parsing)23.3 Augmented Grammars and Semantic Interpretation23.4 Machine Translation23.5 Speech Recognition23.6 Summary, Bibliographical and Historical Notes, Exercises24. Perception24.1 Image Formation24.2 Early Image-Processing Operations24.3 Object Recognition by Appearance24.4 Reconstructing the 3D World24.5 Object Recognition from Structural Information24.6 Using Vision24.7 Summary, Bibliographical and Historical Notes, Exercises25. Robotics25.1 Introduction25.2 Robot Hardware25.3 Robotic Perception25.4 Planning to Move25.5 Planning Uncertain Movements25.6 Moving25.7 Robotic Software Architectures25.8 Application Domains25.9 Summary, Bibliographical and Historical Notes, ExercisesVII. Conclusions26 Philosophical Foundations26.1 Weak AI: Can Machines Act Intelligently?26.2 Strong AI: Can Machines Really Think?26.3 The Ethics and Risks of Developing Artificial Intelligence26.4 Summary, Bibliographical and Historical Notes, Exercises27. AI: The Present and Future27.1 Agent Components27.2 Agent Architectures27.3 Are We Going in the Right Direction?27.4 What If AI Does Succeed?AppendicesA. Mathematical BackgroundA.1 Complexity Analysis and O() NotationA.2 Vectors, Matrices, and Linear AlgebraA.3 Probability DistributionsB. Notes on Languages and AlgorithmsB.1 Defining Languages with Backus—Naur Form (BNF)B.2 Describing Algorithms with PseudocodeB.3 Online HelpBibliographyIndex