Artificial intelligence/ Elaine Rich, Kevin Knight, Shivashankar B Nair

PART I: PROBLEMS AND SEARCH
1. What is Artificial Intelligence?
1.1 The AI Problems 4
1.2 The Underlying Assumption 6
1.3 What is an AI Technique? 7
1.4 The Level of the Model 18
1.5 Criteria for Success 20
1.6 Some General References 21
1.7 One Final Word and Beyond 22
2. Problems, Problem Spaces, and Search
2.1 Defining the Problem as a State Space Search 25
2.2 Production Systems 30
2.3 Problem Characteristics 36
2.4 Production System Characteristics 43
2.5 Issues in the Design of Search Programs 45
2.6 Additional Problems 47
3. Heuristic Search Techniques
3.1 Generate-and-Test 50
3.2 Hill Climbing 52
3.3 Best-first Search 57
3.4 Problem Reduction 64
3.5 Constraint Satisfaction 68
3.6 Means-ends Analysis 72


PART II: KNOWLEDGE REPRESENTATION
4. Knowledge Representation Issues
4.1 Representations and Mappings 79
4.2 Approaches to Knowledge Representation 82
4.3 Issues in Knowledge Representation 86
4.4 The Frame Problem 96
5. Using Predicate Logic
5.1 Representing Simple Facts in Logic 99
5.2 Representing Instance and ISA Relationships 103
5.3 Computable Functions and Predicates 105
5.4 Resolution 208
5.5 Natural Deduction 124
6. Representing Knowledge Using Rules
6.1 Procedural Versus Declarative Knowledge 129
-' 6.2 Logic Programming 132
6.3 Forward Versus Backward Reasoning 134
6.4 Matching 138
6.5 Control Knowledge 142
7. Symbolic Reasoning Under Uncertainty
7.1 Introduction to Nonmonotonic Reasoning 147
7.2 Logics for Nonmonotonic Reasoning 150
7.3 Implementation Issues 157
7.4 Augmenting a Problem-solver 158
7.5 Implementation: Depth-first Search 160
7.6 Implementation: Breadth-first Search 166
8. Statistical Reasoning
3.1 Probability and Bayes' Theorem 172
8.2 Certainty Factors and Rule-based Systems 174
8.3 Bayesian Networks 179
8.4 Dempster-Shafer Theory 181
8.5 Fuzzy Logic 184
9. Weak Slot-and-Filler Structures
9.1 Semantic Nets 188
9.2 Frames 193
10. Strong Slot-and-Filler Structures
10.1 Conceptual Dependency 207
10.2 Scripts 212
10.3 CYC 216
11. Knowledge Representation Summary
11.1 Syntactic-semantic Spectrum of Representation 222
11.2 Logic and Slot-and-filler Structures 224
11.3 Other Representational Techniques 225
11.4 Summary of the Role of Knowledge 227


PART III: ADVANCED TOPICS
12. Game Playing
12.1 Overview 231.
12.2 The Minimax Search Procedure 233
12.3 Adding Alpha-beta Cutoffs 236
12.4 Additional Refinements 240
12.5 Iterative Deepening 242
12.6 References on Specific Games 244
13. Planning
13.1 Overview 247
13.2 An Example Domain: The Blocks World 250.
13.3 Components of a Planning System 250
13.4 Goal Stack Planning 255
13.5 Nonlinear Planning Using Constraint Posting 262
13.6 Hierarchical Planning 268
13.7 Reactive Systems 269
13.8 Other Planning Techniques 269
14. Understanding.
14.1 What is Understanding? 272
14.2 What Makes Understanding Hard? 273
14.3 Understanding as Constraint Satisfaction 278
15. Natural Language Processing
15.1 Introduction 286
15.2 Syntactic Processing 291
15.3 Semantic Analysis 300
15.4 Discourse and Pragmatic Processing 313
15.5 Statistical Natural Language Processing 321
15.6 Spell Checking 325
16. Parallel and Distributed AI
16.1 Psychological Modeling 333
16.2 Parallelism in Reasoning Systems 334
16.3 Distributed Reasoning Systems 336
17. Learning
17.1 What is Learning? 347
17.2 Rote Learning 348
17.3 Learning by Taking Advice 349
17.4 Learning in Problem-solving 351
17.5 Learning from Examples: Induction 355
17.6 Explanation-based Learning 364
17.7 Discovery 367
17.8 Analogy 371
17.9 Formal Learning Theory 372
17.10 Neural Net Learning and Genetic Learning 373
18. Connectionist Models
18.1 Introduction: Hopfield Networks 377
18.2 Learning in Neural Networks 379
18.3 Applications of Neural Networks 396
18.4 Recurrent Networks 399
18.5 Distributed Representations 400
18.6 Connectionist AI and Symbolic AI 403
19. Common Sense
19.1 Qualitative Physics 409
19.2 Common Sense Ontologies 411
19;d Memory Organization 417
19.4 Case-based Reasoning 419
20. Expert Systems
20.1 Representing and Using Domain Knowledge 422
20.2 Expert System Shells 424
20.3 Explanation 425
20.4 Knowledge Acquisition 427
21. Perception and Action
21.1 Real-time Search 433
21.2 Perception 434
21.3 Action 438
21.4 Robot Architectures 441
22. Fuzzy Logic Systems
22.1 Introduction 445
22.2 Crisp Sets 445
22.3 Fuzzy Sets 446
22.4 Some Fuzzy Terminology 446
22.5 Fuzzy Logic Control 447
22.6 Sugeno Style of Fuzzy Inference Processing 453
22.7 Fuzzy Hedges 454
22.8 a Cut Threshold 454
22.9 Neuro Fuzzy Systems 455
22.10 Points to Note 455
23. Genetic Algorithms: Copying Nature's Approaches
23.1 A Peek into the Biological World 457
23.2 Genetic Algorithms (OAs) 458
23.3 Significance of the Genetic Operators 470
23.4 Termination Parameters 471
23.5 Niching and Speciation 471
23.6 Evolving Neural Networks 472
23.7 Theoretical Grounding 474
23.8 Ant Algorithms 476
23.9 Points to'Ponder 477
24. Artificial Immune Systems
24.1 Introduction 479
24.2 The Phenomenon of Immunity 479
24.3 Immunity and Infection 480
24.4 The Innate Immune System—The First Line of Defence 24.5 The Adaptive Immune System—The Second Line of Defence 481
24.6 Recognition 483
24.7 Clonal Selection 484
24.7 Learning 485
24.8 Immune Network Theory 485
24.9 Mapping Immune Systems to Practical Applications 486
24.10 Other Applications 493
24.11 Points to Ponder 493
25. Prolog—The Natural Language of Artificial Intelligence
25.1 Introduction 496
25.2 Converting English to Prolog Facts and Rules 496
25.3 Goals 497
25.4 Prolog Terminology 499
25.5 Variables 499
25.6 Control Structures 500
25.7 Arithmetic Operators 500
25.8 Matching in Prolog 502
25.9 Backtracking 503
25.10 Cuts 505
25.11 Recursion 506
25.12 Lists 508
25.13 Dynamic Databases 512
25.14 Input/Output and Streams 515
25.15 Some Aspects Specific to LPA Prolog 516
26. Conclusion
26.1 Components of an AI Program 529
26.2 AI Skeptics—An Open Argument 529