Artificial intelligence: A new synthesis Nils J. Nilsson

Includes bibliography and index

Introduction
1.1 What Is AI?
1.2 Approaches to Artificial lntelligence
1.5 Brief History of AI
1.4 Plan of the Book
1.5 Additional Readings and Discussion
I Reactive Machines
Stimulus-Response Agents
2.1 Perception and Action
2.1.1 Perception
2.1.2 Action
2.1.3 Boolean Algebra
2.1.4 Classes and Forms of Boolean Functions
2.2 Representing and Implementing Action Functions 27
2.2.1 Production Systems 27
2.2.2 Networks 29
2.2.5 The Subsumption Architecture 32
2.5 Additional Readings and Discussion 33
Neural Networks 57
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 Widrow-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 3.4 Generalization, Accuracy, and Overfitting 51
3.5 Additional Readings and Discussion 54
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
4.2.3 Evolving a Wall-Following Robot 65
4.5 Additional Readings and Discussion 69
State Machines
5.1 Representing the Environment by Feature Vectors 71
5.2 Elman Networks
5.5 Iconic Representations 74
5.4 Blackboard Systems 77
5.5 Additional Readings and Discussion
6.1 Introduction
6.2 Steering an Automobile
6.5 Two Stages of Robot Vision
6.4 Image Processing
6.4.1 Averaging
6.4.2 Edge Enhancement
6.4.3 Combining Edge Enhancement with Averaging
6.4.4 Region Finding
6.4.5 Using Image Attributes Other Than Intensity 101
6.5 Scene Analysis
6.5.1 Interpreting Lines and Curves in the Image
6.5.2 Model-Based Vision
6.6 Stereo Vision and Depth Information 108
6.7 Additional Readings and Discussion HO
II Search in State Spaces 115
7 Agents That Plan 117
7.1 Memory Versus Computation 117
1.1 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
8 Uninformed Search 129
8.1 Formulating the State Space 129
8.2 Components of Implicit State-Space Graphs 150
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
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*
9.2.5 Recursive Best-First Search 154
9.3 Heuristic Functions and Search Efficiency 155
9.4 Additional Readings and Discussion 160
Planning, Acting, and Learning 165
10.1 The Sense/Plan/Act Cycle 165
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
10.2.5 Building Reactive Procedures 170
10.3 Learning Heuristic Functions 172
10.3.1 Explicit Graphs 172
10.3.2 Implicit Graphs 175
10.4 Rewards Instead of Goals 175
10.5 Additional Readings and Discussion 177
Alternative Search Formulations and
Applications
11.1 Assignment Problems 181
11.2 Constructive Methods 185
11.3 Heuristic Repair 187
11.4 Function Optimization 189
Adversarial Search 195
12.1 Two-Agent Games 195
12.2 The Minimax Procedure 197
12.5 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
Ill Knowledge Representation and
Reasoning 215
The Propositional Calculus 217
13.1 Using Constraints on Feature Values 217
15.2 The Language 219
15.5 Rules of Inference 220
15.4 Definition of Proof 221
15.5 Semantics 222
15.5.1 Interpretations 222
13.5.2 The Propositional Truth Table 225
13.5.3 Satisfiability and Models 224
13.5.4 Validity 224
13.5.5 Equivalence 225
13.5.6 Entailment 225
15.6 Soundness and Completeness 226
15.7 The PSAT Problem 227
15.8 Other Important Topics 228
13.8.1 Language Distinctions 228
13.8.2 Metatheorems 22H
13.8.3 Associative Laws 22*^
13.8.4 Distributive Laws
15.1 Motivation
15.2 The Language and Its Syntax
15.5 Semantics
15.5.4 Knowledge
15.4 Quantification
15.5 Semantics of Quantifiers
Resolution in the Propositional Calculus 231
14.1 A New Rule of Inference: Resolution 231
14.1.1 Clauses as wlfs
14.1.2 Resolution on Clauses
14.1.3 Soundness of Resolution
14.2 Converting Arbitrary wffs to Conjunctions of Clauses
14.5 Resolution Refutations
14.4 Resolution Refutation Search Strategies
14.4.1 Ordering Strategies
14.4.2 Refinement Strategies
14.5 Horn Clauses
15.3 The Predicate Calculus 259
15.3.1 Worlds
15.3.2 Interpretations
15.3.3 Models and Related Notions 243
15.5.1 Universal Quantifiers 246
15.5.2 Existential Quantifiers 247
15.5.3 Useful Equivalences
15.5.4 Rules of Inference
15.6 Predicate Calculus as a Language for Representing
Knowledge 248
15.6.1 Conceptualizations
15.6.2 Examples 248
15.7 Additional Readings and Discussion 250
Resolution in the Predicate Calculus 255
16.1 Unification 255
16.2 Predicate-Calculus Resolution 256
16.5 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
Knowledge-Based Systems 269
Confronting the Real World 269
Reasoning Using Horn Clauses 270
Maintenance in Dynamic Knowledge Bases 275
17.4 Rule-Based Expert Systems 280
17.5 Rule Learning 286
17.5.1 Learning Prepositional 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
Representing Commonsense Knowledge
18.1 The Commonsense World
18.1.1 What Is Commonsense Knowledge?
18.1.2 Difficulties in Representing Commonsense Knowledge
18.1.3 The Importance of Commonsense Knowledge
18.1.4 Research Areas
18.2 Time
18.3 Knowledge Representation by Networks
18.5.1 Taxonomic Knowledge
18.3.2 Semantic Networks
18.3.3 Nonmonotonic Reasoning in Semantic Networks 309
18.3.4 Frames
18.4 Additional Readings and Discussion
Reasoning with Uncertain Information 517
19.1 Review of Probability Theory
19.1.1 Fundamental Ideas
19.1.2 Conditional Probabilities
19.2 Probabilistic Inference
19.2.1 A General Method
19.2.2 Conditional Independence
19.5 Bayes Networks
19.4 Patterns of Inference in Bayes Networks
19.5 Uncertain Evidence
19.6 D-Separation
19.7 Probabilistic Inference in Polytrees 532
19.7.1 Evidence Above
19.7.2 Evidence Below
19.7.3 Evidence Above and Below 336
19.7.4 A Numerical Example 336
19.8 Additional Readings and Discussion 358
Learning and Acting with Bayes Nets 345
20.1 Learning Bayes Nets 343
20.1.1 Known Network Structure 343
20.1.2 Learning Network Structure 346
20.2 Probabilistic Inference and Action 351
20.2.1 The General Setting 351
20.2.2 An Extended Example 552
20.2.5 Generalizing the Example 556
20.5 Additional Readings and Discussion 358
IV Planning Methods Based on
Logic 361
The Situation Calculus 363
21.1 Reasoning about States and Actions 563
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 570
Planning 575
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
V Communication and Integration 405
Multiple Agents 407
25.1 Interacting Agents 407
25.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
25.5 A Modal Logic of Knowledge 412
23.3.1 Modal Operators 412
23.3.2 Knowledge Axioms 413
25.5.3 Reasoning about Other Agents'Knowledge 415
25.5.4 Predicting Actions of Other Agents 417
23.4 Additional Readings and Discussion 417
Communication among Agents 421
24.1 Speech Acts 421
24.1.1 Planning Speech Acts 425
24.1.2 Implementing Speech Acts 425
24.2 Understanding Language Strings 425
24.2.1 Phrase-Structure Grammars 425
24.2.2 Semantic Analysis 428
24.2.5 Expanding the Grammar 452
24.3 Efficient Communication 435
24.5.1 Use of Context 455
24.5.2 Use of Knowledge to Resolve Ambiguities 456
24.4 Natural Language Processing 437
24.5 Additional Readings and Discussion 440
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