🤖 AI

An Undecidability Proof for the Plan Existence Problem

This paper proves that the plan existence problem in epistemic logic is undecidable, even under highly restricted conditions such as limited modal depth for action preconditions and the absence of postconditions.

Original authors: Antonis Achilleos

Published 2026-04-27

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Antonis Achilleos

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Mystery of the Infinite Instruction Manual: An Explanation

Imagine you are playing a video game where you have to guide a character through a series of rooms to reach a treasure. This is a "planning problem." In most games, the rules are simple: "If you have a key, you can open the door."

But this paper is about a much more complex game called Epistemic Planning. In this game, the character isn't just moving through physical rooms; they are moving through states of mind. The goal isn't just to "be in the treasure room," but to "know that the treasure is in the treasure room" or "be certain that your teammate knows the secret code."

The paper proves something startling: Even if the rules for your actions are incredibly simple, the game can become impossible to solve.

The Core Problem: The "Knowledge" Maze

In standard planning, you deal with facts: The door is open.
In epistemic planning, you deal with beliefs: I believe the door is open, but I’m not sure if you believe it.

The researcher, Antonis Achilleos, looked at a specific version of this game. In this version:

Simple Rules: The "preconditions" (the requirements to do something) are very basic. You don't need complex, nested logic like "I know that you know that I know..." You only need one level of depth: "I know X."
No Changes to Reality: The actions don't actually change the physical world (like moving a chair); they only change what the characters know or believe (like telling a secret).

You might think, "If the rules are that simple and nothing in the physical world changes, surely a computer can eventually figure out a plan!"

The paper says: No. It is "undecidable." This means there is no master algorithm that can look at any given setup and guaranteed-ly say "Yes, a plan exists" or "No, a plan doesn't exist" in a finite amount of time.

The Analogy: The Infinite Lego Tower

To understand why this is so hard, let's use the Lego Tower Analogy.

Imagine you are given a set of Lego instructions. Each instruction is a "block" consisting of two different colored pieces (let's say a Red piece and a Blue piece). Your goal is to build two separate towers—one using only the Red pieces and one using only the Blue pieces—such that the two towers are exactly identical in height and pattern.

This is a famous mathematical puzzle called the Post Correspondence Problem (PCP). It is known to be impossible for a computer to solve for every possible set of blocks.

The researcher's "Magic Trick":
He proved that you can translate this Lego puzzle into the "Knowledge Game."

The Red pieces become the character's "knowledge of the top sequence."
The Blue pieces become the "knowledge of the bottom sequence."
The Actions in the game act like adding a Lego block to the tower.
The Goal is to reach a state where the character "knows" the two sequences are perfectly matched.

Because the Lego puzzle is impossible to solve with a universal formula, and because the Knowledge Game can perfectly mimic the Lego puzzle, the Knowledge Game must also be impossible to solve.

Why does this matter?

You might ask, "Why do we care if a computer can't solve a game about knowledge?"

This research is about the limits of Artificial Intelligence. As we build AI agents that need to coordinate with humans (like self-driving cars communicating with traffic lights, or robots working in a warehouse), they need to reason about what others know.

This paper serves as a "Warning Sign" on the map of computer science. It tells engineers: "Be careful. If you give your AI agents even a tiny bit of ability to reason about knowledge, you might accidentally create a problem that is mathematically impossible for them to ever fully master."

Technical Summary: An Undecidability Proof for the Plan Existence Problem

Author: Antonis Achilleos
Subject: Epistemic Planning (EP), Modal Logic, Theory of Computation

1. The Problem: Epistemic Plan Existence

The paper addresses the Plan Existence Problem within the framework of Epistemic Planning (EP). In EP, the goal is to find a sequence of actions (a plan) that transforms an initial epistemic state (represented as a pointed Kripke model) into a state that satisfies a specific goal formula expressed in multi-agent epistemic logic.

Unlike classical planning, which deals with physical states, EP deals with the knowledge and beliefs of agents. Epistemic actions are defined by:

Preconditions: Modal formulas that determine if an action can be applied.
Postconditions: Rules describing how the values of propositional atoms change (though this paper specifically investigates the case where postconditions are absent).

The core research question is: How much restriction on the preconditions (specifically their modal depth) is required to make the plan existence problem decidable?

2. Methodology: Reduction from Post’s Correspondence Problem (PCP)

The author proves undecidability by reducing the Post’s Correspondence Problem (PCP)—a well-known undecidable problem in formal language theory—to an instance of the epistemic plan existence problem.

The Reduction Strategy:
The reduction is designed to simulate the construction and verification of a PCP match using two distinct stages of planning:

Stage 1 (Construction): Epistemic actions are used to "build" two branching paths in the Kripke model. One path represents the concatenation of strings from the "top" set of PCP tiles, and the other represents the "bottom" set. The actions effectively append blocks of symbols to these paths.
Stage 2 (Verification): Once the construction is complete, a transition action moves the plan to a verification stage. Here, the plan must iteratively "prune" or remove symbols from the ends of both paths. If the two paths are identical (a match), the plan can successfully reduce both paths back to the root state. If they differ, the plan enters a "failed" state.

3. Key Contributions and Technical Results

The paper provides a comprehensive mapping of undecidability across various logical constraints:

Main Result (Undecidability): The author proves that the plan existence problem is undecidable even under extremely restrictive conditions: preconditions have a modal depth of at most 1 and there are no postconditions. This fills a previously unknown gap in the complexity landscape of EP.
Multi-Agent Case: The proof is extended to multi-agent systems. To prevent unintended "shortcuts" caused by symmetry or transitivity in multi-agent accessibility relations, the author introduces a separator symbol ( $\#$ ) and alternates accessibility relations between agents to ensure the encoding remains robust.
Single-Agent Logic Variations: The author explores different modal logic axioms:
- Logic K: Proves undecidability for a single agent with no restrictions on accessibility.
- Reflexive/Symmetric Frames: Proves undecidability for single agents where the accessibility relation is reflexive or symmetric (but not both, as that would imply transitivity/S5).
- Transitive Frames: Proves undecidability for transitive frames by reversing the order of loops and encoding states to prevent transitivity from "collapsing" the structure.
Decidability Boundary: The paper identifies the boundary of decidability. It proves that if a single agent has negative introspection (the Euclidean property, characteristic of logic S5), the problem becomes NP-complete.

4. Summary of Results Table

Precondition Depth	Postconditions	Agent Type	Logic/Frame Property	Complexity
$\leq 1$	None	Single/Multi	General (K)	Undecidable
$\leq 1$	None	Single	Reflexive/Symmetric	Undecidable
$\leq 1$	None	Single	Transitive	Undecidable
Arbitrary	Arbitrary	Single	S5 (Negative Introspection)	NP-complete

5. Significance

This paper is significant because it establishes that the complexity of epistemic planning is driven by the structure of the epistemic state rather than just the complexity of the formulas used.

By showing that even "shallow" preconditions (modal depth 1) can trigger undecidability, the author demonstrates that the ability of actions to manipulate the connectivity of Kripke models is a powerful computational tool. This provides critical guidance for researchers in automated reasoning: to ensure decidability in practical epistemic planners, one must impose stronger constraints, such as action separability or bounding plan length, rather than simply limiting the modal depth of preconditions.