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.
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.
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