Provably Correct Theories of Action (Preliminary Report)

Fangzhen Lin, Yoav Shoham

Introduction

In the late 1980s, the field of Artificial Intelligence and Knowledge Representation faced a significant crisis of confidence. The primary challenge was the Frame Problem: the difficulty of concisely representing the fact that most properties of the world remain unchanged when an action is performed. While various nonmonotonic logics were proposed to handle "default" reasoning—assuming things stay the same unless specified otherwise—the infamous "Yale Shooting Problem" (YSP) demonstrated that these logics often produced counter-intuitive or mathematically unsound results.

In their 1991 paper, "Provably Correct Theories of Action," Fangzhen Lin and Yoav Shoham sought to move the field beyond debating specific examples. They introduced a rigorous mathematical framework to evaluate theories of action, providing the first formal proof of correctness for nonmonotonic temporal reasoning.

The Problem: A Lack of Formal Criteria

Before Lin and Shoham’s work, researchers evaluated solutions to the Frame Problem based on whether they "seemed to work" on specific scenarios like the YSP. This led to a "splintered controversy" where different logical formalisms were pitted against one another without a common metric for success. The core issue was the lack of a formal criterion to determine if a nonmonotonic theory—one that is succinct and avoids listing every "frame axiom" (e.g., "painting a box does not change its location")—actually captured the intended reality.

Methodology: The Epistemological Yardstick

The authors utilize Situation Calculus as their foundational framework, representing the world through situations, actions, and fluents (time-varying properties). To resolve the controversy, they proposed a three-step methodology centered on the concept of epistemological completeness.

1. Defining Epistemological Completeness

A theory is defined as epistemologically complete if, given a complete description of an initial state, the theory can deduce a complete description of the state resulting from any deterministic action. This provides a clear, functional requirement for any theory of action.

2. The Monotonic Benchmark

Lin and Shoham argue that for any domain, one can write a "monotonic" theory that explicitly includes every single frame axiom. While such a theory is pragmatically inadequate due to its length and complexity (the very problem the Frame Problem seeks to avoid), it serves as an indisputable, "obviously correct" ground truth.

3. Proving Nonmonotonic Equivalence

The authors then use Circumscription—a formal method for minimizing the extent of predicates—to construct a succinct nonmonotonic theory. The goal is to prove that this compact theory is mathematically equivalent to the verbose but correct monotonic benchmark. This approach effectively treats the Frame Problem as an optimization problem: how can we achieve the same deductive power as the monotonic version with a fraction of the axioms?

Key Insights and Formal Results

The paper moves the discourse from heuristic-based reasoning to provable guarantees. Key contributions include:

  • Causal Theories: The authors identify a specific class of "causal theories" consisting of domain constraints and direct effect rules.
  • Theorem 1: This theorem establishes the specific conditions under which a monotonic causal theory is guaranteed to be epistemologically complete.
  • Theorem 2: This is the paper's central result. It proves that a specific application of circumscription (minimizing "abnormality" while allowing certain fluents to vary) perfectly captures the frame axioms of causal theories.
  • Resolution of the YSP: By applying their framework, the authors formally demonstrate that "chronological minimization"—a previously proposed solution to the Yale Shooting Problem—is correct because it is mathematically equivalent to the completed monotonic version of the problem.

Analogy to Database Logic

To explain their approach, the authors draw an analogy to the Closed World Assumption (CWA) in databases. In a flight database, we do not list every flight that does not exist; we simply list the ones that do and assume the rest are false. Similarly, Lin and Shoham argue we should not have to list every property that does not change; we should only list the changes and have a logic that correctly infers the rest.

Limitations and Future Directions

While foundational, this preliminary report acknowledges several boundaries:

  • Determinism: The framework is currently limited to deterministic actions with certain outcomes.
  • Concurrency: The model does not yet account for multiple actions occurring simultaneously.
  • The Qualification Problem: The authors distinguish the Frame Problem from the Qualification Problem (the difficulty of listing all preconditions for an action). Their current work does not solve the latter.

Conclusion

Lin and Shoham’s work provided a much-needed "yardstick" for the AI community. By shifting the focus from suggestive examples to formal equivalence and epistemological completeness, they established a rigorous path forward for the development of provably correct theories of action, bridging the gap between succinct representation and logical accuracy.

Summary updated

Abstract

Provably Correct Theories of Action (Preliminary Report) Fangzhen Lin, Yoav Shoham Research on nonmonotonic temporal reasoning in general, and the Yale Shooting Problem in particular, has suffered from the absence of a criterion against which to evaluate solutions. Indeed, researchers in the area disagree not only on the solutions but also on the problems. We propose a formal yet intuitive criterion by which to evaluate theories of actions, define a monotonic class of theories that satisfy this criterion, and then provide their provably-correct nonmonotonic counterpart. This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.
BibTeX
@inproceedings{lin1991provably,
  author = {Fangzhen Lin and Yoav Shoham},
  title = {{Provably Correct Theories of Action (Preliminary Report)}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1991},
}
Figure