Solving the Frame Problem

A Mathematical Investigation of the Common Sense Law of Inertia

Murray Shanahan

Contents

Introduction

  1. Why Is the Frame Problem Important?
  2. The Role of Representation in Artificial Intelligence
  3. The Limits of the Representational Approach
  4. The Role of Representation in Robotics
  5. The Role of Logic in Knowledge Representation

Chapter One

What Is the Frame Problem?

  1. Describing the Non-Effects of Actions
  2. Introducing the Situation Calculus
  3. Frame Axioms
  4. Towards a Solution
  5. Making Frame Axioms More Compact
  6. Criteria for a Solution to the Frame Problem
  7. Elaboration Tolerance
  8. Non-Monotonic Solutions
  9. The Common Sense Law of Inertia
  10. Monotonic Versus Non-Monotonic Solutions
  11. Explanations, Qualifications and Narratives
  12. Philosophical Reflections

Chapter Two

Logical Foundations

  1. The Language of Predicate Calculus
  2. The Semantics of Predicate Calculus
  3. Many-Sorted Predicate Calculus
  4. Second-Order Predicate Calculus
  5. The Ontology and Language of Situation Calculus
  6. Situation Calculus Formulae
  7. Situations and the Result Function
  8. The Limitations of the Situation Calculus
  9. Default Reasoning
  10. Circumscription
  11. More Complicated Circumscription Policies

Chapter Three

Towards a Non-Monotonic Solution

  1. Formalising the Common Sense Law of Inertia
  2. An Example that Works
  3. The Hanks-McDermott Problem
  4. Variations on Hanks and McDermottÕs Theme
  5. Differences in Situation Calculus Style
  6. The Importance of the Hanks-McDermott Problem

Chapter Four

Chronological Minimisation

  1. The Yale Shooting Scenario in Default Logic
  2. Generating Extensions in Default Logic
  3. The Directionality of Time
  4. Formalising Chronological Minimisation
  5. Chronological Minimisation and the Yale Shooting Scenario
  6. Chronological Minimisation and the Stolen Car Scenario
  7. Improving Chronological Minimisation

Chapter Five

Causal Minimisation

  1. Eliminating Spontaneous Change
  2. Causal Minimisation and the Yale Shooting Scenario
  3. The Principles of Separation and Directionality
  4. Actions with Context-Dependent Effects
  5. Causal Minimisation and Explanation
  6. Ramifications and Causal Minimisation

Chapter Six

Introducing State-Based Minimisation

  1. Varying the Result Function
  2. Adding an Existence-of-Situations Axiom
  3. The Need for Domain Closure Axioms
  4. A Universal Existence-of-Situations Axiom

Chapter Seven

Generalising State-Based Minimisation

  1. Logical Prerequisites
  2. First-Order Formalisations
  3. Applying State-Based Minimisation
  4. State-Based Minimisation and Explanation
  5. A Second-Order Existence-of-Situations Axiom
  6. General Theorems about State-Based Minimisation

Chapter Eight

Tailor-Made Techniques

  1. Explanation Closure Axioms
  2. Ramifications and Explanation Closure
  3. Automatically Derived Frame Axioms
  4. Successor State Axioms
  5. Ramifications and Successor State Axioms
  6. The Language A

Chapter Nine

Narratives in the Situation Calculus

  1. The Need for Narratives
  2. Arboreality and Existence-of-Situations
  3. Associating a Time with Each Actual Situation
  4. Two Theorems of Circumscription
  5. Two Separation Theorems for Narratives
  6. Associating a Situation with Each Time Point
  7. Comparing the Approaches

Chapter Ten

Incomplete Narratives and Concurrent Actions

  1. Over-Zealous Event Occurrence Minimisation
  2. Context-Sensitive Event Occurrence Minimisation
  3. A Worked Example of Narratives as Contexts
  4. Concurrent Actions in the Situation Calculus
  5. Narratives with Concurrent Actions

Chapter Eleven

The Foundations of Logic Programming

  1. The Basis of Logic Programming
  2. SLD-Resolution
  3. A Logic Programming System
  4. Logic Programming and the Situation Calculus
  5. Negation as Failure
  6. The Semantics of Negation-as-Failure

Chapter Twelve

Logic Programs for Reasoning about Action

  1. Negation-as-Failure and the Situation Calculus
  2. Situation Calculus Semantic Issues
  3. Knowledge Representation Issues
  4. Introducing the Event Calculus
  5. Applying the Original Event Calculus

Chapter Thirteen

Simplifying and Extending the Event Calculus

  1. A Simplified Event Calculus
  2. Event Calculus Semantic Issues
  3. Representing Continuous Change in the Event Calculus
  4. Triggered Events and Continuous Change

Chapter Fourteen

A Circumscriptive Calculus of Events

  1. The Simplified Event Calculus with Circumscription 257
  2. States
  3. A Calculus of Events
  4. The Blocks World
  5. A Separation Theorem for the Calculus
  6. The Yale Shooting Scenario

Chapter Fifteen

Applying the Calculus of Events

  1. Ramifications
  2. Non-Deterministic Effects
  3. Releasing Fluents
  4. Concurrent Events
  5. Continuous Change

Chapter Sixteen

Forced Separation

  1. Eliminating Existence-of-Situations Axioms
  2. The Intuition Behind Forced Separation
  3. An Event Calculus Using Forced Separation
  4. Continuous Change and Triggered Events

Chapter Seventeen

Explanation: The Assimilation of Observations

  1. Explanation in the Situation Calculus
  2. Towards a Narrative-Based Approach
  3. Narratives and Explanation
  4. A Hard Example for State-Based Minimisation
  5. A Hard Example for the Deductive Approach
  6. The Abductive Approach
  7. Abduction and Knowledge Assimilation
  8. Non-Determinism and the Abductive Approach
  9. Abduction and the Circumscriptive Event Calculus

Epilogue: Is the Frame Problem Solved?

Bibliography

Appendix A: Proof of Theorem 9.7.5

Appendix B: Proof of Theorem 14.4.2

Appendix C: Temporal Projection Algorithms

Appendix D: Proof of Theorem 15.5.3

Index