Non-omniscient belief as context-based reasoning

Fausto Giunchiglia, Luciano Serafini, Enrico Giunchiglia, Marcello Frixione1993

TL;DR

This paper introduces a novel framework for modeling non-omniscient beliefs in multi-agent systems. Instead of a single monolithic theory, it proposes representing each agent's beliefs as distinct logical theories (contexts), managed by a central "computer" theory. This approach allows for a more nuanced and compositional understanding of how agents reason about their own and others' beliefs, particularly when they don't possess complete knowledge.

What Problem Does This Paper Address?

Traditional approaches to formalizing belief in artificial intelligence often rely on a single, unified logical theory. This theory might represent the "true" state of the world or a single reasoner's perspective. When modeling beliefs, especially in multi-agent systems, this often leads to the assumption of "logical omniscience" – agents are assumed to believe all logical consequences of their beliefs. This is unrealistic, as real agents have limited reasoning capabilities, incomplete knowledge, and finite resources. The paper addresses the challenge of formally capturing these "non-omniscient" aspects of belief, where agents don't necessarily believe everything that logically follows from their initial beliefs.

Methods

The core of the paper's contribution is the Multi-Context (MC) system framework. In this framework:

  • Agents as Theories (Contexts): Each agent's beliefs are modeled as a distinct axiomatic formal system, referred to as a "context." This context consists of a language and a set of theorems (beliefs).
  • The Computer as a Meta-Theorist: A central "computer" context acts as a meta-reasoner. It doesn't simulate agents but rather reasons about their beliefs by having theories that represent the agents' theories.
  • Bridge Rules: Special "bridge rules" connect these contexts. These rules allow the computer context to infer beliefs about an agent's beliefs based on what is derivable within the agent's own context, and vice-versa. This is crucial for modeling how agents' beliefs are represented and reasoned about.
  • Classification of Non-Omniscience: The framework provides a systematic way to classify different forms of non-logical omniscience. These are categorized based on incompleteness in the agent's language (e.g., not knowing certain propositions) or its deductive rules (e.g., not being able to derive all logical consequences).
  • Compositionality: Complex forms of non-omniscience can be "constructed" by composing these basic forms within the MC system structure.

The paper introduces several specific MC system instantiations:

  • MBI: Models an ideal, logically omniscient reasoner.
  • MBIE: Extends MBI to model an agent with both ideal (implicit) and realized (explicit) beliefs.
  • MBIE(n): Generalizes MBIE to model an agent with multiple "frames of mind" (contexts), allowing for localized reasoning.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Decoupling Belief Representation: The most significant insight is the move away from a single theory to multiple, interacting contexts. This allows for a much finer-grained and modular representation of beliefs.
  • "Theory of the Computer": The idea of a central "computer" theory that reasons about agent theories, rather than simulating them, is a powerful abstraction. It avoids the complexity of embedding all agent knowledge within a single system.
  • Compositional Non-Omniscience: The framework's ability to classify and combine basic forms of non-omniscience (e.g., lack of awareness, incomplete deduction rules) into more complex scenarios is a major advantage for modeling realistic agents.
  • Localization of Reasoning: The MC system naturally supports localized reasoning. Properties of an agent are imposed on its specific context, making formalizations more intuitive and manageable.

Key Results

The paper primarily presents a formal framework and a classification of non-omniscient beliefs. It demonstrates how this framework can:

  • Classify Basic Forms of Non-Omniscience: The paper systematically categorizes incompleteness in language and deduction rules.
  • Model Ideal and Realized Beliefs: The MBIE system shows how to distinguish between an agent's implicit (idealized) and explicit (realized) beliefs.
  • Support Localized Reasoning: The MBIE(n) system illustrates how to model agents with multiple, interconnected "frames of mind," reflecting how humans often compartmentalize information.
  • Reconstruct Existing Logics: The authors suggest that their framework can uniformly reconstruct various existing formalisms for knowledge and belief (e.g., those by Fagin & Halpern, Levesque, Konolige).

While the paper focuses on representational issues rather than empirical results, it provides formal definitions and proofs for key properties of its proposed systems (e.g., Proposition 3.1, Proposition 3.2, Theorem 4.1, Theorem 4.2).

Limitations and Future Work

  • Focus on Representation: The paper acknowledges that it doesn't delve deeply into computational complexity or provide extensive empirical analysis of the efficiency gains from this approach, although it's intuitively suggested.
  • Nested Belief: The authors mention that they do not consider nested belief (beliefs about beliefs about beliefs) in this version of the framework.
  • Semantics: While a formal definition of deduction is provided, a detailed semantic account is deferred to other work.
  • Future Work: The paper suggests exploring more complex interactions between contexts, investigating the computational aspects, and further formalizing the relationship between explicit and implicit beliefs. The authors also hint at the potential for this framework to model other propositional attitudes beyond belief.

Summary updated

Abstract

This paper describes a general framework for the formalization of monotonic reasoning about belief in a multiagent environment. The agents* beliefs are modeled as logical theories. The reasoning about their beliefs is formalized in still another theory, which we call the theory of the computer. The framework is used to model non-omniscient belief and shown to have many advantages. For instance, it allows for an exhaustive classification of the "basic " forms of non logical omniscience and for their "composition" into the structure of the system modeling multiagent omniscient belief. 1 The approach This paper describes a general framework for the formalization of monotonic reasoning about belief in a multiagent environment. The most common solution is to take a first order (propositional) theory, to extend it using a set of modal operators, and to take as meaning that an agent believes A (see for instance [Halpern and Moses, 1985]). There is only one theory of the world, however this theory proves facts about the agents ' beliefs. According to a first interpretation, this theory is taken to model things how they really are. It is therefore a finite (and possibly incomplete) presentation of what is true in the world, and the fact that B i A is a theorem means that it is, in fact, the case that a i believes A. According to another interpretation, this theory is taken to be the perspective that a generic reasoner has of the world. It is therefore a finite presentation of the reasoner's beliefs, and the fact that A is a theorem means that the reasoner believes that believes A. Once one accepts the second interpretation (as we do), a mechanized theory is naturally taken as representing the beliefs of the computer where it is implemented. Moreover, in the case of multiagent belief, a further step is to have, together with the theory of the computer, one theory (at least, see later) for each agent.
BibTeX
@misc{giunchiglia1993non,
  author = {Fausto Giunchiglia and Luciano Serafini and Enrico Giunchiglia and Marcello Frixione},
  title = {{Non-omniscient belief as context-based reasoning}},
  year = {1993},
}
Figure