Default Reasoning, Nonmonotonic Logics, and the Frame Problem

Steve Hanks, Drew V. McDermottAAAI 1986

Abstract

In their seminal 1986 paper, Steve Hanks and Drew McDermott exposed a fundamental flaw in the application of nonmonotonic logics to temporal reasoning. By introducing the "Yale Shooting Problem," they demonstrated that existing frameworks like Circumscription and Default Logic produce multiple, equally valid logical extensions—some of which are profoundly counterintuitive. This work highlighted the necessity of incorporating temporal asymmetry into formal models of common-sense reasoning.

Introduction

During the 1980s, a primary goal in Artificial Intelligence was the formalization of human knowledge using logic. While classical logic is monotonic—meaning new information cannot invalidate previously proven truths—human reasoning is inherently nonmonotonic. We often make default assumptions that are retracted upon learning new facts. A central challenge in this domain is the Frame Problem: the difficulty of efficiently representing what remains unchanged when an action occurs.

The Yale Shooting Problem

To test the efficacy of nonmonotonic logics in solving the frame problem, Hanks and McDermott proposed a simple temporal scenario involving three actions:

  1. Load: A gun is loaded.
  2. Wait: A period of time passes.
  3. Shoot: The gun is fired at a target.

Common sense dictates that if the gun is loaded and nothing happens during the "wait" period, the target should be dead after the "shoot" action. However, formal logics like McCarthy’s Circumscription and Reiter’s Default Logic fail to reach this single conclusion.

Models of the Yale Shooting Problem: (a) first-order axioms, (b) the intended minimal model where the target dies, and (c) the unintended minimal model where the gun mysteriously unloads.

The Failure of Minimization

The core of the issue lies in how these logics "minimize abnormalities" (represented as AB predicates). In the intended model (Figure 1b), the target's death is the only abnormality relative to the state before shooting. In the unintended model (Figure 1c), the gun becoming unloaded during the "wait" action is the abnormality, which allows the target to remain alive after the "shoot" action.

Because the logic treats all abnormalities as equal, it cannot distinguish between the gun spontaneously unloading (an "abnormality" in the past) and the target dying (a consequence in the future). This logical symmetry contradicts our intuitive understanding of temporal flow, where we prefer to keep the past stable.

Key Results and Formal Analysis

The authors proved that standard nonmonotonic frameworks are inadequate for temporal prediction because they generate multiple extensions. As shown in the formal predicates below, the logic produces two competing sets of truths.

Formal logical extensions for the intended model (left) and the unintended model (right).

As seen in Figure 2, the left column represents the intended outcome where the target is dead at state S3. The right column represents the "freak" outcome where an abnormality occurs during the wait period, leading to the target remaining alive. Since both are logically consistent minimal models, the system cannot definitively predict the outcome.

Conclusion

The Yale Shooting Problem served as a wake-up call for the AI community, demonstrating that "logical wishful thinking"—the hope that technical tools would automatically align with human intuition—was insufficient. It suggested that temporal reasoning requires specific constraints, such as chronological minimality, where assumptions about the past are prioritized over predictions about the future.

Summary updated

BibTeX
@inproceedings{hanks1986default,
  author = {Steve Hanks and Drew V. McDermott},
  title = {{Default Reasoning, Nonmonotonic Logics, and the Frame Problem}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1986},
}
Figure