Undecidability in Epistemic Planning
Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence. Pages 27-32.
Abstract
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).
@inproceedings{ijcai2013p16,
title = {Undecidability in Epistemic Planning},
author = {Aucher, Guillaume and Bolander, Thomas},
booktitle = {Proceedings of the Twenty-Third International Joint Conference on
Artificial Intelligence, {IJCAI-13}},
publisher = {AAAI Press / International Joint Conferences on Artificial Intelligence},
editor = {Francesca Rossi},
pages = {27--32},
year = {2013},
month = {8},
url = {https://ijcai.org/proceedings/2013/16},
}
TY - CPAPER TI - Undecidability in Epistemic Planning AU - Aucher, Guillaume AU - Bolander, Thomas T2 - Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, IJCAI-13 PB - AAAI Press / International Joint Conferences on Artificial Intelligence PY - 2013 SP - 27 EP - 32 UR - https://ijcai.org/proceedings/2013/16 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
