Belief Change in the Context of Fallible Actions and Observations

Aaron Hunter, James P. DelgrandeAAAI 2006

Abstract

Traditional AI models often distinguish between belief update (world changes) and belief revision (new information about a static world). This paper introduces a unified framework for "graded world views" that handles fallible actions and observations simultaneously. By utilizing Spohn-style ranking functions, agents can assign plausibility to both states and actions, enabling them to resolve conflicts and retrospectively revise their beliefs about the past.

Introduction

In real-world scenarios, agents frequently encounter contradictions between their beliefs about past actions and current observations. For instance, an agent might believe they locked a door, only to find it open later. Existing formalisms often struggle with such scenarios because they treat actions as infallible or observations as absolute. This research addresses the gap by providing a formal mechanism to compare the plausibility of actions versus observations over time.

Methodology: Graded World Views

The framework is built upon two pillars: transition systems and plausibility functions. Transition systems model how actions ($A$) transition the world between states ($S$). Plausibility functions, inspired by Wolfgang Spohn’s ranking functions, assign non-negative integers (ranks) to states and actions. A rank of 0 indicates maximum plausibility, while higher ranks represent increasing levels of "surprisingness."

Plausibility Rankings

The core innovation is the Graded World View, which tracks an agent's beliefs through a history of events. To determine the most likely sequence of events, the agent employs an aggregate plausibility function (e.g., a simple sum of ranks). The agent identifies the "cheapest" history—the one with the lowest total rank—as the most plausible.

Figure 1: Plausibility rankings for observations. A rank of 0 denotes high plausibility, while 9 indicates a highly surprising observation.

Key Insights

Unified Currency for Conflict Resolution

By representing both actions and observations as plausibility rankings, the framework creates a "common currency." This allows an agent to weigh a reliable observation against a questionable memory of an action. If an observation has a low rank (high reliability) but contradicts a high-rank (unreliable) action, the agent can retract the action from its subjective history.

Retrospective Revision

Unlike standard update operators that only look forward, this framework allows for retrospective revision. New information received at a later time can fundamentally change what the agent believes occurred at an earlier stage. This is crucial for agents operating in dynamic, uncertain environments where initial perceptions may be flawed.

The authors illustrate the theory using a "cookie example." Bob believes his cookie is safe. However, a reliable source (Trent) informs him it has been bitten. Bob knows Alice is more likely to take a cookie than Eve. Using the framework, Bob calculates the most plausible history.

Figure 2: Plausibility rankings for actions. Here, Alice biting the cookie (rank 1) is considered significantly more plausible than Eve doing so (rank 10) in action profile a1.

Even though he didn't initially believe it, the framework concludes that Alice likely bit the cookie at an earlier time step, demonstrating the power of retrospective revision. Furthermore, the paper proves that this framework generalizes the classic AGM (Alchourrón, Gärdenfors, and Makinson) belief revision theory. Under conditions of high reliability, the graded world view behaves identically to standard revision.

Limitations and Future Work

While the logic is robust, computational complexity remains a concern as history sequences grow. Additionally, the current model assumes independence between action likelihood and world state. Future research aims to incorporate conditional events, handle partial observability, and further axiomatize admissible aggregate functions to define the mathematical properties of "fair" belief combinations.

Summary updated

BibTeX
@inproceedings{hunter2006belief,
  author = {Aaron Hunter and James P. Delgrande},
  title = {{Belief Change in the Context of Fallible Actions and Observations}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2006},
}
Figure