Beyond Minimizing Change

AAAI 1997

TL;DR

This paper introduces a novel methodology for comparing non-monotonic reasoning approaches to action, focusing on "elaboration tolerance" – how easily new information can be integrated. They propose a new assumption, "minimizing preconditions," which, unlike the traditional "frame assumption," naturally allows for both adding effects and adding preconditions to actions, offering a more flexible way to model real-world scenarios.

What Problem Does This Paper Address?

Reasoning about how the world changes over time, especially when dealing with incomplete information, is a fundamental challenge in AI. This is often framed as the "frame problem": how to represent what doesn't change when an action occurs, without explicitly listing every unchanged fact. Traditional approaches, like the "frame assumption," focus on minimizing changes (effects) and implicitly assume that listed preconditions are sufficient. However, this makes it difficult to add new preconditions later without re-writing existing axioms. The authors highlight that real-world reasoning often involves not just adding new effects but also discovering and adding new preconditions for actions. Existing non-monotonic logics struggle with this flexibility, leading to brittle representations.

Methods

The authors propose a new way to formalize reasoning about action within the situation calculus, a standard logical framework for representing change. Their core contribution is a new non-monotonic assumption, which they call the "precondition problem."

Instead of minimizing changes (effects) as the primary goal, they propose minimizing the number of preconditions required for an action to have an effect. This is achieved using circumscription, a technique for formalizing non-monotonic reasoning.

Specifically, they introduce two minimization principles:

  1. Minimizing Effects: This is similar to the standard frame assumption, where we aim to have as few effects as possible.
  2. Minimizing Preconditions: This is their novel contribution. It assumes that the listed preconditions for an action are necessary, not necessarily sufficient. This allows for the addition of new preconditions by simply adding new clauses that state when an action fails to have an effect.

They formalize this by using circumscription to minimize both the occurrences of action effects and the conditions under which actions fail to have their intended effects. The key insight is that by framing the problem as minimizing preconditions, they naturally allow for the addition of new preconditions, which is a common and necessary aspect of real-world reasoning.

Datasets

Not discussed in the paper. The paper focuses on formalizing reasoning principles and uses well-known benchmark problems for illustration.

Key Insights and Ideas

  • Elaboration Tolerance is Key: The paper argues that the true measure of a non-monotonic reasoning system for action is its "elaboration tolerance" – how easily it can incorporate new information.
  • Preconditions are Not Always Sufficient: The traditional "frame assumption" implicitly treats listed preconditions as sufficient. The authors show that treating them as necessary is more flexible and aligns better with how we often discover new constraints in the real world.
  • Minimizing Preconditions is Natural: The paper demonstrates that assuming actions have as few preconditions as possible is a natural and powerful way to reason about change, allowing for the addition of new constraints without breaking existing models.
  • Circumscription for Flexibility: Circumscription, a powerful non-monotonic logic tool, is effectively used to formalize this new "precondition minimization" principle, enabling the addition of both effects and preconditions.

Key Results

The paper demonstrates that their proposed methodology, based on minimizing preconditions, can naturally handle:

  • Adding Effects: Similar to existing approaches.
  • Adding Preconditions: This is the significant advancement. They show how their formalism allows for the addition of new preconditions, which is difficult or impossible with traditional effect axiom-based approaches.
  • Standard Benchmark Problems: They show their approach can solve classic problems like the Yale Shooting Problem.
  • New Problems: They also illustrate how their method can address problems that specifically require the addition of preconditions, which are challenging for prior methods.

Limitations and Future Work

  • Deterministic Change: The paper primarily focuses on deterministic change, where the outcome of an action is fully determined by the current state. Extending this to non-deterministic actions would be a natural next step.
  • Language Simplification: While they use a simplified language for clarity, exploring the application of their ideas in richer logical frameworks could be beneficial.
  • Efficiency: While the formalization is sound, the computational efficiency of their circumscription-based approach for large-scale problems is not discussed and remains an open question.

The authors suggest that considering "elaboration tolerance" is a valuable tool for evaluating and developing non-monotonic reasoning systems, and their work provides a concrete example of how this can be achieved by shifting the focus from minimizing effects to minimizing preconditions.

Summary updated

BibTeX
@inproceedings{1997beyond,
  title = {{Beyond Minimizing Change}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1997},
}
Figure