In this paper, we propose a novel algorithm for epistemic planning based on
dynamic epistemic logic (DEL). The novelty is that we limit the depth of
reasoning of the planning agent to an upper bound b, meaning that the planning
agent can only reason about higher-order knowledge to at most (modal) depth b.
The algorithm makes use of a novel type of canonical b-bisimulation contraction
guaranteeing unique minimal models with respect to b-bisimulation. We show our
depth-bounded planning algorithm to be sound. Additionally, we show it to be
complete with respect to planning tasks having a solution within bound b of
reasoning depth (and hence the iterative bound-deepening variant is complete in
the standard sense). For bound b of reasoning depth, the algorithm is shown to
be (b + 1)-EXPTIME complete, and furthermore fixed-parameter tractable in the
number of agents and atoms. We present both a tree search and a graph search
variant of the algorithm, and we benchmark an implementation of the tree search
version against a baseline epistemic planner.

本文提出了一种基于动态认知逻辑 (DEL) 的新型算法，该算法限制了规划代理的推理深度为一个上界 b，以模态深度 b 为最多的高阶知识进行推理。算法利用了一种新型的 b-bisimulation 收缩确保了最小模型的唯一性。我们证明了深度有界规划算法是正确的。此外，我们证明了在推理深度的限制 b 内具有解决方案的规划任务的完备性（因此按照标准定义的迭代界限增加变体是完备的）。在推理深度的限制 b 下，该算法被证明是 (b + 1)-EXPTIME 完全，同时在代理和原子的数量上是固定参数可处理的。我们提供了算法的树搜索和图搜索变体，并将树搜索版本的实现与基准认知规划器进行了基准测试。