AGM Revision of Beliefs about Action and Time

Marc van Zee, Dragan Doder, Mehdi Dastani, Leendert W. N. van der TorreIJCAI 2015 · OpenReview

Introduction

In artificial intelligence, the ability of an agent to rationally update its knowledge in the face of new, potentially conflicting information is a cornerstone of intelligent behavior. This process, known as Belief Revision, has long been governed by the AGM theory (Alchourrón, Gärdenfors, and Makinson). While AGM provides a robust framework for static propositional logic, real-world applications—such as autonomous robotics or intelligent scheduling—require agents to reason about time and actions.

Bridging the gap between the static nature of AGM and the dynamic requirements of temporal reasoning has been a significant challenge. This paper introduces Parameterized-time Action Logic (PAL), a framework that successfully extends AGM belief revision to temporal settings by employing a finite time horizon.

The Problem of Temporal Belief Revision

The primary obstacle in applying AGM theory to temporal logic is the "infinite models" problem. Standard AGM proofs rely on the ability to order a finite set of possible worlds (models) by preference. However, temporal logics typically involve an infinite future, leading to an infinite number of possible timelines. This mathematical infinity makes traditional "representation theorems"—which prove that revision rules correspond to logical orderings of models—impossible to establish.

Previous attempts to combine temporal reasoning with belief revision often remained "syntactic," meaning they could show that certain rules were followed but lacked the "semantic" proof linking those rules to an underlying model of the world.

Parameterized-time Action Logic (PAL)

To address these challenges, the authors propose PAL. This logic uses atoms indexed by time (e.g., $p_t$ indicates that $p$ is true at time $t$) and incorporates a "do" operator ($do(a)_t$) to represent the execution of actions. Crucially, PAL includes explicit pre- and post-conditions for actions, allowing the agent to reason about the causal structure of the world.

Formal Axiomatization

The logical foundation of PAL is built upon a set of axioms that govern how propositions, actions, and time interact. These include standard modal logic axioms (K, T, 5) and specific axioms for temporal persistence and action effects.

Table of PAL Axioms including propositional tautologies, modal operators, and action-specific rules.

As shown in the table above, axioms A1 and A2 handle the persistence of propositional atoms, while A8 and A9 define the relationship between action preconditions and their subsequent effects.

Methods: The $t$-Bounded Approach

The key innovation of this research is the introduction of $t$-bounded revision. By restricting the agent's focus to a specific, finite time point $t$, the authors effectively bound the model space. This finiteness allows for the application of standard propositional revision tools to a temporal domain.

This approach enables the proof of two critical representation theorems:

  1. Katsuno-Mendelzon (KM): Demonstrates that revising a belief set is semantically equivalent to selecting the "closest" possible world according to a preference ordering.
  2. Darwiche-Pearl (DP): Extends this logic to iterated revision, ensuring that an agent remains rational even after multiple sequential updates to its beliefs.

Semantic Grounding and Model Representation

A key contribution of this work is providing the semantic link between logical postulates and model-based reasoning. In PAL, different possible timelines are represented as models.

Comparison of three PAL models illustrating different action sequences and their temporal consequences.

The figure above illustrates how different models represent distinct possibilities. For instance, an agent might consider a world where action $a$ occurs ($ar{m}_1$) versus one where a choice between $a$ and $b$ is available ($ar{m}_2$). By learning new information, the agent can re-evaluate the plausibility of these different timelines.

Key Results and Insights

The authors successfully provided a full axiomatization of PAL, proving it to be both sound and strongly complete. By adapting the KM and DP theorems, they have established a rigorous mathematical bridge between temporal action logics and the mainstream belief revision community.

Furthermore, the logic supports "optimistic planning." An agent can maintain a belief that an action will occur in the future even if its preconditions are not currently met, provided it believes they will be met by the time the action is scheduled.

Limitations and Future Directions

While PAL represents a significant step forward, several challenges remain:

  • The Frame Problem: The current framework lacks "frame axioms" to explicitly handle non-change (e.g., ensuring a property remains true if no action affects it).
  • BDI Integration: Future work aims to extend PAL to include intentions and goals, moving toward a full Belief-Desire-Intention (BDI) model.
  • Infinite Horizons: Finding a way to handle truly infinite temporal revision without the $t$-bounding constraint remains an open theoretical challenge.

In conclusion, PAL provides a solid formal foundation for agents that must navigate a changing world, allowing them to update their beliefs about the past, present, and future in a mathematically sound and rational manner.

Summary updated

Abstract

The AGM theory of belief revision is based on propositional belief sets. In this paper we develop a logic for revision of temporal belief bases, containing expressions about temporal propositions (tomorrow it will rain), possibility (it may rain tomorrow), actions (the robot enters the room) and pre- and post-conditions of these actions. We prove the Katsuno-Mendelzon and the Darwiche-Pearl representation theorems by restricting the logic to formulas representing beliefs up to certain time. We illustrate our belief change model through several examples.
BibTeX
@inproceedings{zee2015agm,
  author = {Marc van Zee and Dragan Doder and Mehdi Dastani and Leendert W. N. van der Torre},
  title = {{AGM Revision of Beliefs about Action and Time}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
  url = {https://openreview.net/forum?id=HyW_e4fuZB},
}
Figure