Abstract
This dissertation provides both foundational and practical contributions in epistemic planning based on Dynamic Epistemic Logic (DEL). On the foundational side, we begin with a decidability analysis of fragments of DEL-based epistemic planning (or in short DEL-planning) pursuing a novel semantic approach. Rather than relying on syntactic constraints on the action theory, our approach requires states and actions to satisfy the axioms of a specific logic L. We introduce a novel logic for DEL-planning called commutative epistemic logic, obtained by augmenting the logic of knowledge S5n with an interaction axiom called the commutativity axiom, and we show that DEL-planning under such logic is decidable. A key property of the introduced logic that is instrumental towards decidability is that the reasoning power of agents is guaranteed to be bounded to a certain depth. We further explore this idea by considering a variation of DEL-planning, that we call depth-bounded DEL-planning, where we limit the reasoning depth of agents to a certain bound b. Having such a bound in place, we can lighten epistemic states by discarding all information beyond depth b. We devise a novel type of bounded bisimulation contraction called rooted b-contraction, which provides a minimal representation of the beliefs of agents up to depth b. Based on this novel kind of contractions, we develop an algorithm for computing depth-bounded epistemic plans, called iterative bound-deepening search, which calculates plans that require the lowest bound. We provide soundness, completeness and complexity results for the proposed algorithm and we perform an experimental comparison with a baseline algorithm on a set of benchmarks from the epistemic planning literature. The algorithms are implemented in the publicly available epistemic planner DAEDALUS, a novel solver for general DEL-planning problems. To describe the benchmarks more in detail, we introduce the Epistemic Planning Domain Definition Language (EPDDL), a general language for representing DEL-based epistemic planning domains and problems. We provide a representation of the benchmarks in EPDDL, which is a resource of independent interest for the epistemic planning community. In the second part of the thesis we introduce DELPHIC, a novel semantics for dynamic epistemic logic that is based on an alternative representation of epistemic states called possibilities. First introduced by Gerbrandy and Groeneveld (1997), possibilities are objects grounded in non-well-founded set theory, a subfield of set theory that deals with sets x that give rise to possibly infinite sequences x ∈ x ′ ∈ x ′′ ∈ . . . of sets. After motivating the use of this alternative semantics, we introduce it formally. We complement Gerbrandy and Groeneveld’s possibility semantics for epistemic logic with a richer formalization of epistemic states called possibility spectrums, a novel formalization of epistemic actions called eventuality spectrums and a new update operator called union update. Moreover, we show that the resulting formalism is as expressive as the traditional Kripke semantics for dynamic epistemic logic. Possibilities have been shown to improve performances in epistemic planners, as they allow for a more efficient use of both time and space resources. For this reason, we extend our experimental evaluation by comparing the baseline and the iterative bound-deepening search algorithms with a tree search algorithm based on DELPHIC. We provide an implementation of latter algorithm in the DAEDALUS planner. Finally, given the promising results of both the aforementioned techniques, we lay the theoretical foundations of depth bounded epistemic planning under the DELPHIC semantics. Specifically, we introduce a novel operation on possibility spectrums called b-absorption, that akin to b-contractions provides a minimal possibility-based representation of the beliefs of agents up to depth b. Based on this operation, we recast our iterative bound-deepening search algorithm under the DELPHIC semantics and we show it to be equivalent to its Kripke-based counterpart, in the sense that the two algorithms produce the same solutions for each given input problem. We leave the implementation of the new technique as future work. Due to the practical improvements provided separately from the algorithms based on iterative bound-deepening search and DELPHIC, we believe that their combination will show compelling results.