A Logic of Knowledge and Belief for Recursive Modeling: A Preliminary Report

Piotr J. Gmytrasiewicz, Edmund H. DurfeeAAAI 1992

Abstract

This paper introduces a personal recursive framework for multiagent modeling, extending classical Kripke structures to allow agents to nest models of other agents within their own possible worlds. By shifting from an external observer's perspective to an agent-centric one, the authors provide a formal, intuitive distinction between knowledge and belief based on an agent's commitment to the truth of its own observations. The framework is demonstrated through the resolution of classic epistemic puzzles and suggests a path toward integrating logical reasoning with decision theory.

Introduction: The Problem of External Perspectives

In multiagent systems, an intelligent agent must reason not just about the state of the world, but about what other agents know and believe. Traditional approaches, such as standard Kripke structures used in modal logic, often adopt an "external" or "God's eye" view. In these models, a single structure contains the possibility relations for all agents, implying that agents can somehow "peek" into each other's internal logic.

A standard Kripke structure representing possible worlds and relations.

The authors argue this is counter-intuitive for autonomous agents. In reality, an agent only has its own personal perspective. It doesn't have access to another agent's true possibility relation; it only has a model of what it thinks the other agent considers possible. The challenge is to create a formal logic that reflects this recursive, subjective nesting of models while still allowing for rigorous deductive reasoning.

Methods: Personal Recursive Kripke Structures

The authors propose Personal Recursive Kripke Structures (RM) to address these limitations. While a standard Kripke structure is defined as $(S, \pi, R)$, where $S$ is a set of worlds, $\pi$ is a truth assignment, and $R$ is a possibility relation, the RM framework introduces a recursive twist.

In this framework, each possible world in an agent's model is "augmented." It contains the physical state of the world plus the Kripke structures that the agent attributes to every other agent in that specific world. This creates a hierarchy where Agent 1 has a model of Agent 2, which in turn contains Agent 2’s model of Agent 1, and so on.

The recursive structure of an agent's view, showing nested models of other agents' perspectives in the context of a hat puzzle.

This nesting allows for a formal distinction between knowledge and belief:

  • Knowledge: Agent 1 "knows" $p$ if $p$ is true in all worlds it considers possible. When Agent 1 says Agent 2 "knows" $p$, it implies a commitment: Agent 1 believes $p$ is true in its own view and believes Agent 2's view is consistent with that truth.
  • Belief: Statements about another agent's "beliefs" do not require this same commitment to truth from the observer's perspective.

Key Insights and Ideas

The most significant shift is moving from a global model to a local, agent-centric model, which better represents the functioning of autonomous robots or software agents. The framework captures the classic philosophical definition of knowledge as "justified true belief." For Agent 1 to say "Agent 2 knows $p$," Agent 1 must believe $p$ is true (the "truth" requirement) and believe Agent 2 has a model supporting $p$ (the "justified belief" requirement).

Furthermore, the authors introduce a "subordination relation" between a parent world and the "child" worlds nested within it. They prove that if this relation is reflexive—meaning an agent's model of another agent is always perfectly accurate—the distinction between knowledge and belief disappears. The model also allows for "introspective" knowledge, where an agent models its own modeling process, providing a path toward self-aware AI reasoning.

Key Results

The power of this logic is demonstrated through its application to the "Three Wise Men" (or "Muddy Children") puzzle. By using a recursive structure developed to the third level, an agent can deductively eliminate possible worlds based on the lack of knowledge reported by other agents. Additionally, the paper suggests that these recursive logical models can serve as the foundation for payoff matrices in game theory, bridging the gap between purely deductive reasoning (logic) and utility-based reasoning (decision theory).

Limitations and Future Work

Despite its promise, the framework faces several challenges:

  • Infinite Recursion: Theoretically, the nesting of "I think that you think..." can go on forever. While finite levels (e.g., level 3) suffice for many puzzles, a general rule for "bottoming out" recursion is needed.
  • Computational Complexity: Building and traversing these recursive trees is computationally expensive, requiring strong heuristics to prevent combinatorial explosions.
  • Formal Completeness: As a preliminary report, the paper lacks a full axiomatization or proofs of completeness and consistency, which remain primary goals for future research.

Summary updated

BibTeX
@inproceedings{gmytrasiewicz1992logic,
  author = {Piotr J. Gmytrasiewicz and Edmund H. Durfee},
  title = {{A Logic of Knowledge and Belief for Recursive Modeling: A Preliminary Report}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1992},
}
Figure