On the Impact of Modal Depth in Epistemic Planning

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. PDF