A General Multi-agent Epistemic Planner Based on Higher-order Belief Change
This work addresses the problem of efficient and flexible multi-agent epistemic planning for AI and logic communities, though it appears incremental as it builds on existing contingent planning algorithms.
The paper tackled the limitations of existing multi-agent epistemic planners, such as generating only linear plans and handling only public actions, by proposing a general representation language and implementing the MEPK planner, which supports arbitrary multi-agent epistemic formulas and action trees branching on sensing results.
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.