Modeling Belief in Dynamic Systems, Part I: Foundations

Nir Friedman, Joseph Y. Halpern

Abstract

In the field of artificial intelligence, agents must maintain and update internal models of the world as they receive new information. This paper, the first in a foundational series by Nir Friedman and Joseph Halpern, introduces a rigorous semantic framework for belief dynamics. By unifying modal logic with a generalized theory of uncertainty known as "plausibility," the authors bridge the gap between rule-based logic and probabilistic reasoning. The framework provides a unified account of how agents should update their beliefs in both static and changing environments, utilizing "conditioning" as the core mechanism for rational change.

Introduction

How should an autonomous agent change its mind? In AI research, this question has historically been split into two distinct domains: Belief Revision, which concerns how an agent incorporates new information about a static world (e.g., correcting a mistake about a past event), and Belief Update, which concerns tracking a world that is actively changing (e.g., observing a car being moved).

Existing approaches, such as the influential AGM (Alchourrón, Gärdenfors, and Makinson) postulates, were primarily axiomatic—they defined how beliefs should behave without providing a deep semantic model of why. Furthermore, these models often struggled to integrate multiple agents or the explicit passage of time. Friedman and Halpern address these gaps by providing a semantic foundation that handles knowledge, belief, and temporal dynamics simultaneously.

The Plausibility Framework

The core of the authors' approach is the Plausibility Measure, a significant generalization of probability theory. While standard probability assigns a numerical value between 0 and 1 to an event, a plausibility measure assigns values from a partially ordered set. This allows the framework to represent qualitative reasoning (e.g., "Situation A is more plausible than Situation B") without requiring the precise numerical data that probability often demands.

Within this framework, belief is not treated as a primitive concept. Instead, it is derived from the interaction between knowledge and plausibility: an agent believes a proposition $\phi$ if they know that $\phi$ is more plausible than its negation, $\neg\phi$. This allows the authors to leverage standard Kripke structures (possible-worlds models) to represent knowledge while using plausibility to rank those worlds.

Dynamics and Conditioning

To model how beliefs evolve, the authors adopt the "interpreted systems" framework. In this model, the world consists of a set of "runs" (histories) over time. At any specific point in time, an agent’s local state determines which runs they consider possible.

The mechanism for belief change is conditioning. When an agent receives a new observation, they condition their prior plausibility measure on that information. This process effectively "zooms in" on the possibilities consistent with the observation while maintaining the relative plausibility of the remaining states. The authors argue that conditioning represents the most natural form of "minimal change," as it preserves as much of the agent's prior ranking as logically possible.

Key Results and Complexity

The paper provides several significant theoretical contributions:

  • Axiomatization: The authors provide complete axiomatizations for languages that combine knowledge, plausibility, and temporal operators (such as the "next" operator, $\bigcirc$).
  • The KD45 Connection: They demonstrate that under natural assumptions of normality and consistency, the resulting belief operator automatically satisfies the KD45 axioms—the standard logical framework for representing rational belief.
  • Complexity Analysis: The paper maps the computational landscape of this logic. While the general reasoning problem is EXPTIME-complete, the authors show that for a single agent with consistency properties, the complexity can be reduced to co-NP-complete, making it more tractable for certain AI applications.
  • Circuit Diagnosis: To illustrate the practical utility of the logic, the authors apply it to a "full adder" circuit diagnosis example, showing how an agent can identify faulty components over time based on changing inputs and outputs.

Discussion and Limitations

As a foundational work, this paper establishes the "what" and "why" of belief dynamics, leaving specific mappings to existing postulates (like AGM and KM) for Part II. However, the authors identify several areas for future exploration:

  1. Synchrony and Memory: The current analysis largely assumes "perfect recall" and "synchrony" (agents know the current time). Relaxing these to model agents that forget or are uncertain about the passage of time remains a challenge.
  2. Infinite State Spaces: While the framework supports infinite worlds, the complexity results are primarily focused on finite models.
  3. Unification: The paper successfully argues that revision and update are not fundamentally different processes, but rather different applications of conditioning on a prior plausibility measure.

By providing a unified semantic language for uncertainty and change, Friedman and Halpern offer a robust alternative to purely axiomatic or purely probabilistic models of artificial intelligence.

Summary updated

BibTeX
@article{friedman1997modeling,
  author = {Nir Friedman and Joseph Y. Halpern},
  title = {{Modeling Belief in Dynamic Systems, Part I: Foundations}},
  journal = {Artificial Intelligence},
  year = {1997},
  doi = {10.1016/s0004-3702(97)00040-4},
}
Figure