{'fraction_non_alphanumeric': 0.053980505665231805, 'fraction_numerical': 0.00643214091336401, 'mean_word_length': 3.693915466790525, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 8, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Generating explanations for answer set programming applications

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.


INTRODUCTION
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 informationthat 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, nonmonotonic, 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.

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 where c, a i 's, and b j 's are atoms of a propositional language * and 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 , . . . , a m } and {b 1 , . . . , 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 |= a) if a ∈ I. The body of a rule r is satisfied by I if r + ⊆ I and r − ∩ I = ∅. A rule r is satisfied by I if I |= head(r) or I |= 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 − ∩ I = ∅, 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. ⊆) 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, . . . , 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): colored(u, g) ← not colored(u, b), not colored(u, r) colored(u, r) ← not colored(u, b), not colored(u, g) colored(u, b) ← 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: 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.

Properties of ASP
Given a program P and an answer set A, the following properties hold: 1. If c ∈ A, there exists a rule r in P such that • head(r) = c; • r + ⊆ A; and, For such a rule r, we define support(c, r) = {p | p ∈ A ∧ p ∈ r + } ∪ {∼ n | n / ∈ A ∧ n ∈ r − } and refer to this set as a supported set of c for rule r.

If c /
∈ A, for every rules r such that head(r) = c, then For such a rule r, we define support(∼ c, r) ∈ {{p} | p ∈ A ∧ p ∈ r − } ∪ {{∼ n} | n / ∈ A ∧ n ∈ r + } and refer to it as a supported set of ∼ c for rule r.

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 . N AN T (P ) = {a | a ∈ r − ∧ r ∈ 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 + ∪ 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 ⊆ N AN T (P )\(A∪C(P )) is called a set of assumptions with respect to A if A = C(P \{r ∈ P | head(r) ∈ U }).
Intuitively, given an answer set A of a program P , an atom a ∈ A (a ∈ 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 ∈ A (or ∈ 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 and ⊥ represent true and false, respectively. An explanation graph of an atom a occurring in P is a finite labeled and where (x, y, z) ∈ E a represents a link from x to y with the label z, and satisfies the following conditions: • if a ∈ A then a ∈ N a and every node in N a must be reachable from a; • if a ∈ A then ∼ a ∈ N a and every node in N a must be reachable from ∼ a; • if (∼ x, ⊥, +) ∈ E a then there exists no rule in P whose head is x; • there exists no x, y such that ( , x, y) ∈ E a , (⊥, x, y) ∈ E a , or (assume, x, y) ∈ E a ; • for every x ∈ N a ∩ A and x is not a fact in P , is a rule r ∈ P whose head is x such that r + = X + and r − = X − ; and -DG a contains no cycle containing x.
and for every rule r ∈ P whose head is x we have that r + ∩ X − = ∅ or r − ∩ X + = ∅; and 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 ∼ x for some atom x, then the set of nodes directly connected to ∼ 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.  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 where (x, y, z) ∈ E a represents a link from x to y with the label z, and satisfies the following conditions: then there exists no rule in P whose head is x; • there exists no x, y such that ( , x, y) ∈ E a and (⊥, x, y) ∈ E a ; • for every x ∈ N a ∩ A and x is not a fact in P , 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.
and for every rule r whose head is x in P we have that r 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.

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.

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 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 ∈ 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 . By doing this, we prevent clingo from simplifying rules when computing the aspif representation of P via its grounder, gringo. 7 Let us illustrate this process using Example 1. The aspif statements are given in Listing 1.
Example 1. Let us consider the program P 1 containing the rules: The program P 1 is as follows: Because we had changed facts to external statements in the modified program, facts are represented in lines starting with 5 and have the form: 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. 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 aspif representation of the modified program P to create a dictionary D P = {h → B | h ∈ H, B = {body(r) | r ∈ 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 → V | k ∈ {a | a ∈ A} ∪ {∼ a | a / ∈ A}, V = {support(k, r) | r ∈ P }}. Algorithm 1 first checks the truth value of atom a ∈ H (recall that H is the Herbrand base of the given program). If a is true w.r.t A (Line 4), the function true atom processing is used to compute  As can be seen from Example 2, E P1 contains supported sets for the keys in E P1 . For instance, atom e in rule r 2 is not in any supported set for atom b, so e does not appear in E P1 [b]'s value.
We will also use the aspif representation to compute N AN T (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 ∈ N AN T (P 1 ), and N AN T (P 1 ) = {a, b, c, k}.

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 ∈ 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 Algorithm 2 shows the pseudo-code for computing T U which consists of all minimal assumption sets U . The cautious consequence C(P ) is computed using clingo. N AN T (P ) and E are obtained in Sec. 3.1. First, T A 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 3) where T = T A P (A) \ T . T is the set of atoms from T A P (A) and do not belong to T which is computed by the for-loop (Line 12-26). For each x ∈ T , there exists one derivation path of x that either depends on other atoms in T A 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 T A P (A).
D 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 30-33). • For the program P 1 , we have: T A P (A) = {c, a, k} • As can be seen from E in Example 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 • Two minimal assumption sets are as follows:

ASP-based explanation graph
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 ∈ U is {"assume"} (Lines 1-2). Supported sets of a are then computed and assigned to L (Line 4). Lines 5-9 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 17-40). If the derivation graph is an explanation graph, it will be displayed as a graph on the screen. As can be seen from Fig. 3, 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.
Algorithm 2: assumption f unc(C(P ), N AN T (P ), E) 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.

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 5. 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 Algorithm 5: explanation graph(a, E, U )    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(f riday), day(saturday), day(sunday), home(monday), home(tuesday), baby(tuesday), opera(wednesday), opera(thursday), opera(f riday), opera(saturday), opera(sunday)}.
Some explanation graphs w.r.t A are displayed below: • Fig. 4 (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. 4 (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. 4 (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 6. 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.
Other information about Peter is given by the following program: This program, together with the facts, has an answer set A = {tightOnM oney, shortSighted, caresP racticality, af raidT oT ouchEyes, student, likesSports, correctiveLens, intraocularLens}.
Therefore, intraocularLens is suggested to Peter. The explanation graph for this recommendation is depicted in Fig. 5. As can be seen from Fig. 5, 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 tightOnM oney 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 af raidT oT ouchEyes which is a fact.
• The truth value of glasses is False, because -Negatively it depends on the truth value of caresP racticality which is True, because * It has information that Peter likes sports (likeSports is a fact).

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.