Hierarchical Expertise-Level Modeling for User Specific Robot-Behavior
Explanations

arXiv:1802.06895v1 [cs.AI] 19 Feb 2018

Sarath Sreedharan and Siddharth Srivastava and Subbarao Kambhampati
School of Computing, Informatics, and Decision Systems Engineering
Arizona State University, Tempe, AZ 85281 USA
{ ssreedh3, siddharths, rao } @ asu.edu
Abstract
There is a growing interest within the AI research
community to develop autonomous systems capable of explaining their behavior to users. One aspect
of the explanation generation problem that has yet
to receive much attention is the task of explaining
plans to users whose level of expertise differ from
that of the explainer. We propose an approach for
addressing this problem by representing the user’s
model as an abstraction of the domain model that
the planner uses. We present algorithms for generating minimal explanations in cases where this abstract human model is not known. We reduce the
problem of generating explanation to a search over
the space of abstract models and investigate possible greedy approximations for minimal explanations. We also empirically show that our approach
can efficiently compute explanations for a variety
of problems.

1

Introduction

AI systems have the potential to transform society by assisting humans in diverse situations ranging from extraplanetary
exploration to assisted living. In order to achieve this potential, however, humans working with such systems need to be
able to understand them just as they would understand human
team members. This presents a number of challenges because
most humans do not understand AI algorithms and their behavior at the same intuitive level that they understand other
humans. Recently, there have been attempts to bridge this
gap by developing systems capable of explaining its behavior. Most recently [Chakraborti et al., 2017] formulated the
problem of generating explanations for plans as that of model
reconciliation. Their approach relied on identifying ways of
bringing the human model (i.e the explainee model) closer to
the robot model so that the plan in question appears optimal
in the new model. Their work looked at scenarios in which the
human used a model of the domain that was at the same level
of fidelity as the one used by the agent to generate the plan.
This approach, unfortunately, did not capture scenarios where
the human possessed a lower level of expertise and thus used
a more “abstract” or coarser representation of the model as
compared to the AI agent.

In this paper, we propose a new approach to this problem
where the agent explains its ongoing or planned behavior to
humans with arbitrary levels of expertise. We consider explanations in the framework of counterfactual reasoning, where
a user who is confused by the agent's activity (or proposed
activity) presents alternative behavior that they would have
expected the agent to execute. This aligns with the widely
held belief that humans expect explanations to be contrastive
[Miller, 2017]. In keeping with the terminology used in social
sciences literature we will call the set of alternative behavior
as a foil to the proposed robot behavior.
For instance, consider a mission-control operator who
needs to supervise the activity of an autonomous robot on
Mars in the midst of a sandstorm that could present valuable
data for analysis. If the robot proposes to go back to the base
before going to a vantage point for observing the storm, the
operator would naturally be perplexed, and may be motivated
to ask, why doesn't the robot go directly to the vantage point?!
Similarly, a human team member at a manufacturing plant
may be perplexed by a robot's unnecessary detours while assembling an automobile engine. Not only do such situations
involve personnel with varying skill levels, they also place a
premium on the size of explanations.
A natural interaction would have the robot present an explanation about why the human's counterfactual suggestion
would not apply in the current situation. This explanation
could involve facts about the environment as well as about
the robot's constraints. E.g., “I need to get a new battery pack
to observe the sandstorm for at least 30 minutes without interruption”. Such explanations need to be attuned to the level
of understanding of the human involved. If the operator happens to be the lead designer of the robot's sequential decisionmaking engine, the robot could provide more specific information, e.g. “I am carrying battery-pack #00920”, because
this operator knows that some battery packs wouldn't allow it
to carry out the full observation.
In this paper we present the Hierarchical Expertise-Level
Modeling or the HELM approach for facilitating such context and user-specific explanations. HELM generates the appropriate explanation by searching through a model lattice of
possible abstractions of the agent's model. Each model within
this lattice represents a different level of understanding of the
task, with the highest fidelity representation (corresponding
to the most detailed understanding of the domain used by the

Each state s ∈ S is uniquely represented by the set of propositions that are true in that state, i.e, s ⊆ P .
Each action a ∈ A is associated with a set of preconditions
preca that needs to hold for the effects (ea ) of that action to be
applied to a particular state. Each effect set ea can be further
−
separated into a set of add effects e+
a and delete effects ea .
The result of executing an actions a on a state s in this setting
is defined as follows

−
(S ∪ e+
a ) \ ea , if preca ⊆ S
a(S) =
S
otherwise

Figure 1: An illustration of the hierarchical explanation process.
The human observer who views the task at a higher level of abstraction expects the rover to execute a different plan from the one chosen
by the rover. The rover presents the human with an explanation it believes will help resolve the foils in the human’s updated model.

robot) forming the base of the lattice and the model representing the most naive understanding of the task (for example one
held by a lay user) forming the highest node. We assume that
the user's understanding of the domain will align with one of
these abstracted models.
Our explanations consist of information that may be absent
in the user's abstract model, and show why the foil doesn't
apply in the true situation. These explanations will cause the
user’s model to shift to a more accurate model in the lattice
(and ultimately achieve model reconciliation). We will refer
to model updates constituting these explanations as model
concretizations. Our framework can also be extended to situations where a user's understanding is abstract and erroneous.
In this paper, we focus on the fundamental aspects of the
problem and restrict our attention to settings where the user's
understanding is a sound abstraction of the actual situation.
Since the user's level of expertise is unknown to the agent,
our algorithm estimates the human model before searching
for an explanation.
The rest of this paper is structured as follows. In section 2,
we present the formal framework we use to study this problem. Section 3 will cover different approaches for generating
explanation and in section 4 we present empirical evaluation
of these methods on standard IPC domains. Finally in sections 5 and 6, we will discuss the related work and possible
future direction for this work.

2

Hierarchical Expertise-Level Models

In this work, we will focus on abstractions that form models by projecting out state fluents. While the presentation in
the following sections is equally valid for both predicate and
propositional abstractions, we will focus on propositional abstractions to keep our formulation clear and concise. We will
look at planning models of the form M = hP, S, A, I, Gi
where P gives the set of state fluents, S the set of possible
states, A the set of actions, I the initial state and G the goal.

A plan π is defined as a sequence of actions (ha1 , .., an i, n
being the size of the plan), and a plan is said to be executable
for the problem M (i.e, π(I) |=M G) if π(I) ⊇ G.
Following works like [Seipp and Helmert, 2013; Backstrom and Jonsson, 2013], we will also use the concept of a
transition system induced by the planning model to describe
ideas related to abstraction. Intuitively, a transition system
constitutes a graph where the nodes represent possible states,
and the edges capture the transitions between the states that
are valid in the corresponding planning model. We refer the
readers to the previously mentioned works for further analyses of state transition systems and their connection to abstractions.
Definition 1. For a set of states S, a set X is said to be a
propositional abstraction of S with respect to some set of
propositions Λ, if there exist a surjective mapping fΛ : S →
X, such that for every state s ∈ S, there exists a state fΛ (s) ∈
X where fΛ (s) = s \ Λ
For notational convenience we will refer to the set of states
obtained by abstracting out the proposition set Λ from some
set of states S as [S]fΛ .
Definition 2. For a planning model M = hP, S, A, I, Gi
with a corresponding transition system T , a model
M0 = hP 0 , S 0 , A0 , I 0 , G0 i with a transition system T 0
is considered an abstraction of M , if there exist a set
of propositions Λ, such that P 0 = P − Λ, S 0 = [S]fΛ ,
a
I 0 = fΛ (I), G0 = fΛ (G) and for every transition s1 −
→ s2
in T corresponding to an action a, there exists an equivalent
a
transition (s1 \ Λ) −
→ (s2 \ Λ) in T 0 .
As per Definition 2, abstractions induce an “imprecise”
model of the underlying domain. All plans that were valid
in the original model will have an equivalent plan in this
new model. We will use the operator @ to capture the fact
that a model M is less abstract than the model M0 , i.e if
M @ M0 then there exist a set of propositions Λ such that
M0 = [M]fΛ . With the definition of abstraction and related
notations in place, we are now ready to define a model lattice. Most approaches discussed in this paper will rely on this
lattice to both estimate human’s model and to identify explanations.
Definition 3. For a model M# , the model lattice L is a tuple of the form L = hM, E, P, `i, where M is the set of lattice
nodes ,E the lattice edges, P the superset of propositions considered for abstraction within this lattice and finally ` is a
function mapping edges to labels, provided M# ∈ M and all

nodes M0 ∈ M satisfy the condition M# v M0 . Additionally, for each edge ei = (Mi , Mj ) there exists a proposition
p ∈ P such that [Mi ]fp = Mj and `(Mi , Mj ) = p.
Thus each edge in this lattice corresponds to an abstraction
formed by projecting out a single proposition (represented by
the label of the edge). We can also define a concretization
function γp that retrieves the model that was used to generate
the given abstract model by projecting out the proposition p,
i.e, γp (M) = M0 if (M0 , M) ∈ E and `(M0 , M) = p.
Through the rest of this work, we will make some assumptions on the structure of the lattice L and the abstraction methods used by L to simplify our discussions. In this paper, we
will focus on lattices where each node in M has an incoming edge for every proposition missing from its corresponding model. We will refer to lattices that satisfy this property as
Proposition Conserving lattices. Additionally, we will call
a proposition conserving lattice that contains an abstract node
corresponding to each possible subset of P as the Complete
Lattice for M given P.
A lattice L is Proposition Conserving, if for any model
M ∈ M and ∀p ∈ P, if p not in PM then there exists a model
M0 ∈ M, such that (M0 , M) ∈ E and `(M0 , M) = p).
Notice that enforcing conservation of propositions doesn’t require any further assumptions about the human model and can
be easily ensured by the agent generating the lattice.
We also assume that all abstraction functions used in generating the models in the lattice are commutative and idempotent, i.e., [[M]fp1 ]fp2 = [[M]fp2 ]fp1 and [[M]fp1 ]fp1 =
[M]fp1 . Readers can refer to [Srivastava, Russell, and Pinto,
2016] for a comprehensive list of ways to generate imprecise
abstract models that satisfy these properties.
As mentioned earlier, we consider an explanation generation setting where the human observer uses a task
model (denoted as MH = hPH , SH , AH , IH , GH i), that
is a more abstract version of the robot’s model (MR =
hPH , SR , AR , IR , GR i). While the robot may not have access to MH , it understands that MH is a member of the set
M for the lattice L. The human comes up with the foil set F
= {π1 , π2 , ..., πm } that the robot needs to refute by providing some explanation E regarding the task. The explanation
should contain information about specific domain properties
(i.e., state fluents) that are missing from the human’s model
and how these properties affect different actions (for example which actions use these propositions as preconditions and
which ones generate/delete them).We can represent such an
explanation using the set of propositions whose concretization is required to refute the given foils.
Definition 4. An explanation E of size n for the human model
MH and a foil set F can be represented as a set of propositions of the form E = {p1 , ..., pn } such that
∀π ∈ F, π(IγE (MH ) ) 6|=γE (MH ) GγE (MH )
Where γE (MH ) is the model obtained by applying the concretizations corresponding to E on the model MH .
Example 1. Consider a simplified version of the rover domain mentioned earlier. Suppose the rover uses a modified version of the IPC rover domain [International Planning
Competition, 2011] that also takes into account the battery
level of the robot. Each rover operation has a different energy

Figure 2: A possible abstraction lattice for the grounded rover domain.

requirement, and the battery level needs to be above a predefined threshold for it to execute them, e.g., it can perform rock
sampling only if the battery level is above 75%. Furthermore,
the rover needs to visit the base station (i.e., the lander) and
perform a reset action to recharge its batteries.
The rover knows that the human observer is at most
ignorant of its energy requirements and/or storage capabilities. So the model lattice L needs to consider
abstractions corresponding to the following propositions
P={battery level above 25 perc, battery level above 50 perc,
battery level above 75 perc, full store}. Figure 2 shows the

lattice that the robot would use in this setting. Here we will
create each abstract model by dropping a proposition from
the more concrete model and by making the effects of action
non-deterministic if the dropped predicate appears in the precondition. For example, if the action drop store1 has effects
of the form
{full store1, store of store1} → {¬full store1, empty store1}

Now in an abstract version of this model, if the proposition
full store1 is dropped the effect becomes
{ store of store1} → N D{ empty store1}

Which now says that the action’s effects are nondeterministic and executing drop store1 may or may
not turn the fluent empty store1 true.
Let the plan πR be h navigate w0 lander, reset at lander,
navigate lander w1, sample rock store0 w1i
and
the
foil set F be {h navigate w0 w1, navigate lander w1,
sample rock store0 w1 i}
In Example 1, the rover would have difficulty coming up
with a single explanation as it does not know MH . One possibility would be to restrict its attention to just the models that
are consistent with the foils . In this scenario, this would correspond to {c6, c7, c9, c10, c11, c12}. Now we need to find
a way of generating explanations given this reduced set of
models.
Proposition 1. Let Mi be some model in L such that MH v
Mi . If E is a valid explanation for Mi and some foil set F ,
then E must also explain F for MH .
This proposition directly follows from the fact that for
a proposition conserving lattice γE (Mi ) will be a logical
weaker model than γE (MH ).
Next, we will define the concept of a minimal abstraction
set for a given lattice L and foils F

Definition 5. Given an the abstraction lattice L =
hM, E, P, `i the minimal abstraction set Mmin is the supremum of all the models that are consistent with the foil set F .
Mmin = sup{Mi |Mi ∈ M, ∀π ∈ F (π(IMi ) |=Mi GMi )}
In Example 1, the minimal abstract model set will be
Mmin = {c11, c12}.
If we can find an explanation that is valid for all the models
in Mmin then by Proposition 1 it must work for MH as well.
Proposition 2. For a given model lattice L, the minimal abstraction set Mmin and a set of foils F , there exist an explanation E such that for each M0 ∈ Mmin and ∀π ∈ F ,
π(IγE (M0 ) ) 6|=γE (M0 ) GγE (M0 )
It is easy to see why this property holds, as any explanation that involves concretizing all possible propositions in P
satisfies this property.
In most cases, we would prefer to get the least costly or
the shortest explanation (if all concretizations are equally expensive) to the listener. In the rover example, even if the human is unaware of multiple task details, the robot can easily
resolve the user’s doubts by explaining the concretizations
related to the proposition battery level above 75 perc without getting into other details. Describing the details of others propositions is unnecessary and in the worst case might
leave the human feeling overwhelmed and confused. In this
case, the explanation would just include Information regarding battery levels and how to identify when the battery level
is or above 75% and model updates like
sample rock-has-precondition-battery level above 75 perc
sample soil-has-precondition-battery level above 75 perc
...

Before delving into the optimization version, let us look at the
complexity of the corresponding decision problem
Theorem 1. Given a minimal abstraction set Mmin , a plan
πR , the set of propositions being abstracted P and the set of
foils F for a model M, the problem of identifying whether
an explanation of size k exists for the complete lattice is NPcomplete.
Proof (Sketch). The fact that we can test the validity of the
given explanation in polynomial time (size of the explanation
is guaranteed to be smaller than |P|) shows that the problem is
NP. We can show NP-completeness by reducing the set covering problem [Bernhard and Vygen, 2008] to an instance of
the explanation generation problem. Let’s consider a set covering problem with U as the universe set and S as the set of
sub-collections. Now let us create an explanation generation
problem where the set of foils F is equal to U and the propositions in the set P contains a proposition for each member
of S. Additionally concretizing with respect to a proposition
will resolve only the foils covered by its corresponding subset in S. For this setting, we can construct a fully connected
proposition conserving lattice L of height |S|. Within the lattice, there exists a unique most abstract model where all the
foils hold and a single most concrete model (where none of
the foils hold). Now if we can come up with an explanation
of size k in this setting, then this explanation corresponds to
a set cover of size k.

3

Generating Minimal Explanations

As mentioned earlier, we are interested in producing the
smallest possible explanation. Additionally, in most domains,
the cost of communicating the concretization details could
vary among propositions. An explanation that involves a
proposition that appears in every action definition might be
harder to communicate than one that only uses a proposition
that is part of the definition of a single action.
In addition to the actual size, the comprehensibility of the
explanations may also depend on factors like human’s mental
load, the familiarity with the concepts captured by the propositions, etc.. To keep our discussions simple, we will restrict
the cost of communicating an explanation to the number of
unique model updates this explanation would bring about in
the human model.We will use the symbol Cp to represent the
cost of communicating the changes related to the proposition
p. We will overload C to also work on sets of propositions.
Now our problem is to find the cheapest explanation (represented as Emin ) for a given set of foils F , and the minimal
abstract model set Mmin . One possibility is to perform an A*
search [Hart, Nilsson, and Raphael, 1968] over the space of
possible propositional concretizations to identify Emin . Each
search state consists of the minimal set of abstract models
for the human model given the current explanation prefix. We
will stop the search as soon as we find a state where the foils
no longer hold for the current minimal set.
Proposition 3. Let Mmin be the minimal abstraction set for
a given lattice L = hM, E, P, `i and foil set F . Then for
b min formed by applying the cona proposition p, the set M
cretization corresponding to p on every element of Mmin will
b formed by applying the conbe the minimal abstract set for M
cretization γp on every element of M given F .
The above property implies that we don’t need to look at
the lattice L to recalculate minimal abstraction set after the
application of every concretization function. We can also further simplify our problem by exploiting the fact that a particular propositional concretization resolves a foil (i.e., make
the foil no longer valid) when it either adds a precondition (or
a new condition for a conditional effect) or a goal fact that
can not be satisfied by the foil. To concisely capture this idea
we will introduce the concept of a foil resolution set to represent the subset of foils resolved by the concretization of a
particular proposition.
Definition 6. For a set of models M0 , a foil set F and
a proposition p, the resolution set RF (M0 , p) gives the
subset of foils that no longer holds in the concretized
models, i.e RF (M0 , p) = {π|π ∈ F ∧ (∀M0 ∈
M0 (π(Iγp (M0 ) ) 6|=γp (M0 ) Gγp (M0 ) ))}.
We will also use RF to represent the set of foils resolved
by a sequence of propositions
Proposition 4. For a set of model M0 and a foil set F
RF (M0 , hp1 , p2 i) = RF (M0 , hp1 i) ∪ RF (M0 , hp2 i)
The above property implies that concretizing any n propositions cannot resolve foils that weren’t resolved by the individual propositions.

b
Algorithm 1 Greedy Algorithm for Generating E
1: procedure G REEDY- EXP - SEARCH
2: Input: hF, L = hM, E, P, `ii
3: Output: Explanation Eb
4: Procedure:
5:
curr model = hMmin , F i
b = {}
6:
E
7:
Mmin
←MinimalAbstractModels(L, F )
8:
Precompute the resolution sets RF (Mmin , p) for each p ∈ P
9:
while True do
10:
M0 , F 0 = curr model
b
b if all the foils are resolved
11:
if |F 0 | = 0 then return E
. Return E
12:
else
C
13:
pnext = arg minp ( |F 0 ∩R p(M0 ,p)| )
F
14:
Mnew = {γpnext (M)|M ∈ M0 }
15:
curr model = hMnew , F \ RF (M0 , p)i
b=E
b∪p
16:
E

Proposition 5. For two models M1 , M2 and a set of foils F ,
if M1 v M2 then for any proposition p, RF ({M1 }, p) ⊆
RF ({M2 }, p)
The above proposition ensures that if an explanation is the
minimal one for Mmin , then it must be the minimal explanation for MH as well.
These propositions will be instrumental in proving the effectiveness of our greedy algorithm described by Algorithm
1. In each iteration of this search, the algorithm greedily
C
chooses the proposition that minimizes |F 0 ∩RFp(M0 ,p)| , where
F 0 is the set of unresolved foils at that iteration and the search
ends when all foils are resolved.
b generated by Algorithm 1 for
Theorem 2. The explanation E
a set of foils F and a lattice L = hM, E, P, `i is less than or
equal to (ln k)∗CEmin , where CEmin is the cost of an optimal
explanation and k represents the maximum number of foils
that can be resolved by concretizing a single proposition, i.e,
k = maxp |RF (Mmin , p)|.
Proof (Sketch). We will prove the above theorem by showing
that Algorithm 1 corresponds to the greedy search algorithm
for a weighted set cover problem. Consider a weighted set
cover problem hU, S, W i such that the universe set U = F ,
the subcollections set S is defined as S = {sp |p ∈ P} where
sp = RF (Mmin , p) and the cost of each subset sp is gives as
W (sp ) = Cp . Proposition 4 ensures that the size of resolution
set is a submodular and monotonic function. In this setting,
the act of identifying a set of propositions that resolve the
foil set is identical to coming up with a set cover for U in
the new weighted set cover problem. Furthermore, we can
show that the optimal set cover Copt must correspond to the
cheapest explanation Emin (We can prove this equivalence
using Propositions 1,2 and 4, we are skipping the details of
this proof due to space constraints). Algorithm 1 describes
a greedy way of identifying the cheapest set cover for this
weighted set cover problem and thus the minimal explanation
for the original problem. For weighted set cover the above
greedy algorithm is guaranteed to generate solutions that are
at most ln k ∗W (Copt ) [Young, 2008], where k = maxs∈S |s|
and this approximation guarantee will hold for Emin as well.

Figure 3: An example explanation generated by our system for IPC
rover domain. The human incorrectly believes that the rover can
communicate sample information without explicitly collecting any
samples. While the abstraction lattice in this example was generated
by projecting out upto 12 predicates, the search correctly identifies
concretizations related to (have soil analysis ?r - rover ?w - waypoint) as the cheapest explanation (CE = 2 as opposed to CP = 55)

We will use this algorithm to both generate solutions and
to calculate an inadmissible heuristic for the previously mentioned A* search. For the heuristic generation, we will further simplify the calculations (specifically step 8 in Algorithm
1) by considering an over-approximation of RF . Instead of
considering the set of all foils resolved by concretizing each
proposition p, we will consider the set of foils where p appears in the precondition of one of the actions in it. This set
should be a superset for RF for any proposition.

4

Empirical Evaluations

In our evaluation, we wanted to understand how effective our
approaches were in terms of the conciseness of the explanations produced, the solution generation time and the usefulness of approximation. For the approximation, we were interested in identifying the trade-off between decrease in runtime
vs. reduction in solution quality.
All three explanation methods discussed in this paper (Blind, heuristic and greedy) were evaluated on five
IPC benchmark domains[International Planning Competition, 2011]. All the experiments detailed in this section were
run on an Ubuntu workstation with 12 core Intel(R) Xeon(R)
CPU and 64G RAM.
For each domain, we selected 30 problems from either
available test sets or by using standard problem generators
(the problems sizes were selected to reflect the size of previous IPC test problems). The lattice for each problem domain
pair was generated by randomly selecting 50% of domain
predicates and then generating a fully connected proposition
conserving lattice using that set of predicates. Each abstract
model was created using ND-operators similar to Example
1. Each search generates the set of proposition whose concretizations can resolve the foils set F . In actual applications,
this set of propositions needs to be converted into an explanan
(the actual message) by considering how this proposition is
used in the robot model. Figure 3 shows the explanation generated by our approach for a problem in Rover domain.
The table in Figure 4 presents the results from our empirical evaluation on the IPC domains. The table shows the aver-

Domain Name

Barman

Rover

Satellite

Woodworking

Sokoban

|P|

CP

|F |

84.07
84
90.7
168.66
188.83
192.83
53.01
60.77
62.73
156.71
146.33
154
220.6
151.72
220.69

7
7
7
12
12
12
4
4
4
7
7
7
3
3
3

1
2
4
1
2
4
1
2
4
1
2
4
1
2
4

Blind Search (Optimal)
Cost
Size
Time(S)
6.87
1
2.43
8.94
1.22
6.35
17.19
1.77
24.99
3.58
1
7.86
6.13
1.48
51.36
10.87
2
203.83
18.73
1
2.23
32
1.61
7.21
43.27
2.29
18.67
14.45
1
2.84
20.62
1.21
6.88
28.62
1.69
24.70
51.21
1
1.51
94.52
1.55
3.93
136.41
2.22
8.75

Heuristic Search
Cost
Size
Time(S)
6.87
1
2.08
8.94
1.22
5.71
17.19
1.77
23.7
3.58
1
5.22
6.12
1.48
34.04
10.87
2
181.87
18.73
1
1.92
32
1.6
5.86
43.27
2.29
16.42
14.45
1
2.23
20.62
1.21
4.93
28.62
1.69
19.49
51.21
1
1.35
94.52
1.55
3.35
136.41
2.22
8.3

Greedy Set Cover
Cost
Size
Time(S)
6.87
1
3.61
9.90
1.39
6.05
18.45
1.97
10.34
3.58
1
19.18
6.26
1.52
30.5
11.42
2.19
49.32
18.73
1
1.49
32.53
1.7
3.04
43.88
2.39
5.85
14.45
1
3.35
21.38
1.38
6.25
30.41
2
12.13
51.21
1
1.28
98.31
1.73
2.59
141.93
2.37
5.23

Figure 4: Table showing runtime/cost for explanations generated for standard IPC domains.Column |P| represents number of predicates that
were used in generating the lattice, while CP represents the cost of an explanation that tries to concretize all propositions in P and provides
an upper bound on explanation cost. The graph on right side compares the performance of greedy set cover against the optimal blind search
for |F | = 4. It plots the average time saved by the set cover and the average increase in cost of the solution for each domain.

Figure 5: The grocery putaway domain setting.
age cost/size of each explanation along with the time taken to
generate them. Note that by size, we refer to the no of predicates that are part of the explanation while the cost reflects the
total number of unique model updates induced by that explanation. We attempted explanation generation for foil set sizes
of one, two and four per problem.
The first point of interest is that the heuristic search seems
to outperform blind search in almost every problem and generates near-optimal solutions (Blind search always generates
the minimal explanation). Further, we saw that greedy search
outperformed heuristic search in most cases barring a few exceptions. The greedy was able to make significant gains especially for higher foil sizes. This is entirely expected due to
the fact that step 8 in Algorithm 1 can be expensive for problems with long plans (but still polynomial). This expensive
pre-computation pays off as we move to cases where Emin
consists of multiple propositions. Additionally, we found out
that greedy solutions were quite comparable to the optimal
solutions with respect to their costs.

5

(:action pickup
:parameters (?x - item ?y - storage ?u - pose ?v - traj)
:precondition (and
(is pickup pose ?u ?x)
(is collision free traj ?x ?y ?u ?v)
(in ?x ?y)
(handempty)
)
:effect (and
(not (handempty))
(not (in ?x ?y))
(holding ?x)
(increase (total-cost) 1)
)
)
(:action place in high shelf
:parameters (?x - item ?y - storage ?u - pose ?v - traj)
:precondition (and
(is putdown pose ?u ?x)
(is collision free traj ?x ?y ?u ?v)
(is condiment type ?x)
(holding ?x)
(is high shelf ?y)
)
:effect (and
(handempty)
(in ?x ?y)
(not (holding ?x))
(item putaway ?x)
(increase (total-cost) 1)
)
)

Robot Demonstration

This section describes a demonstration of our approach on a
physical robot for a simple grocery putaway task. Figure 5
presents the basic setup for the task. The goal of the robot
here is to put away a bottle of tablets, a can of energy drink

Figure

6: The action definitions for pickup
place in high shelf from the most concrete model.

and

(:action pickup
:parameters (?x - item ?y - storage)
:precondition (and
(in ?x ?y)
(handempty)
(reachable ?y)
)
:effect (and
(not (handempty))
(not (in ?x ?y))
(holding ?x)
(increase (total-cost) 1)
)
)

Figure 7: The plan and foils used in the scenario.
and a jar of sugar to proper storage locations. The storage
location of each object is decided based on its type, for example, the robot should place the medicine bottle in the medicine
cabinet, the sugar jar in the high pantry shelf, while the energy drink needs to be handed over to the human. In addition to these task-level constraints, the robots operations are
restricted by various motion level constraints that limit the
possible physical movements that the robot can perform. For
example, given the current position of the sugar jar on the
table, the robot couldn’t come up with any pickup pose that
would allow the robot to place the sugar jar on the high shelf.
In such cases, the robot could always enlist the help of the
human to complete the plan.
In this setting, we will assume that the most concrete
robot model consists of action descriptions that include
both task-level symbols as well as continuous geometric arguments. Figure 6 presents the definitions for pickup and
place in high shelf actions in the most concrete model. In this
model, the arguments of type ?pose and ?traj represents the
pickup/putdown pose (the position and orientation of the end
effector) and motion plans followed by the robot to perform
the pickup/putdown. For this demo, we will consider a non
proposition conserving model lattice that spans multiple levels of abstractions. Starting out we can convert each of the
continuous arguments into geometric symbols (this is similar
to the approach used in [Srivastava et al., 2014]). Next, we
will further abstract the poses to align with possible regions
on the object (i.e., pick up the object from the bottom, middle
or top). We will also consider abstractions where we combine
the predicates is putdown pose and collision free trajectory
into a single predicate called reachable predicate and also create new models by dropping arguments from the actions (We
only drop an argument when none of the predicates use this
argument). Figure 8 presents an intermediate model where
most of the geometric predicates are already abstracted out.
There could also be additional non-geometric predicates (like
the is condiment type predicate) that can be abstracted out.
Figure 7 presents a plan and possible foils that could be
generated in this domain. The plan involves the robot placing
the energy drink and medicine on its own but relying on the
human to complete the place action for sugar jar. The naive
user asks merely why the robot doesn’t finish the plan on its
own while the expert user provides specific grasp that she/he
believes can help the robot complete the plan. While the ex-

(:action place in high shelf
:parameters (?x - item ?y - storage)
:precondition (and
(is condiment type ?x)
(holding ?x)
(reachable ?y)
(is high shelf ?y)
)
:effect (and
(handempty)
(in ?x ?y)
(not (holding ?x))
(item putaway ?x)
(increase (total-cost) 1)
)
)
Figure

8: The action definitions for
place in high shelf from an abstract model.

pickup

and

planation to the naive user relies on the high-level predicate
reachable, the expert explanation is more detailed and relates
to the fact that a lower region grasp will result in a collision
with the table. We can present such collisions to the human by
simulating the trajectories using tools like Rviz [Hershberger,
Gossow, and Faust, 2016].
The readers can view the demonstration of the scenario
implemented on a fetch robot at https://youtu.be/
qUHg8RABjsw. OpenRAVE [Diankov, 2010] was used to
compute the trajectories of the robot arm for the pickup and
place actions. COLLADA [Arnaud and Barnes, 2006] models
of the furniture and the items were created and populated in
the OpenRAVE environment using AR markers, the transformation of which was obtained using the ar track alvar package available in ROS. Resulting OpenRAVE trajectories were
then converted into ROS JointTrajectory messages and executed on the robot.

6

Related Works

There is increasing interest within the automated planning
community to solve the problem of generating explanations for plans ([Fox, Long, and Magazzeni, 2017]). Earlier

works like [Seegebarth et al., 2012; Bercher et al., 2014;
Kambhampati, 1990] looked at explanations as a way of describing the effects of plans, while works like [Sohrabi, Baier,
and McIlraith, 2011; Meadows, Langley, and Emery, 2013]
looked at plans itself as explanations for a set of observations. Another approach that has received a lot of interest recently is to view explanations as a way of achieving model
reconciliation[Chakraborti et al., 2017]. Such explanations
are referred to as MRP explanations and this approach postulates that the goal of an explanation is to update the model
of the observer so they can correctly evaluate the plans in
question.
Similar to MRP, we can also see our explanations as model
updates, but we focus on a specific type of update, namely
model concretization. Unlike MRP we do not make any assumptions about the availability of human model or the human’s computational capabilities. The assumption that we
have access to foils help us scale to much larger problems
as compared to the original MRP approach. Following the
conventions of the original MRP paper, we can see that the
explanations studied here are both complete and monotonic.
The idea of using foils or counterexamples to drive model
refinement has also been studied in model checking community under the banner of “Counter-example Guided Abstraction Refinement” or CEGAR [Clarke et al., 2000].
Many planning works have also successfully used CEGAR
based methods to generate abstraction heuristics ([Seipp and
Helmert, 2013; Seipp and Helmert, 2014]). Even though related, we do not believe that vanilla CEGAR methods can
address the problems studied here. Firstly, CEGAR works do
not consider model uncertainty which is central to our explanation generation problem. To the best of our knowledge, CEGAR based methods do not assign any costs to refinements,
and therefore would not be able to identify the minimal explanation for a given foil set. Finally, since we are considering sets of foils, it may be prohibitively expensive to follow
CEGAR approaches and test each foil in the most concrete
model to identify specific faults.
Many abstraction schemes have been proposed for planning tasks (starting with [Sacerdoti, 1974]), but in this paper,
we mainly focused on state abstractions and based our formulation on previous works like [Srivastava, Russell, and Pinto,
2016] and [Backstrom and Jonsson, 2013].It would be interesting to see how we can extend the approaches discussed
in this paper to handle temporal and procedural abstractions
(e.g., HLAs [Marthi, Russell, and Wolfe, 2007]).

7

Conclusion and Discussion

In this paper, we investigated the problem of generating explanations when the explainee understands the task model at a
lower levels of abstraction. We looked at how we can use explanations as concretization for such scenarios and proposed
algorithms for generating minimal explanations. One unique
aspect of our approach is the use of foils as a way of capturing human confusion about the problem. This not only helps
us formulate more efficient explanation generation methods
but also aligns with how humans ask for explanations. Moreover, in most real-world scenarios when we expect someone

to explain something, we include the foil in the request for the
explanation unless the foil is quite apparent from the context.
Future directions include extending the methods to handle
models that are incorrect in addition to being imprecise and
looking at other possible methods for abstraction.

Acknowledgments
The authors would like to thank Midhun Pookkottil Madhusoodanan for helping setup the robot demo that is described in the paper. 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.

References
[Arnaud and Barnes, 2006] Arnaud, R., and Barnes, M. C.
2006. COLLADA: sailing the gulf of 3D digital content
creation. CRC Press.
[Backstrom and Jonsson, 2013] Backstrom, C., and Jonsson,
P. 2013. Bridging the gap between refinement and heuristics in abstraction. In Twenty-Third International Joint
Conference on Artificial Intelligence.
[Bercher et al., 2014] Bercher, P.; Biundo, S.; Geier, T.; Hoernle, T.; Nothdurft, F.; Richter, F.; and Schattenberg, B.
2014. Plan, repair, execute, explain-how planning helps to
assemble your home theater. In ICAPS.
[Bernhard and Vygen, 2008] Bernhard, K., and Vygen, J.
2008. Combinatorial optimization: Theory and algorithms.
Springer, Third Edition, 2005.
[Chakraborti et al., 2017] Chakraborti, T.; Sreedharan, S.;
Zhang, Y.; and Kambhampati, S. 2017. Plan explanations as model reconciliation: Moving beyond explanation
as soliloquy. In IJCAI.
[Clarke et al., 2000] Clarke, E.; Grumberg, O.; Jha, S.; Lu,
Y.; and Veith, H. 2000. Counterexample-guided abstraction refinement. In International Conference on Computer
Aided Verification, 154–169. Springer.
[Diankov, 2010] Diankov, R. 2010. Automated Construction
of Robotic Manipulation Programs. Ph.D. Dissertation,
Carnegie Mellon University, Robotics Institute.
[Fox, Long, and Magazzeni, 2017] Fox, M.; Long, D.; and
Magazzeni, D. 2017. Explainable Planning. In IJCAI
XAI Workshop.
[Hart, Nilsson, and Raphael, 1968] Hart, P. E.; Nilsson,
N. J.; and Raphael, B. 1968. A formal basis for
the heuristic determination of minimum cost paths.
IEEE transactions on Systems Science and Cybernetics
4(2):100–107.
[Hershberger, Gossow, and Faust, 2016] Hershberger,
D.; Gossow, D.; and Faust, J.
2016.
Rviz.
http://wiki.ros.org/rviz.
[International Planning Competition, 2011] International
Planning Competition. 2011. IPC Competition Domains.
https://goo.gl/i35bxc.

[Kambhampati, 1990] Kambhampati, S. 1990. A classification of plan modification strategies based on coverage and
information requirements. In AAAI 1990 Spring Symposium on Case Based Reasoning. Citeseer.
[Marthi, Russell, and Wolfe, 2007] Marthi, B.; Russell, S. J.;
and Wolfe, J. A. 2007. Angelic semantics for high-level
actions. In ICAPS, 232–239.
[Meadows, Langley, and Emery, 2013] Meadows, B. L.;
Langley, P.; and Emery, M. J. 2013. Seeing beyond
shadows: Incremental abductive reasoning for plan understanding. In AAAI Workshop: Plan, Activity, and Intent
Recognition, volume 13, 13.
[Miller, 2017] Miller, T. 2017. Explanation in artificial
intelligence: Insights from the social sciences. CoRR
abs/1706.07269.
[Sacerdoti, 1974] Sacerdoti, E. D. 1974. Planning in a hierarchy of abstraction spaces. Artificial intelligence 5(2):115–
135.
[Seegebarth et al., 2012] Seegebarth, B.; Müller, F.; Schattenberg, B.; and Biundo, S. 2012. Making hybrid plans
more clear to human users-a formal approach for generating sound explanations. In Twenty-Second International
Conference on Automated Planning and Scheduling.
[Seipp and Helmert, 2013] Seipp, J., and Helmert, M. 2013.
Counterexample-guided cartesian abstraction refinement.
In ICAPS.
[Seipp and Helmert, 2014] Seipp, J., and Helmert, M. 2014.
Diverse and additive cartesian abstraction heuristics. In
ICAPS.
[Sohrabi, Baier, and McIlraith, 2011] Sohrabi, S.; Baier,
J. A.; and McIlraith, S. A. 2011. Preferred explanations:
Theory and generation via planning. In AAAI.
[Srivastava et al., 2014] Srivastava, S.; Fang, E.; Riano, L.;
Chitnis, R.; Russell, S.; and Abbeel, P. 2014. Combined
task and motion planning through an extensible plannerindependent interface layer. In Robotics and Automation
(ICRA), 2014 IEEE International Conference on, 639–
646. IEEE.
[Srivastava, Russell, and Pinto, 2016] Srivastava, S.; Russell, S. J.; and Pinto, A. 2016. Metaphysics of planning
domain descriptions. In AAAI, 1074–1080.
[Young, 2008] Young, N. E. 2008. Greedy set-cover algorithms. In Encyclopedia of algorithms. Springer. 1–99.

