Towards Epistemic-Doxastic Planning with Observation and Revision

Thorsten Engesser, Andreas Herzig, Elise PerrotinAAAI 2024 · DOI

Abstract

This paper introduces a lightweight logic fragment called REDA (Repetition-Free Epistemic-Doxastic Atoms) designed to enable AI agents to reason about knowledge and beliefs—including false beliefs—in multi-agent environments. By restricting the language to repetition-free atoms, the authors reduce complex epistemic reasoning to propositional logic, achieving a planning complexity of PSPACE-complete, equivalent to standard classical planning. The framework is validated through the formalization of the Sally-Anne task, demonstrating its ability to handle second-order beliefs and belief revision.

1. Introduction

In multi-agent systems, such as human-robot interaction, agents require a "Theory of Mind" to reason about the mental states of others. While Dynamic Epistemic Logic (DEL) is the standard formalism for this, it is often computationally intractable or undecidable. Existing lightweight alternatives frequently fail to model belief revision: the process where an agent updates a false belief upon observing a contradiction. This paper addresses this gap by providing a formalism that handles second-order false beliefs (e.g., "Anne believes that Sally believes the marble is in the basket") while remaining computationally efficient.

2. The REDA Framework

The core of the REDA fragment lies in its specialized operators and structural restrictions:

  • Epistemic-Doxastic Operators: Instead of standard modal operators, REDA uses $TBA_i\phi$ (True Belief), indicating agent $i$ has a correct belief about $\phi$, and $MBA_i\phi$ (Mere Belief), indicating the agent holds a belief that may or may not be true.
  • Repetition-Free Restriction: The logic forbids redundant self-reasoning (e.g., $K_i K_i p$). This restriction ensures that epistemic atoms are logically independent, allowing them to be treated as simple propositional variables by solvers.
  • Action Dynamics: The framework defines rules for Ontic actions (physical changes) and Epistemic actions (observing or ceasing observation). These rules manage how beliefs transition from true to false when the environment changes outside an agent's field of view.
Figure 1: Modeling the first-order Sally-Anne task in REDA, showing the transition from knowledge to mere belief and eventually false belief.

3. Modeling the Sally-Anne Task

The authors use the Sally-Anne task—a classic psychological benchmark for Theory of Mind—to demonstrate REDA's capabilities. In the first-order scenario (Figure 1), Sally's knowledge of a marble's location ($p$) degrades into a mere belief ($MBA_s p$) once she stops observing. When Anne moves the marble, Sally's belief becomes false ($FBA_s p$).

REDA excels in modeling the second-order Sally-Anne task, where the system must track what Anne believes about Sally's beliefs. As shown in Figure 2, the framework successfully tracks nested observations and the resulting belief states as agents start and stop observing one another.

Figure 2: Second-order modeling in REDA, tracking Anne's observations and beliefs regarding Sally's internal state.

4. Key Results and Complexity

The theoretical contributions of the paper are summarized in two main theorems:

  • Satisfiability: Checking the satisfiability of a REDA formula is equivalent to simple propositional SAT, a significant reduction in complexity compared to standard modal logics.
  • Planning Complexity: The "Plan Existence" problem for REDA is proven to be PSPACE-complete. This is a major result, as it places epistemic planning in the same complexity class as classical STRIPS planning, making it viable for real-world robotic applications.

5. Conclusion and Future Work

REDA provides a practical path forward for epistemic planning by treating knowledge as a state of active observation and leveraging the independence of repetition-free atoms. Current limitations include a restriction to an epistemic depth of two and the assumption of transparent observation (knowing exactly what another agent sees). Future research will focus on extending the logic to deeper nesting and handling more ambiguous observational scenarios.

Summary updated

BibTeX
@inproceedings{engesser2024towards,
  author = {Thorsten Engesser and Andreas Herzig and Elise Perrotin},
  title = {{Towards Epistemic-Doxastic Planning with Observation and Revision}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2024},
  doi = {10.1609/aaai.v38i9.28919},
}
Figure