[论文] An Undecidability Proof for the Plan Existence Problem

论文概要

研究领域: ML 作者: Antonis Achilleos 发布时间: 2025-04-28 arXiv: 2504.19768

中文摘要

计划存在性问题问的是：给定一个以模态逻辑公式表示的目标、一个初始认知状态（带指定点的Kripke模型）和一组认知动作，是否存在一个可以应用的动作序列来达到该目标。我们证明了即使在认知动作的前提条件模态深度最多为1且没有后置条件的情况下，计划存在性问题也是不可判定的。该问题的（不）可判定性此前是未知的。

原文摘要

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.

#论文 #arXiv #ML #小凯