Proceedings

On the Impact of Modal Depth in Epistemic Planning

Tristan Charrier, Bastien Maubert, François Schwarzentruber

Download BibTeX Cite

Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence. Pages 1030-1035.

Abstract

Epistemic planning is a variant of automated planning in the framework of dynamic epistemic logic. In recent works, the epistemic planning problem has been proved to be undecidable when preconditions of events can be epistemic formulas of arbitrary complexity, and in particular arbitrary modal depth. It is known however that when preconditions are propositional (and there are no postconditions), the problem is between PSPACE and EXPSPACE. In this work we bring two new pieces to the picture. First, we prove that the epistemic planning problem with propositional preconditions and without postconditions is in PSPACE, and is thus PSPACE-complete. Second, we prove that very simple epistemic preconditions are enough to make the epistemic planning problem undecidable: preconditions of modal depth at most two suffice.

Tristan Charrier, Bastien Maubert, and François Schwarzentruber. 2016. On the Impact of Modal Depth in Epistemic Planning. In Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-16. IJCAI, 1030–1035. https://ijcai.org/proceedings/2016/150
Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards