# A General Multi-agent Epistemic Planner Based on Higher-order Belief Change

arXiv: https://arxiv.org/abs/1806.11298 · HTML: https://mlsanity.com/paper/1806.11298/

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Jun 2018.

## Built on by (most cited first, 10 of 10)

- [Evaluating LLM-based Agents for Multi-Turn Conversations: A Survey](https://mlsanity.com/paper/2503.22458/) (2025)
- [Answer Set Planning: A Survey](https://mlsanity.com/paper/2202.05793/) (2022)
- [Efficient Multi-agent Epistemic Planning: Teaching Planners About Nested Belief](https://mlsanity.com/paper/2110.02480/) (2021)
- [Fast and Slow Planning](https://mlsanity.com/paper/2303.04283/) (2023)
- [Architecting Trust in Artificial Epistemic Agents](https://mlsanity.com/paper/2603.02960/) (2026)
- [Comprehensive Multi-Agent Epistemic Planning](https://mlsanity.com/paper/2109.08301/) (2021)
- [A Computable Game-Theoretic Framework for Multi-Agent Theory of Mind](https://mlsanity.com/paper/2511.22536/) (2025)
- [Bob and Alice Go to a Bar: Reasoning About Future With Probabilistic Programs](https://mlsanity.com/paper/2108.03834/) (2021)
- [Team Plan Recognition: A Review of the State of the Art](https://mlsanity.com/paper/2301.13288/) (2023)
- [Scaling Multi-Agent Epistemic Planning through GNN-Derived Heuristics](https://mlsanity.com/paper/2508.12840/) (2025)

## Abstract (arXiv)

In recent years, multi-agent epistemic planning has received attention from both dynamic logic and planning communities. Existing implementations of multi-agent epistemic planning are based on compilation into classical planning and suffer from various limitations, such as generating only linear plans, restriction to public actions, and incapability to handle disjunctive beliefs. In this paper, we propose a general representation language for multi-agent epistemic planning where the initial KB and the goal, the preconditions and effects of actions can be arbitrary multi-agent epistemic formulas, and the solution is an action tree branching on sensing results. To support efficient reasoning in the multi-agent KD45 logic, we make use of a normal form called alternating cover disjunctive formulas (ACDFs). We propose basic revision and update algorithms for ACDFs. We also handle static propositional common knowledge, which we call constraints. Based on our reasoning, revision and update algorithms, adapting the PrAO algorithm for contingent planning from the literature, we implemented a multi-agent epistemic planner called MEPK. Our experimental results show the viability of our approach.