On the Impact of Modal Depth in Epistemic Planning

Tristan Charrier, Bastien Maubert, François SchwarzentruberIJCAI 2016

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.

Basic epistemic models and product updates used to represent changing knowledge states.

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.

An epistemic model gadget representing a two-counter machine state with program counter $\ell=1$ and counters $c_1=3, c_2=2$.

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

BibTeX
@inproceedings{charrier2016impact,
  author = {Tristan Charrier and Bastien Maubert and François Schwarzentruber},
  title = {{On the Impact of Modal Depth in Epistemic Planning}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
}
Figure