Undecidability in Epistemic Planning

Guillaume Aucher, Thomas Bolander

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

92 Downloads (Pure)


Dynamic epistemic logic (DEL) provides a very expressive framework for multi-agent planning that can deal with nondeterminism, partial observability, sensing actions, and arbitrary nesting of beliefs about other agents’ beliefs. However, as we show in this paper, this expressiveness comes at a price. The planning framework is undecidable, even if we allow only purely epistemic actions (actions that change only beliefs, not ontic facts). Undecidability holds already in the S5 setting with at least 2 agents, and even with 1 agent in S4. It shows that multi-agent planning is robustly undecidable if we assume that agents can reason with an arbitrary nesting of beliefs about beliefs. We also prove a corollary showing undecidability of the DEL model checking problem with the star operator on actions (iteration).
Original languageEnglish
Title of host publicationProceedings of the Twenty-Third International Joint Conference on Artificial Intelligence
PublisherAAAI Press
Publication date2013
ISBN (Print)978-1-57735-633-2
Publication statusPublished - 2013
Event23rd International Conference on Artificial Intelligence (IJCAI 2013) - Beijing, China
Duration: 3 Aug 20139 Aug 2013


Conference23rd International Conference on Artificial Intelligence (IJCAI 2013)
Internet address

Fingerprint Dive into the research topics of 'Undecidability in Epistemic Planning'. Together they form a unique fingerprint.

Cite this