Heuristic Strategies for Accelerating Multi-Agent Epistemic Planning

Multi-agent epistemic planning (MEP) is about achieving an epistemic goal in a multi-agent environment using agents’ actions that have epistemic preconditions and effects. Recently, MEP has received interest from both the dynamic logic and planning communities, leading to the development of several innovative planners. One such state of the art planner is MEPK. In this paper, we propose two novel strategies to enhance the search methods within MEPK. Our first strategy, the enhancement strategy, dynamically updates the heuristic based on the search path to the first goal-reachable node, potentially reducing the number of nodes that need to be explored to find a solution. Our second, the belief lock strategy, prevents the planner from continuing to search a particular state that cannot progress to a goal state due to the possession by an agent of a certain belief. Our experiments on existing benchmarks show that the new strategies can indeed accelerate the problem solving. We also construct new harder instances and demonstrate that our strategies significantly improve the performance on these hard benchmarks. Overall, we consider our new planner a significant improvement over the existing one in terms of computational efficiency.