In an explanation generation problem, an agent needs to identify and explain the reasons for its decisions to another agent. Existing work in this area is mostly confined to planning-based systems that use automated planning approaches to solve the problem. In this paper, we approach this problem from a new perspective, where we propose a general logic-based framework for explanation generation. In particular, given a knowledge base $KB_1$ that entails a formula $\phi$ and a second knowledge base $KB_2$ that does not entail $\phi$, we seek to identify an explanation $\epsilon$ that is a subset of $KB_1$ such that the union of $KB_2$ and $\epsilon$ entails $\phi$. We define two types of explanations, model- and proof-theoretic explanations, and use cost functions to reflect preferences between explanations. Further, we present our algorithm implemented for propositional logic that compute such explanations and empirically evaluate it in random knowledge bases and a planning domain. With increasing proliferation and integration of AI systems in our daily life, there is a surge of interest in explainable AI, which includes the development of AI systems whose actions can be easily understood by humans. Driven by this goal, machine learning (ML) researchers have begun to classify commonly used ML algorithms according to different dimensions of explainability (Guidotti et al. 2018) ; improved the explainability of existing ML algorithms BID3 BID0 BID3 ; as well as proposed new ML algorithms that trade off accuracy for increasing explainability (Dong et al. 2017; BID1 . 1 While the term interpretability is more commonly used in the ML literature and can be used interchangeably with explainability, we use the latter term as it is more commonly used broadly across different subareas of AI.In contrast, researchers in the automated planning community have mostly taken a complementary approach. While there is some work on adapting planning algorithms to find easily explainable plans 2 (i.e., plans that are easily understood and accepted by a human user) BID0 , most work has focused on the explanation generation problem (i.e., the problem of identifying explanations of plans found by planning agents that when presented to users, will allow them to understand and accept the proposed plan) (Langley 2016; Kambhampati 1990) . Within this context, researchers have tackled the problem where the model of the human user may be (1) inconsistent with the model of the planning agent (Chakraborti et al. 2017b) ; (2) must be learned BID0 ; and (3) a different form or abstraction than that of the planning agent BID0 Tian et al. 2016) . However, a common thread across most of these works is that they, not surprisingly, employ mostly automated planning approaches. For example, they often assume that the models of both the agent and human are encoded in PDDL format.In this paper, we approach the explanation generation problem from a different perspective -one based on knowledge representation and reasoning (KR). We propose a general logic-based framework for explanation generation, where given a knowledge base KB 1 (of an agent) that entails a formula φ and a knowledge base KB 2 (of a human user) that does not entail φ, the goal is to identify an explanation ⊆ KB 1 such that KB 2 ∪ entails φ. We define two types of explanations, model-and proof-theoretic explanations, and use cost functions to reflect preferences between explanations. Further, we present an algorithm, implemented for propositional logic, that computes such explanations and evaluate its performance experimentally in random knowledge bases as well as in a planning domain.In addition to providing an alternative approach to solve the same explanation generation problem tackled thus far by the automated planning community, our approach has the merit of being more generalizable to other problems beyond planning problems as long as they can be modeled using a logical KR language. There is a very large body of work related to the very broad area of explainable AI. We have briefly discussed some of them from the ML literature in Section . We refer readers to surveys by BID0 and (Dosilovic et al. 2018 ) for more in-depth discussions of this area. We focus below on related work from the KR and planning literature only since we employ KR techniques to solve explainable planning problems in this paper.Related Work from the KR Literature: We note that the notion of an explanation proposed in this paper might appear similar to the notion of a diagnosis that has been studied extensively in the last several decades (e.g., (Reiter 1987)) as both aim at explaining something to an agent. Diagnosis focuses on identifying the reason for the inconsistency of a theory whereas an mor p-explanation aims at identifying the support for a formula. The difference lies in that a diagnosis is made with respect to the same theory and m-or p-explanation is sought for the second theory.Another earlier research direction that is closely related to the proposed notion of explanation is that of developing explanation capabilities of knowledge-based systems and decision support systems, which resulted in different notions of explanation such as trace, strategic, deep, or reasoning explanations (see review by BID3 for a discussion of these notions). All of these types of explanations focus on answering why certain rules in a knowledge base are used and how a conclusion is derived. This is not our focus in this paper. The present development differs from earlier proposals in that m-or p-explanations are identified with the aim of explaining a given formula to a second theory. Furthermore, the notion of an optimal explanation with respect to the second theory is proposed.There have been attempts to using argumentation for explanation (Cyras et al. 2017; Cyras et al. 2019) because of the close relation between argumentation and explanation. For example, argumentation was used by (Cyras et al. 2019) to answer questions such as why a schedule does (does not) satisfy a criteria (e.g., feasibility, efficiency, etc.); the approach was to develop for each type of inquiry, an abstract argumentation framework (AF) that helps explain the situation by extracting the attacks (non-attacks) from the corresponding AF. Our work differs from these works in that it is more general and does not focus on a specific question.It is worth to pointing out that the problem of computing a most preferred explanation for ϕ from KB 1 to KB 2 might look similar to the problem of computing a weakest sufficient condition of ϕ on KB 1 under KB 2 as described by BID3 . As it turns out, the two notions are quite different. Given that KB 1 = {p, q} and KB 2 = {p}. It is easy to see that q is the unique explanation for q from KB 1 to KB 2 . On the other hand, the weakest sufficient condition of q on KB 1 under KB 2 is ⊥ (Proposition 8, BID3 ).Related Work from the Planning Literature: In human-aware planning, the (planning) agent must have knowledge of the human model in order to be able to contemplate the goals of the humans as well as foresee how its plan will be perceived by them. This is of the highest importance in the context of explainable planning since an explanation of a plan cannot be onesided (i.e., it must incorporate the human's beliefs of the planner). In a plan generation process, a planner performs argumentation over a set of different models (Chakraborti et al. 2017a ); these models usually are the model of the agent incorporating the planner, the model of the human in the loop, the model the agent thinks the human has, the model the human thinks the agent has, and the agent's approximation of the latter.Therefore, the necessity for plan explanations arises when the model of the agent and the model the human thinks the agent has diverge so that the optimal plans in the agent's model are inexplicable to the human. During a collaborative activity, an explainable planning agent BID1 ) must be able to account for such model differences and maintain an explanatory dialogue with the human so that both of them agree on the same plan. This forms the nucleus of explanation generation of an explainable planning agent, and is referred to as model reconciliation (Chakraborti et al. 2017b) . In this approach , the agent computes the optimal plan in terms of his model and provides an explanation of that plan in terms of model differences. Essentially, these explanations can be viewed as the agent's attempt to move the human's model to be in agreement with its own. Further, for computing explanations using this approach the following four requirements are considered:• Completeness -No better solution exists. This is achieved by enforcing that the plan being explained is optimal in the updated human model.• Conciseness -Explanations should be easily understandable to the human.• Monotonicity -The remaining model differences cannot change the completeness of an explanation.• Computability -Explanations should be easy to compute (from the agent's perspective).As our work is motivated by these ideas , we now identify some similarities and connections with our proposed approach. First, it is easy to see that we implicitly enforce the first three requirements when computing an explanation -the notions of completeness and conciseness are captured through the use of our cost functions. We do not claim to satisfy the computability requirement as it is more subjective and is more domain dependent.In a nutshell, the model reconciliation approach works by providing a model update such that the optimal plan is feasible and optimal in the updated model of the human. This is similar to our definition of the explanation generation problem where we want to identify an explanation ⊆ KB 1 (i.e., a set of formulae) such that KB 2 ∪ |= φ. In addition, the ⊆-minimal support in Definition 1 is equivalent to minimally complete explanations (MCEs) (the shortest explanation). The -general support can be viewed as similar to the minimally monotonic explanations (MMEs) (the shortest explanation such that no further model updates invalidate it), with the only difference being that in the general support scenario, the explanations are such that all subsuming are also valid supports.In contrast, model patch explanations (MPEs) (includes all the model updates) are trivial explanations and are equivalent to our definition that KB 1 itself serves as an m-explanation for KB 2 . Note that, in our approach, we do not allow for explanations on "mistaken" expectations in the human model, as it can be inferred from Proposition 1 (monotonic language L). From the model reconciliation perspective, such restriction is relaxed and allowed. However, a similar property can be seen if the mental model is not known and, therefore, by taking an "empty" model as starting point explanations can only add to the human's understanding but not mend mistaken ones. Explanation generation is an important problem within the larger explainable AI thrust. Existing work on this problem has been done in the context of automated planning domains, where researchers have primarily employed, unsurprisingly, automated planning approaches. In this paper, we approach the problem from the perspective of KR, where we propose a general logic-based framework for explanation generation. We further define two types of explanations, model-and proof-theoretic explanations, and use cost functions to reflect preferences between explanations. Our empirical results with algorithms implemented for propositional logic on both random knowledge bases as well as a planning domain demonstrate the generality of our approach beyond planning problems. Future work includes investigating more complex scenarios, such as one where an agent needs to persuade another that its knowledge base is incorrect.
A general framework for explanation generation using Logic. This paper researches explanation generation from a KR point of view and conducts experiments measuring explanation size and runtime on random formulas and formulas from a Blocksworld instance. This paper provides a perspective on explanations between two knowledge bases, and runs parallel to work on model reconciliation in planning literature.