An Undecidability Proof for the Plan Existence Problem (arXiv 2504.19768)

Forum topic · 小凯 · 2026-04-28

Summary

A new paper by Antonis Achilleos (arXiv 2504.19768, posted April 28, 2025) resolves a previously open question in dynamic epistemic logic: the undecidability of the plan existence problem. The problem asks whether, given a goal expressed as a modal logic formula, an initial epistemic state represented as a pointed Kripke model, and a set of epistemic actions, there exists a sequence of actions whose application reaches the goal. Achilleos proves that the problem remains undecidable even under strong restrictions: when the preconditions of the epistemic actions have modal depth at most 1 and there are no postconditions. Since the decidability status of this restricted version was previously unknown, this result closes the gap by showing that neither depth-bounded preconditions nor the absence of postconditions restores decidability. The result is relevant to automated planning, knowledge representation, and theoretical computer science.

Paper Overview

Field: ML Author: Antonis Achilleos Published: 2025-04-28 arXiv: 2504.19768

Abstract (Original)

The plan existence problem asks, given a goal in the form of a formula in modal logic, an initial epistemic state (a pointed Kripke model), and a set of epistemic actions, whether there exists a sequence of actions that can be applied to reach the goal. We prove that even in the case where the preconditions of the epistemic actions have modal depth at most 1, and there are no postconditions, the plan existence problem is undecidable. The (un)decidability of this problem was previously unknown.

Key Points

The plan existence problem takes as input:
a goal expressed as a modal logic formula,
an initial epistemic state (a pointed Kripke model),
a set of epistemic actions.
The question is whether some sequence of actions can be applied to reach the goal.
Main result: the problem is undecidable even when:
the preconditions of epistemic actions have modal depth at most 1, and
there are no postconditions.
The (un)decidability of this restricted version was previously unknown, making this a new result.

---

*Automatically collected on 2026-04-28*