Computational Intelligence

A Logical Approach

David Poole
Alan Mackworth
Randy Goebel

Copyright © Oxford University Press, New York, 1998.

Detailed Table of Contents

Chapter 1 Computational Intelligence and Knowledge1
1.1What Is Computational Intelligence? 1
Artificial or Computational Intelligence?1
Flying Machines and Thinking Machines2
Technological Models of Mind3
Science and Engineering5
Relationship to Other Disciplines6
1.2Agents in the World7
1.3Representation and Reasoning9
Representation and Reasoning System9
Ontology and Conceptualization 10
The Autonomous Delivery Robot12
The Diagnostic Assistant14
The Infobot16
Common Features18
1.6References and Further Reading 20
Chapter 2 A Representation and Reasoning System23
2.2Representation and Reasoning Systems23
2.3Simplifying Assumptions of the Initial RRS27
Formal Semantics32
User's View of Semantics37
The Computer's View of Semantics39
2.6Questions and Answers40
Interpreting Variables41
Clauses, Questions, and Answers43
Bottom-Up Ground Proof Procedure47
Top-Down Ground Proof Procedure49
Bottom-Up Procedure with Variables54
Definite Resolution with Variables56
2.8Extending the Language with Function Symbols58
Proof Procedures with Function Symbols61
2.9References and Further Reading63
Chapter 3 Using Definite Knowledge69
3.2Case Study: House Wiring70
3.3Databases and Recursion75
Database Operations75
Recursion and Mathematical Induction78
3.4Verification and Limitations79
Verification of Logic Programs79
3.5Case Study: Representing Abstract Concepts81
3.6Case Study: Representing Regulatory Knowledge86
3.7Applications in Natural Language Processing91
Using Definite Clauses for Context-Free Grammars93
Augmenting the Grammar97
Building Structures for Nonterminals97
Canned Text Output98
Enforcing Constraints98
Building a Natural Language Interface to a Database 101
3.8References and Further Reading104
3.9Exercises 104
Chapter 4 Searching113
4.1Why Search?113
4.2Graph Searching114
Formalizing Graph Searching116
4.3A Generic Searching Algorithm119
Finding Paths123
4.4Blind Search Strategies125
Depth-First Search125
Breadth-First Search128
Lowest-Cost-First Search131
4.5Heuristic Search132
Best-First Search133
Heuristic Depth-First Search134
A* Search135
Summary of Search Strategies137
4.6Refinements to Search Strategies138
Cycle Checking138
Multiple-Path Pruning139
Iterative Deepening140
Direction of Search143
Bidirectional Search143
Island-Driven Search144
Searching in a Hierarchy of Abstractions145
Dynamic Programming145
4.7Constraint Satisfaction Problems147
Posing a Constraint Satisfaction Problem148
Generate-and-Test Algorithms150
Backtracking Algorithms151
Consistency Algorithms152
Hill Climbing156
Randomized Algorithms158
Beam Search and Genetic Algorithms161
4.8References and Further Reading163
Chapter 5 Representing Knowledge169
5.2Defining a Solution170
Quality of Solutions171
Decisions and Outcomes172
Information Availability and Solution Quality173
Computation Cost and Solution Quality173
5.3Choosing a Representation Language174
Expressiveness and Complexity175
Levels of Representations177
5.4Mapping from Problem to Representation180
Level of Abstraction180
Choosing Objects and Relations182
Building Flexible Representations185
Primitive Versus Derived Relations188
Acquiring and Debugging a Knowledge Base191
5.5Choosing an Inference Procedure192
5.6References and Further Reading195
Chapter 6 Knowledge Engineering199
6.2Knowledge-Based System Architecture200
Base Languages and Metalanguages202
A Vanilla Meta-Interpreter205
Expanding the Base Language207
Depth-Bounded Search209
Delaying Goals210
6.4Querying the User212
Yes/No Questions213
Functional Relations214
More General Questions215
How Did the System Prove a Goal?217
Why Did the System Ask a Question?220
6.6Debugging Knowledge Bases221
Incorrect Answers222
Missing Answers224
Infinite Loops226
6.7A Meta-Interpreter with Search226
6.9References and Further Reading233
6.10Exercises 233
Chapter 7 Beyond Definite Knowledge235
Allowing Equality Assertions236
Axiomatizing Equality237
Special-Purpose Equality Reasoning237
Unique Names Assumption238
Top-Down Procedure for the Unique Names Assumption239
7.3Integrity Constraints241
Applications of Integrity Constraints243
Consistency-Based Diagnosis243
Integrity Constraints in Databases245
Reasoning with Integrity Constraints245
Bottom-Up Implementation245
Top-Down Implementation247
7.4Complete Knowledge Assumption248
Proof Procedures253
Bottom-Up Procedure253
Top-Down Procedure255
7.5Disjunctive Knowledge256
Queries and Answers259
Proof Procedures260
Bottom-Up Procedure260
A Top-Down Proof Procedure262
Answer Extraction266
Application Examples267
7.6Explicit Quantification268
7.7First-Order Predicate Calculus270
Proof Procedure272
Converting to Negation Normal Form272
Converting Negation Normal Form to Clausal Form273
7.8Modal Logic275
Possible Worlds Semantics275
Proof Procedures277
7.9References and Further Reading277
Chapter 8 Actions and Planning281
Representing Time282
The Delivery Robot World284
Initial World Description286
Derived Relations286
8.2Representations of Actions and Change287
The STRIPS Representation288
The Situation Calculus290
The Event Calculus294
Comparing the Representations296
8.3Reasoning with World Representations298
Forward Planning299
Planning as Resolution300
The STRIPS Planner301
Partial-Order Planning309
8.4References and Further Reading315
8.5Exercises 316
Chapter 9 Assumption-Based Reasoning319
9.2An Assumption-Based Reasoning Framework321
9.3Default Reasoning323
Making Normality Assumptions323
Overriding Assumptions326
Resolving Competing Arguments328
Defining Default Prediction330
A Minimal Model Semantics for Default Prediction332
9.5Evidential and Causal Reasoning335
Abduction Followed by Default Reasoning337
Axiomatizing Both Causal and Evidential Directions338
9.6Algorithms for Assumption-Based Reasoning339
9.7References and Further Reading342
Chapter 10 Using Uncertain Knowledge345
Random Variables348
Semantics of Probability349
Axioms for Probability352
Conditional Probability353
Semantics of Conditional Probability354
Bayes' Theorem356
Expected Values359
Information Theory360
10.3Independence Assumptions361
Belief Networks363
Belief Networks as a Factorization of Probabilities368
Reasoning in a Belief Network369
Constructing Belief Networks373
Implementing Belief Networks376
An Algorithm For Evaluating Belief Networks377
10.4Making Decisions Under Uncertainty381
Decision Variables384
Simple Decisions385
Sequential Decisions385
Decision Networks386
Expected Value of a Policy389
The Value of Information391
10.5References and Further Reading394
Chapter 11 Learning397
11.2Learning as Choosing the Best Representation403
Learning Decision Trees403
Searching for a Good Decision Tree405
Neural Networks408
11.3Case-Based Reasoning414
11.4Learning as Refining the Hypothesis Space416
Version-Space Learning418
Candidate Elimination Algorithm419
The Bias Involved in Version Space Learning420
Probably Approximately Correct Learning421
11.5Learning Under Uncertainty424
Bayesian learning of decision trees426
Maximum A Posteriori Probability and Minimum Description Length427
Averaging Over Models428
Naive Bayesian Classifier429
Probabilities from Experts432
11.6Explanation-Based Learning433
11.7References and Further Reading437
Chapter 12 Building Situated Robots443
12.2Robotic Systems444
12.3The Agent Function446
12.4Designing Robots447
12.5Uses of Agent Models449
12.6Robot Architectures450
12.7Implementing a Controller451
Maintaining State Using the Event Calculus452
Implementing a Layered Controller453
12.8Robots Modeling the World457
12.9Reasoning in Situated Robots458
12.10References and Further Reading459
Appendix A Glossary461
Appendix B The Prolog Programming Language477
B.2Interacting with Prolog478
Infix Operators480
B.5Database Relations483
Global Variables485
B.6Returning All Answers485
B.7Input and Output487
B.8Controlling Search488
Appendix C Some More Implemented Systems491
C.1Bottom-Up Interpreters491
Bottom-Up Definite Clause Interpreter491
Bottom-Up Negation as Failure Implementation493
Bottom-Up Assumable Interpreter495
C.2Top-Down Interpreters498
Meta-Interpreter for Traversing Proof Trees498
Iterative Deepening Definite Clause Interpreter502
Querying the User504
Meta-Interpreter with Search505
C.3Constraint Satisfaction Problem Solver507
C.4Neural Network Learner511
C.5Partial-Order Planner515
C.6Implementing Belief Networks521
C.7Robot Controller529

List of Figures

1.1An agent as a black box8
1.2An environment for the delivery robot14
1.3An electrical environment for the diagnostic assistant16
2.1The role of semantics in a representation and reasoning system26
2.2Truth table defining and and if35
2.3Clauses provided by the user44
2.4Bottom-up proof procedure for computing consequences of KB47
2.5Top-down definite clause interpreter, without variables51
2.6Top-down definite clause interpreter, with variables56
3.1An electrical environment with individuals named71
3.2Sample database76
3.3Example database of student record information87
3.4Example database relations about the university88
3.5A context-free grammar for a very restricted subset of English96
3.6A simple dictionary97
3.7Grammar for output of canned English99
3.8A grammar that enforces number agreement and builds a parse tree100
3.9A grammar that constructs a query102
3.10A dictionary for constructing a query103
4.1The delivery robot domain with interesting locations labeled115
4.2A graph to search for the delivery robot domain117
4.3A search graph for an SLD derivation118
4.4Problem solving by graph searching120
4.5A graph, with cycles, for the delivery robot domain127
4.6Summary of search strategies138
4.7Iterative deepening searcher142
4.8Arc consistency algorithm AC-3153
4.9Domain-consistent constraint network for the scheduling problem154
4.10A foothill, plateau, and ridge on a contour map159
4.11Simulated annealing algorithm160
4.12A grid searching problem165
4.13A crossword puzzle to be solved with six words167
5.1The knowledge representation framework170
5.2Solution quality as a function of time for an anytime algorithm174
5.3Lattice of sublogics176
5.4A hierarchy of representations178
5.5A flat semantic network186
5.6A structured semantic network189
6.1Knowledge-based system architecture200
6.2The non-ground representation for the base language204
6.3The vanilla definite clause meta-interpreter205
6.4A base-level knowledge base for house wiring206
6.5A meta-interpreter that uses built-in calls and disjunction208
6.6A meta-interpreter for depth-bounded search209
6.7A meta-interpreter that collects delayed goals211
6.8An ask-the-user interpreter in pseudo-code213
6.9A meta-interpreter that builds a proof tree218
6.10A meta-interpreter that collects ancestor rules for WHY questions221
6.11An algorithm for debugging incorrect answers223
6.12An algorithm for debugging missing answers225
6.13Meta-interpreter with search228
6.14Pseudocode for unification using the ground representation232
7.1Two chairs236
7.2Bottom-up proof procedure for computing conflicts of T246
7.3A meta-interpreter to find conflicts248
7.4Bottom-up negation as failure proof procedure254
7.5Truth table for the clausal operators259
7.6Bottom-up proof procedure for computing prime implicates of KB261
7.7Meta-interpreter for general clauses263
7.8A proof tree for Example 7.32265
7.9Theorem prover with answer extraction267
7.10Truth table for predicate calculus operators272
7.11Modal logic, their constraints on R, and their axioms276
7.12Axioms for L277
8.1The delivery robot domain with objects285
8.2A simple STRIPS planner that uses STRIPS representation302
8.3Finding weakest preconditions using the STRIPS representation306
8.4A regression planner307
8.5Partial-order planner311
8.6Threat handler for the partial-order planner313
8.7Partial elaboration of the partial-ordered planning example314
9.1Diagrammatic representation of the defaults from Example 9.3325
9.2A diagrammatic representation of Example 9.5328
9.3Causal network for Example 9.8336
10.1Belief network for the electrical domain of Figure 3.1365
10.2Belief network for report of leaving of Example 10.16370
10.3Belief network for aching limbs of Example 10.17374
10.4Decision tree for delivery robot decision of Example 10.20383
10.5Decision network for delivery robot decision387
10.6Decision network for the alarm problem388
10.7Value for alarm decision network388
10.8Possible money-utility tradeoff from Example 10.29394
10.9Belief network for overhead projector396
11.1The learning architecture398
11.2Some classification data for learning user preferences400
11.3Simple decision tree404
11.4Simple decision tree learning program for binary attributes406
11.5The sigmoid or logistic function410
11.6Simple neural network with one hidden layer411
11.7Simulation of the neural net learning algorithm413
11.8Candidate elimination algorithm419
11.9Posterior distributions of probA based on different samples425
11.10Belief network corresponding to a naive Bayesian classifier430
11.11A meta-interpreter for explanation-based learning434
11.12Example background KB for explanation-based learning436
12.1A robotic system and its components445
12.2A hierarchical robotic system architecture451
12.3A hierarchical decomposition of the delivery robot454
12.4A simulation of the robot carrying out the plan of Example 12.4457
B.1Syntactic translation between this book and standard Prolog479
C.1Forward-chaining assumption-based reasoner495

Computational Intelligence: A Logical Approach