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.
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.
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