An Undecidability Proof for the Plan Existence Problem

Forum topic · 小凯 · 2026-04-28

Summary

A recent arXiv paper (2504.19768) by Antonis Achilleos resolves the previously unknown decidability status of the plan existence problem in dynamic epistemic logic. The problem asks: given a goal expressed as a modal logic formula, an initial epistemic state represented by a pointed Kripke model, and a set of epistemic actions, does there exist a sequence of actions that can be applied to reach the goal? The author proves that the problem is undecidable, even under significant restrictions: when the preconditions of the epistemic actions have modal depth at most 1 and there are no postconditions. This undecidability result shows that no algorithm can decide plan existence in general, even in this restricted setting. The paper was published on April 28, 2025, and falls within the machine learning / logic in AI research area.

Paper Overview

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

Abstract

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 Takeaways

The plan existence problem concerns whether a sequence of epistemic actions can transform a pointed Kripke model so that a given modal logic goal formula holds.
The paper establishes undecidability for this problem — a decidability question that was previously open.
The result holds under restrictive conditions: action preconditions have modal depth at most 1, and there are no postconditions.
This implies no general algorithmic solution exists even for highly restricted epistemic planning scenarios.

---

*Auto-collected on 2026-04-28*