Artificial Intelligence: A Modern Approach

Cover......Page 1
Preface......Page 8
About the Authors......Page 12
Summary of Contents......Page 14
Contents......Page 16
1.1 What is AI?......Page 30
1.2 The Foundations of Artificial Intelligence......Page 34
1.3 The History of Artificial Intelligence......Page 45
1.4 The State of the Art......Page 56
1.5 Summary......Page 57
2.1 Agents and Environments......Page 61
2.2 Good Behavior: The Concept of Rationality......Page 63
2.3 The Nature of Environments......Page 67
2.4 The Structure of Agents......Page 73
2.5 Summary......Page 83
3.1 Problem-Solving Agents......Page 88
3.2 Example Problems......Page 93
3.3 Searching for Solutions......Page 98
3.4 Uninformed Search Strategies......Page 102
3.5 Avoiding Repeated States......Page 110
3.6 Searching with Partial Information......Page 112
3.7 Summary......Page 116
4.1 Informed (Heuristic) Search Strategies......Page 123
4.2 Heuristic Functions......Page 134
4.3 Local Search Algorithms and Optimization Problems......Page 139
4.4 Local Search in Continuous Spaces......Page 148
4.5 Online Search Agents and Unknown Environments......Page 151
4.6 Summary......Page 158
5.1 Constraint Satisfaction Problems......Page 166
5.2 Backtracking Search for CSPs......Page 170
5.3 Local Search for Constraint Satisfaction Problems......Page 179
5.4 The Structure of Problems......Page 180
5.5 Summary......Page 184
6.1 Games......Page 190
6.2 Optimal Decisions in Games......Page 191
6.3 Alpha-Beta Pruning......Page 196
6.4 Imperfect, Real-Time Decisions......Page 200
6.5 Games that Include an Element of Chance......Page 204
6.6 State-of-the-Art Game Programs......Page 209
6.7 Discussion......Page 212
6.8 Summary......Page 214
7- Logical Agents......Page 223
7.1 Knowledge-Based Agents......Page 224
7.2 The Wumpus World......Page 226
7.3 Logic......Page 229
7.4 Propositional Logic: A Very Simple Logic......Page 233
7.5 Reasoning Patterns in Propositional Logic......Page 240
7.6 Effective Propositional Inference......Page 249
7.7 Agents Based on Propositional Logic......Page 254
7.8 Summary......Page 261
8.1 Representation Revisited......Page 269
8.2 Syntax and Semantics of First-Order Logic......Page 274
8.3 Using First-Order Logic......Page 282
8.4 Knowledge Engineering in First-Order Logic......Page 289
8.5 Summary......Page 295
9.1 Propositional vs. First-Order Inference......Page 301
9.2 Unification and Lifting......Page 304
9.3 Forward Chaining......Page 309
9.4 Backward Chaining......Page 316
9.5 Resolution......Page 324
9.6 Summary......Page 339
10.1 Ontological Engineering......Page 349
10.2 Categories and Objects......Page 351
10.3 Actions, Situations and Events......Page 357
10.4 Mental Events and Mental Objects......Page 370
10.5 The Internet Shopping World......Page 373
10.6 Reasoning Systems for Categories......Page 378
10.7 Reasoning with Default Information......Page 383
10.8 Truth Maintenance Systems......Page 389
10.9 Summary......Page 391
11.1 The Planning Problem......Page 404
11.2 Planning with State-Space Search......Page 411
11.3 Partial-Order Planning......Page 416
11.4 Planning Graphs......Page 424
11.5 Planning with Propositional Logic......Page 431
11.6 Analysis of Planning Approaches......Page 436
11.7 Summary......Page 437
12.1 Time, Schedules, and Resources......Page 446
12.2 Hierarchical Task Network Planning......Page 451
12.3 Planning and Acting in Nondeterministic Domains......Page 459
12.4 Conditional Planning......Page 462
12.5 Execution Monitoring and Replanning......Page 470
12.6 Continuous Planning......Page 474
12.7 Multiagent Planning......Page 478
12.8 Summary......Page 483
13.1 Planning under Uncertainty......Page 491
13.2 Basic Probability Notation......Page 495
13.3 The Axioms of Probability......Page 500
13.4 Inference Using Full Joint Distributions......Page 504
13.5 Independence......Page 506
13.6 Bayes' Rule and Its Use......Page 508
13.7 The Wumpus World Revisited......Page 512
13.8 Summary......Page 515
14.1 Representing Knowledge in an Uncertain Domain......Page 521
14.2 The Semantics of Bayesian Networks......Page 524
14.3 Efficient Representation of Conditional Distributions......Page 529
14.4 Exact Inference in Bayesian Networks......Page 533
14.5 Approximate Inference in Bayesian Networks......Page 540
14.6 Extending Probability to First-Order Representations......Page 548
14.7 Other Approaches to Uncertain Reasoning......Page 552
14.8 Summary......Page 557
15.1 Time and Uncertainty......Page 566
15.2 Inference in Temporal Models......Page 570
15.3 Hidden Markov Models......Page 578
15.4 Kalman Filters......Page 580
15.5 Dynamic Bayesian Networks......Page 588
15.6 Speech Recognition......Page 597
15.7 Summary......Page 607
16.1 Combining Beliefs and Desires under Uncertainty......Page 613
16.2 The Basis of Utility Theory......Page 615
16.3 Utility Functions......Page 618
16.4 Multiattribute Utility Functions......Page 622
16.5 Decision Networks......Page 626
16.6 The Value of Information......Page 629
16.7 Decision-Theoretic Expert Systems......Page 633
16.8 Summary......Page 636
17.1 Sequential Decision Problems......Page 642
17.2 Value Iteration......Page 647
17.3 Policy Iteration......Page 653
17.4 Partially Observable MDPs......Page 654
17.5 Decision-Theoretic Agents......Page 658
17.6 Decisions with Multiple Agents: Game Theory......Page 660
17.7 Mechanism Design......Page 669
17.8 Summary......Page 672
18.1 Forms of Learning......Page 678
18.2 Inductive Learning......Page 680
18.3 Learning Decision Trees......Page 682
18.4 Ensemble Learning......Page 693
18.5 Why Learning Works: Computational Learning Theory......Page 697
18.6 Summary......Page 702
19.1 A Logical Formulation of Learning......Page 707
19.2 Knowledge in Learning......Page 715
19.3 Explanation-Based Learning......Page 719
19.4 Learning Using Relevance Information......Page 723
19.5 Inductive Logic Programming......Page 726
19.6 Summary......Page 736
20.1 Statistical Learning......Page 741
20.2 Learning with Complete Data......Page 745
20.3 Learning with Hidden Variables: The EM Algorithm......Page 753
20.4 Instance-Based Learning......Page 762
20.5 Neural Networks......Page 765
20.6 Kernel Machines......Page 778
20.7 Case Study: Handwritten Digit Recognition......Page 781
20.8 Summary......Page 783
21.1 Introduction......Page 792
21.2 Passive Reinforcement Learning......Page 794
21.3 Active Reinforcement Learning......Page 800
21.4 Generalization in Reinforcement Learning......Page 806
21.5 Policy Search......Page 810
21.6 Summary......Page 813
22.1 Communication as Action......Page 819
22.2 A Formal Grammar for a Fragment of English......Page 824
22.3 Syntactic Analysis (Parsing)......Page 827
22.4 Augmented Grammars......Page 835
22.5 Semantic Interpretation......Page 839
22.6 Ambiguity and Disambiguation......Page 847
22.7 Discourse Understanding......Page 850
22.8 Grammar Induction......Page 853
22.9 Summary......Page 855
23.1 Probabilistic Language Models......Page 863
23.2 Information Retrieval......Page 869
23.3 Information Extraction......Page 877
23.4 Machine Translation......Page 879
23.5 Summary......Page 886
24.1 Introduction......Page 892
24.2 Image Formation......Page 894
24.3 Early Image Processing Operations......Page 898
24.4 Extracting Three-Dimensional Information......Page 902
24.5 Object Recognition......Page 914
24.6 Using Vision for Manipulation and Navigation......Page 921
24.7 Summary......Page 923
25.1 Introduction......Page 930
25.2 Robot Hardware......Page 932
25.3 Robotic Perception......Page 936
25.4 Planning to Move......Page 945
25.5 Planning Uncertain Movements......Page 952
25.6 Moving......Page 955
25.7 Robotic Software Architectures......Page 961
25.8 Application Domains......Page 964
25.9 Summary......Page 967
26.1 Weak AI: Can Machines Act Intelligently?......Page 976
26.2 Strong AI: Can Machines Really Think?......Page 981
26.3 The Ethics and Risks of Developing Artificial Intelligence......Page 989
26.4 Summary......Page 993
27.1 Agent Components......Page 997
27.2 Agent Architectures......Page 999
27.3 Are We Going in the Right Direction?......Page 1001
27.4 What if AI Does Succeed?......Page 1003
A.1 Complexity Analysis and O() Notation......Page 1006
A.2 Vector, Matrices, and Linear Algebra......Page 1008
A.3 Probability Distributions......Page 1010
B.1 Defining Languages with Backus-Naur Form (BNF)......Page 1013
B.3 Online Help......Page 1014
Bibliography......Page 1016
Index......Page 1074