Planning with Perspectives -- Decomposing Epistemic Planning using Functional STRIPS

• Published in: The Journal of artificial intelligence research 2022-01, Vol.75, p.489-539
• Main Authors: Hu, Guang, Miller, Tim, Lipovetzky, Nir
• Format: Article
• Language: English
• Subjects: Agents (artificial intelligence); Artificial intelligence; Canonical forms; Decomposition; Epistemology; Multiagent systems; Planning; Semantics; Solvers
• ISSN: 1076-9757; 1076-9757; 1943-5037
• DOI: 10.1613/jair.1.13446

In this paper, we present a novel approach to epistemic planning called planning with perspectives (PWP) that is both more expressive and computationally more efficient than existing state-of-the-art epistemic planning tools. Epistemic planning — planning with knowledge and belief — is essential in many multi-agent and human-agent interaction domains. Most state-of-the-art epistemic planners solve epistemic planning problems by either compiling to propositional classical planning (for example, generating all possible knowledge atoms or compiling epistemic formulae to normal forms); or explicitly encoding Kripke-based semantics. However, these methods become computationally infeasible as problem sizes grow. In this paper, we decompose epistemic planning by delegating reasoning about epistemic formulae to an external solver. We do this by modelling the problem using Functional STRIPS, which is more expressive than standard STRIPS and supports the use of external, black-box functions within action models. Building on recent work that demonstrates the relationship between what an agent ‘sees’ and what it knows, we define the perspective of each agent using an external function, and build a solver for epistemic logic around this. Modellers can customise the perspective function of agents, allowing new epistemic logics to be defined without changing the planner. We ran evaluations on well-known epistemic planning benchmarks to compare an existing state-of-the-art planner, and on new scenarios that demonstrate the expressiveness of the PWP approach. The results show that our PWP planner scales significantly better than the state-of-the-art planner that we compared against, and can express problems more succinctly.