Pruning with Belief Traps in Multi-agent Epistemic Planning

Multi-agent epistemic planning (MEP) addresses planning problems involving multiple agents with epistemic reasoning, often requiring the consideration of nested beliefs. In this paper, we extend the notion of traps in classical planning to MEP, and call them belief traps, which are epistemic formulas that once entailed by an epistemic state, remain entailed by all successor states. Identifying belief traps can sometimes improve MEP solving significantly. Here, we consider two methods for identifying and using belief traps to improve planning efficiency. Our first method adapts a classical preprocessing algorithm with integration into an MEP planner, simple-form construction of traps, and a novel use of beneficial traps to guide search. The second method systematically generalizes the belief lock strategy by formalizing its underlying preservation condition. Our experiments show that the new pruning techniques can accelerate problem-solving in the domains with irreversible beliefs.