An Improved Multi-agent Epistemic Planner via Higher-Order Belief Change Based on Heuristic Search

摘要

Recently, multi-agent epistemic planning has drawn attention from both dynamic logic and planning communities. Existing implementations are based on compilation into classical planning, which suffers from limitations such as incapability to handle disjunctive beliefs, or higher-order belief change and forward state space search, as exploited by the planner MEPK. However, MEPK does not scale well. In this paper, we propose two improvements for MEPK. Firstly, we exploit another normal form for multi-agent KD45, which is more space efficient than the normal form used by MEPK, and propose efficient reasoning, revision, and update algorithms for it. Secondly, we propose a heuristic function for multi-agent epistemic planning, and apply heuristic search algorithm AO* with cycle checking and two heuristic pruning strategies. We implement a multi-agent epistemic planner called MEPL. Our experimental results show that MEPL outperforms MEPK in most planning instances, and solves a number of instances which MEPK cannot solve.