Research map / Multi-agent systems and games / Human-AI and goal-conditioned
Towards Epistemic-Doxastic Planning with Observation and Revision
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes a repetition-free epistemic-doxastic action language (true vs mere belief atoms) that handles belief revision from observation, reduces reasoning to propositional logic, and yields PSPACE-complete planning for false-belief tasks.
Problem
Epistemic planning with observations in the presence of false beliefs, which requires belief revision; existing DEL-based planning is undecidable and tractable fragments disallow uncertainty-increasing actions.
Approach
Replace knowledge/belief operators with repetition-free atoms TBA_i (true belief) and MBA_i (mere belief), identify observation with knowledge about an atom, and define ontic and epistemic actions (start/stop observing) whose indirect effects are derived from agents' observational status, so belief revision needs no plausibility orderings.
Key results
- Proves that satisfiability for boolean combinations of repetition-free epistemic-doxastic atoms is equivalent to propositional satisfiability (Theorem 1).
- Shows REDA plan existence is PSPACE-complete, the same complexity as classical planning with conditional effects (Theorem 2).
- Models the Sally-Anne Task and a second-order false-belief task, including revision of false beliefs via startobs1 and startobs2 actions.
Surprising findings
- Certain scenarios, such as an agent observing that another agent does not observe p while having no knowledge of the other's beliefs, cannot be modelled in the formalism.
Limitations
- Cannot model situations where an agent observes that another agent does not observe p while having no knowledge of that agent's beliefs.
- Restricted to belief depth at most two and effects of modal depth at most two.
- Assumes beliefs are never lost and there is no forgetting or doxastic voluntarism.
Experimental setup
Baselines: mA* Bolander edge-conditioned action language Lorini and Romero belief base approach Wan et al. KD45 update and revision planning
Builds on: dynamic epistemic logic Herzig and Perrotin true/mere belief logic Herzig, Lorini and Maffre knowing-whether atoms mA* Bolander second-order false-belief action language
Closest papers by meaning
- When Planning Fails Despite Correct Execution: On Epistemic Calibration for LLM-Based Multi-Agent Systems (ICML 2026 · similarity 0.87)
- A Logical Analysis of Hanabi (AAAI 2025 · similarity 0.86)
- Reasoning in Visual Navigation of End-to-end Trained Agents: A Dynamical Systems Approach (CVPR 2025 · similarity 0.85)
- Agent Planning with World Knowledge Model (NeurIPS 2024 · similarity 0.85)
- From Assumptions to Actions: Turning LLM Reasoning into Uncertainty-Aware Planning for Embodied Agents (ICLR 2026 · similarity 0.85)
- Introspective Planning: Aligning Robots' Uncertainty with Inherent Task Ambiguity (NeurIPS 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.