1 Introduction 1
1．1 What Is AI? 1
1．2 Approaches to Artificial Intelligence 6
1．3 Brief History of AI 8
1．4 Plan of the Book 11
1．5 Additional Readings and Discussion 14
Exercises 17
ⅠReactive Machines 19
2 Stimulus-Response Agents 21
2．1 Perception and Action 21
2．1．1 Perception 24
2．1．2 Action 24
2．1．3 Boolean Algebra 25
2．1．4 Classes and Forms of Boolean Functions 26
2．2 Representing and Implementing Action Functions 27
2．2．1 Production Systems 27
2．2．2 Networks 29
2．2．3 The Subsumption Architecture 32
2．3 Additional Readings and Discussion 33
Exercises 34
3 Neural Networks 37
3．1 Introduction 37
3．2 Training Single TLUs 38
3．2．1 TLU Geometry 38
3．2．2 Augmented Vectors 39
3．2．3 Gradient Descent Methods 39
3．2．4 The Windrow-Hoff Procedure 41
3．2．5 The Generalized Delta procedure 41
3．2．6 The Error-Correction Procedure 43
3．3 Neural Networks 44
3．3．1 Motivation 44
3．3．2 Notation 45
3．3．3 The Backpropagation Method 46
3．3．4 Computing Weight Changes in the Final Layer 48
3．3．5 Computing Changes to the Weights in Intermediate Layers 48
3．4 Generalization ,Accuracy, and Overfitting 51
3．5 Additional Readings and Discussion 54
Exercises 55
4 Machine Evolution 59
4．1 Evolutionary Computation 59
4．2 Genetic Programming 60
4．2．1 Program Representation in GP 60
4．2．2 The GP Process 62
4．2．3 Evolving a Wall-Following Robot 65
4．3 Additional Readings and Discussion 69
Exercises 69
5 State Machines 71
5．1 Representing the Environment by Feature Vectors 71
5．2 Elman Networks 73
5．3 Iconic Representations 74
5．4 Blackboard Systems 77
5．5 Additional Readings and Discussion 80
Exercises 80
6 Robot Vision 85
6．1 Introduction 85
6．2 Steering and Automobile 86
6．3 Two Stages of Robot Vision 88
6．4 Image Processing 91
6．4．1 Averaging 91
6．4．2 Edge Enhancement 93
6．4．3 Combining Edge Enhancement with Averaging 96
6．4．4 Region Finding 97
6．4．5 Using Image Attributes Other Than Intensity 101
6．5 Scene Analysis 102
6．5．1 Interpreting Lines and Curves in the Image 103
6．5．2 Model -Based Vision 106
6．6 Stereo Vision and Depth Information 108
6．7 Additional Readings and Discussion 110
Exercises 111
Ⅱ Search in State Spaces 115
7 Agents That Plan 117
7．1 Memory Versus Computation 117
7．2 State-Space Graphs 118
7．3 Searching Explicit State Spaces 121
7．4 Feature-Based State Spaces 122
7．5 Graph Notation 124
7．6 Additional Readings and Discussion 125
Exercises 126
8 Uninformed Search 129
8．1 Formulating the State Space 129
8．2 Components of Implicit State-Space Graphs 130
8．3 Breadth-First Search 131
8．4 Depth-First or Backtracking Search 133
8．5 Iterative Deepening 135
8．6 Additional Readings and Discussion 136
Exercises 137
9 Heuristic Search 139
9．1 Using Evaluation Functions 139
9．2 A General Graph-Searching Algorithm 141
9．2．1 Algorithm A 142
9．2．2 Admissibility of A 145
9．2．3 The Consistency (or Monotone)Condition 150
9．2．4 Iterative-Deepening A 153
9．2．5 Recursive Best-First Search 154
9．3 Heuristic Functions and Search Efficiency 155
9．4 Additional Readings and Discussion 160
Exercises 160
10 Planning, Acting ,and Learning 163
10．1 The Sense/Plan/Act Cycle 163
10．2 Approximate Search 165
10．2．1 Island-Driven Search 166
10．2．2 Hierarchical Search 167
10．2．3 Limited-Horizon Search 169
10．2．4 Cycles 170
10．2．5 Building Reactive Procedures 170
10．3 Learning Heuristic Functions 172
10．3．1 Explicit Graphs 172
10．3．2 Implicit Graphs 173
10．4 Rewards Instead of Goals 175
10．5 Additional Readings and Discussion 177
Exercises 178
11 Alternative Search Formulations and Applications 181
11．1 Assignment Problems 181
11．2 Constructive Methods 183
11．3 Heuristic Repair 187
11．4 Function Optimization 189
Exercises 192
12 Adversarial Search 195
12．1 Two-Agent Games 195
12．2 The Minimax Procedure 197
12．3 The Alpha-Beta Procedure 202
12．4 The Search Efficiency of the Alpha-Beta Procedure 207
12．5 Other Important Matters 208
12．6 Games of Chance 208
12．7 Learning Evaluation Functions 210
12．8 Additional Readings and Discussion 212
Exercises 213
Ⅲ Knowledge Representation and Reasoning 215
13 The Propositional Calculus 217
13．1 Using Constraints on Feature Values 217
13．2 The Language 219
13．3 Rules of Inference 220
13．4 Definition of Proof 221
13．5 Semantics 222
13．5．1 Interpretations 222
13．5．2 The Propositional Truth Table 223
13．5．3 Satisfiability and Models 224
13．5．4 Validity 224
13．5．5 Equivalence 225
13．5．6 Entailment 225
13．6 Soundness and Completeness 226
13．7 The PSAT Problem 227
13．8 Other Important Topics 228
13．8．1 Language Distinctions 228
13．8．2 Metatheorems 228
13．8．3 Associative Laws 229
13．8．4 Distributive Laws 229
Exercises 229
14 Resolution in the Propositional Calculus 231
14．1 A New Rule of Inference: Resolution 231
14．1．1 Clauses as wffs 231
14．1．2 Resolution on Clauses 231
14．1．3 Soundness of Resolution 232
14．2 Converting Arbitrary wffs to Conjunctions of Clauses 232
14．3 Resolution Refutations 233
14．4 Resolution Refutation Search Strategies 235
14．4．1 Ordering Strategies 235
14．4．2 Refinement Strategies 236
14．5 Horn Clauses 237
Exercises 238
15 The Predicate Calculus 239
15．1 Motivation 239
15．2 The Language and Its Syntax 240
15．3 Semantics 241
15．3．1 Worlds 241
15．3．2 Interpretations 242
15．3．3 Models and Related Notions 243
15．3．4 Knowledge 244
15．4 Quantification 245
15．5 Semantics of Quantifiers 246
15．5．1 Universal Quantifiers 246
15．5．2 Existential Quantifiers 247
15．5．3 Useful Equivalences 247
15．5．4 Rules of Inference 247
15．6 Predicate Calculus as a Language for Representing Knowledge 248
15．6．1 Conceptualizations 248
15．6．2 Examples 248
15．7 Additional Readings and Discussion 250
Exercises 250
16 Resolution in the Predicate Calculus 253
16．1 Unification 253
16．2 Predicate-Calculus Resolution 256
16．3 Completeness and Soundness 257
16．4 Converting Arbitrary wffs to Clause Form 257
16．5 Using Resolution to Prove Theorems 260
16．6 Answer Extraction 261
16．7 The Equality Predicate 262
16．8 Additional Readings and Discussion 265
Exercises 265
17 Knowledge-Based Systems 269
17．1 Confronting the Real World 269
17．2 Reasoning Using Horn Clauses 270
17．3 Maintenance in Dynamic Knowledge Bases 275
17．4 Rule-Based Expert Systems 280
17．5 Rule Learning 286
17．5．1 Learning Propositional Calculus Rules 286
17．5．2 Learning First-Order Logic Rules 291
17．5．3 Explanation-Based Generalization 295
17．6 Additional Readings and Discussion 297
Exercises 298
18 Representing Commonsense Knowledge 301
18．1 The Commonsense World 301
18．1．1 What Is Commonsense Knowledge? 301
18．1．2 Difficulties in Representing Commonsense Knowledge 303
18．1．3 The Importance of Commonsense Knowledge 304
18．1．4 Research Areas 305
18．2 Time 306
18．3 Knowledge Representation by Networks 308
18．3．1 Taxonomic Knowledge 308
18．3．2 Semantic Networks 309
18．3．3 Nonmonotonic Reasoning in Semantic Networks 309
18．3．4 Frames 312
18．4 Additional Readings and Discussion 313
Exercises 314
19 Reasoning with Uncertain Information 317
19．1 Review of Probability Theory 317
19．1．1 Fundamental Jdeas 317
19．1．2 Conditional Probabilities 320
19．2 Probabilistic Inference 323
19．2．1 A General Method 323
19．2．2 Conditional Independence 324
19．3 Bayes Networks 325
19．4 Patterns of Inference in Bayes Networks 328
19．5 Uncertain Evidence 329
19．6 D-Separation 330
19．7 Probabilistic Inference in Polytrees 332
19．7．1 Evidence Above 332
19．7．2 Evidence Below 334
19．7．3 Evidence Above and Below 336
19．7．4 A Namerical Example 336
19．8 Additional Readings and Discussion 338
Exercises 339
20 Learning and Acting with Bayes Nets 343
20．1 Learning Bayes Nets 343
20．1．1 Known Network Structure 343
20．1．2 Learning Networks Structure 346
20．2 Probabilistic Inference and Action 351
20．2．1 The General Setting 351
20．2．2 An Extended Example 352
20．2．3 Generalizing the Example 356
20．3 Additional Readings and Discussion 358
Exercises 358
Ⅳ Planning Methods Based on Logic 361
21 The Situation Caluclus 363
21．1 Reasoning about States and Actions 363
21．2 Some Difficulties 367
21．2．1 Frame Axioms 367
21．2．2 Qualifications 369
21．2．3 Ramifications 369
21．3 Generating Plans 369
21．4 Additional Readings and Discussion 370
Exercises 371
22 Planning 373
22．1 STRIPS Planning Systems 373
22．1．1 Describing States and Goals 373
22．1．2 Forward Search Methods 374
22．1．3 Recursive STRIPS 376
22．1．4 Plans with Run-Time Conditionals 379
22．1．5 The Sussman Anomaly 380
22．1．6 Backward Search Methods 381
22．2 Plan Spaces and Partial-Order Planning 385
22．3 Hierarchical Planning 393
22．3．1 ABSTRIPS 393
22．3．2 Combining Hierarchical and Partial-Order Planning 395
22．4 Learning Plans 396
22．5 Additional Readings and Discussion 398
Exercises 400
ⅤCommunication and Integration 405
23 Multiple Agents 407
23．1 Interacting Agents 407
23．2 Models of Other Agents 408
23．2．1 Varieties of Models 408
23．2．2 Simulation Strategies 410
23．2．3 Simulated Databases 410
23．2．4 The Intentional Stance 411
23．3 A Modal Logic of Knowledge 412
23．3．1 Modal Operators 412
23．3．2 Knowledge Axioms 413
23．3．3 Reasoning about Other Agents Knowledge 415
23．3．4 Predicting Actions of Other Agents 417
23．4 Additional Readings and Discussion 417
Exercises 418
24 Communication among Agents 421
24．1 Speech Acts 421
24．1．1 Planning Speech Acts 423
24．1．2 Implementing Speech Acts 423
24．2 Understanding Language Strings 425
24．2．1 Phrase-Structure Grammars 425
24．2．2 Semantic Analysis 428
24．2．3 Expanding the Grammar 432
24．3 Efficient Communication 435
24．3．1 Use of Context 435
24．3．2 Use of Knowledge to Resolve Ambiguities 436
24．4 Natural Language Processing 437
24．5 Additional Readings and Discussion 440
Exercises 440
25 Agent Architectures 443
25．1 Three-Level Architectures 444
25．2 Goal Arbitration 446
25．3 The Triple-Tower Architecture 448
25．4 Bootstrapping 449
25．5 Additional Readings and Discussion 450
Exercises 450
Bibliography 453
Index 493