On the Range of Applicability of Baker’s Approach to the Frame Problem

AAAI 1996

TL;DR

This paper investigates the limitations of Baker's influential approach to the frame problem in AI, specifically when applied to action languages. The authors demonstrate that Baker's method is sound and complete for "temporal projection" and "deterministic" action domains, providing a clear characterization of when it can be reliably used.

What Problem Does This Paper Address?

The "frame problem" in artificial intelligence is the challenge of efficiently and accurately representing the fact that most things remain unchanged when an action occurs. If you move a block, the color of the sky doesn't change. Early AI systems struggled to represent this implicitly, leading to combinatorial explosions. Baker's approach, using circumscription, offered a more elegant solution by assuming that only explicitly stated changes occur. However, it was later observed that Baker's method could sometimes lead to unintuitive conclusions. This paper aims to precisely define the conditions under which Baker's approach does yield intuitively correct results, thereby clarifying its range of applicability.

Methods

The authors introduce an action language called AR, which is a subset of a more general language. They then define a translation from AR domains into a circumscriptive theory. This translation involves encoding domain constraints, action effects, and the commonsense law of inertia into logical axioms. The core of their method is to prove the soundness and completeness of this translation for specific classes of domains. Soundness means that if a conclusion is derived using Baker's approach, it's also derivable in the original AR domain. Completeness means that if a conclusion is derivable in the AR domain, it's also derivable using Baker's approach.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Defining "Intuitively Correct": The paper tackles the ambiguity of "intuitively correct" by formalizing it as conclusions entailed by an action language (AR) encoding of the domain. This provides a rigorous basis for evaluating AI reasoning methods.
  • Characterizing Baker's Success: The key insight is identifying two specific classes of domains – "temporal projection" and "deterministic" domains – where Baker's approach is provably sound and complete. This offers practical guidance on when to apply the method.
  • Temporal Projection Domains: These are domains where all value propositions are of the form "initially C" (e.g., the initial state of the world). This restriction simplifies reasoning about future states.
  • Deterministic Domains: In these domains, each action has a single, predictable outcome in any given state. This predictability aligns well with circumscriptive assumptions.
  • The "Two Bus" Example: The paper uses the "Two Bus" example (a non-deterministic domain) to illustrate a case where Baker's approach fails, highlighting the importance of the identified domain restrictions.

Key Results

The paper establishes the following:

  • Soundness: For any finite, executable domain in AR, there exists a model of the translated circumscriptive theory that is "similar" to a model of the AR domain. This implies that conclusions drawn from Baker's approach are valid within the AR framework.
  • Completeness for Temporal Projection Domains: For finite, consistent, executable, temporal projection domains, the translation is complete. This means that any conclusion derivable in the AR domain can be derived using Baker's approach.
  • Completeness for Deterministic Domains: For finite, consistent, deterministic domains, the translation is also complete.

Limitations and Future Work

  • Executability Restriction: The authors acknowledge that their translation is restricted to "executable" domains, where actions always have at least one possible outcome. They suggest that extending this to non-executable domains would require treating the Result function as partial, potentially using "possibility" predicates.
  • Finite Domains: The translation is presented for finite domains (finite fluents, actions, and propositions). Extending this to infinite domains would be a natural next step.
  • Beyond Temporal Projection and Deterministic: The paper's main contribution is defining the boundaries of Baker's applicability. Future work could explore how to adapt or extend Baker's approach to handle more complex, non-deterministic, or non-temporal projection domains, perhaps by modifying the translation or the circumscription policy.

Summary updated

BibTeX
@inproceedings{1996range,
  title = {{On the Range of Applicability of Baker’s Approach to the Frame Problem}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1996},
}
Figure