Titre : Epistemic Planning via Dynamic Epistemic Logic: Can We Overcome Intractability?
Abstract
Epistemic planning extends classical planning by incorporating epistemic notions such as knowledge and belief, thereby enabling reasoning not only about the world but also about how it is perceived by a group of
agents. Dynamic Epistemic Logic (DEL) provides a highly expressive formalism for this purpose, supporting reasoning about higher-order knowledge and belief, uncertainty, non-determinism, and both ontic and
epistemic change. Unsurprisingly, this expressiveness comes at a cost: the epistemic plan existence problem is undecidable in general, and becomes tractable only under strict conditions. This seminar will first present an accessible formal introduction to epistemic planning in the DEL framework. We will then survey the main decidability and complexity results obtained over the past fifteen years, showing the principal sources of intractability. The seminar will then focus on algorithmic techniques for DEL-based epistemic planning, with particular emphasis on Depth-Bounded Epistemic Planning. In this approach, the reasoning depth of the planning agent is restricted to an upper bound b, so that the agent can only reason about higher-order knowledge up to modal depth b.Plans are then computed by iteratively increasing the reasoning depth until a solution is found. This method leverages bounded bisimulation contractions to reduce the size of epistemic state spaces, yielding highly efficient runtimes and demonstrating that general DEL planners can, in practice, be made efficient. The seminar will conclude with a discussion of promising directions for future research in DEL-based epistemic planning.