Alan Mackworth

Randy Goebel

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 | |

97 | ||

98 | ||

98 | ||

101 | ||

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 |

123 | ||

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 | |

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 | |

143 | ||

144 | ||

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 | |

237 | ||

237 | ||

Unique Names Assumption | 238 | |

239 | ||

7.3 | Integrity Constraints | 241 |

Applications of Integrity Constraints | 243 | |

243 | ||

245 | ||

Reasoning with Integrity Constraints | 245 | |

245 | ||

247 | ||

7.4 | Complete Knowledge Assumption | 248 |

Proof Procedures | 253 | |

253 | ||

255 | ||

7.5 | Disjunctive Knowledge | 256 |

Syntax | 257 | |

Semantics | 258 | |

259 | ||

Proof Procedures | 260 | |

260 | ||

262 | ||

266 | ||

Application Examples | 267 | |

7.6 | Explicit Quantification | 268 |

7.7 | First-Order Predicate Calculus | 270 |

Proof Procedure | 272 | |

272 | ||

273 | ||

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 | |

284 | ||

286 | ||

286 | ||

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 | |

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 | |

354 | ||

356 | ||

Expected Values | 359 | |

Information Theory | 360 | |

10.3 | Independence Assumptions | 361 |

Belief Networks | 363 | |

368 | ||

369 | ||

373 | ||

Implementing Belief Networks | 376 | |

377 | ||

10.4 | Making Decisions Under Uncertainty | 381 |

384 | ||

384 | ||

385 | ||

385 | ||

Decision Networks | 386 | |

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 | |

405 | ||

Neural Networks | 408 | |

11.3 | Case-Based Reasoning | 414 |

11.4 | Learning as Refining the Hypothesis Space | 416 |

Version-Space Learning | 418 | |

419 | ||

420 | ||

Probably Approximately Correct Learning | 421 | |

11.5 | Learning Under Uncertainty | 424 |

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 |

484 | ||

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 |

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