Minimal Change and Maximal Coherence: A Basis for Belief Revision and Reasoning about Actions

TL;DR

This paper proposes a unified formal framework for belief revision and reasoning about actions, grounded in the principles of "minimal change" and "maximal coherence." By formalizing these principles, the authors present a theory that elegantly solves the long-standing frame and ramification problems in AI, enabling more robust reasoning in dynamic, real-world scenarios.

What Problem Does This Paper Address?

Artificial Intelligence research has long grappled with two distinct but related challenges: how an agent should update its beliefs when new information arrives (belief revision) and how an agent should reason about the consequences of its actions in a changing world (reasoning about actions). While both areas inherently deal with change, they have largely been studied in isolation. A key difficulty in reasoning about actions is the "frame problem" – determining what doesn't change after an action – and the "ramification problem" – specifying all the indirect effects of an action. Existing approaches often struggle with these issues, particularly in dynamic environments where external factors also influence the world state. This paper aims to bridge this gap by identifying and formalizing common underlying principles that can unify these two areas.

Methods

The authors introduce a formal theory based on a modal logic of time-dependent beliefs, specifically a branching-time temporal logic. They adopt an autoepistemic interpretation of belief, where an agent's beliefs include beliefs about its own beliefs. The core of their approach lies in two fundamental principles:

  • Minimal Change: When an agent's beliefs are updated (either due to new information or an action), the number of beliefs that are added or removed should be minimized.
  • Maximal Coherence: The agent should retain as many of its existing coherent beliefs as possible during a state change.

These principles are formalized using dynamic modal operators for expansion (adding beliefs), contraction (removing beliefs), and revision (a combination of contraction and expansion). The theory of belief revision is then extended to a theory of actions. Actions are defined by preconditions and consequents, and the "action function" selects the closest possible future states that satisfy these conditions while adhering to minimal change and maximal coherence. This approach provides a semantic solution to the frame and ramification problems by implicitly determining what remains unchanged and what new beliefs are formed as a consequence of an action.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Unifying Principles: The paper argues that "minimal change" and "maximal coherence" are not just useful heuristics but fundamental principles that can unify belief revision and reasoning about actions.
  • Elegant Solution to Frame/Ramification Problems: By defining actions in terms of belief revision principles, the theory implicitly handles what changes and what doesn't, and how side-effects propagate, without requiring explicit frame axioms or complex ramification rules.
  • Dynamic World Reasoning: The framework is well-suited for dynamic situations where the world can change due to external factors (e.g., "nature") concurrently with an agent's actions, allowing for reasoning about success or failure based on the interaction of these changes.
  • Autoepistemic Logic Foundation: The use of autoepistemic logic provides a robust way to model an agent's beliefs about its own knowledge, which is crucial for reasoning about dynamic belief states.

Key Results

The paper presents a sound and complete theory of belief revision based on the coherence modal system and coherence D-models. This theory is then used to define a theory of actions that:

  • Provides an inferential and model-theoretic solution to the conceptual frame and ramification problems.
  • Enables reasoning in dynamic situations where the world changes during action execution.
  • Offers a unified framework for both belief revision and action reasoning.

The authors illustrate their theory with an example involving moving blocks, demonstrating how it correctly deduces the resulting state without explicit frame axioms.

Limitations and Future Work

The authors explicitly state that this paper focuses on the conceptual problem and does not address computational efficiency. They acknowledge that their approach, while providing a sound and complete theoretical foundation, does not offer efficient algorithms for computing contractions and revisions. Future work could involve developing such algorithms. They also note that while their theory handles dynamic situations, more complex multi-agent domains with intricate interactions between agents and the environment would require further exploration. The paper also briefly mentions that Shoham's approach provides an algorithm for computing a special class of theories, which is a direction not pursued here.

Summary updated

BibTeX
@inproceedings{1989minimal,
  title = {{Minimal Change and Maximal Coherence: A Basis for Belief Revision and Reasoning about Actions}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1989},
}
Figure