Preface vii

Publisher's Acknowledgements xv

PART I ARTIFICIAL INTELLIGENCE: ITS ROOTS AND SCOPE 1

1 AI: HISTORY AND APPLICATIONS 3

1.1 From Eden to ENIAC: Attitudes toward Intelligence, Knowledge, and Human Artifice 3

1.2 Overview of AI Application Areas 20

1.3 Artificial Intelligence--A Summary 30

1.4 Epilogue and References 31

1.5 Exercises 33

PART II ARTIFICIAL INTELLIGENCE AS REPRESENTATION AND SEARCH 35

2 THE PREDICATE CALCULUS 45

2.0 Introduction 45

2.1 The Propositional Calculus 45

2.2 The Predicate Calculus 50

2.3 Using Inference Rules to Produce Predicate Calculus Expressions 62

2.4 Application: A Logic-Based Financial Advisor 73

2.5 Epilogue and References 77

2.6 Exercises 77

3 STRUCTURES AND STRATEGIES FOR STATE SPACE SEARCH 79

3.0 Introduction 79

3.1 Graph Theory 82

3.2 Strategies for State Space Search 93

3.3 Using the State Space to Represent Reasoning with the Predicate Calculus 107

3.4 Epilogue and References 121

3.5 Exercises 121

4 HEURISTIC SEARCH 123

4.0 Introduction 123

4.1 Hill Climbing and Dynamic Programming 127

4.2 The Best-First Search Algorithm 133

4.3 Admissibility, Monotonicity, and Informedness 145

4.4 Using Heuristics in Games 150

4.5 Complexity Issues 157

4.6 Epilogue and References 161

4.7 Exercises 162

5 STOCHASTIC METHODS 165

5.0 Introduction 165

5.1 The Elements of Counting 167

5.2 Elements of Probability Theory 170

5.3 Applications of the Stochastic Methodology 182

5.4 Bayes' Theorem 184

5.5 Epilogue and References 190

5.6 Exercises 191

6 CONTROL AND IMPLEMENTATION OF STATE SPACE SEARCH 193

6.0 Introduction 193

6.1 Recursion-Based Search 194

6.2 Production Systems 200

6.3 The Blackboard Architecture for Problem Solving 187

6.4 Epilogue and References 219

6.5 Exercises 220

PART III REPRESENTATION AND INTELLIGENCE: THE AI CHALLENGE 223

7 KNOWLEDGE REPRESENTATION 227

7.0 Issues in Knowledge Representation 227

7.1 A Brief History of AI Representational Systems 228

7.2 Conceptual Graphs: A Network Language 248

7.3 Alternatives to Explicit Representation 258

7.4 Agent Based and Distributed Problem Solving 235

7.5 Epilogue and References 240

7.6 Exercises 243

8 STRONG METHOD PROBLEM SOLVING 277

8.0 Introduction 277

8.1 Overview of Expert System Technology 279

8.2 Rule-Based Expert Systems 286

8.3 Model-Based, Case Based, and Hybrid Systems 298

8.4 Planning 314

8.5 Epilogue and References 329

8.6 Exercises 331

9 REASONING IN UNCERTAIN SITUATIONS 333

9.0 Introduction 333

9.1 Logic-Based Abductive Inference 335

9.2 Abduction: Alternatives to Logic 350

9.3 The Stochastic Approach to Uncertainty 363

9.4 Epilogue and References 379

9.5 Exercises 381

PART IV MACHINE LEARNING 385

10 MACHINE LEARNING: SYMBOL-BASED 387

10.0 Introduction 387

10.1 A Framework for Symbol-based Learning 390

10.2 Version Space Search 396

10.3 The ID3 Decision Tree Induction Algorithm 408

10.4 Inductive Bias and Learnability 417

10.5 Knowledge and Learning 422

10.6 Unsupervised Learning 433

10.7 Reinforcement Learning 442

10.8 Epilogue and References 449

10.9 Exercises 450

11 MACHINE LEARNING: CONNECTIONIST 453

11.0 Introduction 453

11.1 Foundations for Connectionist Networks 455

11.2 Perceptron Learning 458

11.3 Backpropagation Learning 467

11.4 Competitive Learning 474

11.5 Hebbian Coincidence Learning 484

11.6 Attractor Networks or "Memories" 495

11.7 Epilogue and References 505

11.8 Exercises 506

12 MACHINE LEARNING: SOCIAL AND EMERGENT 507

12.0 Social and Emergent Models of Learning 507

12.1 The Genetic Algorithm 509

12.2 Classifier Systems and Genetic Programming 519

12.3 Artificial Life and Society-Based Learning 530

12.4 Epilogue and References 541

12.5 Exercises 542

PART V ADVANCED TOPICS FOR AI PROBLEM SOLVING 545

13 AUTOMATED REASONING 547

13.0 Introduction to Weak Methods in Theorem Proving 547

13.1 The General Problem Solver and Difference Tables 548

13.2 Resolution Theorem Proving 554

13.3 PROLOG and Automated Reasoning 575

13.4 Further Issues in Automated Reasoning 581

13.5 Epilogue and References 588

13.6 Exercises 589

14 UNDERSTANDING NATURAL LANGUAGE 591

14.0 Role of Knowledge in Language Understanding 591

14.1 Deconstructing Language: A Symbolic Analysis 594

14.2 Syntax 597

14.3 Syntax and Knowledge with ATN Parsers 606

14.4 Stochastic Tools for Language Analysis 616

14.5 Natural Language Applications 623

14.6 Epilogue and References 630

14.7 Exercises 632

PART VI LANGUAGES AND PROGRAMMING TECHNIQUES FOR ARTIFICIAL INTELLIGENCE 635

15 AN INTRODUCTION TO PROLOG 641

15.0 Introduction 641

15.1 Syntax for Predicate Calculus Programming 642

15.2 Abstract Data Types (ADTs) in PROLOG 654

15.3 A Production System Example in PROLOG 658

15.4 Designing Alternative Search Strategies 663

15.5 A PROLOG Planner 668

15.6 PROLOG: Meta-Predicates, Types, and Unification 671

15.7 Meta-Interpreters in PROLOG 679

15.8 Learning Algorithms in PROLOG 694

15.9 Natural Language Processing in PROLOG 704

15.10 Epilogue and References 716

15.11 Exercises 676

16 AN INTRODUCTION TO LISP 723

16.0 Introduction 723

16.1 LISP: A Brief Overview 724

16.2 Search in LISP: A Functional Approach to the Farmer, Wolf, Goat, and Cabbage Problem 746

16.3 Higher-Order Functions and Procedural Abstraction 751

16.4 Search Strategies in LISP 755

16.5 Pattern Matching in LISP 759

16.6 A Recursive Unification Function 761

16.7 Interpreters and Embedded Languages 765

16.8 Logic Programming in LISP 767

16.9 Streams and Delayed Evaluation 776

16.10 An Expert System Shell in LISP 780

16.11 Semantic Networks and Inheritance in LISP 787

16.12 Object-Oriented Programming Using CLOS 791

16.13 Learning in LISP: The ID3 Algorithm 803

16.14 Epilogue and References 815

16.15 Exercises 816

PART VII EPILOGUE 821

17 ARTIFICIAL INTELLIGENCE AS EMPIRICAL ENQUIRY 823

17.0 Introduction 823

17.1 Artificial Intelligence: A Revised Definition 825

17.2 The Science of Intelligent Systems 838

17.3 AI: Current Challanges and Future Direstions 848

17.4 Epilogue and References 853

Bibliography 855

Author Index 883

Subject Index 889