Compiling Model Reconciliation Explanation Problems into Stackelberg and FOND Planning Problems

Abstract

Despite its popularity, most model reconciliation explanation generation methods rely on blind breadth-first search, and even available heuristics are rudimentary at best. In this paper, we propose two novel approaches to compile the problem of generating bounded model-reconciliation explanations into existing planning formalisms. First, we compile the problem into a Stackelberg planning problem, which is an adversarial problem consisting of a leader and follower agent. Here, the leader agent is responsible for identifying the explanation, while the follower checks the validity of the identified explanation. In the second approach, we see how the same problem can also be converted into a fully observable non-deterministic (FOND) planning problem. Here, the nondeterministic actions are used to generate and test the possibility of a shorter plan. We show the effectiveness of the proposed approaches by comparing them against each other and two existing baselines on standard planning benchmark problems.