An Undecidability Proof for the Plan Existence Problem
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908991215370240 |
|---|---|
| author | Achilleos, Antonis |
| author_facet | Achilleos, Antonis |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_22736 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | An Undecidability Proof for the Plan Existence Problem Achilleos, Antonis Logic in Computer Science Artificial Intelligence 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. |
| title | An Undecidability Proof for the Plan Existence Problem |
| topic | Logic in Computer Science Artificial Intelligence |
| url | https://arxiv.org/abs/2604.22736 |