Complexity Results in Epistemic Planning
Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence. Special Track on Knowledge Representation and Reasoning. Pages 2791-2796.
Abstract
Epistemic planning is a very expressive framework that extends automated planning by the incorporation of dynamic epistemic logic (DEL). We provide complexity results on the plan existence problem for multi-agent planning tasks, focusing on purely epistemic actions with propositional preconditions. We show that moving from epistemic preconditions to propositional preconditions makes it decidable, more precisely in EXPSPACE. The plan existence problem is PSPACE-complete when the underlying graphs are trees and NP-complete when they are chains (including singletons). We also show PSPACE-hardness of the plan verification problem, which strengthens previous results on the complexity of DEL model checking.
@inproceedings{ijcai2015p395,
title = {Complexity Results in Epistemic Planning},
author = {Bolander, Thomas and Jensen, Martin Holm and Schwarzentruber, François},
booktitle = {Proceedings of the Twenty-Fourth International Joint Conference on
Artificial Intelligence, {IJCAI-15}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Qiang Yang and Michael Wooldridge},
pages = {2791--2796},
year = {2015},
month = {7},
note = {Special Track on Knowledge Representation and Reasoning},
url = {https://ijcai.org/proceedings/2015/395},
}
TY - CPAPER TI - Complexity Results in Epistemic Planning AU - Bolander, Thomas AU - Jensen, Martin Holm AU - Schwarzentruber, François T2 - Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-15 PB - International Joint Conferences on Artificial Intelligence PY - 2015 SP - 2791 EP - 2796 UR - https://ijcai.org/proceedings/2015/395 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
