Plan Explanations as Model Reconciliation: Moving Beyond Explanation as Soliloquy

1 Introduction

There has been significant renewed interest recently in developing AI systems that can automatically provide explanations to humans in the loop. While much of the interest has been focused on learning systems that can explain their classification decisions, a related broader problem involves providing explanations in the context of human-AI interaction and humanin-the-loop decision making systems. In such scenarios, the automated agents are called upon to provide explanation of their behavior or plans [Langley, 2016].

Although explanation of plans has been investigated in the past (c.f. [Kambhampati, 1990; Sohrabi et al., 2011]), much of that work involved the planner explaining its decisions with respect to its own model (i.e. current state, actions and goals) and assuming that this "soliloquy" also helps the human in the loop. While such a sanguine assumption may well be requited when the human is an expert "debugger" and is intimately familiar with the agent's innards, it is completely unrealistic in most human-AI interaction scenarios, where the humans may have a domain and task model that differs significantly from that used by the AI system. This is illustrated in Figure 1, where the plans generated by the AI system with respect to its model need to be interpreted by the human with respect to his model. Of course, the AI system can avoid the need to provide explanations by being "explicable" [Zhang et al., 2017; Kulkarni et al., 2016] - i.e., generate plans that also make sense with respect to the humans' model. Such explicability requirement however puts additional constraints on the agent's plans, and may not always be feasible. When the robot's plan is different from what the human would expect given his model of the world, the robot will be called on to "explain" its plan. We posit that such explanations should be seen as the robot's attempt to move the human's model to be in conformance with its own.

∗Authors marked with asterix contributed equally.

The primary contribution of this paper is to show how such model updates or explanations can be formulated concisely as the model reconciliation problem (MRP), which aims to make minimal changes to the human's model to bring it closer to the robot's model, in order to make the robot's plan optimal with respect to this changed human's model. One immediate complication in tackling an MRP is that the human's model is not directly made available to the robot, and will have to be learned instead (c.f. [Zhang et al., 2017]). The learned model may also be in a different form and at a different level of abstraction than the one used by the robot [Tian et al., 2016; Perera et al., 2016]. Nevertheless, for the purposes of this paper, we will assume that the human's model is made available and is in PDDL format, just like the robot's one. This allows us to focus on the explanation generation aspects.

In the rest of the paper, we will formalize the scenario in Figure 1 as the Multi-Model Planning setting, and characterize explanation generation as a model reconciliation process in it. We start by enumerating a few desirable requirements of such explanations - namely completeness, conciseness, monotonicity and computability. We then formulate different kinds of explanations that satisfy these requirements and relax one of these requirements at a time in the interests of computability. We present an A∗ -search formulation for searching in the space of models to compute these explanations, and develop approximations and heuristics for the same. Finally, we present a preliminary evaluation of the efficiency of our algorithms for generating explanations in randomly generated problems in a few benchmark planning domains.

AMotivating Example Let us illustrate the concept of explanations via model reconciliation through an example based on the Fetch robot whose design requires it to tuck its arms and lower its torso or crouch before moving - which is not obvious to a human navigating it. This may lead to an unbalanced base and toppling of the robot if the human deems such actions as unnecessary. The move action for the robot is described in PDDL in the following model snippet -

(:action move :parameters (?from ?to - location) :precondition (and (robot-at ?from) (hand-tucked) (crouched)) :effect (and (robot-at ?to) (not (robot-at ?from)))) (:action tuck :parameters () :precondition () :effect (and (hand-tucked) (crouched))) (:action crouch :parameters () :precondition () :effect (and (crouched)))

Notice that the tuck action also involves a lowering of torso so that the arm can rest on the base once it is tucked in. Now, consider a problem with the following initial and goal states (here, identical for both the robot and the human) -

(:init (block-at b1 loc1) (robot-at loc1) (hand-empty)) (:goal (and (block-at b1 loc2)))

An optimal plan for the robot, in this case, involves a tuck action followed by a move -

pick-up b1 -> tuck -> move loc1 loc2 -> put-down b1

The human, on the other hand, expects a much simpler model, as shown below. The move action does not have the preconditions for tucking the arm and lowering the torso, while tuck does not automatically lower the torso either.

(:action move :parameters (?from ?to - location) :precondition (and (robot-at ?from) :effect (and (robot-at ?to) (not (robot-at ?from)))) (:action tuck :parameters () :precondition () :effect (and (hand-tucked)) (:action crouch :parameters () :precondition () :effect (and (crouched)))

Clearly, the original plan is no longer optimal (and hence explicable) here. One possible model update (i.e. explanation) that can mitigate this situation is -

Explanation >> MOVE_LOC1_LOC2-has-precondition-HAND-TUCKED

This correction brings the human and the robot model closer, and is necessary and sufficient to make the robot's plan optimal in the resultant domain. As indicated before, we refer to such model corrections as multi-model explanations.

2 RelatedWork

Our view of explanation as a model reconciliation process is supported by studies in the field of psychology which stipulate that explanations "privilege a subset of beliefs, excluding possibilities inconsistent with those beliefs... can serve as a source of constraint in reasoning..." [Lombrozo, 2006]. This is achieved in our case by the appropriate change in the expectation of the model that is believed to have engendered the plan in question. Further, authors in [Lombrozo, 2012] also underline that explanations are "typically contrastive... the contrast provides a constraint on what should figure in a selected explanation..." - this is especially relevant in order for an explanation to be self-contained and unambiguous. Hence the requirement of optimality in our explanations, which not only ensures that the current plan is valid in the updated model, but is also better than other alternatives. This is consistent with the notion of optimal (single-model) explanations investigated in [Sohrabi et al., 2011] where less costly plans are referred to as preferred explanations. The optimality criterion, however, makes the problem fundamentally different from model change algorithms in [G¨obelbecker et al., 2010; Herzig et al., 2014; Bryce et al., 2016] which focus more on the feasibility of plans or correctness of domains.

Finally, while the human-in-the-loop setting discussed here does bring back memories of mixed-initiative planners of the past [Ferguson et al., 1996; Ai-Chang et al., 2004], most of the work there involved the humans entering the land of planners; and not the other way around. Not surprisingly, it did not have the planner taking the human model into account in its planning or explanation.

3 The Multi-Model Planning (MMP) Setting

A Classical Planning Problem [Russell et al., 2003] requires a model M = 〈D, I, G〉 (represented in PDDL [McDermott et al., 1998]) consisting of the domain D = 〈F,A〉 - where F is a finite set of fluents that define the world state s ⊆ F, and A is a finite set of actions - and the initial and goal states I, G ⊆ F. Action a ∈ A is a tuple 〈ca, pre(a), eff+(a), eff-(a)〉 where ca denotes cost, and pre(a), eff+(a), eff-(a) ⊆ F is the set of preconditions and add / delete effects, i.e. δM(s, a) |= ⊥ if s ̸|= pre(a); else δM(s, a) |= s ∪ eff+(a) \ eff-(a) where δM(·) is the transition function. The cumulative transition function is given by δM(s, 〈a1, a2, . . . , an〉) = δM(δM(s, a1), 〈a2, . . . , an〉). The solution to the planning problem is a sequence of actions or a (satisficing) plan π = 〈a1, a2, . . . , an〉 such that δM(I, π) |= G. The cost of a plan π is given by C(π,M) = ∑a∈π ca if δM(I, π) |= G; ∞ otherwise. The cheapest plan π∗ = argminπ{C(π,M) ∀π such that δM(I, π) |= G} is called the (cost) optimal plan. We will refer to the cost of the optimal plan in the model M as C ∗M.

From the perspective of classical planning, the question of plan explicability may indeed be posed in terms of plan optimality. The intuition here is that if a plan is the best possible plan that the planner could have come up with, then it is also comprehensible to a human with the same planning model and reasoning capabilities, i.e. the existence of such a plan requires no further explanation. However, the human's understanding of a planning problem often differs from the planner's, e.g. if she does not have access to the planner's actual goal, or does not know the current state accurately, or has a different perception of the action model being used. In such situations, a plan π produced in the robot's model MR is being evaluated in terms of a different model MH in the human's mind, as a result of which what is optimal (and explicable) in the planner's model may no longer be so in the human's, i.e C(π,MR) = C ∗MR, but C(π,MH ) > C ∗MH. Based on this, we define the following setting -

A Multi-Model Planning (MMP) Setting is given by the tuple 〈MR,MH 〉, where MR = 〈DR, I R, G R〉 is the planner's model of the planning problem, while MH = 〈DH , I H , GH 〉 is the human's approximation of the same.

As we mentioned in the introduction, from the point of view of the planner, there can be two approaches to achieve common ground with the human in such settings - (1) Change its own behavior in order to be explicable to the human - in [Zhang et al., 2017; Kulkarni et al., 2016] the authors propose to modify the robot plan π itself so that C(π,MH ) ≈ C ∗MH ∧ δMR(I R, π) |= GR. Thus the planner chooses to sacrifice optimality in order to make its behavior explicable to the human observer; and (2) Bring the human's model closer to its own by means of explanations in the form of model updates - here, the planner does not change its own behavior, but rather corrects the human's incorrect perception of its model via explanations. We refer to this as the model reconciliation process. In this paper, we will focus on this only.

The Model Reconciliation Problem (MRP) is a tuple 〈π∗ , 〈MR,MH 〉〉 where C(π∗ ,MR) = C ∗MR, i.e. the robot's model, the human's approximation of it, and a plan that is optimal in the former.

Before we go into the details of the model reconciliation process, we will define the following state representation over planning problems. We intend to use this in our "model-space search" for model reconciliation.

A mapping function Γ : M ↦→ s represents any planning problemM = 〈〈F, A〉, I, G〉 as a state s ⊆ F as follows -

We can now define a model-space search problem 〈〈F,Λ〉, Γ(M1), Γ(M2)〉 with a new action set Λ containing unit model change actions λ : F → F such that |s1∆s2| = 1, where the new transition or edit function is given by δM1,M2 (s1, λ) = s2 such that condition 1 : s2 \ s1 ⊆ Γ(M2) and condition 2 : s1 \ s2 ̸⊆ Γ(M2) are satisfied. This means that model change actions can only make a single change to a domain at a time, and all these changes are consistent with the model of the planner. The solution to a model-space search problem is given by a set of edit functions {λi} that can transform the model M1 to the model M2, i.e. δM1,M2 (Γ(M1), {λi}) = Γ(M2).

A Multi-Model Explanation denoted by E is a solution to an MRP, i.e. a solution to the model-space search problem 〈〈F,Λ〉, Γ(MH ), Γ(̂ M)〉 with the transition function δMH,MR such that C(π∗ , ̂ M)-C ∗̂ M < C(π∗ , MH )-C ∗MH .

This means that in the updated model after the explanation, the plan in question is closer to the optimal (and hence less inexplicable) than it was in the original model that the human had. The human in the loop can either chose to use this explanation to update her own model or negotiate in course of further dialog (e.g. to update the robot's model).

As we go on to develop approaches to compute different types of such explanations, we will consider the following four requirements that characterize each solution.

• R1. Completeness - Explanations of a plan should be able to be compared and contrasted against other alternatives, so that no better solution exists. We enforce this property by requiring that in the updated human model the plan being explained is optimal.

• R2. Conciseness - Explanation should be concise so that they are easily understandable to the explainee. Larger an explanation is, the harder it is for the human to incorporate that information into her deliberative process.
• R3. Monotonicity - This ensures that remaining model differences cannot change the completeness of an explanation, i.e. all aspects of the model that engendered the

plan have been reconciled. This thus subsumes completeness and requires more detailed 1 explanations.

R4. Computability -While conciseness deals with howeasy it is for the explainee to understand an explanation, computability measures the ease of computing the explanation from the point of view of the planner.

We will now introduce different kinds of multi-model explanations that can participate in the model reconciliation process, propose algorithms to compute them, and compare and contrast their respective properties. We note that the requirements outlined above are in fact often at odds with each other - an explanation that is very easy to compute may be very hard to comprehend. This (as seen in Table 1) will become clearer in course of this discussion.

A simple way to compute an explanation would be to provide the model differences pertaining to only the actions that are present in the plan that needs to be explained -

Clearly, such an explanation is easy to compute and concise by focusing only on plan being explained. However, it may also contain information that need not have been revealed, while at the same time ignoring model differences elsewhere inMH that could have contributed to the plan being suboptimal in it. Thus, it is incomplete. An adoption of VAL [Howey et al., 2004] to the MMP setting will be, in fact, a subset of such PPEs, and suffer from the same limitations. An easy way to compute a complete explanation would be to provide the entire model difference to the human -

AModel Patch Explanation (MPE) is given by E MPE = Γ(MR)∆Γ(MH ).

This is clearly also easy to compute but can be quite large and is hence far from being concise. Thus, in the rest of paper, we will try to minimize the size (and hence increase the comprehensibility) of explanations by searching in the space of models and thereby not exposing information that is not relevant to the plan being explained while still trying to satisfy as many requirements as we can.

AMinimally Complete Explanation (MCE) is the shortest complete explanation, i.e.

The explanation provided before in the Fetch domain is indeed the smallest domain change that may be made to make the given plan optimal in the updated action model, and is thus an example of a minimally complete explanation. An implicit assumptions we make here is that the computation power (or planning capability) of the human is is the same as that of the planner. This means that the human can compute the optimal plan given a planning problem.

1 This is a very useful property to have. Doctors, for example, reveal different amount of details of their model to their patients as opposed to their peers. Further, the idea of completeness, i.e. withholding information on other model changes as long as they explain the observed plan, is also quite prevalent in how we deal with similar scenarios ourselves - e.g. progressing from Newtonian physics in high school to Einsteins Laws of Relativity in college.

Model-space search for MCEs To compute MCEs, we employ A∗ search, similar to [Wayllace et al., 2016], in the space of models, as shown in Algorithm 1. Given an MRP, we start off with the initial state Γ(MH ) derived from the human's expectation of a given planning problemMR, and modify it incrementally until we arrive at a planning problem ̂ M with C(π∗ , ̂ M) = C ∗̂ M, i.e. the given plan is explained. Note that the model changes are represented as a set, i.e. there is no sequentiality in the search problem. Also, we assign equal importance to all model corrections. We can easily capture differential importance of model updates by attaching costs to the edit actions λ - the algorithm remains unchanged.

We also employ a selection strategy of successor nodes to speed up search (by overloading the way the priority queue is being popped) by first processing model changes that are relevant to the actions in π∗R and πH before the rest.

Proposition 1 The successor selection strategy outlined in Algorithm 1 yields an admissible heuristic for model space search for minimally complete explanations.

Proof Let E be the MCE for anMRP problem and let E ′ be any intermediate explanation found by our search such that E ′ ⊂ E, then the set E \ E ′ must contain at least one λ related to actions in the set {a | a ∈ π∗R ∨a ∈ π′ } (where π′ is the optimal plan for the model ˆMwhere δMH,MR (Γ(MH ), E ′ ) = Γ( ˆM). To see why this is true, consider an E ′ where |E ′ | = |E| -1. If the action in E \ E ′ does not belong to either π∗R or π′ then it can not improve the cost of π∗R in comparison to π′ and hence E can not be the MCE. Similarly we can show that this relation will hold for any size of E ′ . We can leverage this knowledge about E \ E ′ to create an admissible heuristic that will only consider the relevant changes at any given point of time (by giving very large values to all other changes).

We also note that the optimality criterion is relevant to both the cases where the human expectation is better, or when it is worse, than the plan computed by the planner. This might be counter to intuition, since in the latter case one might expect that just establishing feasibility of a better (than expected optimal) plan would be enough. Unfortunately, this is not the case, as can be easily seen by creating counter-examples where other faulty parts of the human model might disprove the optimality of the plan in the new model -

Proposition 2 If C(π∗ ,MH ) < minπ C(π,MH ), then ensuring feasibility of the plan in the modified planning problem, i.e. δ̂ M(̂ I, π∗ ) |= ̂ G, is a necessary but not a sufficient condition for ̂ M = 〈 ̂D, ̂ I, ̂ G〉 to yield a valid explanation.

Algorithm 1 Search for Minimally Complete Explanations

1: procedure MCE-SEARCH 2: Input: MRP 〈π∗ , 〈MR,MH 〉〉 3: Output: Explanation EMCE 4: Procedure: 5: fringe ←Priority Queue() 6: c list ←{} ▷ Closed list 7: π∗R ← π∗ ▷ Optimal plan being explained 8: πH ← π such that C(π,MH ) = C∗MH ▷ Plan expected by human 9: fringe.push(〈MH , {}〉, priority = 0) 10: while True do 11: 〈 ̂ M, E〉, c ← fringe.pop( ̂ M) 12: if C(π∗R, ̂ M) = C∗̂M then return E ▷ Return E if π∗R optimal in ̂ M 13: else 14: c list ←c list ∪ ̂ M 15: for f ∈ Γ( ̂ M) \ Γ(MR) do ▷Models that satisfy condition 1 16: λ ← 〈1, { ̂ M}, {}, {f}〉 ▷ Removes f from ̂ M 17: if δMH,MR(Γ( ̂ M), λ) ̸∈ c list then 18: fringe.push(〈δMH ,MR (Γ( ̂ M), λ), E ∪ λ〉, c + 1) 19: for f ∈ Γ(MR) \ Γ(̂ M) do ▷Models that satisfy condition 2 20: λ ← 〈1, { ̂ M}, {f}, {}〉 ▷ Adds f to ̂ M 21: if δMH,MR(Γ( ̂ M), λ) ̸∈ c list then 22: fringe.push(〈δMH ,MR (Γ( ̂ M), λ), E ∪ λ〉, c + 1) 23: procedure PRIORITY QUEUE.POP( ˆM) 24: candidates ← {〈〈 ̂ M, E〉, c∗ 〉 | c∗ = arg minc 〈〈 ̂ M, E〉, c〉} 25: pruned list ← {} 26: πH ← π such that C(π, ˆM) = C∗ˆM 27: for 〈〈 ̂ M, E〉, c〉 ∈ candidates do 28: if ∃a ∈ π∗R ∪πH such that τ -1 (Γ( ̂ M)∆Γ( ˆM)) ∈ {ca}∪pre(a)∪ eff+(a) ∪ eff-(a) then ▷ Candidates relevant to π∗R or πH 29: pruned list ← pruned list ∪ 〈〈̂ M, E〉, c〉 30: if pruned list = φ then 〈 ̂ M, E〉, c ∼ Unif(candidate list) 31: else 〈 ̂ M, E〉, c ∼ Unif(pruned list)

Note that a minimally complete explanation for an MRP can be rendered invalid given further updates to the model. This can be easily demonstrated in our running example in the Fetch domain. Imagine that if, at some point, the human were to find out that the action move also has a precondition (crouched), then the previous robot plan will no longer make sense to the human since now, according to the human's faulty model (being unaware that the tucking action also lowers the robot's torso) the robot would need to do both tuck and crouch actions before moving. Consider the following explanation in the Fetch domain instead -

Explanation >> TUCK-has-add-effect-CROUCHED MOVE_LOC2_LOC1-has-precondition-CROUCHED

This explanation does not reveal all model differences but at the same time ensures that the robot's plan remains optimal for this problem, irrespective of any other changes to the model, by accounting for all the relevant parts of the model that engendered the plan. It is also the smallest possible among all such explanations. The requirement of monotonicity and minimality brings us to the notion of -

A Minimally Monotonic Explanation (MME) is the shortest explanation that preserves both completeness and monotonicity, given the MRP 〈π∗ , 〈MR,MH 〉〉, i.e.

Algorithm 2 Search for Minimally Monotonic Explanations

1: procedure MME-SEARCH 2: Input: MRP 〈π∗ , 〈MR,MH 〉〉 3: Output: Explanation EMME 4: Procedure: 5: EMME ←{} 6: fringe ←Priority Queue() 7: c list ←{} ▷ Closed list 8: h list ←{} ▷ List of incorrect model changes 9: fringe.push(〈MR, {}〉, priority = 0) 10: while fringe is not empty do 11: 〈 ̂ M, E〉, c ← fringe.pop( ̂ M) 12: if C(π∗ , ̂ M) > C∗̂M then 13: h list ← h list ∪ (Γ(̂ M) ∆ Γ(MR)) ▷ Updating h list 14: else 15: c list ←c list ∪ ̂ M 16: for f ∈ Γ( ̂ M) \ Γ(MH ) do ▷Models that satisfy condition 1 17: λ ← 〈1, { ̂ M}, {}, {f}〉 ▷ Removes f from ̂ M 18: if δMR,MH (Γ( ̂ M), λ) ̸∈ c list and ∄S s.t. (Γ( ̂ M)∆Γ(MR)) ⊇ S ∈ h list then ▷ Prop 3 19: fringe.push(〈δMR,MH (Γ( ̂ M), λ), E ∪ λ〉, c + 1) 20: EMME ← max|·|{EMME , E} 21: for f ∈ Γ(MH ) \ Γ(̂ M) do ▷Models that satisfy condition 2 22: λ ← 〈1, { ̂ M}, {f}, {}〉 ▷ Adds f from ̂ M 23: if δMR,MH (Γ( ̂ M), λ) ̸∈ c list and ∄S s.t. (Γ( ̂ M)∆Γ(MR)) ⊇ S ∈ h list then ▷ Prop 3 24: fringe.push(〈δMR,MH (Γ( ̂ M), λ), E ∪ λ〉, c + 1) 25: EMME ← max|·|{EMME , E} 26: EMME ← (Γ(̂ M) ∆ Γ(MR)) \ EMME 27: return EMME

The last constraint enforces the monotonicity requirement. This means that beyond the model obtained from the minimally monotonic explanation, there do not exist any models which are not explanations of the same MRP, while at the same time making as few changes to the original problem as possible. It follows that this is the largest set of changes that can be done on the planner's planning problemMR and still find a model ̂ Mwhere C(π∗ , ̂ M) = C ∗̂ M - we are going to use this property in the search for MMEs.

We also note that an MME solution may not be unique to an MRP problem. This can happen when there are multiple model differences supporting the same causal links in the plan - an MME can get by (i.e. guarantee optimality in the modified model) by only exposing one of them to the human.

Proposition 4 MMEs are not unique, i.e. there might be multiple minimally monotonic solutions to an MRP.

We also note that even though MCEs are an abridged version of an MME, it is easy to see that an MCE may not necessarily be part of an actual MME. This is due to the nonuniqueness of MMEs. Thus, we emphasize -

Proposition 5 An MCE may not be a subset of an MME, but it is always smaller or equal in size, i.e. |MCE| ≤ |MME|.

Model-space search for MMEs This is similar to the model-space search for MCEs described before, but this time starting from the robot's model MR instead. The goal here is to find the largest set of model changes for which the explicability criterion becomes invalid for the first time (due to either suboptimality or inexecutability). This requires a search over the entire model space, as described in detail in Algorithm 2. We can leverage Proposition 3 to reduce our search space. Starting from MR, given a set of model changes E where δMR,MH (Γ(MR), E) = Γ( ̂ M) and C(π∗ , ̂ M) > C ∗̂ M, no superset of E can lead to an MME solution. In Algorithm 2, we keep track of such unhelpful model changes in the list h list. The variable E MME keeps track of the current best list of model changes. Whenever we find a new set of model changes where π∗ is optimal and is larger than E MME , we update E MME with E. The resulting MME is all the possible model changes that did not appear in E MME .

Figure 3 contrasts MCE with MME search. MCE search starts fromMH , computes updates ̂ M towards MR and returns the first node (indicated in orange) where C(π∗ , ̂ M) = C ∗̂ M. MME search starts from MR and moves towards MH . It finds the longest path (indicated in blue) where C(π∗ , ̂ M) = C ∗̂ M for all ̂ M in the path. The MME (shown in green) is the rest of the path towardsMH .

Approximate Solution for MCEs

Both MCEs and MMEs may be hard to compute - in the worst case it involves a search over the entire space of model differences. Thus the biggest bottleneck here is the check for optimality of a plan given a new model. A check for necessary or sufficient conditions for optimality, without actually computing optimal plans can be used as a powerful tool to further prune the search tree. In the following section, we thus investigate an approximation to an MCE by employing a few simple proxies to the optimality test. By doing this we lose the completeness guarantee but improve the computability of an explanation. Specifically, we replace the equality test in line 12 of Algorithm 1 by the following rules -

1. δ̂ M(̂ I, π∗R) |= ̂ G; and

1. Each action contributes at least one causal link to π∗R.

The first criterion simply ensures that the plan π∗R originally computed by the planner is actually valid in the new hypothesis model. Criterion (2) requires that this plan has either become better in the new model or at least that the human's expected plan π∗H has been disproved. Finally, in Criterion (3), we ensure that for each action ai ∈ π∗R there exists an effect p that satisfies the precondition of at least one action ak (where ai ≺ ak) and there exists no action aj (where ai ≺ aj ≺ ak) such that p ∈ eff-(aj).

Proposition 6 Criterion (3) is a necessary condition for optimality of π∗ in ̂ M.

Proof Assume that for an optimal plan π∗R, there exists an action ai where criterion (3) is not met. Now we can rewrite π∗R as π′R = 〈a0, a1, . . . , ai-1, ai, ai+1, . . . , an, an+1〉, where pre(a0) = φ and eff+(a0) = {I} and pre(an+1) = {G} and eff(an+1) = φ. It is easy to see that δ ̂ M(φ, π′R) |= G. Now let us consider a cheaper plan ˆ π′R = 〈a0, a1, . . . , ai-1, ai+1, . . . , an, an+1〉. Since ai does not contribute any causal links to the original plan π∗R, we will also have δ ̂ M(φ, ˆπ′R) |= G. This contradicts our original assumption of π∗R being optimal, hence proved.

4 Empirical Evaluations

Our explanation generation system (as previewed in the Fetch domain) integrates calls to Fast-Downward [Helmert, 2006] for planning, VAL [Howey et al., 2004] for plan validation, and pyperplan [Alkhazraji et al., 2016] for parsing. The results reported here are from experiments run on a 12 core Intel(R) Xeon(R) CPU with an E5-2643 v3@3.40GHz processor and a 64G RAM. The latest version of the code will be available at https://goo.gl/Bybq7E. We use three planning domains - BlocksWorld, Logistics and Rover - for our experiments. In order to generate explanations we created the human model by randomly removing parts (preconditions and effects) of the action model. Though the following experiments are only pertaining to action model differences, it does not make any difference at all to the approaches, given the way the state was defined. Also note that these removals, as well as the corresponding model space search, was done in the lifted representation of the domain.

Table 2 In Table 2 we make changes at random to the domains and measure the number of explanations produced and the time taken (in secs) to produce them, against the ground truth. Observe the gains produced by the heuristic in terms of time spent on each problem. Further, note how close the approximate version of MCEs are to the exact solutions. As expected, MME search is significantly costlier to compute than MCE. However, note that both MCEs and MMEs are significantly smaller in size (∼ 20%) than the total model difference (which can be arbitrarily large) in certain domains, further underlining the usefulness of generating minimally complete explanations as opposed to dumping the entire model difference on the human. A general rule of thumb is -

Note that the time required to calculate an MME in the Logistics problems is lower than that for the corresponding MCE. This is because for most of these problems a single change in the planner's model made the plan be no longer optimal so that the search ended after checking all possible unit changes. In general, closer an MCE is to the total number of changes shorter the MME search would be. Also note how PPE solutions, though much easier to compute, do not have completeness and monotonicity properties, and yet often spans the entire model difference, containing information that are not needed to support the optimality of the given plan.

Table 3 We now increase the number of changes in the human model in BlocksWorld, and illustrate the relative time (in secs) taken to search for exact MCEs in Table 3. As expected there is an exponential increase in the time taken, which can be problematic with even a modest number of model differences. This further highlights the importance of finding useful approximations to the explanation generation problem.

Table 4 Finally, we demonstrate how Proposition 3 reduces the number of nodes that need to be searched to find MMEs in random problems from the BlocksWorld domain with 10 faults in the human model, as opposed to the total possible 210 models that can be evaluated - equal to the cardinality of the power set of model changes |P(Γ(MR)∆Γ(MH ))|.

5 Conclusions and FutureWork

In this paper, we argued that to explain its plans to the human agents in the loop, an AI system needs to explicitly acknowledge that the human may be using a different model than it does. Explanations in this multi-model setting become a process of identifying and reconciling the relevant differences between the models. One immediate future direction is to allow for human's models that are of different form and/or level of abstraction than the robot's, so as to allow effective learning of the human's models (c.f. [Tian et al., 2016; Zhang et al., 2017]), as well as allow for different cognitive abilities of the human using ϵ-optimality or top-K plans [Riabov et al., 2014] for hypothesis generation.

In cases where the ground truth is not known, the explanation process might also need to consider distributions over relevant models, and iterative refinement of the same via dialog with the human. Work on plan monitoring [Fritz and McIlraith, 2007] can also provide clues to speeding up the search process by providing proxies to the optimality check.

Also note that we insisted that explanations must be compatible with the planner's model. If this requirement is relaxed, it allows the planner to generate alternative explanations that it knows are not true, and thus deceive the human. While endowing the planner with such abilities may warrant significant ethical concerns, we note that the notion of white lies, and especially the relationship between explanations, excuses and lies [Boella et al., 2009] has received very little attention [van Ditmarsch, 2014] and affords a rich set of exciting research problems.

Acknowledgments

This research is supported in part by the ONR grants N00014161-2892, N00014-13-1-0176, N00014- 13-1-0519, N00014-15-1-2027, and the NASA grant NNX17AD06G.