Abstract
In recent years, multi-agent epistemic planning has received attention fromboth dynamic logic and planning communities. Existing implementations ofmulti-agent epistemic planning are based on compilation into classical planningand 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-agentepistemic planning where the initial KB and the goal, the preconditions andeffects of actions can be arbitrary multi-agent epistemic formulas, and thesolution is an action tree branching on sensing results. To support efficientreasoning in the multi-agent KD45 logic, we make use of a normal form calledalternating cover disjunctive formulas (ACDFs). We propose basic revision andupdate algorithms for ACDFs. We also handle static propositional commonknowledge, which we call constraints. Based on our reasoning, revision andupdate algorithms, adapting the PrAO algorithm for contingent planning from theliterature, we implemented a multi-agent epistemic planner called MEPK. Ourexperimental results show the viability of our approach.