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.
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.
Key Results: The Cookie Example
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.
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