Artificial Intelligence: A Modern Approach

Cover......Page 1
Title Page......Page 5
Copyright......Page 6
Preface......Page 9
About the Authors......Page 14
Contents......Page 15
1.1 What Is AI?......Page 21
1.2 The Foundations of Artificial Intelligence......Page 25
1.3 The History of Artificial Intelligence......Page 36
1.4 The State of the Art......Page 48
1.5 Summary, Bibliographical and Historical Notes, Exercises......Page 49
2.1 Agents and Environments......Page 54
2.2 Good Behavior: The Concept of Rationality......Page 56
2.3 The Nature of Environments......Page 60
2.4 The Structure of Agents......Page 66
2.5 Summary, Bibliographical and Historical Notes, Exercises......Page 79
3.1 Problem-Solving Agents......Page 84
3.2 Example Problems......Page 89
3.3 Searching for Solutions......Page 95
3.4 Uninformed Search Strategies......Page 101
3.5 Informed (Heuristic) Search Strategies......Page 112
3.6 Heuristic Functions......Page 122
3.7 Summary, Bibliographical and Historical Notes, Exercises......Page 128
4.1 Local Search Algorithms and Optimization Problems......Page 140
4.2 Local Search in Continuous Spaces......Page 149
4.3 Searching with Nondeterministic Actions......Page 153
4.4 Searching with Partial Observations......Page 158
4.5 Online Search Agents and Unknown Environments......Page 167
4.6 Summary, Bibliographical and Historical Notes, Exercises......Page 173
5.1 Games......Page 181
5.2 Optimal Decisions in Games......Page 183
5.3 Alpha–Beta Pruning......Page 187
5.4 Imperfect Real-Time Decisions......Page 191
5.5 Stochastic Games......Page 197
5.6 Partially Observable Games......Page 200
5.7 State-of-the-Art Game Programs......Page 205
5.8 Alternative Approaches......Page 207
5.9 Summary, Bibliographical and Historical Notes, Exercises......Page 209
6.1 Defining Constraint Satisfaction Problems......Page 222
6.2 Constraint Propagation: Inference in CSPs......Page 228
6.3 Backtracking Search for CSPs......Page 234
6.4 Local Search for CSPs......Page 240
6.5 The Structure of Problems......Page 242
6.6 Summary, Bibliographical and Historical Notes, Exercises......Page 247
7 Logical Agents......Page 254
7.1 Knowledge-Based Agents......Page 255
7.2 The Wumpus World......Page 256
7.3 Logic......Page 260
7.4 Propositional Logic: A Very Simple Logic......Page 263
7.5 Propositional Theorem Proving......Page 269
7.6 Effective Propositional Model Checking......Page 279
7.7 Agents Based on Propositional Logic......Page 285
7.8 Summary, Bibliographical and Historical Notes, Exercises......Page 294
8.1 Representation Revisited......Page 305
8.2 Syntax and Semantics of First-Order Logic......Page 310
8.3 Using First-Order Logic......Page 320
8.4 Knowledge Engineering in First-Order Logic......Page 327
8.5 Summary, Bibliographical and Historical Notes, Exercises......Page 333
9.1 Propositional vs. First-Order Inference......Page 342
9.2 Unification and Lifting......Page 345
9.3 Forward Chaining......Page 350
9.4 Backward Chaining......Page 357
9.5 Resolution......Page 365
9.6 Summary, Bibliographical and Historical Notes, Exercises......Page 377
10.1 Definition of Classical Planning......Page 386
10.2 Algorithms for Planning as State-Space Search......Page 393
10.3 Planning Graphs......Page 399
10.4 Other Classical Planning Approaches......Page 407
10.5 Analysis of Planning Approaches......Page 412
10.6 Summary, Bibliographical and Historical Notes, Exercises......Page 413
11.1 Time, Schedules, and Resources......Page 421
11.2 Hierarchical Planning......Page 426
11.3 Planning and Acting in Nondeterministic Domains......Page 435
11.4 Multiagent Planning......Page 445
11.5 Summary, Bibliographical and Historical Notes, Exercises......Page 450
12.1 Ontological Engineering......Page 457
12.2 Categories and Objects......Page 460
12.3 Events......Page 466
12.4 Mental Events and Mental Objects......Page 470
12.5 Reasoning Systems for Categories......Page 473
12.6 Reasoning with Default Information......Page 478
12.7 The Internet Shopping World......Page 482
12.8 Summary, Bibliographical and Historical Notes, Exercises......Page 487
13.1 Acting under Uncertainty......Page 500
13.2 Basic Probability Notation......Page 503
13.3 Inference Using Full Joint Distributions......Page 510
13.4 Independence......Page 514
13.5 Bayes’ Rule and Its Use......Page 515
13.6 The Wumpus World Revisited......Page 519
13.7 Summary, Bibliographical and Historical Notes, Exercises......Page 523
14.1 Representing Knowledge in an Uncertain Domain......Page 530
14.2 The Semantics of Bayesian Networks......Page 533
14.3 Efficient Representation of Conditional Distributions......Page 538
14.4 Exact Inference in Bayesian Networks......Page 542
14.5 Approximate Inference in Bayesian Networks......Page 550
14.6 Relational and First-Order Probability Models......Page 559
14.7 Other Approaches to Uncertain Reasoning......Page 566
14.8 Summary, Bibliographical and Historical Notes, Exercises......Page 571
15.1 Time and Uncertainty......Page 586
15.2 Inference in Temporal Models......Page 590
15.3 Hidden Markov Models......Page 598
15.4 Kalman Filters......Page 604
15.5 Dynamic Bayesian Networks......Page 610
15.6 Keeping Track of Many Objects......Page 619
15.7 Summary, Bibliographical and Historical Notes, Exercises......Page 623
16.1 Combining Beliefs and Desires under Uncertainty......Page 630
16.2 The Basis of Utility Theory......Page 631
16.3 Utility Functions......Page 635
16.4 Multiattribute Utility Functions......Page 642
16.5 Decision Networks......Page 646
16.6 The Value of Information......Page 648
16.7 Decision-Theoretic Expert Systems......Page 653
16.8 Summary, Bibliographical and Historical Notes, Exercises......Page 656
17.1 Sequential Decision Problems......Page 665
17.2 Value Iteration......Page 672
17.3 Policy Iteration......Page 676
17.4 Partially Observable MDPs......Page 678
17.5 Decisions with Multiple Agents: Game Theory......Page 686
17.6 Mechanism Design......Page 699
17.7 Summary, Bibliographical and Historical Notes, Exercises......Page 704
18.1 Forms of Learning......Page 713
18.2 Supervised Learning......Page 715
18.3 Learning Decision Trees......Page 717
18.4 Evaluating and Choosing the Best Hypothesis......Page 728
18.5 The Theory of Learning......Page 733
18.6 Regression and Classification with Linear Models......Page 737
18.7 Artificial Neural Networks......Page 747
18.8 Nonparametric Models......Page 757
18.9 Support Vector Machines......Page 764
18.10 Ensemble Learning......Page 768
18.11 Practical Machine Learning......Page 773
18.12 Summary, Bibliographical and Historical Notes, Exercises......Page 777
19.1 A Logical Formulation of Learning......Page 788
19.2 Knowledge in Learning......Page 797
19.3 Explanation-Based Learning......Page 800
19.4 Learning Using Relevance Information......Page 804
19.5 Inductive Logic Programming......Page 808
19.6 Summary, Bibliographical and Historical Notes, Exercises......Page 817
20.1 Statistical Learning......Page 822
20.2 Learning with Complete Data......Page 826
20.3 Learning with Hidden Variables: The EM Algorithm......Page 836
20.4 Summary, Bibliographical and Historical Notes, Exercises......Page 845
21.1 Introduction......Page 850
21.2 Passive Reinforcement Learning......Page 852
21.3 Active Reinforcement Learning......Page 859
21.4 Generalization in Reinforcement Learning......Page 865
21.5 Policy Search......Page 868
21.6 Applications of Reinforcement Learning......Page 870
21.7 Summary, Bibliographical and Historical Notes, Exercises......Page 873
22.1 Language Models......Page 880
22.2 Text Classification......Page 885
22.3 Information Retrieval......Page 887
22.4 Information Extraction......Page 893
22.5 Summary, Bibliographical and Historical Notes, Exercises......Page 902
23.1 Phrase Structure Grammars......Page 908
23.2 Syntactic Analysis (Parsing)......Page 912
23.3 Augmented Grammars and Semantic Interpretation......Page 917
23.4 Machine Translation......Page 927
23.5 Speech Recognition......Page 932
23.6 Summary, Bibliographical and Historical Notes, Exercises......Page 938
24 Perception......Page 948
24.1 Image Formation......Page 949
24.2 Early Image-Processing Operations......Page 955
24.3 Object Recognition by Appearance......Page 962
24.4 Reconstructing the 3D World......Page 967
24.5 Object Recognition from Structural Information......Page 977
24.6 Using Vision......Page 981
24.7 Summary, Bibliographical and Historical Notes, Exercises......Page 985
25.1 Introduction......Page 991
25.2 Robot Hardware......Page 993
25.3 Robotic Perception......Page 998
25.4 Planning to Move......Page 1006
25.5 Planning Uncertain Movements......Page 1013
25.6 Moving......Page 1017
25.7 Robotic Software Architectures......Page 1023
25.8 Application Domains......Page 1026
25.9 Summary, Bibliographical and Historical Notes, Exercises......Page 1030
26.1 Weak AI: Can Machines Act Intelligently?......Page 1040
26.2 Strong AI: Can Machines Really Think?......Page 1046
26.3 The Ethics and Risks of Developing Artificial Intelligence......Page 1054
26.4 Summary, Bibliographical and Historical Notes, Exercises......Page 1060
27.1 Agent Components......Page 1064
27.2 Agent Architectures......Page 1067
27.3 Are We Going in the Right Direction?......Page 1069
27.4 What If AI Does Succeed?......Page 1071
A.1 Complexity Analysis and O() Notation......Page 1073
A.2 Vectors, Matrices, and Linear Algebra......Page 1075
A.3 Probability Distributions......Page 1077
B.1 Defining Languages with Backus–Naur Form (BNF)......Page 1080
B.2 Describing Algorithms with Pseudocode......Page 1081
B.3 Online Help......Page 1082
Bibliography......Page 1083