Artificial Intelligence: A Modern Approach
Table of Contents for AI: A Modern Approach
Part I: Artificial Intelligence
1. Introduction ... 1
1.1. What is AI? ... 1
Acting humanly: The Turing Test approach ... 2
Thinking humanly: The cognitive modeling approach ... 3
Thinking rationally: The ``laws of thought'' approach ... 4
Acting rationally: The rational agent approach ... 4
1.2. The Foundations of Artificial Intelligence ... 5
Philosophy (428 B.C.-present) ... 5
Mathematics (B.C. 800-present) ... 7
Economics (1776-present) ... 9
Neuroscience (1861-present) ... 10
Psychology (1879-present) ... 12
Computer engineering (1940-present) ... 14
Control theory and Cybernetics (1948-present) ... 15
Linguistics (1957-present) ... 16
1.3. The History of Artificial Intelligence ... 16
The gestation of artificial intelligence (1943-1955) ... 16
The birth of artificial intelligence (1956) ... 17
Early enthusiasm, great expectations (1952-1969) ... 18
A dose of reality (1966-1973) ... 21
Knowledge-based systems: The key to power? (1969-1979) ... 22
AI becomes an industry (1980-present) ... 24
The return of neural networks (1986-present) ... 25
AI becomes a science (1987-present) ... 25
The emergence of intelligent agents (1995-present) ... 27
1.4. The State of the Art ... 27
1.5. Summary ... 28
Bibliographical and Historical Notes. ... 29
Exercises. ... 30
2. Intelligent Agents ... 32
2.1. Agents and Environments ... 32
2.2. Good Behavior: The Concept of Rationality ... 34
Performance measures ... 35
Rationality ... 35
Omniscience, learning, and autonomy ... 36
2.3. The Nature of Environments ... 38
Specifying the task environment ... 38
Properties of task environments ... 40
2.4. The Structure of Agents ... 44
Agent programs ... 44
Simple reflex agents ... 46
Model-based reflex agents ... 48
Goal-based agents ... 49
Utility-based agents ... 51
Learning agents ... 51
2.5. Summary ... 54
Bibliographical and Historical Notes. ... 55
Exercises. ... 56
Part II: Problem-solving
3. Solving Problems by Searching ... 59
3.1. Problem-Solving Agents ... 59
Well-defined problems and solutions ... 62
Formulating problems ... 62
3.2. Example Problems ... 64
Toy problems ... 64
Real-world problems ... 67
3.3. Searching for Solutions ... 69
Measuring problem-solving performance ... 71
3.4. Uninformed Search Strategies ... 73
Breadth-first search ... 73
Uniform-cost search ... 75
Depth-first search ... 75
Depth-limited search ... 77
Iterative deepening depth-first search ... 78
Bidirectional search ... 79
Comparing uninformed search strategies ... 81
3.5. Avoiding Repeated States ... 81
3.6. Searching with Partial Information ... 83
Sensorless problems ... 84
Contingency problems ... 86
3.7. Summary ... 87
Bibliographical and Historical Notes. ... 88
Exercises. ... 89
4. Informed Search and Exploration ... 94
4.1. Informed (Heuristic) Search Strategies ... 94
Greedy best-first search ... 95
A* search: Minimizing the total estimated solution cost ... 97
Memory-bounded heuristic search ... 101
Learning to search better ... 104
4.2. Heuristic Functions ... 105
The effect of heuristic accuracy on performance ... 106
Inventing admissible heuristic functions ... 107
Learning heuristics from experience ... 109
4.3. Local Search Algorithms and Optimization Problems ... 110
Hill-climbing search ... 111
Simulated annealing search ... 115
Local beam search ... 115
Genetic algorithms ... 116
4.4. Local Search in Continuous Spaces ... 119
4.5. Online Search Agents and Unknown Environments ... 122
Online search problems ... 123
Online search agents ... 125
Online local search ... 126
Learning in online search ... 127
4.6. Summary ... 129
Bibliographical and Historical Notes. ... 130
Exercises. ... 134
5. Constraint Satisfaction Problems ... 137
5.1. Constraint Satisfaction Problems ... 137
5.2. Backtracking Search for CSPs ... 141
Variable and value ordering ... 143
Propagating information through constraints ... 144
Forward checking ... 144
Constraint propagation ... 145
Handling special constraints ... 147
Intelligent backtracking: looking backward ... 148
5.3. Local Search for Constraint Satisfaction Problems ... 150
5.4. The Structure of Problems ... 151
5.5. Summary ... 155
Bibliographical and Historical Notes. ... 156
Exercises. ... 158
6. Adversarial Search ... 161
6.1. Games ... 161
6.2. Optimal Decisions in Games ... 162
Optimal strategies ... 163
The minimax algorithm ... 165
Optimal decisions in multiplayer games ... 165
6.3. Alpha-Beta Pruning ... 167
6.4. Imperfect, Real-Time Decisions ... 171
Evaluation functions ... 171
Cutting off search ... 173
6.5. Games That Include an Element of Chance ... 175
Position evaluation in games with chance nodes ... 177
Complexity of expectiminimax ... 177
Card games ... 179
6.6. State-of-the-Art Game Programs ... 180
6.7. Discussion ... 183
6.8. Summary ... 185
Bibliographical and Historical Notes. ... 186
Exercises. ... 189
Part III: Knowledge and reasoning
7. Logical Agents ... 194
7.1. Knowledge-Based Agents ... 195
7.2. The Wumpus World ... 197
7.3. Logic ... 200
7.4. Propositional Logic: A Very Simple Logic ... 204
Syntax ... 204
Semantics ... 206
A simple knowledge base ... 208
Inference ... 208
Equivalence, validity, and satisfiability ... 210
7.5. Reasoning Patterns in Propositional Logic ... 211
Resolution ... 213
Conjunctive normal form ... 215
A resolution algorithm ... 215
Completeness of resolution ... 217
Forward and backward chaining ... 217
7.6. Effective propositional inference ... 220
A complete backtracking algorithm ... 221
Local-search algorithms ... 222
Hard satisfiability problems ... 224
7.7. Agents Based on Propositional Logic ... 225
Finding pits and wumpuses using logical inference ... 225
Keeping track of location and orientation ... 227
Circuit-based agents ... 227
A comparison ... 231
7.8. Summary ... 232
Bibliographical and Historical Notes. ... 233
Exercises. ... 236
8. First-Order Logic ... 240
8.1. Representation Revisited ... 240
8.2. Syntax and Semantics of First-Order Logic ... 245
Models for first-order logic ... 245
Symbols and interpretations ... 246
Terms ... 248
Atomic sentences ... 248
Complex sentences ... 249
Quantifiers ... 249
Universal quantification ... 249
Existential quantification ... 250
Nested quantifiers ... 251
Connections between Forall and Exists ... 252
Equality ... 253
8.3. Using First-Order Logic ... 253
Assertions and queries in first-order logic ... 253
The kinship domain ... 254
Numbers, sets, and lists ... 256
The wumpus world ... 258
8.4. Knowledge Engineering in First-Order Logic ... 260
The knowledge engineering process ... 261
The electronic circuits domain ... 262
Identify the task ... 262
Assemble the relevant knowledge ... 263
Decide on a vocabulary ... 263
Encode general knowledge of the domain ... 264
Encode the specific problem instance ... 265
Pose queries to the inference procedure ... 265
Debug the knowledge base ... 266
8.5. Summary ... 266
Bibliographical and Historical Notes. ... 267
Exercises. ... 268
9. Inference in First-Order Logic ... 272
9.1. Propositional vs. First-Order Inference ... 272
Inference rules for quantifiers ... 273
Reduction to propositional inference ... 274
9.2. Unification and Lifting ... 275
A first-order inference rule ... 275
Unification ... 276
Storage and retrieval ... 278
9.3. Forward Chaining ... 280
First-order definite clauses ... 280
A simple forward-chaining algorithm ... 281
Efficient forward chaining ... 283
Matching rules against known facts ... 283
Incremental forward chaining ... 285
Irrelevant facts ... 286
9.4. Backward Chaining ... 287
A backward chaining algorithm ... 287
Logic programming ... 289
Efficient implementation of logic programs ... 290
Redundant inference and infinite loops ... 292
Constraint logic programming ... 294
9.5. Resolution ... 295
Conjunctive normal form for first-order logic ... 295
The resolution inference rule ... 297
Example proofs ... 297
Completeness of resolution ... 300
Dealing with equality ... 303
Resolution strategies ... 304
Unit preference ... 305
Set of support ... 305
Input resolution ... 305
Subsumption ... 306
Theorem provers ... 306
Design of a theorem prover ... 306
Extending Prolog ... 307
Theorem provers as assistants ... 308
Practical uses of theorem provers ... 309
9.6. Summary ... 310
Bibliographical and Historical Notes. ... 310
Exercises. ... 315
10. Knowledge Representation ... 320
10.1. Ontological Engineering ... 320
10.2. Categories and Objects ... 322
Physical composition ... 324
Measurements ... 325
Substances and objects ... 327
10.3. Actions, Situations, and Events ... 328
The ontology of situation calculus ... 329
Describing actions in situation calculus ... 330
Solving the representational frame problem ... 332
Solving the inferential frame problem ... 333
Time and event calculus ... 334
Generalized events ... 335
Processes ... 337
Intervals ... 338
Fluents and objects ... 339
10.4. Mental Events and Mental Objects ... 341
A formal theory of beliefs ... 341
Knowledge and belief ... 343
Knowledge, time, and action ... 344
10.5. The Internet Shopping World ... 344
Comparing offers ... 348
10.6. Reasoning Systems for Categories ... 349
Semantic networks ... 350
Description logics ... 353
10.7. Reasoning with Default Information ... 354
Open and closed worlds ... 354
Negation as failure and stable model semantics ... 356
Circumscription and default logic ... 358
10.8. Truth Maintenance Systems ... 360
10.9. Summary ... 362
Bibliographical and Historical Notes. ... 363
Exercises. ... 369
Part IV: Planning
11. Planning ... 375
11.1. The Planning Problem ... 375
The language of planning problems ... 377
Expressiveness and extensions ... 378
Example: Air cargo transport ... 380
Example: The spare tire problem ... 381
Example: The blocks world ... 381
11.2. Planning with State-Space Search ... 382
Forward state-space search ... 382
Backward state-space search ... 384
Heuristics for state-space search ... 386
11.3. Partial-Order Planning ... 387
A partial-order planning example ... 391
Partial-order planning with unbound variables ... 393
Heuristics for partial-order planning ... 394
11.4. Planning Graphs ... 395
Planning graphs for heuristic estimation ... 397
The Graphplan algorithm ... 398
Termination of Graphplan ... 401
11.5. Planning with Propositional Logic ... 402
Describing planning problems in propositional logic ... 402
Complexity of propositional encodings ... 405
11.6. Analysis of Planning Approaches ... 407
11.7. Summary ... 408
Bibliographical and Historical Notes. ... 409
Exercises. ... 412
12. Planning and Acting in the Real World ... 417
12.1. Time, Schedules, and Resources ... 417
Scheduling with resource constraints ... 420
12.2. Hierarchical Task Network Planning ... 422
Representing action decompositions ... 423
Modifying the planner for decompositions ... 425
Discussion ... 427
12.3. Planning and Acting in Nondeterministic Domains ... 430
12.4. Conditional Planning ... 433
Conditional planning in fully observable environments ... 433
Conditional planning in partially observable environments ... 437
12.5. Execution Monitoring and Replanning ... 441
12.6. Continuous Planning ... 445
12.7. MultiAgent Planning ... 449
Cooperation: Joint goals and plans ... 450
Multibody planning ... 451
Coordination mechanisms ... 452
Competition ... 454
12.8. Summary ... 454
Bibliographical and Historical Notes. ... 455
Exercises. ... 459
Part V: Uncertain knowledge and reasoning
13. Uncertainty ... 462
13.1. Acting under Uncertainty ... 462
Handling uncertain knowledge ... 463
Uncertainty and rational decisions ... 465
Design for a decision-theoretic agent ... 466
13.2. Basic Probability Notation ... 466
Propositions ... 467
Atomic events ... 468
Prior probability ... 468
Conditional probability ... 470
13.3. The Axioms of Probability ... 471
Using the axioms of probability ... 473
Why the axioms of probability are reasonable ... 473
13.4. Inference Using Full Joint Distributions ... 475
13.5. Independence ... 477
13.6. Bayes' Rule and Its Use ... 479
Applying Bayes' rule: The simple case ... 480
Using Bayes' rule: Combining evidence ... 481
13.7. The Wumpus World Revisited ... 483
13.8. Summary ... 486
Bibliographical and Historical Notes. ... 487
Exercises. ... 489
14. Probabilistic Reasoning ... 492
14.1. Representing Knowledge in an Uncertain Domain ... 492
14.2. The Semantics of Bayesian Networks ... 495
Representing the full joint distribution ... 495
A method for constructing Bayesian networks ... 496
Compactness and node ordering ... 496
Conditional independence relations in Bayesian networks ... 499
14.3. Efficient Representation of Conditional Distributions ... 500
Bayesian nets with continuous variables ... 501
14.4. Exact Inference in Bayesian Networks ... 504
Inference by enumeration ... 504
The variable elimination algorithm ... 507
The complexity of exact inference ... 509
Clustering algorithms ... 510
14.5. Approximate Inference in Bayesian Networks ... 511
Direct sampling methods ... 511
Rejection sampling in Bayesian networks ... 512
Likelihood weighting ... 514
Inference by Markov chain simulation ... 516
The MCMC algorithm ... 516
Why MCMC works ... 517
14.6. Extending Probability to First-Order Representations ... 519
14.7. Other Approaches to Uncertain Reasoning ... 523
Rule-based methods for uncertain reasoning ... 524
Representing ignorance: Dempster-Shafer theory ... 525
Representing vagueness: Fuzzy sets and fuzzy logic ... 526
14.8. Summary ... 528
Bibliographical and Historical Notes. ... 528
Exercises. ... 533
15. Probabilistic Reasoning over Time ... 537
15.1. Time and Uncertainty ... 537
States and observations ... 538
Stationary processes and the Markov assumption ... 538
15.2. Inference in Temporal Models ... 541
Filtering and prediction ... 542
Smoothing ... 544
Finding the most likely sequence ... 547
15.3. Hidden Markov Models ... 549
Simplified matrix algorithms ... 549
15.4. Kalman Filters ... 551
Updating Gaussian distributions ... 553
A simple one-dimensional example ... 554
The general case ... 556
Applicability of Kalman filtering ... 557
15.5. Dynamic Bayesian Networks ... 559
Constructing DBNs ... 560
Exact inference in DBNs ... 563
Approximate inference in DBNs ... 565
15.6. Speech Recognition ... 568
Speech sounds ... 570
Words ... 572
Sentences ... 574
Building a speech recognizer ... 576
15.7. Summary ... 578
Bibliographical and Historical Notes. ... 578
Exercises. ... 581
16. Making Simple Decisions ... 584
16.1. Combining Beliefs and Desires under Uncertainty ... 584
16.2. The Basis of Utility Theory ... 586
Constraints on rational preferences ... 586
And then there was Utility ... 588
16.3. Utility Functions ... 589
The utility of money ... 589
Utility scales and utility assessment ... 591
16.4. Multiattribute Utility Functions ... 593
Dominance ... 594
Preference structure and multiattribute utility ... 596
Preferences without uncertainty ... 596
Preferences with uncertainty ... 597
16.5. Decision Networks ... 597
Representing a decision problem with a decision network ... 598
Evaluating decision networks ... 599
16.6. The Value of Information ... 600
A simple example ... 600
A general formula ... 601
Properties of the value of information ... 602
Implementing an information-gathering agent ... 603
16.7. Decision-Theoretic Expert Systems ... 604
16.8. Summary ... 607
Bibliographical and Historical Notes. ... 607
Exercises. ... 609
17. Making Complex Decisions ... 613
17.1. Sequential Decision Problems ... 613
An example ... 613
Optimality in sequential decision problems ... 616
17.2. Value Iteration ... 618
Utilities of states ... 619
The value iteration algorithm ... 620
Convergence of value iteration ... 620
17.3. Policy Iteration ... 624
17.4. Partially observable MDPs ... 625
17.5. Decision-Theoretic Agents ... 629
17.6. Decisions with Multiple Agents: Game Theory ... 631
17.7. Mechanism Design ... 640
17.8. Summary ... 643
Bibliographical and Historical Notes. ... 644
Exercises. ... 646
Part VI: Learning
18. Learning from Observations ... 649
18.1. Forms of Learning ... 649
18.2. Inductive Learning ... 651
18.3. Learning Decision Trees ... 653
Decision trees as performance elements ... 653
Expressiveness of decision trees ... 655
Inducing decision trees from examples ... 655
Choosing attribute tests ... 659
Assessing the performance of the learning algorithm ... 660
Noise and overfitting ... 661
Broadening the applicability of decision trees ... 663
18.4. Ensemble Learning ... 664
18.5. Why Learning Works: Computational Learning Theory ... 668
How many examples are needed? ... 669
Learning decision lists ... 670
Discussion ... 672
18.6. Summary ... 673
Bibliographical and Historical Notes. ... 674
Exercises. ... 676
19. Knowledge in Learning ... 678
19.1. A Logical Formulation of Learning ... 678
Examples and hypotheses ... 678
Current-best-hypothesis search ... 680
Least-commitment search ... 683
19.2. Knowledge in Learning ... 686
Some simple examples ... 687
Some general schemes ... 688
19.3. Explanation-Based Learning ... 690
Extracting general rules from examples ... 691
Improving efficiency ... 693
19.4. Learning Using Relevance Information ... 694
Determining the hypothesis space ... 695
Learning and using relevance information ... 695
19.5. Inductive Logic Programming ... 697
An example ... 699
Top-down inductive learning methods ... 701
Inductive learning with inverse deduction ... 703
Making discoveries with inductive logic programming ... 705
19.6. Summary ... 707
Bibliographical and Historical Notes. ... 708
Exercises. ... 710
20. Statistical Learning Methods ... 712
20.1. Statistical Learning ... 712
20.2. Learning with Complete Data ... 716
Maximum-likelihood parameter learning: Discrete models ... 716
Naive Bayes models ... 718
Maximum-likelihood parameter learning: Continuous models ... 719
Bayesian parameter learning ... 720
Learning Bayes net structures ... 722
20.3. Learning with Hidden Variables: The EM Algorithm ... 724
Unsupervised clustering: Learning mixtures of Gaussians ... 725
Learning Bayesian networks with hidden variables ... 727
Learning hidden Markov models ... 731
The general form of the EM algorithm ... 731
Learning Bayes net structures with hidden variables ... 732
20.4. Instance-Based Learning ... 733
Nearest-neighbor models ... 733
Kernel models ... 735
20.5. Neural Networks ... 736
Units in neural networks ... 737
Network structures ... 738
Single layer feed-forward neural networks (perceptrons) ... 740
Multilayer feed-forward neural networks ... 744
Learning neural network structures ... 748
20.6. Kernel Machines ... 749
20.7. Case Study: Handwritten Digit Recognition ... 752
20.8. Summary ... 754
Bibliographical and Historical Notes. ... 755
Exercises. ... 759
21. Reinforcement Learning ... 763
21.1. Introduction ... 763
21.2. Passive Reinforcement Learning ... 765
Direct utility estimation ... 766
Adaptive dynamic programming ... 767
Temporal difference learning ... 767
21.3. Active Reinforcement Learning ... 771
Exploration ... 771
Learning an Action-Value Function ... 775
21.4. Generalization in Reinforcement Learning ... 777
Applications to game-playing ... 780
Application to robot control ... 780
21.5. Policy Search ... 781
21.6. Summary ... 784
Bibliographical and Historical Notes. ... 785
Exercises. ... 788
Part VII: Communicating, perceiving, and acting
22. Communication ... 790
22.1. Communication as Action ... 790
Fundamentals of language ... 791
The component steps of communication ... 792
22.2. A Formal Grammar for a Fragment of English ... 795
The Lexicon of E_0 ... 795
The Grammar of E_0 ... 796
22.3. Syntactic Analysis (Parsing) ... 798
Efficient parsing ... 800
22.4. Augmented Grammars ... 806
Verb subcategorization ... 808
Generative capacity of augmented grammars ... 809
22.5. Semantic Interpretation ... 810
The semantics of an English fragment ... 811
Time and tense ... 812
Quantification ... 813
Pragmatic Interpretation ... 815
Language generation with DCGs ... 817
22.6. Ambiguity and Disambiguation ... 818
Disambiguation ... 820
22.7. Discourse Understanding ... 821
Reference resolution ... 821
The structure of coherent discourse ... 823
22.8. Grammar Induction ... 824
22.9. Summary ... 826
Bibliographical and Historical Notes. ... 827
Exercises. ... 831
23. Probabilistic Language Processing ... 834
23.1. Probabilistic Language Models ... 834
Probabilistic context-free grammars ... 836
Learning probabilities for PCFGs ... 839
Learning rule structure for PCFGs ... 840
23.2. Information Retrieval ... 840
Evaluating IR systems ... 842
IR refinements ... 844
Presentation of result sets ... 845
Implementing IR systems ... 846
23.3. Information Extraction ... 848
23.4. Machine Translation ... 850
Machine translation systems ... 852
Statistical machine translation ... 853
Learning probabilities for machine translation ... 856
23.5. Summary ... 857
Bibliographical and Historical Notes. ... 858
Exercises. ... 861
24. Perception ... 863
24.1. Introduction ... 863
24.2. Image Formation ... 865
Images without lenses: the pinhole camera ... 865
Lens systems ... 866
Light: the photometry of image formation ... 867
Color: the spectrophotometry of image formation ... 868
24.3. Early Image Processing Operations ... 869
Edge detection ... 870
Image segmentation ... 872
24.4. Extracting Three-Dimensional Information ... 873
Motion ... 875
Binocular stereopsis ... 876
Texture gradients ... 879
Shading ... 880
Contour ... 881
24.5. Object Recognition ... 885
Brightness-based recognition ... 887
Feature-based recognition ... 888
Pose Estimation ... 890
24.6. Using Vision for Manipulation and Navigation ... 892
24.7. Summary ... 894
Bibliographical and Historical Notes. ... 895
Exercises. ... 898
25. Robotics ... 901
25.1. Introduction ... 901
25.2. Robot Hardware ... 903
Sensors ... 903
Effectors ... 904
25.3. Robotic Perception ... 907
Localization ... 908
Mapping ... 913
Other types of perception ... 915
25.4. Planning to Move ... 916
Configuration space ... 916
Cell decomposition methods ... 919
Skeletonization methods ... 922
25.5. Planning uncertain movements ... 923
Robust methods ... 924
25.6. Moving ... 926
Dynamics and control ... 927
Potential field control ... 929
Reactive control ... 930
25.7. Robotic Software Architectures ... 932
Subsumption architecture ... 932
Three-layer architecture ... 933
Robotic programming languages ... 934
25.8. Application Domains ... 935
25.9. Summary ... 938
Bibliographical and Historical Notes. ... 939
Exercises. ... 942
Part VIII: Conclusions
26. Philosophical Foundations ... 947
26.1. Weak AI: Can Machines Act Intelligently? ... 947
The argument from disability ... 948
The mathematical objection ... 949
The argument from informality ... 950
26.2. Strong AI: Can Machines Really Think? ... 952
The mind-body problem ... 954
The ``brain in a vat'' experiment ... 955
The brain prosthesis experiment ... 956
The Chinese room ... 958
26.3. The Ethics and Risks of Developing Artificial Intelligence ... 960
26.4. Summary ... 964
Bibliographical and Historical Notes. ... 964
Exercises. ... 967
27. AI: Present and Future ... 968
27.1. Agent Components ... 968
27.2. Agent Architectures ... 970
27.3. Are We Going in the Right Direction? ... 972
27.4. What if AI Does Succeed? ... 974
A. Mathematical background ... 977
A.1. Complexity Analysis and O() Notation ... 977
Asymptotic analysis ... 977
NP and inherently hard problems ... 978
A.2. Vectors, Matrices, and Linear Algebra ... 979
A.3. Probability Distributions ... 981
Bibliographical and Historical Notes. ... 983
B. Notes on Languages and Algorithms ... 984
B.1. Defining Languages with Backus-Naur Form (BNF) ... 984
B.2. Describing Algorithms with Pseudocode ... 985
B.3. Online Help ... 985
Bibliography ... 987
Index ... 1057