# Generating explanations for answer set programming applications

Ly Ly Trieu  New Mexico State University, MSC CS, PO Box 30001, Las Cruces,
New Mexico, USA  Tran Cao Son  New Mexico State University, MSC CS, PO Box
30001, Las Cruces, New Mexico, USA  Enrico Pontelli  New Mexico State
University, MSC CS, PO Box 30001, Las Cruces, New Mexico, USA  Marcello
Balduccini  Saint Joseph’s University, 5600 City Avenue, Philadelphia, PA, USA

###### Abstract

We present an explanation system for applications that leverage Answer Set
Programming (ASP). Given a program $P$, an answer set $A$ of $P$, and an atom
$a$ in the program $P$, our system generates all explanation graphs of $a$
which help explain why $a$ is true (or false) given the program $P$ and the
answer set $A$. We illustrate the functionality of the system using some
examples from the literature.

###### keywords:

Explainable AI, Answer Set Programming, Artificial Intelligence

##  1 INTRODUCTION

[2,r,  ,Interactions between AI System and Human User ] In recent years,
explainable AI has been introduced to help users gain confidence in the AI’s
decisions and conclusions. We aim at developing AI systems capable of
explaining their responses to a request from a user until the user finds that
the answers are acceptable as illustrated in Fig. 1. It starts with the user
sending a request (Step 1). The system responds with an initial answer (2).
Thereafter, a dialog between the two ensues with user sending questions and
information—that the user believes might be different than those owned by the
system—to the system (3), and the system responds with explanations and
information—that the system believes the user might not have or have in
incorrect form (4). This process continues until the user agrees with the AI
system. During this process, the AI will need to take into consideration the
human model of the situation and the information sent by the user,
differentiate it from its own, and inform the user about missing or false
information. In addition, the AI’s model of the human will need to be learned
and updated as exchanges between the two sides occur. Most current AI systems
lack components for dealing with the steps (3)-(4).

In this paper, we focus on a key component needed in steps (3)-(4) in the
above architecture. We propose an _explainable Answer Set Programming (ASP)_
system. ASP is a programming paradigm that has been applied in several
applications such as planning, diagnosis, robotics, etc. ASP is attractive as
it is declarative, non-monotonic, and elaboration tolerant, and has free and
scalable solvers. Thus far, only limited attention has been paid to explaining
the output of an ASP execution. The proposed system will take a program $P$
and a model $A$ of $P$ and explain “why an atom is true/false in $A$.” In
addition, the system will also produce explanation graphs for atoms in an ASP
program.

The paper is organized as follows. We will start with a short illustration of
answer set programming with focus on why ASP is an appropriate paradigm for
the development of AI applications and when is it most appropriate for using
ASP. Afterwards, we will define the notion of a justification (explanation
graph) of an atom in a given answer set. We will then describe a system for
generating explanations for answer set programming and present some initial
applications.

##  2 PRELIMINARIES

###  2.1 Answer Set Programming (ASP)

(ASP) [1, 2] is a declarative programming paradigm based on logic programming
under the answer set semantics. A logic program $P$ is a set of rules of the
form

$c\leftarrow a_{1},\ldots,a_{m},\>not\>b_{1},\ldots,\>not\>b_{n}$ (1)

where $c$, $a_{i}$’s, and $b_{j}$’s are atoms of a propositional
language111For simplicity, we often use first order logic atoms, as a
representation of all of their ground instantiations. and $\mathit{not}$
represents (default) negation. Intuitively, a rule states that if all $a_{i}$
are believed to be true and none of the $b_{j}$ is believed to be true then
$c$ will be true. For a rule $r$, $r^{+}$ and $r^{-}$ denote the sets
$\\{a_{1},\ldots,a_{m}\\}$ and $\\{b_{1},\ldots,b_{n}\\}$, respectively. We
write $head(r)$ and $body(r)$ to denote $c$ and the right side of a rule $r$.
Both the head and the body or a rule $r$ can be empty; when the body is empty,
the rule is called a fact; when the head is empty, it is a constraint. We use
$H$ to denote the Herbrand base of a logic program $P$, which is the set of
all ground atoms in $P$.

Let $P$ be a program. An interpretation $I$ of $P$ is a subset of $H$. $I$
satisfies an atom $a$ ($I\models a$) if $a\in I$. The body of a rule $r$ is
satisfied by $I$ if $r^{+}\subseteq I$ and $r^{-}\cap I=\emptyset$. A rule $r$
is satisfied by $I$ if $I\models head(r)$ or $I\not\models body(r)$. $I$ is a
model of $P$ if it satisfies all rules in $P$.

For an interpretation $I$ and a program $P$, the _reduct_ of $P$ w.r.t. $I$
(denoted by $P^{I}$) is the program obtained from $P$ by deleting (i) each
rule $r$ such that $r^{-}\cap I\neq\emptyset$, and (ii) all elements of the
form $\>not\>a$ in the bodies of the remaining rules. Given an interpretation
$I$, observe that the program $P^{I}$ is a program with no occurrences of
$\>not\>a$. An interpretation $I$ is an _answer set_ of $P$ if $I$ is the
least model (w.r.t. $\subseteq$) of $P^{I}$ [3]. Answer sets of logic programs
can be computed using efficient and scalable answer set solvers, such as
clingo[4].

We illustrate the concepts of answer set programming by showing how the
3-coloring problem of a undirected graph $G$ can be solved using ASP. Let the
three colors be red ($r$), blue ($b$), and green ($g$), and the vertices of
$G$ be $0,1,\ldots,n$. Let $P(G)$ be the program consisting of

  * •

the set of atoms $edge(u,v)$ and $edge(v,u)$ for every pair of connected
vertices $u,v$ in $G$,

  * •

for each vertex $u$ of $G$, three rules stating that $u$ must be assigned one
of the colors red, blue, or green ($colored(x,c)$ denotes that the node $x$ is
colored with the color $c$):

$\displaystyle colored(u,g)\leftarrow\>not\>colored(u,b),\>not\>colored(u,r)$
$\displaystyle colored(u,r)\leftarrow\>not\>colored(u,b),\>not\>colored(u,g)$
$\displaystyle colored(u,b)\leftarrow\>not\>colored(u,r),\>not\>colored(u,g)$

and

  * •

for each edge $(u,v)$ of $G$, three rules representing the constraint that $u$
and $v$ must have different color:

$\displaystyle\leftarrow colored(u,r),colored(v,r),edge(u,v)$
$\displaystyle\leftarrow colored(u,b),colored(v,b),edge(u,v)$
$\displaystyle\leftarrow colored(u,g),colored(v,g),edge(u,v)$

It can be shown that for each graph $G$, (i) $P(G)$ does not have answer sets
iff the 3-coloring problem of $G$ does not have a solution; and (ii) if $P(G)$
has solutions, then each answer set of $P(G)$ corresponds to a solution of the
3-coloring problem of $G$ and vice versa.

###  2.2 Properties of ASP

Given a program $P$ and an answer set $A$, the following properties hold:

  1. 1.

If $c\in A$, there exists a rule $r$ in $P$ such that

     * •

$head(r)=c$;

     * •

$r^{+}\subseteq A$; and,

     * •

$r^{-}\cap A=\emptyset$

For such a rule $r$, we define $support(c,r)=\\{p\mid p\in A\land p\in
r^{+}\\}\cup\\{\sim\\!n\mid n\notin A\land n\in r^{-}\\}$ and refer to this
set as a _supported set_ of $c$ for rule $r$.

  2. 2.

If $c\notin A$, for every rules $r$ such that $head(r)=c$, then

     * •

$r^{+}\setminus A\neq\emptyset$; or,

     * •

$r^{-}\cap A\neq\emptyset$

For such a rule $r$, we define $support(\sim\\!c,r)\in\\{\\{p\\}\mid p\in
A\land p\in r^{-}\\}\cup\\{\\{\sim\\!n\\}\mid n\notin A\land n\in r^{+}\\}$
and refer to it as a supported set of $\sim\\!c$ for rule $r$.

###  2.3 Explanation Graph

We rely on the notion of an off-line justification introduced by [5] as an
explanation of an atom $a$ given an answer set $A$ of a program $P$.
$NANT(P)=\\{a\mid a\in r^{-}\land r\in P\\}$ is the set of all negation atoms
in $P$. Let $C(P)$ denote the set of cautious consequences of $P$, i.e.,
$C(P)=C^{+}\cup C^{-}$ where $C^{+}$ is the set of atoms belonging to all
answer sets of $P$ and $C^{-}$ is the set of atoms which do not belong to any
answer set of $P$. A set of atoms $U$ such that $U\subseteq
NANT(P)\setminus(A\cup C(P))$ is called a set of assumptions with respect to
$A$ if $A=C(P\setminus\\{r\in P\mid head(r)\in U\\})$.

Intuitively, given an answer set $A$ of a program $P$, an atom $a\in A$
($a\not\in A$) is considered to be true (false) given $A$. An off-line
justification for an atom $a$ presents a possible reason for the truth value
of $a$, i.e., it answers the question “ _why $a\in A$ (or $\not\in A$)?_”. If
$a$ is true in $A$, an off-line justification of $a$ represents a derivation
of $a$ from the set of assumptions $U$ and the set of facts in $P$. If $a$ is
false in $A$, an off-line justification encodes the reason why it is not
supported by $A$, which can be that it is assumed to be false (being an
assumption in $U$) or there exists no possible derivation of it given $A$. An
off-line justification of $a$ is analogous to the well-known SLDNF tree in
that it represents the derivation for $a$. The key difference between these
two notions is that an off-line justification might contain a cycle consisting
of negative atoms, i.e., atoms not belonging to $A$. For this reason, a
justification is represented as an explanation graph, defined as follows.

######  Definition 2.1 (Explanation Graph).

Let us consider a program $P$, an answer set $A$, and a set of assumptions $U$
with respect to $A$. Let $N=\\{x\mid x\in A\\}\cup\\{\sim{x}\mid x\not\in
A\\}\cup\\{\top,\bot,\mathtt{assume}\\}$ where $\top$ and $\bot$ represent
true and false, respectively. An _explanation graph_ of an atom $a$ occurring
in $P$ is a finite labeled and directed graph $DG_{a}=(N_{a},E_{a})$ with
$N_{a}\subseteq N$ and $E_{a}\subseteq N_{a}\times
N_{a}\times\\{+,-,\circ\\}$, where $(x,y,z)\in E_{a}$ represents a link from
$x$ to $y$ with the label $z$, and satisfies the following conditions:

  * •

if $a\in A$ then $a\in N_{a}$ and every node in $N_{a}$ must be reachable from
$a$;

  * •

if $a\not\in A$ then $\sim\\!a\in N_{a}$ and every node in $N_{a}$ must be
reachable from $\sim\\!a$;

  * •

if $(x,\top,+)\in E_{a}$ then $x$ is a fact in $P$;

  * •

if $(\sim\\!x,\mathtt{assume},\circ)\in E_{a}$ then $x\in U$;

  * •

if $(\sim\\!x,\bot,+)\in E_{a}$ then there exists no rule in $P$ whose head is
$x$;

  * •

there exists no $x,y$ such that $(\top,x,y)\in E_{a}$, $(\bot,x,y)\in E_{a}$,
or $(\mathtt{assume},x,y)\in E_{a}$;

  * •

for every $x\in N_{a}\cap A$ and $x$ is not a fact in $P$,

    * –

there exists no $y\in N_{a}\cap A$ such that $(x,y,-)$ or $(x,y,\circ)$ belong
to $E_{a}$;

    * –

there exists no $\sim\\!y\in N_{a}\cap\\{\sim\\!u\mid u\not\in A\\}$ such that
$(x,\sim\\!y,+)$ or $(x,\sim\\!y,\circ)$ belong to $E_{a}$;

    * –

if $X^{+}=\\{a\mid(x,a,+)\in E_{a}\\}$ and $X^{-}=\\{a\mid(x,\sim\\!a,-)\in
E_{a}\\}$ then $X^{+}\subseteq A$, $X^{-}\cap A=\emptyset$, and there is a
rule $r\in P$ whose head is $x$ such that $r^{+}=X^{+}$ and $r^{-}=X^{-}$; and

    * –

$DG_{a}$ contains no cycle containing $x$.

  * •

for every $\sim\\!x\in N_{a}\cap\\{\sim\\!u\mid u\not\in A\\}$ and $x\not\in
U$,

    * –

there exists no $y\in N_{a}\cap A$ such that $(\sim\\!x,y,+)$ or
$(\sim\\!x,y,\circ)$ belong to $E_{a}$;

    * –

there exists no $\sim\\!y\in N_{a}\cap\\{\sim\\!u\mid u\not\in A\\}$ such that
$(\sim\\!x,\sim\\!y,-)$ or $(\sim\\!x,\sim\\!y,\circ)$ belong to $E_{a}$;

    * –

if $X^{+}=\\{a\mid(\sim\\!x,a,-)\in E_{a}\\}$ and
$X^{-}=\\{a\mid(\sim\\!x,\sim\\!a,+)\in E_{a}\\}$ then $X^{+}\subseteq A$,
$X^{-}\cap A=\emptyset$, and for every rule $r\in P$ whose head is $x$ we have
that $r^{+}\cap X^{-}\neq\emptyset$ or $r^{-}\cap X^{+}\neq\emptyset$; and

    * –

any cycle containing $\sim\\!x$ in $DG_{a}$ contains only nodes in
$N_{a}\cap\\{\sim\\!u\mid u\not\in A\\}$.

Given an explanation graph $G$ and a node $x$ in $G$, if $x$ is an atom $a$
then the nodes directly connected to $a$—the nodes $y$ such that $(x,y,\\_)$
is an edge in $G$—represent a rule whose head is $x$ and whose body is
satisfied by $A$. If $x$ is $\sim\\!x$ for some atom $x$, then the set of
nodes directly connected to $\sim\\!x$ represents a set of atoms who truth
values in $A$ are such to make each rule whose head is $x$ unsatisfied by $A$.
In other words, the direct connections with a node represent the _support_ for
the node being in (or not in) the answer set under consideration. We refer the
readers to the paper by Pontelli et al.[5] for an in-depth discussion of
properties of off-line justifications and the proof of existence of such
justifications for every atom in the program.

Given a program $P$ , an answer set $A$ of $P$, and an atom $a$ occurring in
$P$, explanation graphs for $a$ can be generated by (_i_) determining the set
of assumptions $U$ with respect to $A$; (_ii_) generating explanation graphs
for $a$ using $P$, $A$, and $U$ following its definition.

Fig. 1 illustrates the above definitions for the graph coloring program, given
the graph $G=(\\{1,2,3,4\\},\\{(1,2),\newline (1,3),(2,3),(2,4),(3,4)\\})$ and
a solution on the left, represented by the answer set containing
$\\{colored(1,red),\newline
colored(2,blue),colored(3,green),colored(4,red)\\}$.

---
Figure 1:  A solution to the 3-coloring problem for a graph on the (left), an
explanation for positive atom $colored(1,red)$ (middle), and an explanation
for negative atom $colored(1,blue)$ (middle)

For our computation in the next section, we define a _derivation path_ of an
atom $a$ as follows.

######  Definition 2.2 (Derivation Path).

Given a program $P$, an answer set $A$, a derivation path of an atom $a$ is a
directed graph $D_{a}=(N_{a},E_{a})$ where $N_{a}\subseteq{\\{x\mid x\in
A\\}\cup\\{\sim{x}\mid x\not\in A\\}}\cup\\{\top,\bot\\}$ and $E_{a}\subseteq
N_{a}\times N_{a}\times\\{+,-\\}$, where $(x,y,z)\in E_{a}$ represents a link
from $x$ to $y$ with the label $z$, and satisfies the following conditions:

  * •

if $\\{(\sim\\!x,\bot,+)\in E_{a}\\}$ then there exists no rule in $P$ whose
head is $x$;

  * •

there exists no $x,y$ such that $(\top,x,y)\in E_{a}$ and $(\bot,x,y)\in
E_{a}$;

  * •

for every $x\in N_{a}\cap A$ and $x$ is not a fact in $P$,

    * –

there exists no $y\in N_{a}\cap A$ such that $(x,y,-)$;

    * –

there exists no $\sim\\!y\in N_{a}\cap\\{\sim\\!u\mid u\not\in A\\}$ such that
$(x,\sim\\!y,+)$ belongs to $E_{a}$;

    * –

if $X^{+}=\\{a^{\prime}\mid(x,a^{\prime},+)\in E_{a}\\}$ and
$X^{-}=\\{a^{\prime}\mid(x,\sim\\!a^{\prime},-)\in E_{a}\\}$ then
$X^{+}\subseteq A$ and $X^{-}\cap A=\emptyset$ and there is a rule $r$ whose
head is $x$ in $P$ such that $r^{+}=X^{+}$ and $r^{-}=X^{-}$;

    * –

$D_{a}$ contains no cycle containing $x$.

  * •

for every $\sim\\!x\in N_{a}\cap\\{\sim\\!u\mid u\not\in A\\}$,

    * –

there exists no $y\in N_{a}\cap A$ such that $(\sim\\!x,y,+)$ belongs to
$E_{a}$;

    * –

there exists no $\sim\\!y\in N_{a}\cap\\{\sim\\!u\mid u\not\in A\\}$ such that
$(\sim\\!x,\sim\\!y,-)$ belongs to $E_{a}$;

    * –

if $X^{+}=\\{a^{\prime}\mid(\sim\\!x,a^{\prime},-)\in E_{a}\\}$ and
$X^{-}=\\{a^{\prime}\mid(\sim\\!x,\sim\\!a^{\prime},+)\in E_{a}\\}$ then
$X^{+}\subseteq A$ and $X^{-}\cap A=\emptyset$ and for every rule $r$ whose
head is $x$ in $P$ we have that $r^{+}\cap X^{-}\neq\emptyset$ or $r^{-}\cap
X^{+}\neq\emptyset$;

    * –

any cycle containing $\sim\\!x$ in $D_{a}$ contains only node in
$N_{a}\cap\\{\sim\\!u\mid u\not\in A\\}$.

Note that derivation path is different from the explanation graph. The purpose
of derivation graph is to compute $U$ in Section 3.2, in order to develop the
explanation graphs in Section 3.3.

##  3 exp(ASP): A SYSTEM FOR GENERATING EXPLANATIONS FOR ASP-PROGRAMS

In this section, we describe the algorithm implemented in the system exp(ASP)
that generates explanations for ASP-programs (Section 3.1, 3.2, and 3.3).
Given a program $P$, the preprocessing steps in Section 3.1 are used to obtain
simplified ground rules from the answer set solver clingo and compute support
sets for each rule. Given an answer set $A$ of program $P$, the algorithms in
Section 3.2 compute minimal assumption sets with respect to $A$. Algorithms in
Section 3.3 use a minimal assumption set obtained from Section 3.2 to provide
the explanation graphs for an atom in $P$. For simplicity of the presentation,
the discussion in this section assumes an arbitrary but fixed program $P$,
unless otherwise specified.

###  3.1 Preprocessing

In this development, clingo is utilized as an off-the-shelf tool. Given a
program $P$, simplified ground rules of $P$ are computed via the combination
of the \--text and \--keep-facts options and an intermediate language
$\mathit{aspif}$ [6]. First, by directly utilizing the \--text and \--keep-
facts options, plain text format are obtained. Then, a set of facts $F$ is
extracted from such plain text. Next, each fact $f\in F$ is modified to become
an external statement ($\\#external~{}f$) of the program. Facts in $P$ are
replaced by the external statements, creating a modified program $P^{\prime}$.
By doing this, we prevent clingo from simplifying rules when computing the
$\mathit{aspif}$ representation of $P^{\prime}$ via its grounder, gringo [7].
Let us illustrate this process using Example 3.1. The $\mathit{aspif}$
statements are given in Listing 1.

######  Example 3.1.

Let us consider the program $P_{1}$ containing the rules:

$\begin{array}[]{clclcclclcclcl}(r_{1})&\texttt{a}&\mbox{$\>{\tt:\\!\\!-}\>$}&\texttt{k},\>\>not\>\texttt{b}.&&(r_{4})&\texttt{b}&\mbox{$\>{\tt:\\!\\!-}\>$}&\>\>not\>\texttt{a}.&&(r_{6})&\texttt{f}&\mbox{$\>{\tt:\\!\\!-}\>$}&\texttt{e},\>\>not\>\texttt{k},\>\>not\>\texttt{c}.\\\
(r_{2})&\texttt{k}&\mbox{$\>{\tt:\\!\\!-}\>$}&\texttt{e},\>\>not\>\texttt{b}.&&(r_{5})&\texttt{c}&\mbox{$\>{\tt:\\!\\!-}\>$}&\texttt{k}.&&(r_{7})&\texttt{e}.\\\
(r_{3})&\texttt{c}&\mbox{$\>{\tt:\\!\\!-}\>$}&\texttt{a},\texttt{b}.\end{array}$

The program $P_{1}^{\prime}$ is as follows:

$\begin{array}[]{clclcclclcclcl}(r_{1})&\texttt{a}&\mbox{$\>{\tt:\\!\\!-}\>$}&\texttt{k},\>\>not\>\texttt{b}.&&(r_{4})&\texttt{b}&\mbox{$\>{\tt:\\!\\!-}\>$}&\>\>not\>\texttt{a}.&&(r_{6})&\texttt{f}&\mbox{$\>{\tt:\\!\\!-}\>$}&\texttt{e},\>\>not\>\texttt{k},\>\>not\>\texttt{c}.\\\
(r_{2})&\texttt{k}&\mbox{$\>{\tt:\\!\\!-}\>$}&\texttt{e},\>\>not\>\texttt{b}.&&(r_{5})&\texttt{c}&\mbox{$\>{\tt:\\!\\!-}\>$}&\texttt{k}.&&(r_{7})&\\#external&\texttt{e}.\\\
(r_{3})&\texttt{c}&\mbox{$\>{\tt:\\!\\!-}\>$}&\texttt{a},\texttt{b}.\end{array}$

A rule of the form (1) in Sec. 2.1, in $\mathit{aspif}$ format, is of the
form:

$1~{}H~{}B$

where $H$ describes the head of the rule, starting with $0$, and has the form:

$0~{}n~{}i_{c}$

where $n=\\{0,1\\}$ is the number of head atoms and $i_{c}$ is an integer
identifying the atom $c$. If the head is empty, $n=0$ and $i_{c}=0$.

The body of the rule is described by $B$ and has the form:

$0~{}k~{}i_{a_{1}}~{}...~{}i_{a_{m}}~{}-i_{b_{1}}~{}...~{}~{}-i_{b_{n}}$

where $i_{a_{i}}$’s and $i_{b_{i}}$’s are the integer identifiers of atoms
$a_{i}$’s and $b_{i}$’s, respectively, and $k=n+m$. For instance, in Listing
1, line 3 represents rule $r_{4}$.

The lines starting with $4$ represent the mapping of atoms to their unique
integer identifiers and have the form:

$4~{}m~{}a~{}1~{}i$

where $m$ is the length in bytes of atom $a$ and $i$ is $a$’s identifier. For
instance, line 9 in Listing 1 shows that $2$ is an integer identifying atom
$b$.

Because we had changed facts to external statements in the modified program,
facts are represented in lines starting with $5$ and have the form:

$5~{}i~{}2$

where $i$ is an integer identifier of a fact. For instance, Line 2 in Listing
1 (and Line 12) shows that atom $e$ is associated with the integer identifying
$1$ is a fact.

Listing 1: Representing $P_{1}^{\prime}$ in $\mathit{aspif}$ format

⬇

1asp 1 0 0

25 1 2

31 0 1 2 0 1 -3

41 0 1 4 0 2 -2 1

51 0 1 3 0 2 -2 4

61 0 1 5 0 2 2 3

71 0 1 5 0 1 4

81 0 1 6 0 3 -5 -4 1

94 1 b 1 2

104 1 k 1 4

114 1 a 1 3

124 1 e 1 1

134 1 c 1 5

144 1 f 1 6

150

We implement exp(ASP) using Python. Thus, from now on, whenever we mention a
dictionary, we refer to a Python data structure dictionary. For a dictionary
$D$, we use $D.keys()$ and $D[k]$ to the set of keys in $D$ and the value
associated with $k$ in $D$, respectively.

We use the $\mathit{aspif}$ representation of the modified program
$P^{\prime}$ to create a dictionary $D_{P}=\\{h\mapsto B\mid h\in
H,B=\\{body(r)\mid r\in P,head(r)=h\\}\\}$. For each rule $r$, $body(r)$
consists of $r^{+}$ and $r^{-}$. $D_{P}$ is then used as an input in Algorithm
1 to compute the dictionary $E_{P}=\\{k\mapsto V\mid k\in\\{a\mid a\in
A\\}\cup\\{\sim\\!a\mid a\notin A\\},V=\\{support(k,r)\mid r\in P\\}\\}$.
Algorithm 1 first checks the truth value of atom $a\in H$ (recall that $H$ is
the Herbrand base of the given program). If $a$ is true w.r.t $A$ (Line 1),
the function _true_atom_processing_ is used to compute the supported set for
$a$, following the first property in Sect. 2.2. Otherwise, the function
_false_atom_processing_ is used to compute the supported set for $a$,
following the second property in Sect. 2.2.

1

Input: $D$ \- dictionary of rules (this is $D_{P}$), $F$ \- facts of the
program, $A$ \- an answer set

2

$E\leftarrow\\{\emptyset\mapsto\emptyset\\}$

// Initialize an empty dictionary $E$: $E.key()=\emptyset$

3

4for  _$a\in H$_ do

5 $bodies\leftarrow D[a]$

6 if  _$a\in A$_ then

7

$E[a]=[]$

// Initialize an empty list for the value stored with $a$ in $E$

8

9 for  _$body\in bodies$_ do

10 $E\leftarrow true\\_atoms\\_processing(a,r^{+},r^{-},E,A,F)$

11

12 else

13

$E[\sim\\!a]=[]$

// Initialize an empty list for the value stored with $\sim\\!a$ in $E$

14

15 for  _$body\in bodies$_ do

16 $E\leftarrow false\\_atoms\\_processing(a,r^{+},r^{-},E,A)$

17

18

19

20return $E$

21

22function $true\\_atoms\\_processing(a,r^{+},r^{-},E,A,F)$

23if  _$r^{+}\subseteq A\land r^{-}\cap A=\emptyset$ _ then

24 $S\leftarrow\\{p\mid p\in r^{+}\\}\cup\\{\sim\\!n\mid n\in r^{-}\\}$

25 if  _$a\in F\land r^{+}=\emptyset\land r^{-}=\emptyset$_ then

26 $S\leftarrow\\{``\mathtt{T}"\\}$

27

28 Append $S$ to $E[a]$

29

30return $E$

31

32function $false\\_atoms\\_processing(a,r^{+},r^{-},E,A)$

33$L\leftarrow[\\{\\{\sim\\!p\\}\mid p\in r^{+}\land p\notin
A\\}\cup\\{\\{n\\}\mid n\in r^{-}\land n\in A\\}]$

34if  _$\sim\\!a\notin E.keys()$_ then

35 $E[\sim\\!a]\leftarrow L$

36else

$T=[]$

// Initialize an empty list $T$

37

38 for  _$s\in L$_ do

39 for  _$e\in E[\sim\\!a]$ _ do

40 $t\leftarrow s\cup e$

41 Append $t$ to a list $T$

42

43

44 $E[\sim\\!a]\leftarrow T$

return $E$

Algorithm 1 $preprocessing(D,F,A)$

######  Example 3.2.

Let us reconsider the program $P_{1}$ of Example 3.1 which has an answer set
$A=\\{b,f,e\\}$. The output of Algorithm 1, dictionary $E_{P_{1}}$, is as
follows:

⬇

E = { f : [{$\sim$k, $\sim$c, e}]

b : [{$\sim$a}]

$\sim$c : [{$\sim$k, $\sim$a}]

$\sim$k : [{b}]

$\sim$a : [{$\sim$k}, {b}]

e : [{T}]

}

As can be seen from Example 3.2, $E_{P_{1}}$ contains supported sets for the
keys in $E_{P_{1}}$. For instance, atom $e$ in rule $r_{2}$ is not in any
supported set for atom $b$, so $e$ does not appear in $E_{P_{1}}[b]$’s value.

We will also use the $\mathit{aspif}$ representation to compute $NANT(P)$
(Section 2.3). Note that each negative atom is represented by a negative
integer whose absolute value is in the symbol table. For instance, Line 3 in
Listing 1 shows that the atom associated with integer $3$ is a negative atom,
and Line 11 in Listing 1 shows that $3$ is integer identifying atom $a$; thus,
for $P_{1}$, we have $a\in NANT(P_{1})$, and $NANT(P_{1})=\\{a,b,c,k\\}$.

###  3.2 Minimal Assumption Set

In this section, we compute all minimal assumption sets $U$ w.r.t $A$ that
satisfy conditions of an assumption set in Sect. 2.3. For every $u\in U$, $u$
is false in $A$ and does not belong to the well-founded model and it must be
assumed to be false to guarantee that cycles in the explanation graphs are
acceptable [5].

Input: C(P) - A cautious consequence of a program $P$, NANT(P) - A set of
negative atoms in $P$, E - A dictionary computed in Algorithm 1.

$TU=\emptyset$

// Initialize an empty set $TU$

1

2$TA_{P}(A)=\\{a\mid a\in NANT(P)\land a\notin A\land a\notin C(P)\\}$

3$(T,DA)=derivation\\_path(TA_{P}(A),E)$

4$D=dependency\\_assumption(DA)$

5for  _$M\in D$_ do

6 $U\leftarrow M\cup T$

7 $TU\leftarrow TU\cup\\{U\\}$

8

9return $TU$

10

11function $derivation\\_path(TA,E)$

$DA\leftarrow\\{\emptyset\mapsto\emptyset\\}$ and
$T^{\prime}\leftarrow\emptyset$

// Initialize an empty dictionary $DA$ and an empty set $T^{\prime}$

12

13for  _$a\in TA$_ do

14 $O\leftarrow TA\setminus\\{a\\}$

15 $L\leftarrow E[\sim\\!a]$

16 for  _$S\in L$_ do

$E_{a}\leftarrow\\{\emptyset\mapsto\emptyset\\}$

// Initialize an empty dictionary $E_{a}$

17

18 $E_{a}[\sim\\!a]\leftarrow[S]$

19 $E_{a}\leftarrow get\\_connection(S,E,E_{a})$

20 $M\leftarrow\\{N_{i}\mid N_{i}={k\mapsto V\mid V\in E_{a}[k]}\land\forall
k\in E_{a}.keys(),k\in N_{i}.keys()\land(k\mapsto V_{1}\in N_{i}\land k\mapsto
V_{2}\in N_{i})\Rightarrow V_{1}=V_{2}\\}$

21 for  _$N_{i}\in M$_ do

22 $V\leftarrow[]$, $R\leftarrow\emptyset$,
$C=\\{\emptyset\mapsto\emptyset\\}$ and $D=\emptyset$

23 $(safe,D^{\prime})\leftarrow
check\\_derivation\\_path(\sim\\!a,N_{i},O,V,R,C,D)$

24 if  _$safe=True$_ then

25 $T^{\prime}\leftarrow T^{\prime}\cup\\{a\\}$

26 $DA[a]\leftarrow D^{\prime}$

27 goto line 2

28

29

30

31

32$T\leftarrow TA\setminus T^{\prime}$

33return $(T,DA)$

34

35function $dependency\\_assumption(DA)$

36$DC\leftarrow\\{J\mid J=\\{u_{1},u_{2},...,u_{n}\mid u_{i}\in DA.keys()\land
u_{i+1}\in DA[u_{i<n}]\\}\land u_{1}\in D[u_{n}]\\}$

37$B\leftarrow\\{\\{j_{1},...,j_{n}\\}\mid(j_{1},...,j_{n})\in
J_{1}\times..\times J_{n}\land n=\bigm{|}\\!DC\\!\bigm{|}\land J_{i}\in DC\\}$

38$min(B)\leftarrow\\{M\mid\forall C\in B,C\neq
M\implies\bigm{|}\\!M\\!\bigm{|}\leq\bigm{|}\\!C\\!\bigm{|}\\}$

39return $min(B)$

40

41function $get\\_connection(S,E,E_{a})$

42for  _$e\in S$_ do

43 if  _$e\notin E_{a}.keys()\land e\in E.keys()$_ then

44

45 $E_{a}[e]\leftarrow E[e]$

46 for  _$S_{e}\in E[e]$_ do

47 $E_{a}\leftarrow get\\_connection(S_{e},E,E_{a})$

48

49

50

51return $E_{a}$

Algorithm 2 $assumption\\_func(C(P),NANT(P),E)$

Algorithm 2 shows the pseudo-code for computing $TU$ which consists of all
minimal assumption sets $U$. The cautious consequence $C(P)$ is computed using
clingo. $NANT(P)$ and $E$ are obtained in Sec. 3.1. First, $TA_{P}(A)$, called
_the tentative assumption set_ , is computed in Line 2. It is the set of
negative atoms that are false in $A$ and do not belong to $C(P)$.

$T$ and $DA$ are computed by the function _derivation_path_ (Line 2) where
$T=TA_{P}(A)\setminus T^{\prime}$. $T$ is the set of atoms from $TA_{P}(A)$
and do not belong to $T^{\prime}$ which is computed by the for-loop (Line
2–2). For each $x\in T^{\prime}$, there exists one derivation path of $x$ that
either depends on other atoms in $TA_{P}(A)$ or satisfies the cycle conditions
in the definition of explanation graph. Intuitively, the atoms in $T$ must be
assumed to be false and $DA$ contains the dependencies among atoms in
$TA_{P}(A)$.

$D^{\prime}$ is computed in Algorithm 3. It checks whether a derivation path
of an atom $a$ is acceptable and updates the set of dependency atoms in _the
tentative assumption set_ for $a$. A derivation path is unacceptable if it has
a cycle containing true atoms. This is verified by Algorithm 4.

The computation of sets of minimal atoms that break all cycles in _the
tentative assumption set_ is then done by the function
_$dependency\\_assumption(DA)$_ (Lines 2–2).

$I\leftarrow\emptyset$

// Initialize an empty set $I$

1

2if  _$k\in N.keys()$_ then

3 $I\leftarrow N[k]$

4

5$V\leftarrow V\cup\\{k\\}$

6Append $k$ to list $R$

7for  _$i\in I$_ do

8 $C[k]\leftarrow i$

9 $j\leftarrow i.remove(i.index(0))$

10 if  _$i.index(0)=``\sim"\land j\in O$_ then

11 $Da\leftarrow Da\cup\\{j\\}$

12 else

13 if  _$i\notin V$_ then

14 if  _$check\\_derivation\\_path(i,N,O,V,R,C,Da)[0]=False$_ then

15 return (False,Da)

16

17 else

18 if  _$i\in R$_ then

19 if  _$i.index(0)=``\sim"$_ then

20 if  _$cycle\\_identification(C,i,i)=False$_ then

21 return (False,Da)

22

23 else

24 return (False,Da)

25

26

27

28

29

30$l=R.pop()$

31if  _$l\in C.keys()$_ then

32 $C.pop(l)$

33

return (True,Da)

Algorithm 3 $check\\_derivation\\_path(k,N,O,V,R,C,Da)$

1 $v\leftarrow C[s]$

2if  _$v\neq e\wedge s.index(0)=``\sim"\land v.index(0)=``\sim"$ _ then

3 return $cycle\\_identification(C,v,e)$

4

5if  _$v=e\wedge s.index(0)=``\sim"\land v.index(0)=``\sim"$ _ then

6 return True

7

8return False

Algorithm 4 $cycle\\_identification(C,s,e)$

######  Example 3.3.

Let use reconsider the Examples 3.1 and 3.2.

  * •

For the program $P_{1}$, we have:

$\begin{array}[]{lcl}{TA}_{P}(A)&=&\\{c,a,k\\}\\\ \end{array}$

  * •

As can be seen from $E$ in Example 3.2, $c$, $a$ and $k$ derive from other
atoms in $\\{k,a\\}$, $\\{k\\}$ and $\\{a\\}$, respectively. Also, there is a
cycle associated to $k$ and $a$. Thus, we have

$\begin{array}[]{lcl}T&=&\emptyset\\\ D&=&\\{\\{a\\}\\},\\{k\\}\\}\end{array}$

  * •

Two minimal assumption sets are as follows:

$\begin{array}[]{lcl}U_{1}&=&\\{a\\}\\\ U_{2}&=&\\{k\\}\end{array}$

###  3.3 ASP-based explanation graph

1 for  _$u\in U$_ do

2

3 $E[\sim\\!u]\leftarrow[{``\mathtt{assume}"}]$

4

5$a^{\prime}\leftarrow a$ if $a\in A$ and $a^{\prime}\leftarrow\sim\\!a$ if
$a\notin A$

6$L\leftarrow E[a^{\prime}]$

7for  _$S\in L$_ do

$E_{a}\leftarrow\\{\emptyset\mapsto\emptyset\\}$

// Initialize an empty dictionary $E_{a}$

8

9 $E_{a}[a^{\prime}]\leftarrow[S]$

10 $E_{a}\leftarrow get\\_connection(S,E,E_{a})$

11 $M\leftarrow\\{N_{i}\mid N_{i}={k\mapsto V\mid V\in E_{a}[k]}\land\forall
k\in E_{a}.keys(),k\in N_{i}.keys()\land(k\mapsto V_{1}\in N_{i}\land k\mapsto
V_{2}\in N_{i})\implies V_{1}=V_{2}\\}$

12

13 for  _$N_{i}\in M$_ do

14 $V\leftarrow[]$, $R\leftarrow\emptyset$,
$C\leftarrow\\{\emptyset\mapsto\emptyset\\}$, and an empty graph
$G\leftarrow(\emptyset,\emptyset)$

15 Add node $a^{\prime}$ to $G$

16 $graph\leftarrow get\\_graph(a^{\prime},G,N_{i},V,R,C)$

17 if  _$graph\neq False$_ then

18 Draw $graph$

19

20

21

22

23function $get\\_graph(k,G,N,V,R,C)$

$I\leftarrow\emptyset$

// Initialize an empty set $I$

24

25if  _$k\in N.keys()$_ then

26 $I\leftarrow N[k]$

27

28$V\leftarrow V\cup\\{k\\}$

29Append $k$ to list $R$

30for  _$i\in I$_ do

31 Add node $i$ to $G$

32 $e\leftarrow(k,i,sign)$

33 Add edge $e$ to $G$

34 if  _$i\notin V$_ then

35 if  _$get\\_graph(i,G,N,V,R,C)=False$_ then

36 return False

37

38 else

39 if  _$i\in R$_ then

40 if  _$i.index(0)=``\sim"$_ then

41 if  _$cycle\\_identification(C,i,i)=False$_ then

42 return False

43

44 else

45 return False

46

47

48

49

50$l=R.pop()$

51if  _$l\in C.keys()$_ then

52 $C.pop(l)$

53

54return G

Algorithm 5 $explanation\\_graph(a,E,U)$

In this section, we utilize the dictionary $E_{P}$ and a minimal assumption
set $U$ to provide the explanation graphs of an atom $a$ in the program $P$.
Algorithm 5 shows the pseudo-code for computing the explanation graphs for
$a$. Elements in $u\in U$ is $\\{``\mathtt{assume}"\\}$ (Lines 5–5). Supported
sets of $a$ are then computed and assigned to $L$ (Line 5). Lines 5–5 create
$M$, a collection of dictionaries of derivation paths for $a$. It is then used
for computing explanation graphs for $a$ via the function _get_graph_ (Lines
5–5). If the derivation graph is an explanation graph, it will be displayed as
a graph on the screen.

######  Example 3.4.

For program $P_{1}$ in Example 3.1, the explanation graphs of $f$ w.r.t
$U_{1}$ and $U_{2}$ are shown on the left and right of Fig. 2, respectively.

As can be seen from Fig. 2, a justification for $f$ depends negatively on $c$
and $k$, and positively on $e$. Based on the minimal assumption set we choose,
we receive two different explanation graphs for $f$. The left figure contains
$b$ in its graph while the right figure does not.

---
Figure 2: Explanation graph of $a$ w.r.t $U_{1}$ (left) and $U_{2}$ (right)

##  4 ILLUSTRATION

We have validated a prototype implementation of this system on a number of ASP
programs, ranging from simple benchmarks to complex ASP applications (e.g., we
used it to interpret the responses produced by a diagnosis system modeling the
Three Mile Island disaster [8]). In this paper, we illustrate the use of
exp(ASP) in two examples from the literature.

######  Example 4.1.

Consider the following problem, which represents a variant of the agent
problem described by Garcia et al.[9]. An agent, named Bob, wants to make plan
for the upcoming week. Bob has two choices: stay home or go to the opera. Bob
will stay at home on Monday. He will also stay at home with his best friend
because she has a baby, and the friend comes this Tuesday. The situation can
be encoded as follows:

$\begin{array}[]{lclclclclcl}\texttt{day(monday)}.&&\texttt{day(tuesday)}.&&\texttt{day(wednesday)}.\\\
\texttt{day(thursday)}.&&\texttt{day(friday)}.&&\texttt{day(saturday)}.\\\
\texttt{day(sunday)}.&&\texttt{home(monday)}.&&\texttt{baby(tuesday)}.\\\
\texttt{opera(D)}&\mbox{$\>{\tt:\\!\\!-}\>$}&\texttt{day(D)},\>\>not\>\texttt{
home(D)}.\\\
\texttt{home(D)}&\mbox{$\>{\tt:\\!\\!-}\>$}&\texttt{day(D)},\>\>not\>\texttt{
opera(D)}.\\\
\texttt{home(D)}&\mbox{$\>{\tt:\\!\\!-}\>$}&\texttt{day(D)},\texttt{
baby(D)}.\\\ \end{array}$

The above program has 32 answer sets, i.e., Bob has 32 possible plans. Let us
consider the answer set
$A=\\{day(monday),day(tuesday),day(wednesday),day(thursday),day(friday),day(saturday),day(sunday),\\\
home(monday),home(tuesday),baby(tuesday),opera(wednesday),opera(thursday),opera(friday),\\\
opera(saturday),opera(sunday)\\}$.

Some explanation graphs w.r.t $A$ are displayed below:

---
Figure 3: Explanation of $home(monday)$ (left), $home(tuesday)$ (middle) and
$opera(friday)$ (right)

  * •

Fig. 3 (left) shows that Bob will stay at home on Monday because of the
provided information in the situation that $home(monday)$ is a fact.

  * •

Fig. 3 (middle) shows that Bob will stay at home on Tuesday because his best
friend and her baby will come to his house on Tuesday ($baby(tuesday)$ is a
fact).

  * •

Fig. 3 (right) shows that Bob will go to opera on Friday because it is assumed
to be false that he will not stay at home on Friday.

######  Example 4.2.

Consider the problem of decision making in an ophthalmologist diagnostic
system [10]. We need to provide a suggestion to Peter. Peter is short-sighted.
He is afraid to touch his eyes. He is a student and likes sport. The
information about Peter is encoded by the following facts.

$\begin{array}[]{lclclcl}\texttt{shortSighted}.&&\texttt{afraidToTouchEyes}.\\\
\texttt{student}.&&\texttt{likesSports}.\\\ \end{array}$

Other information about Peter is given by the following program:

$\begin{array}[]{lclclcl}\texttt{tightOnMoney}&\mbox{$\>{\tt:\\!\\!-}\>$}&\texttt{student},\>\>not\>\texttt{richParents}.\\\
\texttt{caresPracticality}&\mbox{$\>{\tt:\\!\\!-}\>$}&\texttt{likesSports}.\\\
\texttt{correctiveLens}&\mbox{$\>{\tt:\\!\\!-}\>$}&\texttt{shortSighted},\>\>not\>\texttt{laserSurgery}.\\\
\texttt{laserSurgery}&\mbox{$\>{\tt:\\!\\!-}\>$}&\texttt{shortSighted},\>\>not\>\texttt{tightOnMoney},\>\>not\>\texttt{correctiveLens}.\\\
\texttt{glasses}&\mbox{$\>{\tt:\\!\\!-}\>$}&\texttt{correctiveLens},\>\>not\>\texttt{caresPracticality},\\\
&&\>\>not\>\texttt{contactLens}.\\\
\texttt{contactLens}&\mbox{$\>{\tt:\\!\\!-}\>$}&\texttt{correctiveLens},\>\>not\>\texttt{afraidToTouchEyes},\\\
&&\>\>not\>\texttt{longSighted},\>\>not\>\texttt{glasses}.\\\
\texttt{intraocularLens}&\mbox{$\>{\tt:\\!\\!-}\>$}&\texttt{correctiveLens},\>\>not\>\texttt{glasses},\>\>not\>\texttt{contactLens}.\\\
\end{array}$

This program, together with the facts, has an answer set

$A=\\{tightOnMoney,shortSighted,caresPracticality,afraidToTouchEyes,student,likesSports,\\\
correctiveLens,intraocularLens\\}$.

Therefore, $intraocularLens$ is suggested to Peter. The explanation graph for
this recommendation is depicted in Fig. 4.

Figure 4: Explanation of $intraocularLens$

As can be seen from Fig. 4, $intraocularLens$ is in the answer set because:

  * •

The truth value of $correctiveLens$ is True, because

    * –

It has information that Peter is short-sighted ($shortSighted$ is a fact).

    * –

Negatively it depends on the truth value of $laserSurgery$ which is False.
This latter truth value derives from the fact that $laserSurgery$ depends
negatively on the truth value of $tightOnMoney$ which is True. This is because
it has information that Peter is student ($student$ is a fact).

  * •

The truth value of $contactLens$ is False, because

    * –

Negatively it depends on the truth value of $afraidToTouchEyes$ which is a
fact.

  * •

The truth value of $glasses$ is False, because

    * –

Negatively it depends on the truth value of $caresPracticality$ which is True,
because

      * *

It has information that Peter likes sports ($likeSports$ is a fact).

##  5 CONCLUSION

In this paper, we described an explanation generation system for ASP programs,
exp(ASP), and illustrate its use in some examples. Our future goal is to use
the proposed system in explainable planning with the full cycle of four steps
(1)-(4) in Fig. 1.

###### Acknowledgements.

This research is partially supported by NSF grants 1757207, 1914635, and
1812619/26. Portions of this publication and research effort are made possible
through the help and support of NIST via cooperative agreement 70NANB19H102.
The views and conclusions contained in this document are those of the authors
and should not be interpreted as representing the official policies, either
expressed or implied, of the sponsoring organizations, agencies, or the U.S.
government.

## References

  * [1] Marek, V. and Truszczyński, M., “Stable models and an alternative logic programming paradigm,” in [The Logic Programming Paradigm: a 25-year Perspective ], 375–398 (1999).
  * [2] Niemelä, I., “Logic programming with stable model semantics as a constraint programming paradigm,” Annals of Mathematics and Artificial Intelligence 25(3,4), 241–273 (1999).
  * [3] Gelfond, M. and Lifschitz, V., “Logic programs with classical negation,” in [Logic Programming: Proceedings of the Seventh International Conference ], Warren, D. and Szeredi, P., eds., 579–597 (1990).
  * [4] Gebser, M., Kaufmann, B., Neumann, A., and Schaub, T., “clasp: A conflict-driven answer set solver,” in [Proceedings of the Ninth International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR’07) ], Baral, C., Brewka, G., and Schlipf, J., eds., Lecture Notes in Artificial Intelligence 4483, 260–265, Springer-Verlag (2007).
  * [5] Pontelli, E., Son, T., and El-Khatib, O., “Justifications for logic programs under answer set semantics,” TPLP 9(1), 1–56 (2009).
  * [6] Kaminski, R., Schaub, T., and Wanko, P., “A tutorial on hybrid answer set solving with clingo,” in [Reasoning Web International Summer School ], 167–203, Springer (2017).
  * [7] Gebser, M., Schaub, T., and Thiele, S., “Gringo: A new grounder for answer set programming,” in [International Conference on Logic Programming and Nonmonotonic Reasoning ], 266–271, Springer (2007).
  * [8] Hanna, B. N., T Trieu, L. L., Son, T. C., and Dinh, N. T., “An application of asp in nuclear engineering: Explaining the three mile island nuclear accident scenario,” Theory and Practice of Logic Programming 20(6), 926–941 (2020).
  * [9] García, A. J., Chesñevar, C. I., Rotstein, N. D., and Simari, G. R., “Formalizing dialectical explanation support for argument-based reasoning in knowledge-based systems,” Expert Systems with Applications 40(8), 3233–3247 (2013).
  * [10] Schulz, C. and Toni, F., “Justifying answer sets using argumentation,” Theory and Practice of Logic Programming 16(1), 59–110 (2016).