Towards a Logic for Reasoning About Learning in a Changing World

Prakash Panangaden, Mehrnoosh SadrzadehLAM@LICS 2010 · DOI

Abstract

We develop an algebraic modal logic that combines epistemic and dynamic modalities with a view to modelling information acquisition (learning) by automated agents in a changing world. Unlike most treatments of dynamic epistemic logic, we have transitions that "change the state" of the underlying system and not just the state of knowledge of the agents. The key novel feature that emerges is the need to have a way of "inverting transitions" and distinguishing between transitions that "really happen" and transitions that are possible. Our approach is algebraic, rather than being based on a Kripke-style semantics. The semantics are given in terms of quantales. We introduce a class of quantales with the appropriate inverse operations and use it to model toy robot-navigation problems, which illustrate how an agent learns information by taking actions. We discuss how a sound and complete logic of the algebra may be obtained from the positive fragment of PDL with converse.

Introduction

Traditional Dynamic Epistemic Logic (DEL) is highly effective at modeling how information changes (e.g., "I just told you the door is locked"), but it often assumes the underlying world remains static. In real-world applications like robotics, actions such as moving between rooms or picking up objects change the physical state of the system, not just the agent's knowledge. This paper addresses the challenge of modeling "fact-changing" actions within an algebraic framework.

Algebraic Foundations and Methods

The authors depart from standard Kripke semantics (graphs of "possible worlds") in favor of an abstract algebraic approach using quantales and modules. In this framework, actions are modeled as elements of a quantale, while propositions (facts about the world) are treated as a module over that quantale. This allows the logic to treat "performing an action" as a mathematical operation on a state.

Axiomatic foundations of the algebraic modal logic.

The core innovation is the introduction of converse operations. By treating epistemic (knowledge) and dynamic (action) modalities as adjoint pairs, the authors simplify complex proofs. The axioms shown above define how these modalities interact, enabling the logic to reason about what an agent knows after an action by "unfolding" these algebraic adjunctions.

Learning through Navigation

A central problem in learning is the "Map vs. Reality" distinction. An agent might have an internal map of possible moves, but it needs to know which move actually occurred to resolve uncertainty. The authors use a second-order structure where "real" actions act upon "potential" actions, allowing the agent to prune away impossible locations as it moves.

State transition diagram for a navigation task.

To evaluate the logic, the authors use toy benchmarks such as the "5-Room Lab" (Figure 1). In this scenario, a robot moves through a laboratory where some rooms are indistinguishable. By using the converse operation—the mathematical engine for "perfect recall"—the robot can look back at its trajectory to uniquely identify its current location. The authors prove that in grid-based navigation, an agent can always learn its exact position by eventually moving into unique landmarks like corners.

Key Results and Logic ($PDL^{+-}$)

The framework successfully bridges abstract algebra and formal logic. The authors propose a logic based on the positive fragment of Propositional Dynamic Logic (PDL) with converse, proving it is sound and complete for their algebraic structures. This system correctly models how a robot resolves spatial ambiguity by using the "uncertainty reduction axiom" to eliminate impossible past trajectories.

Limitations and Future Work

Currently, the logic is restricted to the "positive fragment," meaning it does not handle standard negation (reasoning about what is not true). Future work aims to extend this to a full probabilistic framework, merging the logic with information theory to measure how much an agent learns in bits. Additionally, the authors suggest applying this "learning by doing" logic to computer security protocols to model how attackers learn secrets through system observation.

Summary updated

BibTeX
@inproceedings{panangaden2010towards,
  author = {Prakash Panangaden and Mehrnoosh Sadrzadeh},
  title = {{Towards a Logic for Reasoning About Learning in a Changing World}},
  booktitle = {LAM@LICS},
  year = {2010},
  doi = {10.29007/8g5j},
}
Figure