Abstract
Epistemic planning involves designing agents that can reason about their own knowledge and the knowledge of others. While Dynamic Epistemic Logic (DEL) provides a robust framework for this, the general planning problem is known to be undecidable. This paper maps the "complexity cliff" by examining how limits on modal depth—the degree of nested knowledge—affect solvability. We prove that planning with propositional preconditions ($d=0$) is PSPACE-complete, but adding just two levels of nested knowledge ($d=2$) renders the problem undecidable, even without physical changes to the environment.
Introduction: The Challenge of Nested Knowledge
Epistemic planning uses Dynamic Epistemic Logic (DEL) to help autonomous agents navigate environments where information is a primary resource. A typical goal might be to ensure "Agent A knows that Agent B does not know the secret." These states are represented using Kripke models, where nodes are possible worlds and edges represent agent uncertainty.
Previous research established that if preconditions can have arbitrary complexity (unbounded modal depth), planning is undecidable. Conversely, if preconditions are purely propositional (depth 0), the problem is decidable. This paper identifies the exact threshold where "thinking about thinking" makes the problem impossible to solve algorithmically.
Methods and Results
The authors approach the complexity bounds from two directions:
1. Lowering the Ceiling: PSPACE-completeness for $d=0$
For the simplest case—propositional preconditions and no physical effects—the authors prove the problem is PSPACE-complete. This is a tighter bound than previous estimates. The key insight is that purely epistemic events commute: the final state of knowledge depends on which facts were learned, not the order in which they were learned. This allows for a succinct representation of event sequences that fits within polynomial space.
2. Raising the Floor: Undecidability at $d=2$
To prove undecidability for low modal depth, the authors perform a reduction from the halting problem of a two-counter machine. They design specific epistemic structures, or "gadgets," to represent the machine's program counter and its two integer counters.
Crucially, they demonstrate that these gadgets can be managed and verified using formulas with a modal depth of only two. This "Depth-2 Computer" can simulate incrementing, decrementing, and zero-testing, effectively embedding a Turing-complete system within the epistemic planning framework.
Key Insights: The "Complexity Cliff"
The paper's findings are summarized in the following table:
| Modal Depth ($d$) | Purely Epistemic (No Postconditions) | With Physical Effects (Postconditions) |
|---|---|---|
| $d = 0$ | PSPACE-complete | Decidable |
| $d \le 1$ | Unknown | Undecidable |
| $d \le 2$ | Undecidable | Undecidable |
| Unbounded | Undecidable | Undecidable |
The most striking result is that a modal depth of 2 is sufficient for undecidability even without "ontic" actions (actions that change the physical world). Previous proofs relied on unbounded depth to manage the program counter; this work shows that a finite program counter can be handled within the "depth budget," leaving enough complexity to manage the infinite data counters.
Conclusion and Future Directions
This work provides a definitive map of the epistemic planning landscape but leaves open the "sweet spot" at modal depth $d=1$. Whether reasoning about "what you know" (without the "I know that you know" layer) remains decidable is the next major frontier. Additionally, while $d=0$ planning with physical effects is known to be decidable, its exact complexity remains a significant open question, with a vast gap between known lower and upper bounds.
Summary updated