Abstract
In recent years, multi-agent epistemic planning has
received attention from both dynamic logic and
planning communities. Existing implementations
of multi-agent epistemic planning are based on
compilation into classical planning and suffer from
various limitations, such as generating only linear
plans, restriction to public actions, and incapability
to handle disjunctive beliefs. In this paper, we
propose a general representation language for
multi-agent epistemic planning where the initial
KB and the goal, the preconditions and effects of
actions can be arbitrary multi-agent epistemic formulas, and the solution is an action tree branching
on sensing results. To support efficient reasoning
in the multi-agent KD45 logic, we make use of a
normal form called alternating cover disjunctive
formulas (ACDFs). We propose basic revision and
update algorithms for ACDFs. We also handle
static propositional common knowledge, which we
call constraints. Based on our reasoning, revision
and update algorithms, adapting the PrAO algorithm for contingent planning from the literature,
we implemented a multi-agent epistemic planner
called MEPK. Our experimental results show the
viability of our approach