Complexity Results in Epistemic Planning

Thomas Bolander, Martin Holm Jensen, François SchwarzentruberIJCAI 2015

Introduction

Epistemic planning involves agents reasoning about their own and others' knowledge. While Dynamic Epistemic Logic (DEL) provides a powerful framework for this, the general plan existence problem is notoriously difficult, often crossing into undecidability. This research identifies a "sweet spot" by restricting actions to propositional preconditions and non-factual changes, proving that the problem is decidable and mapping its complexity across various agent interaction structures.

Methods: Action Models and Stabilization

The authors focus on a fragment of DEL where preconditions are purely propositional (e.g., "If the door is open") rather than epistemic (e.g., "If Alice knows the door is open"). Furthermore, actions are restricted to being non-factual, meaning they change what agents believe without altering the physical state of the world.

The product update mechanism in epistemic planning.

A core technique used is action stabilization. The idea is that repeating an epistemic action eventually leads to a point where nested beliefs stop changing in a meaningful way. To analyze this, the authors represent actions as underlying graphs—such as Singletons, Chains, or Trees—which model agent uncertainty. By refining mathematical bounds on when these structures stabilize, the authors transform an infinite search problem into a finite, decidable one.

Key Results: The Complexity Map

The primary contribution is a comprehensive classification of the plan existence problem's complexity based on the structure of the action graph.

Comprehensive complexity landscape for epistemic planning.

As shown in the results table, the "shape" of an agent's uncertainty is the primary driver of computational difficulty:

  • Singletons and Chains: Problems involving public announcements or simple private messages are NP-complete, equivalent to the difficulty of SAT.
  • Trees: Branching uncertainty structures increase complexity to PSPACE-complete, equivalent to QSAT.
  • General Graphs: The most general case with propositional preconditions is in EXPSPACE.

Additionally, the paper proves that plan verification (checking if a specific sequence of actions achieves a goal) is PSPACE-hard even for tree-structured actions, a stronger result than previously known.

Limitations and Future Work

The main constraint of this work is the exclusion of factual change. In many real-world scenarios, actions change both the world and knowledge (e.g., picking up a key changes its location and the agent's knowledge of its location). Adding factual change often makes these problems undecidable again.

Future work suggests using these complexity results to develop heuristics. Similar to how classical planners use simplified versions of a problem to find solutions faster, an epistemic planner could "relax" a complex graph into a tree or chain to estimate plan viability, leading to more scalable multi-agent systems.

Summary updated

BibTeX
@inproceedings{bolander2015complexity,
  author = {Thomas Bolander and Martin Holm Jensen and François Schwarzentruber},
  title = {{Complexity Results in Epistemic Planning}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure