An Undecidability Proof for the Plan Existence Problem

Antonis Achilleos · 2026

Read An Undecidability Proof for the Plan Existence Problem by Antonis Achilleos (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-22736.txt.

Introduction

Achilleos proves that deciding whether a plan exists stays undecidable even under tight limits. Goals are stated in modal logic, the start is a single epistemic state, and actions have preconditions reaching only one level of modal depth, with no postconditions at all. The question asks whether some sequence of knowledge-changing actions can reach the goal. Until this paper, whether that restricted version was decidable or not had remained open.

Catalog record

CREATORAntonis Achilleos
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE111360
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2604.22736

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

An Undecidability Proof for the Plan Existence Problem Antonis Achilleos 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. Department of Computer Science, Reykjavik University, [email protected]://orcid.org/0000-0002-1314-333X ccs Theory of computation Automated reasoning ccs Theory of computation Modal and temporal logics keywords Epistemic Planning, Modal Logic, Undecidability † † runningauthor: A. Achilleos 1 Introduction In the field of Epistemic Planning (EP) [ 3 , 4 ] , we seek to construct a plan , that is, a sequence of actions that achieve a given goal . EP is an approach based on dynamic epistemic logic [ 6 ] that extends classical planning [ 8 ] by incorporating the beliefs and knowledge of multiple agents, allowing for the modeling of complex interactions such as coordination, communication, and secrecy. As expected, in EP, the goal is typically epistemic, in that it involves statements regarding the belief or knowledge of one or multiple agents, and it is expressed with a formula from a multi-agent epistemic logic. The state of the world (including the beliefs or knowledge of the agents) is represented by an epistemic state , which is a pointed Kripke model. Finally, an epistemic action transforms an epistemic state, by affecting the beliefs of the agents, and possibly also the values of the propositional atoms. The agents may be uncertain about the epistemic actions, and therefore these are represented as pointed Kripke frames, where each state is called an event. Each event is further equipped with preconditions , i.e. epistemic formulas that describe when the event can be applied to a world of the epistemic state; and with postconditions that describe how the propositions of a world change value when the event is applied to that world (see [ 3 ] for a more comprehensive description of EP). Thus, a central problem in EP is the plan existence problem : given an initial epistemic state, a goal, and a set of epistemic actions, is there a plan (a sequence of epistemic actions from the given ones) that transforms the initial epistemic state into one that satisfies the goal? The plan existence problem is generally undecidable [ 2 ] . Furthermore, it remains so when epistemic actions are restricted to having no postconditions and preconditions of modal depth at most 2 [ 5 ] ; and to having preconditions of modal depth at most 1 and propositional postconditions [ 10 , 3 ] . On the other hand, it is known that plan existence is decidable when both preconditions and postconditions are propositional [ 14 , 1 , 7 ] . The case of preconditions of modal depth 1 and no postconditions, to the best of our knowledge, remains open to this day. Our contribution We prove that the plan existence problem with preconditions of modal depth at most 1 and no postcondition [ 3 ] , is undecidable. Our proof is by a reduction from Post’s Correspondence Problem (PCP) [ 11 ] . We prove that the problem is undecidable in the case of at least two agents without any assumptions on the modal logic that the agents’ beliefs are based on. For the single-agent case, we need to distinguish between two cases. If the agent’s knowledge behaves according to logic S5, or even if the agent has negative introspection (they know what they do not know), then it is a somewhat straightforward observation that the plan existence problem is decidable. When the agent does not have negative introspection, we consider agents based on a modal logic that extends the basic logic K with axioms T,B,4 , but not both B and 4 , as these imply negative introspection. For these cases, we prove that the plan existence problem is undecidable. Our reduction makes substantial use of the fact that successive applications of epistemic actions can construct long paths with starting and ending states definable by a formula of modal depth 1. We need this property, as we cannot use postconditions to cycle through the states of an encoded machine, nor general preconditions to access the status of worlds further away. Thus, our constructions need to operate in a local manner, having events with preconditions that depend on the immediately accessible worlds. In Section 2 , we give the necessary background on epistemic logic and epistemic planning. In Section 3 , we prove the undecidability of the plan existence problem for a single agent based on modal logic K. This case is likely not particularly realistic for planning situations, or general, but it is sufficiently simple to help us demonstrate our reduction method. In Section 4 , we extend our reduction to the case of multiple agents, and in Section 5 we show how to further adjust our reduction to the case of agents based on logics KTB and KT4, and therefore on any logic between K and KTB, KT4. We conclude in Section 7 and give a straightforward decidability result for a single agent with negative introspection. 2 Background Modal formulae extend propositional logic with a set of modal operators K_{i} , i\in\mathsf{Ag} , often interpreted as asserting an agent i ’s knowledge or belief of the statement it is applied on. We use a set of propositional variables \mathsf{Prp} that can be assumed to be finite or countably infinite. The set of modal formulae is given by the following grammar: \displaystyle\varphi::=\bot\mid p\mid\neg\varphi\mid\varphi\land\varphi\mid K_{i}\varphi, where p\in\mathsf{Prp} and i\in ag . We use the usual definitions for the dual operators of the language: \top:=\neg\bot ; \varphi_{1}\lor\varphi_{2}:=\neg(\neg\varphi_{1}\land\neg\varphi_{2}) ; and \bar{K}\varphi:=\neg K\neg\varphi . A Kripke model is a triple (W,R,V) , where W is a set of states (or worlds), representing different possibilities about reality; R=(R_{i})_{i\in\mathsf{Ag}} , where R_{i}\subseteq W^{2} is an accessibility relation , where (w,w^{\prime})\in R_{i} represents that at state w , agent i considers w^{\prime} a possible reality; and V:W\to 2^{\mathsf{Prp}} labels each state with a set of propositional variables, with the intended meaning that these are the variables that are true at that state. We usually write wR_{i}w^{\prime} instead of (w,w^{\prime})\in R_{i} . The pair (W,R) is a Kripke frame . An epistemic state , also known as a pointed model, is a pair (\mathcal{M},w) , where \mathcal{M}=(W,R,V) is a Kripke model and w\in W — it can also be written as a quadruple (W,R,V,w) . We interpret modal formulae on epistemic states. Let \mathcal{M}=(W,R,V) be a Kriple model and w\in W . Then we define \models between epistemic states and formulae in the following way. \displaystyle(\mathcal{M},w) \displaystyle\not\models\bot \displaystyle(\mathcal{M},w) \displaystyle\models p if and only if \displaystyle p\in V(w) \displaystyle(\mathcal{M},w) \displaystyle\models\neg\varphi if and only if \displaystyle(\mathcal{M},w)\not\models\varphi \displaystyle(\mathcal{M},w) \displaystyle\models\varphi_{1}\land\varphi_{2} if and only if \displaystyle(\mathcal{M},w)\models\varphi_{1}\text{ and }(\mathcal{M},w)\models\varphi_{2} \displaystyle(\mathcal{M},w) \displaystyle\models K_{i}\varphi if and only if \displaystyle(\mathcal{M},w^{\prime})\models\varphi\text{ for every }wR_{i}w^{\prime}. In the case where |\mathsf{Ag}|=1 , we write K\varphi

Read the complete text