Webber / Nilsson Readings in Artificial Intelligence

1. Auflage 2014
ISBN: 978-1-4832-1440-5
Verlag: Elsevier Science & Techn.
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, 558 Seiten, Web PDF

Readings in Artificial Intelligence focuses on the principles, methodologies, advancements, and approaches involved in artificial intelligence. The selection first elaborates on representations of problems of reasoning about actions, a problem similarity approach to devising heuristics, and optimal search strategies for speech understanding control. Discussions focus on comparison with existing speech understanding systems, empirical comparisons of the different strategies, analysis of distance function approximation, problem similarity, problems of reasoning about action, search for solution in the reduction system, and relationship between the initial search space and the higher level search space. The book then examines consistency in networks of relations, non-resolution theorem proving, using rewriting rules for connection graphs to prove theorems, and closed world data bases. The manuscript tackles a truth maintenance system, elements of a plan-based theory of speech acts, and reasoning about knowledge and action. Topics include problems in reasoning about knowledge, integration knowledge and action, models of plans, compositional adequacy, truth maintenance mechanisms, dialectical arguments, and assumptions and the problem of control. The selection is a valuable reference for researchers wanting to explore the field of artificial intelligence.

Autoren/Hrsg.

Webber, Bonnie Lynn

Nilsson, Nils J.

Inhaltsverzeichnis

1;Front Cover;1
2;Readings in Artificial Intelligence;4
3;Copyright Page;5
4;Table of Contents;6
5;PREFACE;8
6;ACKNOWLEDGMENTS;10
7;Part 1: Search and Search Representations;12
7.1;Chapter 1. On Representations of Problems of Reasoning about Actions;13
7.1.1;1. INTRODUCTION;13
7.1.2;2. PROBLEMS OF REASONING ABOUT ACTIONS;13
7.1.3;3. TRANSPORTATION PROBLEMS: INITIAL FORMULATION, F,, OF M&C PROBLEMS;15
7.1.4;4. FORMULATION F2 OF THE M&C PROBLEM IN ELEMENTARY SYSTEMS OF PRODUCTIONS;15
7.1.5;5. FORMULATION F3 OF THE M&C PROBLEM IN AN IMPROVED SYSTEM OF PRODUCTIONS;18
7.1.6;6. FORMULATION F4 OF THE M&C PROBLEM IN AREDUCTION SYSTEM;19
7.1.7;7. THE SEARCH FOR SOLUTION IN THE REDUCTION SYSTEM;19
7.1.8;8. DISCOVERY AND UTILIZATION OF SYMMETRIES IN THE SEARCH SPACE. FORMULATION F, OF THE M&C PROBLEM;20
7.1.9;9. DISCOVERY OF SOLUTION PATTERNS IN AN APPROPRIATE REPRESENTATION OF N-STATE SPACE;23
7.1.10;10. FORMULATION F6 OF EXTENDED M&C PROBLEM IN A MUCH IMPROVED PRODUCTION SYSTEM THAT CORRESPONDS TO A HIGHER LEVEL SEARCH SPACE;27
7.1.11;11. RELATIONSHIPS BETWEEN THE INITIAL SEARCH SPACE AND THE HIGHER LEVEL SEARCH SPACE;29
7.1.12;12. SUMMARY AND CONCLUDING COMMENTS;30
7.1.13;Acknowledgment;32
7.1.14;REFERENCES;32
7.2;Chapter 2. A PROBLEM SIMILARITY APPROACH TO DEVISING HEURISTICS: FIRST RESULTS;34
7.2.1;Abstract;34
7.2.2;1· Introduction;34
7.2.3;2· Problem Similarity: Edge Subgraphs and Supergraphs;35
7.2.4;3. Example: A Sorting Algorithm Used as Heuristic for the 8-Puzzle;36
7.2.5;4. Analysis of Distance Function Approximation;38
7.2.6;5. Discussion;38
7.2.7;6. References;39
7.3;Chapter 3. Optimal Search Strategies for Speech Understanding Control;41
7.3.1;Abstract;41
7.3.2;1. INTRODUCTION;41
7.3.3;2. ISLAND-DRIVE N STRATEGIE S;42
7.3.4;3. THE SHORTFALL SCORING METHOD;44
7.3.5;4. DENSITY SCORING WITH ISLAND COLLISIONS;52
7.3.6;5. SHORTFALL DENSITY;54
7.3.7;6. EFFICIENCY TECHNIQUES;56
7.3.8;7. EMPIRICAL COMPARISON OF THE DIFFERENT STRATEGIES;58
7.3.9;8. COMPARISON WIT H EXISTING SPEECH UNDERSTANDING SYSTEMS;61
7.3.10;9. COST/BENEFITS OF OPTIMALITY;74
7.3.11;10. CONCLUSIONS;76
7.3.12;Acknowledgment;77
7.3.13;References;77
7.4;Chapter 4. Consistency in Networks of Relations;80
7.4.1;ABSTRACT;80
7.4.2;1. Introduction;80
7.4.3;2. The Task;80
7.4.4;3. Backtracking and Three of its Maladies;80
7.4.5;4. Consistency: A State of Affairs that Forestalls Thrashing;82
7.4.6;5. How to Achieve Node Consistency;82
7.4.7;6. How to Achieve Arc Consistency;82
7.4.8;7. How to Achieve Path Consistency;84
7.4.9;8. The Use of Consistency Methods in Problem Solving;87
7.4.10;9. Applications;87
7.4.11;10. Conclusion;89
7.4.12;ACKNOWLEDGMENTS;89
7.4.13;REFERENCES;89
7.5;Chapter 5. The B* Tree Search Algorithm: A Best-FirstProof Procedure†;90
7.5.1;ABSTRACT;90
7.5.2;1. Introduction;90
7.5.3;2. The B* Algorithm;91
7.5.4;3. Tests of the B* Algorithm;93
7.5.5;4. Considerations that Led to the Discovery of the Algorithm;95
7.5.6;5. Evaluation Functions and Meaningful Bounds;96
7.5.7;6. Comparison to other Search Algorithms;97
7.5.8;7. Summary;97
7.5.9;Appendix I. How to Generate Canonical Trees of Uniform Width;98
7.5.10;ACKNOWLEDGMENT;98
7.5.11;REFERENCES;98
8;Part 2: Deduction;100
8.1;Chapter 6. Non-resolution Theorem Proving1;102
8.1.1;ABSTRACT;102
8.1.2;1. Introduction;102
8.1.3;2. Concepts;102
8.1.4;3. Programming Languages;116
8.1.5;4. Comments;116
8.1.6;5. Challenges;116
8.1.7;REFERENCES;117
8.2;Chapter 7. Using Rewriting Rules for Connection Graphs to Prove Theorems;120
8.2.1;ABSTRACT;120
8.2.2;1. Introduction;120
8.2.3;2. Connection Graphs;120
8.2.4;3. Combinations of Substitutions;121
8.2.5;4. Obtaining rewriting Rules from a Connection Graph;121
8.2.6;5. Renaming Variables and Performing Unifications;123
8.2.7;6. Cyclic Rewriting Rules;125
8.2.8;7. Relationship with Existing AI work;126
8.2.9;8. Summary;128
8.2.10;REFERENCES;129
8.3;Chapter 8. ON CLOSED WORLD DATA BASES;130
8.3.1;ABSTRACT;130
8.3.2;INTRODUCTION;130
8.3.3;DATA BASES AND QUERIES;131
8.3.4;THE CLOSED WORLD ASSUMPTION;134
8.3.5;QUERY EVALUATION UNDER THE CWA;138
8.3.6;ON DATA BASES CONSISTENT WITH THE CWA;142
8.3.7;THE CWA AND DATA BASE INTEGRITY;144
8.3.8;SUMMAR;144
8.3.9;ACKNOWLEDGMTE;144
8.3.10;APPENDIX;145
8.3.11;REFERENCES;151
8.4;Chapter 9. A Deductive Approach to Program Synthesis;152
8.4.1;MOTIVATION;152
8.4.2;SPECIFICATION;153
8.4.3;BASIC STRUCTURE;154
8.4.4;SPLITTING RULES;156
8.4.5;TRANSFORMATION RULES;157
8.4.6;RESOLUTION;160
8.4.7;THE RESOLUTION RULES;161
8.4.8;THE POLARITY STRATEGY;164
8.4.9;MATHEMATICAL INDUCTION AND THE FORMATION OF RECURSIVE CALLS;165
8.4.10;A COMPLETE EXAMPLE: FINDING THE QUOTIENT OF TWO INTEGERS;170
8.4.11;THE FORMATION OF AUXILIARY PROCEDURES;173
8.4.12;GENERALIZATION;178
8.4.13;COMPARISON WITH THE PURE TRANSFORMATION-RULE APPROACH;182
8.4.14;ACKNOWLEDGMENTS;182
8.4.15;REFERENCES;183
8.5;Chapter 10. Prolegomena to a Theory of Mechanized Formal Reasoning;184
8.5.1;ABSTRACT;184
8.5.2;1. Introduction;184
8.5.3;2. FOL as a Conversational Program;185
8.5.4;3. The Logic Used by FOL;186
8.5.5;4. Simulation Structures and Semantic Attachment;186
8.5.6;5. Syntactic Simplifier;188
8.5.7;6. A General First Order Logic Expression Evaluator;188
8.5.8;7. Systems of Languages and Simulation Structures;189
8.5.9;8. Metatheory;190
8.5.10;9. Reflection;192
8.5.11;10. Self Reflection;196
8.5.12;11. Conclusion;197
8.5.13;Appendices;198
8.5.14;REFERENCES;202
8.6;Chapter 11. Subjective Bayesian methods for rule-based inference systems;203
8.6.1;ABSTRACT;203
8.6.2;INTRODUCTION;203
8.6.3;FUNDAMENTALS;203
8.6.4;SUBJECTIVE BAYESIAN UPDATING;204
8.6.5;UNCERTAIN EVIDENCE AND THEPROBLEM OF PRIOR PROBABILITIES;205
8.6.6;THE USE OF MULTIPLE EVIDENCE;208
8.6.7;CONCLUSIONS;208
8.6.8;ACKNOWLEDGMENTS;209
8.6.9;REFERENCES;209
8.6.10;APPENDIX;209
9;Part 3: Problem-Solvingand Planning;212
9.1;Chapter 12. APPLICATION O F THEOREM PROVING TO PROBLEM SOLVING;213
9.1.1;Abstract;213
9.1.2;Key Words;213
9.1.3;I . An Introduction to State-Transformation Method;213
9.1.4;II. Refinements of the Method;215
9.1.5;III. An Example: The Monkey and The Bananas;218
9.1.6;IV. Formalizations for the Tower of Hanoi Puzzle;219
9.1.7;V. Applications to the Robot Project;222
9.1.8;VI . Automatic Programming;225
9.1.9;VII. Discussion;230
9.1.10;Acknowledgment;230
9.1.11;REFERENCES;231
9.1.12;APPENDIX;232
9.2;Chapter 13. The Frame Problem and Related Problems in Artificial Intelligence;234
9.2.1;Summary;234
9.2.2;Introduction;234
9.2.3;Time and Change;234
9.2.4;The Frame Problem;235
9.2.5;Frame Rules;235
9.2.6;Some Partial Solutions Using Frame Rules;236
9.2.7;A (Very) Simple Example: Toy Bricks;237
9.2.8;Implementing Frame Rules;238
9.2.9;Consistency and Counterfactuals;238
9.2.10;Conclusions;239
9.2.11;Observations and the Qualification Problem;239
9.2.12;Acknowledgements;240
9.3;Chapter 14. Learning and Executing Generalized Robot Plans1;242
9.3.1;ABSTRACT;242
9.3.2;1. Introduction;242
9.3.3;2. Summary of Strips;243
9.3.4;3. Triangle Tables;245
9.3.5;4. Generalizing Plans;247
9.3.6;5. Execution Strategies;250
9.3.7;6. Planning with MACROPS;252
9.3.8;7. Experimental Results;254
9.3.9;8. Conclusions;259
9.3.10;REFERENCES;260
9.4;Chapter 15. Achieving Several Goals Simultaneously;261
9.4.1;INTRODUCTION;261
9.4.2;PART1. SIMULTANEOUS GOALS, PROGRAM MODIFICATION, AND THE REPRESENTATION OF ACTIONS;262
9.4.3;PART 2. THE REPRESENTATION OF ACTIONS AND SITUATIONS IN CONTEMPORARY PROBLEM SOLVING;273
9.4.4;ACKNOWLEDGMENTS;281
9.4.5;REFERENCES;281
9.5;Chapter 16. Planning and Meta-Planning;283
9.5.1;ABSTRACT;283
9.5.2;1. Introduction;283
9.5.3;2. The Rationale for Layers;283
9.5.4;3. A Model for Planning;287
9.5.5;4. Relationships to Other Work;293
9.5.6;5. Limitations and Further Research;295
9.5.7;6. Summary;296
9.5.8;ACKNOWLEDGMENT;296
9.5.9;REFERENCES;296
10;Part 4: Expert Systemsand AI Applications;298
10.1;Chapter 17. An Experiment in Knowledge-based Automatic Programming;300
10.1.1;ABSTRACT;300
10.1.2;1. Introduction;300
10.1.3;2. Overview of the Knowledge Base;303
10.1.4;3. Sample Programs;305
10.1.5;4. A Detailed Example;307
10.1.6;5. Implementation;314
10.1.7;6. Discussion;315
10.1.8;7. Approaches to Automatic Programming;318
10.1.9;8. Assessment;322
10.1.10;ACKNOWLEDGEMENTS;322
10.1.11;REFERENCES;322
10.2;Chapter 18. Dendral and Meta-Dendral: Their Applications Dimension;324
10.2.1;1. Introduction;324
10.2.2;2. The General Nature of the Applications Tasks;324
10.2.3;3. Heuristic DENDRAL as an Intelligent Assistant;325
10.2.4;4. Meta-DENDRAL;328
10.2.5;5. Problems;330
10.2.6;6. Computers and Languages;331
10.2.7;7. Conclusion;331
10.2.8;ACKNOWLEDGMENTS;331
10.2.9;SELECTED REFERENCES IN CHRONOLOGICAL ORDER;331
10.3;Chapter 19. CONSULTATION SYSTEMS FOR PHYSICIANS;334
10.3.1;ABSTRACT;334
10.3.2;1. INTRODUCTION;334
10.3.3;2. ACCEPTABILITY ISSUES;335
10.3.4;3. DESIGN CRITERIA;335
10.3.5;4. KNOWLEDGE ENGINEERING;337
10.3.6;5. AN EXAMPLE: THE MYCIN SYSTEM;337
10.3.7;6. CONCLUSION;343
10.3.8;REFERENCES;343
10.4;Chapter 20. MODEL DESIGN IN THE PROSPECTOR CONSULTANT SYSTEMFOR MINERAL EXPLORATION;345
10.4.1;ABSTRACT;345
10.4.2;I. INTRODUCTION;345
10.4.3;II. OVERVIEW OF THE PROSPECTOR SYSTEM;346
10.4.4;III. FORMALISM FOR ENCODING EXPLORATION MODELS;347
10.4.5;IV. OVERVIEW OF THE MODEL DEVELOPMENT PROCESS;353
10.4.6;V. USE OF PERFORMANCE EVALUATION IN REFINING A MODEL;355
10.4.7;VI. REMARKS;358
10.4.8;VII. ACKNOWLEDGEMENTS;358
10.4.9;REFERENCES;359
10.5;Chapter 21. The Hearsay-ll Speech-Understanding System: Integrating Knowledge to Resolve Uncertainty;360
10.5.1;INTRODUCTION;361
10.5.2;1. AN EXAMPLE OF RECOGNITION;369
10.5.3;2. COMPARISON WITH OTHER SPEECHUNDERSTANDING SYSTEMS;380
10.5.4;3. SYSTEM PERFORMANCE AND ANALYSIS;386
10.5.5;4. CONCLUSIONS;390
10.5.6;APPENDIX. SYSTEM DEVELOPMENT;395
10.5.7;ACKNOWLEDGMENTS;397
10.5.8;REFERENCES;397
10.6;Chapter 22. Using Patterns and Plans in Chess;401
10.6.1;ABSTRACT;401
10.6.2;1. Introduction;401
10.6.3;2. Overview of PARADISE;402
10.6.4;3. The Need for Concepts;403
10.6.5;4. Knowledge Sources and Concepts;404
10.6.6;5. Plans;405
10.6.7;6. Creating Plans;407
10.6.8;7. How Detailed Should Plans Be?;407
10.6.9;8. Using Plans to Guide the Search;408
10.6.10;9. A Typical Medium-Sized Search;409
10.6.11;10. Measuring PARADISE'S performance;414
10.6.12;11. How PARADISE Goes Wrong;416
10.6.13;12. Comparison to Plans in Robot Problem Solving;417
10.6.14;13. Comparison to Plans in Chess;417
10.6.15;14. Summary;418
10.6.16;15. Issues;419
10.6.17;ACKNOWLEDGEMENTS;420
10.6.18;REFERENCES;420
10.7;Chapter 23. Interactive Transfer of Expertise: Acquisitionof New Inference Rules;421
10.7.1;ABSTRACT;421
10.7.2;1. Introduction;421
10.7.3;2. Meta-Level Knowledge;421
10.7.4;3. Perspective on Knowledge Acquisition;422
10.7.5;4. Design of the Performance Program;422
10.7.6;5. A Word about Natural Language;424
10.7.7;6. Example of TEIRESIAS in Operation;424
10.7.8;7. How it all Works;429
10.7.9;8. Other Uses for the Rule Models;435
10.7.10;9. Assumptions and Limitations;436
10.7.11;10. Conclusions;437
10.7.12;ACKNOWLEDGMENTS;438
10.7.13;REFERENCES;438
11;Part 5: Advanced Topics;440
11.1;Chapter 24. Some Philosophical Problems from the

Standpoint of Artificial Intelligence;442
11.1.1;Abstract;442
11.1.2;1. PHILOSOPHICALQUESTIONS;442
11.1.3;2. FORMALISM;449
11.1.4;3. REMARKSANDOPENPROBLEMS;453
11.1.5;4. DISCUSSION OF LITERATURE;455
11.1.6;Acknowledgements;460
11.1.7;REFERENCES;460
11.2;Chapter 25. The Logic of Frames;462
11.2.1;Introduction: Representation and Meaning;462
11.2.2;Seeing As;464
11.2.3;Defaults;466
11.2.4;Reflexive Reasoning;467
11.2.5;Conclusion;468
11.2.6;Acknowledgements;468
11.2.7;Appendix: Translation of KRL-. into Predicate Logic;468
11.2.8;References;469
11.3;Chapter 26. EPISTEMOLOCICAL PROBLEMS OF ARTIFICIAL INTELLIGENCE;470
11.3.1;Introduction;470
11.3.2;Epistemological problems;471
11.3.3;Circumscription - a way of jumping to conclusions;472
11.3.4;Concepts as objects;473
11.3.5;Philosophical Notes;475
11.3.6;References;476
11.4;Chapter 27. Circumscription—A Form of Non-Monotonic Reasoning;477
11.4.1;ABSTRACT;477
11.4.2;1. Introduction . The Qualification Problem;477
11.4.3;2. The Need for Non-Monotonic Reasoning;477
11.4.4;3. Missionaries and Cannibals;478
11.4.5;4. The Formalism of Circumscription;479
11.4.6;5. Domain Circumscription;480
11.4.7;6. The Model Theory of Predicate Circumscription;481
11.4.8;7. More on Blocks;481
11.4.9;8. Remarks and Acknowledgments;482
11.4.10;REFERENCES;482
11.5;Chapter 28. REASONING ABOUT KNOWLEDGE AND ACTION;484
11.5.1;Abstract;484
11.5.2;1. Introduction;484
11.5.3;2. Problems in Reasoning about Knowledge;484
11.5.4;3. Reasoning about Knowledge via Possible Worlds;485
11.5.5;4. Integrating Knowledge and Action;486
11.5.6;5. Conclusions;487
11.5.7;6. References;488
11.6;Chapter 29. Elements of a Plan-Based Theory of Speech Acts;489
11.6.1;1. INTRODUCTION;489
11.6.2;2. ON MODELS OF OTHERS;491
11.6.3;3. MODELS OF PLANS;492
11.6.4;4. SPEECH ACTS;493
11.6.5;5. A FIRST REFORMULATION OF SEARLE'S CONDITIONS;494
11.6.6;6. COMPOSITIONAL ADEQUACY: QUESTIONS;498
11.6.7;7. COMPOSITIONAL ADEQUACY AND THE POINT OF VIEW PRINCIPLE;500
11.6.8;ACKNOWLEDGMENTS;505
11.6.9;REFERENCES;506
11.7;Chapter 30. A Truth Maintenance System;507
11.7.1;1. Introduction;507
11.7.2;2. Representation of Reasons for Beliefs;510
11.7.3;3. Truth Maintenance Mechanisms;513
11.7.4;4. Dependency-Directed Backtracking;516
11.7.5;5. Summarizing Arguments;518
11.7.6;6. Dialectical Arguments;519
11.7.7;7. Models of Others' Beliefs;520
11.7.8;8. Assumptions and the Problem of Control;521
11.7.9;9. Experience and Extensions;524
11.7.10;10. Discussion;525
11.7.11;ACKNOWLEDGEMENTS;526
11.7.12;REFERENCES;526
11.8;Chapter 31. Generalization as Search;528
11.8.1;1 Introduction;528
11.8.2;2 The Problem;528
11.8.3;3 Generalization as Search;530
11.8.4;4 Three Data-Dr i ven General ? zat i on Strateg i es;531
11.8.5;5. Other General izat ion Strategies;547
11.8.6;6 Further Issues;549
11.8.7;7 Summary;551
11.8.8;8 Acknowledgments;551
11.8.9;References;552
12;INDEX;554