Shanahan Murray. Solving the frame problem: a mathematical investigation of the common sense law of inertia

The MIT Press, 1997 — 407 p. — (Artificial intelligence (Cambridge, Mass.)) — ISBN: 9780262193849, 0-262-19384-1, 305-313-325-3, 272-273-315-3.In 1969, John McCarthy and Pat Hayes uncovered a problem that has haunted the field of artificial intelligence ever since - the frame problem. The problem arises when logic is used to describe the effects of actions and events. Put simply, it is the problem of representing what remains unchanged as a result of an action or event. Many researchers in artificial intelligence believe that its solution is vital to the realization of the field's goals. Solving the Frame Problem presents the various approaches to the frame problem that have been proposed over the years. The author presents the material chronologically - as an unfolding story rather than as a body of theory to be learned by rote. There are lessons to be learned even from the dead ends researchers have pursued, for they deepen our understanding of the issues surrounding the frame problem. In the book's concluding chapters, the author offers his own work on event calculus, which he claims comes very close to a complete solution to the frame problem.What Is the Frame Problem?
Describing the Non-Effects of Actions.
Introducing the Situation Calculus.
Frame Axioms.
Towards a Solution.
Making Frame Axioms More Compact.
Criteria for a Solution to the Frame Problem.
Elaboration Tolerance.
Non-Monotonic Solutions.
The Common Sense Law of Inertia.
Monotonic Versus Non-Monotonic Solutions.
Explanations, Qualifications, and Narratives.
Philosophical Reflections.
Logical Foundations
The Language of Predicate Calculus.
The Semantics of Predicate Calculus.
Many-Sorted Predicate Calculus.
Second-Order Predicate Calculus.
The Ontology and Language of Situation Calculus.
Situation Calculus Formulae.
Situations and the Result Function.
The Limitations of the Situation Calculus.
Default Reasoning.
Circumscription.
More Complicated Circumscription Policies.
Towards a Non-Monotonic Solution
Formalizing the Common Sense Law of Inertia.
An Example that Works.
The Hanks-McDermott Problem.
Variations on Hanks and McDermott’s Theme.
Differences in Situation Calculus Style.
The Importance of the Hanks-McDermott Problem.
Chronological Minimisation
The Yale Shooting Scenario in Default Logic.
Generating Extensions in Default Logic.
The Directionality of Time.
Formalizing Chronological Minimisation.
The Yale Shooting Scenario.
The Stolen Car Scenario.
Improving Chronological Minimisation.
Causal Minimisation
Eliminating Spontaneous Change.
The Yale Shooting Scenario.
The Principles of Separation and Directionality.
Actions with Context-Dependent Effects.
Causal Minimisation and Explanation.
Ramifications and Causal Minimisation.
Introducing State-Based Minimisation
Varying the Result Function.
Adding an Existence-of-Situations Axiom.
The Need for Domain Closure Axioms.
A Universal Existence-of-Situations Axiom.
Generalising State-Based Minimisation
Logical Prerequisites.
First-Order Formalisations.
Applying State-Based Minimisation.
State-Based Minimisation and Explanation.
A Second-Order Existence-of-Situations Axiom.
General Theorems about State-Based Minimisation.
Tailor-Made Techniques
Explanation Closure Axioms.
Ramifications and Explanation Closure.
Automatically Derived Frame Axioms.
Successor State Axioms.
Ramifications and Successor State Axioms.
The Language.
Narratives in the Situation Calculus
The Need for Narratives.
Arboreality and Existence-of-Situations.
Associating a Time with Each Actual Situation.
Two Theorems of Circumscription.
Two Separation Theorems for Narratives.
Associating a Situation with Each Time Point.
Comparing the Approaches.
Incomplete Narratives and Concurrent Actions
Over-Zealous Event Occurrence Minimisation.
Context-Sensitive Event Occurrence Minimisation.
A Worked Example of Narratives as Contexts.
Concurrent Actions in the Situation Calculus.
Narratives with Concurrent Actions.
The Foundations of Logic Programming
The Basis of Logic Programming.
SLD-Resolution.
A Logic Programming System.
Logic Programming and the Situation Calculus.
Negation as Failure.
The Semantics of Negation-as-Failure.
Logic Programs for Reasoning about Action
Negation-as-Failure and the Situation Calculus.
Situation Calculus Semantic Issues.
Knowledge Representation Issues.
Introducing the Event Calculus.
Applying the Original Event Calculus.
Simplifying and Extending the Event Calculus
A Simplified Event Calculus.
Event Calculus Semantic Issues.
Representing Continuous Change in the Event Calculus.
Triggered Events and Continuous Change.
A Circumscriptive Calculus of Events
The Simplified Event Calculus with Circumscription.
States.
A Calculus of Events.
The Blocks World.
A Separation Theorem for the Calculus.
The Yale Shooting Scenario.
Applying the Calculus of Events
Ramifications.
Non-Deterministic Effects.
Releasing Fluents.
Concurrent Events.
Continuous Change.
Forced Separation
Eliminating Existence-of-Situations Axioms.
The Intuition Behind Forced Separation.
An Event Calculus Using Forced Separation.
Continuous Change and Triggered Events.
Explanation: The Assimilation of Observations
Explanation in the Situation Calculus.
Towards a Narrative-Based Approach.
Narratives and Explanation.
A Hard Example for State-Based Minimisation.
A Hard Example for the Deductive Approach.
The Abductive Approach.
Abduction and Knowledge Assimilation.
Non-Determinism and the Abductive Approach.
Abduction and the Circumscriptive Event Calculus.
Epilogue: Is the Frame Problem Solved?Proof of Theorems
Temporal Projection Algorithms.