Computational Intelligence

A Logical Approach

David Poole
Alan Mackworth
Randy Goebel

Detailed Table of Contents

Preface		xv
Chapter 1 Computational Intelligence and Knowledge		1
1.1	What Is Computational Intelligence?	1
	Artificial or Computational Intelligence?	1
	Flying Machines and Thinking Machines	2
	Technological Models of Mind	3
	Science and Engineering	5
	Relationship to Other Disciplines	6
1.2	Agents in the World	7
1.3	Representation and Reasoning	9
	Representation and Reasoning System	9
	Ontology and Conceptualization	10
1.4	Applications	11
	The Autonomous Delivery Robot	12
	The Diagnostic Assistant	14
	The Infobot	16
	Common Features	18
1.5	Overview	19
1.6	References and Further Reading	20
1.7	Exercises	21
Chapter 2 A Representation and Reasoning System		23
2.1	Introduction	23
2.2	Representation and Reasoning Systems	23
2.3	Simplifying Assumptions of the Initial RRS	27
2.4	Datalog	29
2.5	Semantics	31
	Formal Semantics	32
	User's View of Semantics	37
	The Computer's View of Semantics	39
2.6	Questions and Answers	40
	Queries	40
	Interpreting Variables	41
	Clauses, Questions, and Answers	43
2.7	Proofs	46
	Bottom-Up Ground Proof Procedure	47
	Top-Down Ground Proof Procedure	49
	Substitutions	52
	Bottom-Up Procedure with Variables	54
	Definite Resolution with Variables	56
2.8	Extending the Language with Function Symbols	58
	Proof Procedures with Function Symbols	61
2.9	References and Further Reading	63
2.10	Exercises	63
Chapter 3 Using Definite Knowledge		69
3.1	Introduction	69
3.2	Case Study: House Wiring	70
3.3	Databases and Recursion	75
	Database Operations	75
	Recursion and Mathematical Induction	78
3.4	Verification and Limitations	79
	Verification of Logic Programs	79
	Limitations	80
3.5	Case Study: Representing Abstract Concepts	81
3.6	Case Study: Representing Regulatory Knowledge	86
3.7	Applications in Natural Language Processing	91
	Using Definite Clauses for Context-Free Grammars	93
	Augmenting the Grammar	97
	Building Structures for Nonterminals	97
	Canned Text Output	98
	Enforcing Constraints	98
	Building a Natural Language Interface to a Database	101
	Limitations	103
3.8	References and Further Reading	104
3.9	Exercises	104
Chapter 4 Searching		113
4.1	Why Search?	113
4.2	Graph Searching	114
	Formalizing Graph Searching	116
4.3	A Generic Searching Algorithm	119
	Costs	123
	Finding Paths	123
4.4	Blind Search Strategies	125
	Depth-First Search	125
	Breadth-First Search	128
	Lowest-Cost-First Search	131
4.5	Heuristic Search	132
	Best-First Search	133
	Heuristic Depth-First Search	134
	A* Search	135
	Summary of Search Strategies	137
4.6	Refinements to Search Strategies	138
	Cycle Checking	138
	Multiple-Path Pruning	139
	Iterative Deepening	140
	Direction of Search	143
	Bidirectional Search	143
	Island-Driven Search	144
	Searching in a Hierarchy of Abstractions	145
	Dynamic Programming	145
4.7	Constraint Satisfaction Problems	147
	Posing a Constraint Satisfaction Problem	148
	Generate-and-Test Algorithms	150
	Backtracking Algorithms	151
	Consistency Algorithms	152
	Hill Climbing	156
	Randomized Algorithms	158
	Beam Search and Genetic Algorithms	161
4.8	References and Further Reading	163
4.9	Exercises	163
Chapter 5 Representing Knowledge		169
5.1	Introduction	169
5.2	Defining a Solution	170
	Quality of Solutions	171
	Decisions and Outcomes	172
	Information Availability and Solution Quality	173
	Computation Cost and Solution Quality	173
5.3	Choosing a Representation Language	174
	Expressiveness and Complexity	175
	Levels of Representations	177
5.4	Mapping from Problem to Representation	180
	Level of Abstraction	180
	Choosing Objects and Relations	182
	Building Flexible Representations	185
	Primitive Versus Derived Relations	188
	Acquiring and Debugging a Knowledge Base	191
5.5	Choosing an Inference Procedure	192
5.6	References and Further Reading	195
5.7	Exercises	196
Chapter 6 Knowledge Engineering		199
6.1	Introduction	199
6.2	Knowledge-Based System Architecture	200
6.3	Meta-Interpreters	202
	Base Languages and Metalanguages	202
	A Vanilla Meta-Interpreter	205
	Expanding the Base Language	207
	Depth-Bounded Search	209
	Delaying Goals	210
6.4	Querying the User	212
	Yes/No Questions	213
	Functional Relations	214
	More General Questions	215
6.5	Explanation	217
	How Did the System Prove a Goal?	217
	Why Did the System Ask a Question?	220
6.6	Debugging Knowledge Bases	221
	Incorrect Answers	222
	Missing Answers	224
	Infinite Loops	226
6.7	A Meta-Interpreter with Search	226
6.8	Unification	230
6.9	References and Further Reading	233
6.10	Exercises	233
Chapter 7 Beyond Definite Knowledge		235
7.1	Introduction	235
7.2	Equality	235
	Allowing Equality Assertions	236
	Axiomatizing Equality	237
	Special-Purpose Equality Reasoning	237
	Unique Names Assumption	238
	Top-Down Procedure for the Unique Names Assumption	239
7.3	Integrity Constraints	241
	Applications of Integrity Constraints	243
	Consistency-Based Diagnosis	243
	Integrity Constraints in Databases	245
	Reasoning with Integrity Constraints	245
	Bottom-Up Implementation	245
	Top-Down Implementation	247
7.4	Complete Knowledge Assumption	248
	Proof Procedures	253
	Bottom-Up Procedure	253
	Top-Down Procedure	255
7.5	Disjunctive Knowledge	256
	Syntax	257
	Semantics	258
	Queries and Answers	259
	Proof Procedures	260
	Bottom-Up Procedure	260
	A Top-Down Proof Procedure	262
	Answer Extraction	266
	Application Examples	267
7.6	Explicit Quantification	268
7.7	First-Order Predicate Calculus	270
	Proof Procedure	272
	Converting to Negation Normal Form	272
	Skolemization	273
	Converting Negation Normal Form to Clausal Form	273
7.8	Modal Logic	275
	Possible Worlds Semantics	275
	Proof Procedures	277
7.9	References and Further Reading	277
7.10	Exercises	278
Chapter 8 Actions and Planning		281
8.1	Introduction	281
	Representing Time	282
	The Delivery Robot World	284
	Relations	284
	Actions	286
	Initial World Description	286
	Derived Relations	286
8.2	Representations of Actions and Change	287
	The STRIPS Representation	288
	The Situation Calculus	290
	The Event Calculus	294
	Comparing the Representations	296
8.3	Reasoning with World Representations	298
	Forward Planning	299
	Planning as Resolution	300
	The STRIPS Planner	301
	Regression	305
	Partial-Order Planning	309
8.4	References and Further Reading	315
8.5	Exercises	316
Chapter 9 Assumption-Based Reasoning		319
9.1	Introduction	319
9.2	An Assumption-Based Reasoning Framework	321
9.3	Default Reasoning	323
	Making Normality Assumptions	323
	Overriding Assumptions	326
	Resolving Competing Arguments	328
	Defining Default Prediction	330
	A Minimal Model Semantics for Default Prediction	332
9.4	Abduction	332
9.5	Evidential and Causal Reasoning	335
	Abduction Followed by Default Reasoning	337
	Axiomatizing Both Causal and Evidential Directions	338
9.6	Algorithms for Assumption-Based Reasoning	339
9.7	References and Further Reading	342
9.8	Exercises	343
Chapter 10 Using Uncertain Knowledge		345
10.1	Introduction	345
10.2	Probability	346
	Random Variables	348
	Semantics of Probability	349
	Axioms for Probability	352
	Conditional Probability	353
	Semantics of Conditional Probability	354
	Bayes' Theorem	356
	Expected Values	359
	Information Theory	360
10.3	Independence Assumptions	361
	Belief Networks	363
	Belief Networks as a Factorization of Probabilities	368
	Reasoning in a Belief Network	369
	Constructing Belief Networks	373
	Implementing Belief Networks	376
	An Algorithm For Evaluating Belief Networks	377
10.4	Making Decisions Under Uncertainty	381
	Utility	384
	Decision Variables	384
	Simple Decisions	385
	Sequential Decisions	385
	Decision Networks	386
	Expected Value of a Policy	389
	The Value of Information	391
	Utility	392
10.5	References and Further Reading	394
10.6	Exercises	395
Chapter 11 Learning		397
11.1	Introduction	397
	Issues	399
11.2	Learning as Choosing the Best Representation	403
	Learning Decision Trees	403
	Searching for a Good Decision Tree	405
	Neural Networks	408
11.3	Case-Based Reasoning	414
11.4	Learning as Refining the Hypothesis Space	416
	Version-Space Learning	418
	Candidate Elimination Algorithm	419
	The Bias Involved in Version Space Learning	420
	Probably Approximately Correct Learning	421
11.5	Learning Under Uncertainty	424
	Bayesian learning of decision trees	426
	Maximum A Posteriori Probability and Minimum Description Length	427
	Averaging Over Models	428
	Naive Bayesian Classifier	429
	Probabilities from Experts	432
11.6	Explanation-Based Learning	433
11.7	References and Further Reading	437
11.8	Exercises	438
Chapter 12 Building Situated Robots		443
12.1	Introduction	443
12.2	Robotic Systems	444
12.3	The Agent Function	446
12.4	Designing Robots	447
12.5	Uses of Agent Models	449
12.6	Robot Architectures	450
12.7	Implementing a Controller	451
	Maintaining State Using the Event Calculus	452
	Implementing a Layered Controller	453
12.8	Robots Modeling the World	457
12.9	Reasoning in Situated Robots	458
12.10	References and Further Reading	459
12.11	Exercises	460
Appendix A Glossary		461
Appendix B The Prolog Programming Language		477
B.1	Introduction	477
B.2	Interacting with Prolog	478
B.3	Syntax	479
	Infix Operators	480
	Lists	481
B.4	Arithmetic	481
B.5	Database Relations	483
	Meta-programming	484
	Global Variables	485
B.6	Returning All Answers	485
B.7	Input and Output	487
B.8	Controlling Search	488
Appendix C Some More Implemented Systems		491
C.1	Bottom-Up Interpreters	491
	Bottom-Up Definite Clause Interpreter	491
	Bottom-Up Negation as Failure Implementation	493
	Bottom-Up Assumable Interpreter	495
C.2	Top-Down Interpreters	498
	Meta-Interpreter for Traversing Proof Trees	498
	Iterative Deepening Definite Clause Interpreter	502
	Querying the User	504
	Meta-Interpreter with Search	505
C.3	Constraint Satisfaction Problem Solver	507
C.4	Neural Network Learner	511
C.5	Partial-Order Planner	515
C.6	Implementing Belief Networks	521
C.7	Robot Controller	529
Bibliography		533
Index		549

List of Figures

1.1	An agent as a black box	8
1.2	An environment for the delivery robot	14
1.3	An electrical environment for the diagnostic assistant	16
2.1	The role of semantics in a representation and reasoning system	26
2.2	Truth table defining and and if	35
2.3	Clauses provided by the user	44
2.4	Bottom-up proof procedure for computing consequences of KB	47
2.5	Top-down definite clause interpreter, without variables	51
2.6	Top-down definite clause interpreter, with variables	56
3.1	An electrical environment with individuals named	71
3.2	Sample database	76
3.3	Example database of student record information	87
3.4	Example database relations about the university	88
3.5	A context-free grammar for a very restricted subset of English	96
3.6	A simple dictionary	97
3.7	Grammar for output of canned English	99
3.8	A grammar that enforces number agreement and builds a parse tree	100
3.9	A grammar that constructs a query	102
3.10	A dictionary for constructing a query	103
4.1	The delivery robot domain with interesting locations labeled	115
4.2	A graph to search for the delivery robot domain	117
4.3	A search graph for an SLD derivation	118
4.4	Problem solving by graph searching	120
4.5	A graph, with cycles, for the delivery robot domain	127
4.6	Summary of search strategies	138
4.7	Iterative deepening searcher	142
4.8	Arc consistency algorithm AC-3	153
4.9	Domain-consistent constraint network for the scheduling problem	154
4.10	A foothill, plateau, and ridge on a contour map	159
4.11	Simulated annealing algorithm	160
4.12	A grid searching problem	165
4.13	A crossword puzzle to be solved with six words	167
5.1	The knowledge representation framework	170
5.2	Solution quality as a function of time for an anytime algorithm	174
5.3	Lattice of sublogics	176
5.4	A hierarchy of representations	178
5.5	A flat semantic network	186
5.6	A structured semantic network	189
6.1	Knowledge-based system architecture	200
6.2	The non-ground representation for the base language	204
6.3	The vanilla definite clause meta-interpreter	205
6.4	A base-level knowledge base for house wiring	206
6.5	A meta-interpreter that uses built-in calls and disjunction	208
6.6	A meta-interpreter for depth-bounded search	209
6.7	A meta-interpreter that collects delayed goals	211
6.8	An ask-the-user interpreter in pseudo-code	213
6.9	A meta-interpreter that builds a proof tree	218
6.10	A meta-interpreter that collects ancestor rules for WHY questions	221
6.11	An algorithm for debugging incorrect answers	223
6.12	An algorithm for debugging missing answers	225
6.13	Meta-interpreter with search	228
6.14	Pseudocode for unification using the ground representation	232
7.1	Two chairs	236
7.2	Bottom-up proof procedure for computing conflicts of T	246
7.3	A meta-interpreter to find conflicts	248
7.4	Bottom-up negation as failure proof procedure	254
7.5	Truth table for the clausal operators	259
7.6	Bottom-up proof procedure for computing prime implicates of KB	261
7.7	Meta-interpreter for general clauses	263
7.8	A proof tree for Example 7.32	265
7.9	Theorem prover with answer extraction	267
7.10	Truth table for predicate calculus operators	272
7.11	Modal logic, their constraints on R, and their axioms	276
7.12	Axioms for L	277
8.1	The delivery robot domain with objects	285
8.2	A simple STRIPS planner that uses STRIPS representation	302
8.3	Finding weakest preconditions using the STRIPS representation	306
8.4	A regression planner	307
8.5	Partial-order planner	311
8.6	Threat handler for the partial-order planner	313
8.7	Partial elaboration of the partial-ordered planning example	314
9.1	Diagrammatic representation of the defaults from Example 9.3	325
9.2	A diagrammatic representation of Example 9.5	328
9.3	Causal network for Example 9.8	336
10.1	Belief network for the electrical domain of Figure 3.1	365
10.2	Belief network for report of leaving of Example 10.16	370
10.3	Belief network for aching limbs of Example 10.17	374
10.4	Decision tree for delivery robot decision of Example 10.20	383
10.5	Decision network for delivery robot decision	387
10.6	Decision network for the alarm problem	388
10.7	Value for alarm decision network	388
10.8	Possible money-utility tradeoff from Example 10.29	394
10.9	Belief network for overhead projector	396
11.1	The learning architecture	398
11.2	Some classification data for learning user preferences	400
11.3	Simple decision tree	404
11.4	Simple decision tree learning program for binary attributes	406
11.5	The sigmoid or logistic function	410
11.6	Simple neural network with one hidden layer	411
11.7	Simulation of the neural net learning algorithm	413
11.8	Candidate elimination algorithm	419
11.9	Posterior distributions of probA based on different samples	425
11.10	Belief network corresponding to a naive Bayesian classifier	430
11.11	A meta-interpreter for explanation-based learning	434
11.12	Example background KB for explanation-based learning	436
12.1	A robotic system and its components	445
12.2	A hierarchical robotic system architecture	451
12.3	A hierarchical decomposition of the delivery robot	454
12.4	A simulation of the robot carrying out the plan of Example 12.4	457
B.1	Syntactic translation between this book and standard Prolog	479
C.1	Forward-chaining assumption-based reasoner	495

Computational Intelligence: A Logical Approach

Computational Intelligence

A Logical Approach

David Poole Alan Mackworth Randy Goebel

Detailed Table of Contents

List of Figures

David Poole
Alan Mackworth
Randy Goebel