Defeasible logic programming: DeLP-servers, contextual queries, and explanations for answers

1.Introduction

The representation of knowledge and its exploitation in solving problems is one of the most important areas of Artificial Intelligence. In this fertile field of research, described as Knowledge Representation and Reasoning, different systems have been proposed during the past decades, offering interesting and highly valuable alternatives such as McCarthy's Circumscription (McCarthy, 1980), Reiter's Default Logic (Reiter, 1980), McDermott and Doyle's Nonmonotonic Logic (McDermott & Doyle, 1980), Moore's Autoepistemic Logic (Moore, 1984), and the work of Pollock on defeasible reasoning (Pollock, 1987, 1996) and Loui on argumentation (Loui,1987), started lines of research that lead to many proposals to address the problem of having a computational approach to commonsense reasoning.

The research started in the 1980s led to a number of proposals on computationally oriented systems that consider the theoretical and practical underpinnings of argumentation as an effective reasoning process. Particularly, in the argumentation community we can mention the work of Lin and Shoham (1989), Nute (1987, 1988), Simari (1989) and Simari and Loui (1992) considering defeasible reasoning and argumentation, Dung (1993, 1995) on abstract argumentation frameworks, Bondarenko, Toni, and Kowalski (1993) and Bondarenko, Dung, Kowalski, and Toni(1997) leading to Assumption-Based Argumentation, Prakken (2010) and Modgil and Prakken(2013) on the development of ASPIC+, Besnard and Hunter introduced in Besnard and Hunter(2001, 2008) an argumentation system based on classical logic. Several works on the research on argumentation systems have been produced, see Chesñevar, Maguitman, and Loui (2000), Prakkenand Vreeswijk (2002), Bench-Capon and Dunne (2007), Besnard and Hunter (2008), and Rahwanand Simari (2009).

From the body of work on Nonmonotonic and Defeasible Reasoning, Logic Programming has emerged as one of the more attractive choices for its theoretical soundness and effective implementations. Thus, systems based on this paradigm have received increasing attention from industry for the construction of intelligent systems. The introduction of the elements of defeasible reasoning in logic programming was a natural choice to address the problem of inconsistency.

Defeasible Logic Programming, or DeLP for short, provides a computational reasoning system that uses an argumentation engine to obtain answers from a knowledge base represented using a logic programming language extended with defeasible rules that stem from the work reported in Simari (1989) and Simari and Loui (1992). The language of the DeLP system contains classical negation and offers the possibility of using default negation (see Baral & Gelfond, 1994), sharing the declarative capability of logic programming for representing knowledge, and adding the possibility of representing weak information in the form of defeasible rules. The argumentation-based inference mechanism has the ability of considering reasons for and against potential conclusions and deciding which are the ones that can be obtained (warranted) from the knowledge base (see García, 2000, García & Simari, 2004).

The DeLP reasoning engine forms the core of a Defeasible Logic Programming Server, or DeLP-Server for short (García, Rotstein, Tucat, & Simari, 2007). A DeLP-Server is conceived as the support for the implementation of argumentative reasoning services that work over knowledge bases represented as defeasible logic programs. These servers were developed to provide a reasoning service as part of a knowledge-based infrastructure in multi-agent systems (MAS). An inherent characteristic of MASs is that they constitute a distributed environment, where hosts for services and agents could be in different locations that could even be physically apart; thus, client agents that operate in an MAS, can remotely access DeLP-Servers that support different reasoning services that exploit particular knowledge bases.

In addition to answering queries from a knowledge base,11 a DeLP-Server offers the additional capability of complementing these queries with an additional fragment of a defeasible logic program. This program fragment will act as a private context for the query, allowing a DeLP-server to respond to that contextualised query using not only the knowledge stored in the server but also temporarily modifying it with this private context in several specific ways. We will discuss the subject in one of the sections below.

Another important and desirable feature in any knowledge-based system is that of offering explanations that will improve the understanding of an answer returned after a query. In the framework discussed here, explanations aim to transfer the understanding of how, from a given argumentation framework, the status of a particular argument was obtained; thus, an explanation will consist of a structure that reflects the analysis carried out to obtain such status, and it will contain those arguments and counterarguments that were considered in the analysis leading to its warrant status. That is, the warrant status of a claim will be explained by presenting the whole set of dialectical trees that was generated to decide the warrant status of the arguments related to the claim. From the point of view of the receiver, this explanation will make available all the arguments considered, their statuses (i.e. defeated/undefeated), with all their interactions explicitly shown, showing to the receiver of the explanation all the elements at stake in the dialectical analysis that supports the answer.

This paper has the aim of presenting in a progressive manner the elements involved in a knowledge-based system where its reasoning mechanism uses an argumentative approach to epistemic reasoning. We will begin by introducing the essential constituents of DeLP, then we will proceed to describe how a DeLP-Server works, and we will introduce the explanation facility designed with argumentative reasoning in mind. To conclude this work, we will succinctly describe other developments based on DeLP.

2.Knowledge representation

DeLP is a formalisation of defeasible reasoning in which results of Logic Programming and Argumentation are combined. DeLP has the declarative capability of representing knowledge in a language that extends the language of logic programming with the possibility of representing weak information in the form of defeasible rules, and an argumentation-based inference mechanism for warranting conclusions. In what follows, we will use concepts of Logic Programming that will be brought in as necessary in the presentation.

This section will introduce a description of DeLP's features for knowledge representation and then, in the following section, the details concerning its inference mechanism will be explained. Although the work leading to the formalisation of DeLP began in the early 1990s Simari, Chesñevar, García (1994a, 1994b) as an evolution of the work in Simari and Loui (1992), its complete formalisation was completed in García (2000) and finally published in García and Simari (2004). Further developments, that will be described below, can be found in the following related material in García et al. (2007), Tucat, Garcia, and Simari (2009), Martínez, García, and Simari (2012), and García, Chesñevar, Rotstein, and Simari (2013).

Our knowledge representation language will be determined by a set of atoms. Atoms can be preceded by the strong negation symbol ‘∼’. Atoms that are not preceded by strong negation will also be called positive literals and atoms preceded by strong negation will be called negative literals, the term literal, or sometimes objective literal, will refer to either one. A pair of literals involving a positive and a negative literal over the same atom are called complementary or contradictory. For instance, ‘∼guilty’ and ‘guilty’ are two complementary literals. Atoms, while propositional in nature, will be represented in a manner similar to a first-order language. Also, variables will be considered only as place-holders for constants. Thus, an atom containing variables will be a schematic representation of all the possible atoms that can be obtained replacing the variables with the constants in the representation language (Lifschitz, 1996). Our notation will follow standard typographic conventions used in Logic Programming. To distinguish between atoms and variables, as usual, atoms will start with a lowercase letter and variables with an uppercase letter. For instance, ‘∼dangerous(X)’ and ‘dangerous(X)’ are two schematic literals.

A defeasible logic program, abbreviated d.l.p., is a set of facts, strict rules, and defeasible rules defined as follows:

Note that, from a syntactic point of view, strict and defeasible rules differ only in the symbol between the head and the body of the rule. It is interesting to remark here that the representational choice between these two forms of relating the head and the body of a rule is ultimately a matter of context, sometimes a rule could change according to the environment in which it is used; for instance, a rule that locally can be considered strict could become defeasible in a larger environment.

Defeasible rules allow to represent a weak connection between the body (antecedent) and the head (consequence) of the rule. A defeasible rule H≺B expresses that reasons to believe in B provide a (defeasible) reason to believe in H. As an example, consider a scenario where an agent has to decide how to spend the day. Then, the defeasible rule ‘nice≺waves’ can represent that ‘reasons to believe that there are big waves at the beach, is a reason to believe that it should be a nice day for surfing’. The connection between ‘waves’ and ‘nice’ is weak in the sense that there might be other reasons such as ‘normally, if it is raining it is not nice for surfing’, represented as ‘∼nice≺rain’, that will lead to the contrary conclusion. Suppose that today there are big waves and it is raining, then the acceptance of the body of the rule ‘nice≺waves’ does not lead directly to the acceptance of the head.

Nevertheless, strict rules establish a strict connection between body and head; thus, the rule ‘∼working←vacation’ represents the fact that in vacation an agent is not working. Then, as we will show below, due to this strict connection in DeLP if ‘vacation’ is accepted then ‘∼working’ is also accepted.

As discussed in Alferes, Pereira, and Przymusinski (1996), logic programs, deductive databases, and more generally non-monotonic theories, use various forms of default negation, usually denoting ‘not F’ as the default negation of ‘F’, whose major distinctive feature is that not ‘F’ is assumed by default, i.e. it is assumed in the absence of sufficient evidence to the contrary ‘F’. In DeLP default negation can be used in the body of defeasible rules; for instance, the rule ‘alive≺notdead’ represents that if we cannot be sure that something is dead, then there are reasons to believe that it is alive. Thus, DeLP allows for the use of two different forms of negation. For instance, the rule ‘∼guilty≺notguilty’ represents that if we cannot be sure that somebody is guilty, then there are reasons to believe that he is not guilty; and the defeasible rule

Methodologically, it is suggested that the default negation ‘not’ be used only on literals appearing in the body of defeasible rules; these literals, that are known as extended literals, provide another form of defeasibility. The motivation for this recommendation is that strict rules with extended literals in their body would become defeasible (see García & Simari, 2004 for more details).

A defeasible rule with an empty body represents an interesting representational device that can be used as information that could be used when no contrary information exists; this type of defeasible rule was introduced in several approaches to defeasible reasoning and is called a presumption (García & Simari, 2004, Martínez et al., 2012, Nute, 1988).

Note that the symbols ‘−≺’ and ‘←’ denote meta-relations between a literal and a set of literals, and have no interaction with language symbols. As in Logic Programming, strict and defeasible rules are not conditionals nor implications, they are inference rules; consequently, it is not possible to apply contraposition to program rules, strict or defeasible. All defeasible logic programs are ground; nevertheless, following the usual convention in Logic Programming, some examples use ‘schematic rules’ with variables for notational convenience. These schematic rules represent all possible instantiations as ground rules using the constants appearing in the signature of the language of the program (Lifschitz, 1996).

A defeasible logic program is set of facts and rules, however, when required, a d.l.p. is denoted by (Π,Δ), to distinguish the subset Π of facts and strict rules and the subset Δ of defeasible rules. This denotational distinction will be useful for introducing central concepts below. Consider for instance the program (Π2.1,Δ2.1) in the following example.

The program above shows an application example with several facts and rules. The set Π_2.1 has some facts representing that: it is Monday, it is cloudy, it is the dry season, there are big waves at the beach, the grass of our yard is grown, we can hire a gardener, we are on vacation, and three strict rules that represent: on vacation we do not work, if there are not many surfers then there are few surfers and if you are ill then you should not go surfing.

The set Δ_2.1 contains defeasible rules that can be used in the process of building arguments for supporting or attacking different claims. For instance, the first rule in Δ_2.1 represents that having spare time on a nice day, is a good reason to go surfing, and can be used in support of the claim go surfing (surf). Note that there is also a rule that can be used for concluding that today is not a nice day (∼ nice) and another rule that provides reasons for concluding that today I am busy (busy). In the next section, we will show how rules and facts are used in defeasible derivations and then we will show what constitutes an argument that supports a conclusion.

3.Defeasible derivations and arguments

In DeLP a ground literal L will have a defeasible derivation from a program (Π,Δ), if there is a finite sequence of ground literals L1,L2,…,Ln=L, where L_i is a fact in Π, or there exists a rule R_i in (Π,Δ) (strict or defeasible) with head L_i and body B1,B2,…,Bm such that every literal Bj,1⩽j⩽m, of the body is either an element L_k already appearing in the sequence preceding L_i (k<i), or an extended literal, i.e. a literal affected by default negation.

In the program (Π2.1,Δ2.1) shown in Example 2.1, the literal surf has a defeasible derivation: vacation, ∼ working, ∼ busy, spare_time, waves, nice, surf, which contains two facts (vacation and waves), and the use of a strict rule (∼working←vacation) and four defeasible rules. Note that every fact of a DeLP has a defeasible derivation; however, not every head of a rule has a derivation, for instance, neither cold nor ∼ surf have a defeasible derivation. If a literal L has a derivation that uses only uses facts and strict rules from Π and no defeasible rules, in this case we say that L has a strict derivation; thus, ∼ working has a strict derivation from Π_2.1. Note that literals that have a strict derivation must be facts or the head of a strict rules; however, a literal can be the head of a strict rule and might have a defeasible derivation, but not a strict derivation. For instance, few_surfers has no strict derivation from Π_2.1, although it has a defeasible derivation from (Π2.1,Δ2.1) that uses a defeasible rule for the derivation of ∼many_surfers.

Since strong negation is allowed in the head of rules, it is possible to obtain defeasible derivations of contradictory literals from a program, e.g. both literals rain and ∼ rain have a defeasible derivation from (Π2.1,Δ2.1). Observe that the defeasible derivation for rain depends on the use of the defeasible rule rain≺cloudy whereas the defeasible derivation of ∼ rain uses the defeasible rule ∼rain≺dry_season. It is important to note that in DeLP the set Π is used to represent non-defeasible information, consequently it is required that the set be representationally coherent. Therefore, for any program we assume that no pair of contradictory literals can be derived from Π, i.e. no strict derivation for contradictory literals can be obtained from a DeLP-program.

In the presence of defeasible derived contradictory literals, DeLP uses a dialectical process to decide which information prevails, i.e. information such that no acceptable reason can be put forward against it. Reasons will be supported by arguments which are structures based in defeasible derivations. The notion of argument is introduced by the following definition.

Observe that although facts and strict rules are used in the defeasible derivation, the argument structure only mentions the defeasible rules. If there exists an argument A for a literal L then we will also say that A supports L.

We can see that from the program (Π2.1,Δ2.1) there is argument (A0) for the conclusion surf; however, observe that there are arguments for nice and ∼ nice, and arguments for busy and ∼ busy. All the arguments rely on the same facts.

Arguments are related in different forms, and two interesting relations are the subargument relation and counterargument relation. But first, we will make some observations regarding the definition of argument.

As stated in Definition 3.1, a literal L has a supporting argument A from a program (Π,Δ) if A is a minimal set of defeasible rules such that there exist a defeasible derivation for L from Π∪A, and Π∪A is not contradictory. Therefore, it could happen that a literal L has a defeasible derivation from a program P but there is no argument for L from P, as in the following program:

Here, there exists a defeasible derivation for at_home from (Π3.2,Δ3.2), but the set Π3.2∪{at_home≺night} is contradictory, and for that reason there is no argument for at_home.

Let us consider again the program (Π2.1,Δ2.1), and the following subset of defeasible rules S={nice≺waves,∼busy≺∼working} (S⊆Δ2.1). Observe that S∪Π2.1 is not contradictory and allows for the defeasible derivation of nice; nevertheless S is not an argument for nice because it is not minimal. In Example 3.2 we have shown that A2⊂S is an argument for nice.

Next, we will describe the subargument and counterargument relations. In the following section these relations will be used in the introduction of an inference mechanism.

Given a d.l.p. (Π,Δ) and two arguments ⟨A,L⟩ and ⟨B,Q⟩ obtained from it, if B⊆A then we say that ⟨B,Q⟩ is a subargument of ⟨A,L⟩ and that ⟨A,L⟩ is the superargument of ⟨B,Q⟩ (note that trivially every argument is a subargument/superargument of itself). For instance, consider the Example above, ⟨A3,rain⟩ is a subargument of ⟨A1,∼nice⟩, and ⟨A2,nice⟩ is a subargument of ⟨A0,surf⟩.

Two literals L and Q are said to disagree in the context of the program (Π,Δ) if the set Π∪{L,Q} is contradictory, i.e. it is possible to strictly derive a literal and its complementary. For instance, in the program (Π2.1,Δ2.1) the literals working and vacation disagree because from Π2.1∪{working,vacation} it is possible to strictly derive ∼ working. As a particular case, two literals disagree if they are contradictory (e.g. nice and ∼ nice).

In DeLP, an argument ⟨B,Q⟩ is a counterargument for ⟨A,L⟩at literal P, if there exists a subargument ⟨C,P⟩ of ⟨A,L⟩ such that P and Q disagree. The literal P is referred to as the counterargument point and ⟨C,P⟩ as the disagreement subargument. If ⟨B,Q⟩ is a counterargument for ⟨A,L⟩, then we also say that ⟨B,Q⟩ attacks ⟨A,L⟩, and that ⟨B,Q⟩ and ⟨A,L⟩ are in conflict.

Consider the program (Π2.1,Δ2.1). ⟨A1,∼nice⟩ is a counterargument for ⟨A2,nice⟩ and viceversa because in this particular case the conclusion of both arguments disagree. As another example, ⟨A4,∼rain⟩ is a counterargument for ⟨A1,∼nice⟩ at the counterargument point rain and ⟨A3,rain⟩ is the disagreement subargument. Note that in DeLP a counter-argument for an argument A is also a counter-argument for any super-argument of A. For instance, from (Π2.1,Δ2.1) since ⟨A1,∼nice⟩ is a counter-argument for ⟨A2,nice⟩ and ⟨A0,surf⟩ is a super-argument of ⟨A2,nice⟩, then ⟨A1,∼nice⟩ is a counter-argument for ⟨A0,surf⟩.

Given a program P, every literal L that has a strict derivation from P, has a supporting argument with no defeasible rules (i.e. A=∅) that supports L. Also note that in DeLP there is no possible counterargument for a claim having a strict derivation, see García and Simari (2004) for the proof. It was shown in an example above, involving the program (Π3.2,Δ3.2), that there is a strict derivation for ∼ at_home; hence, for that reason there is no argument for at_home and therefore no counter-argument can exist. Observe also that from (Π2.1,Δ2.1) there is a strict derivation for ∼ working, however, although there is a derivation for working, no argument for working can exist, and hence, no counter-argument for ∼working.

4.Warrants and answers for queries

A query is issued to a defeasible logic program (Π,Δ) in the form of a ground literal Q, and this query will succeed when Q can be warranted from (Π,Δ). The intuitive meaning of a literal being warranted is that it is supported by an argument that has no counterargument still standing against it. As it is discussed below, there are four possible answers for a query Q posed to a program P: yes, if Q is warranted from P; no, if the complement of Q is warranted from P; undecided, if neither Q nor its complement is warranted from P; and unknown, if Q is not in the signature of the program P. For instance, as we will show later in this section in detail, from the program (Π2.1,Δ2.1) the answer for ‘surf’ is yes, the answer for ‘busy’ is no, the answer for ‘many_surfers’ is undecided, and the answer for ‘beach_closed’ is unknown.

Informally, a literal Q will be warranted if there exists at least an argument A supporting Q that prevails after going through a dialectical process considering all its counterarguments. To asses this, the counterarguments must be compared to the supporting argument, and each counterargument that is in some predetermined sense found better, becomes a potential defeater which in turn is analysed in a similar way. In the rest of this section we will be describing all the elements involved in the warranting process.

Let us consider again the program (Π2.1,Δ2.1). The argument ⟨A1,∼nice⟩ is a counterargument for ⟨A2,nice⟩ and viceversa. As we will show, if a preference between A1 and A2 can be established, then one of these arguments will defeat the other and its conclusion will prevail. In DeLP a defeater relation is defined in terms of counter-argument and an argument comparison criterion as follows. Recall that if an argument C counter-arguments A, then there exists a disagreement sub-argument B of A.

Given a preference criterion, an argument D is a defeater for A, if one of the following conditions holds:

Observe that in the case that B is preferred to D, although D remains a counterargument for A, D is not a defeater for A. As an argument trivially is a subargument of itself, it is possible that the disagreement subargument be A itself, thus, in this case D will be compared directly with A.

In the context of program (Π2.1,Δ2.1), ⟨A4,∼rain⟩ is a counterargument for ⟨A1,∼nice⟩ at the counterargument point rain and ⟨A3,rain⟩ is the disagreement subargument; therefore, A4 is compared with A3 to determine if it is a defeater.

The argument comparison criterion is modular in DeLP; hence, it is possible to use any preference criterion established over the set of arguments. This allows the user to select the most appropriate criterion for the application domain that is being represented. In García (2000), García and Simari (2004), and Ferretti, Errecalde, García, and Simari (2008), different argument comparison criteria were defined. In the examples of this paper we will use a comparison criterion that was introduced in García and Simari (2004). This argument preference relation uses a partial order defined over defeasible rules that is denoted by ‘<_R’. The intuitive meaning of ‘R₁<_R R₂’ is that: the rule R₂ is preferred over R₁ in the application domain described by the program.

In this argument comparison criterion, referred to as rule's priorities, an argument A1 is preferred to A2 if the following two conditions hold:

If an argument ⟨A1,L1⟩ is defeated by ⟨A2,L2⟩, then ⟨A2,L2⟩ represents a reason for rejecting ⟨A1,L1⟩; nevertheless, as ⟨A2,L2⟩ also is an argument, a defeater ⟨A3,L3⟩ for it might also exist, defeating ⟨A2,L2⟩ and reinstating ⟨A1,L1⟩. This analysis is repeated and the argument ⟨A3,L3⟩ could in turn become defeated, reinstating ⟨A2,L2⟩, and so on. In this manner, a sequence of arguments (called argumentation line) is built; in it, each argument is a defeater of its predecessor in the sequence.

More formally, given ⟨A1,L1⟩, an argumentation line for ⟨A1,L1⟩ is a sequence of arguments, denoted by Λ=[⟨A1,L1⟩,⟨A2,L2⟩,⟨A3,L3⟩,…], where each element of the sequence ⟨Ai,Li⟩, i>1, is a defeater of its predecessor ⟨Ai−1,Li−1⟩. The first element, ⟨A1,L1⟩, becomes a supporting argument for L₁, ⟨A2,L2⟩ an interfering argument, ⟨A3,L3⟩ a supporting argument, ⟨A4,L4⟩ an interfering one, continuing in that manner. Thus, an argumentation line can be split into two disjoint sets: ΛS={⟨A1,L1⟩,⟨A3,L3⟩,⟨A5,L5⟩,…} of supporting arguments, and ΛI={⟨A2,L2⟩,⟨A4,L4⟩,…} of interfering arguments. For instance, from the program (Π2.1,Δ2.1) the following argumentation line can be obtained [⟨A0,surf⟩, ⟨A1,∼nice⟩, ⟨A4,∼rain⟩], where A1 is an interfering argument for surf, and A4 is a supporting argument for surf.

There are undesirable situations, analysed in the literature, that can occur leading to an infinite argumentation line; for instance, if an argument is reintroduced in the sequence, the process could repeat itself indefinitely. Circular argumentation and other forms of fallacious argumentation have been studied in detail (see García & Simari, 2004, Simari et al., 1994b).

In DeLP, argumentation lines are required to be acceptable, that is, they have to be finite, an argument cannot appear twice in it, and the set of supporting (resp. interfering) arguments in the line have to be concordant. Given a program (Π,Δ), a set of arguments {⟨Ai,Li⟩}i=1n is concordant if it is not possible to have a defeasible derivation for a pair of contradictory literals from the set Π∪⋃i=1nAi. For instance, the set {⟨A0,surf⟩, ⟨A4,∼rain⟩} is concordant, whereas the set {⟨A0,surf⟩, ⟨A1,∼nice⟩} is not because from Π∪A0∪A1 there are defeasible derivations for nice and ∼ nice.

The existence of blocking defeaters introduces another situation that is addressed by the last requirement; that is, after introducing a blocking defeater in a line, the next defeater is required to be a proper one to reinstate the blocked argument. Formally, an argumentation line Λ=[⟨A1,L1⟩,…⟨An,Ln⟩] is acceptable if and only if:

For instance, from the program (Π2.1,Δ2.1) two acceptable argumentation lines for ⟨A0,surf⟩ can be obtained:

This example shows how, given a program, there can be more than one argumentation line starting with the same argument ⟨A,L⟩. Therefore, analysing a single acceptable argumentation line for ⟨A,L⟩ will not be enough to determine whether ⟨A,L⟩ is an undefeated argument. In the general situation, there might be several defeaters ⟨B1,Q1⟩,⟨B2,Q2⟩,…,⟨Bk,Qk⟩ for ⟨A1,L1⟩, and for each defeater ⟨Bi,Qi⟩ there could be in turn several defeaters; thus, a tree structure is defined which is called a dialectical tree. In this tree, the root is labelled with ⟨A,L⟩ and every node (except the root) represents a defeater (proper or blocking) of its parent. Each branch in the tree, i.e. each path from a leaf to the root, corresponds to a different acceptable argumentation line.

Let ⟨A1,L1⟩ be an argument obtained from a DeLP-program P, a dialectical tree for ⟨A1,L1⟩ from P is denoted by T⟨A1,L1⟩ and is constructed as follows:

Dialectical trees will be depicted as a tree where labelled triangles represent arguments and edges denote the defeat relation. An argument ⟨A,L⟩ will be depicted as a triangle, where its upper vertex is labelled with L, and A is showed inside the triangle. Figure 1 shows the dialectical tree for argument ⟨A0,surf⟩ obtained from program (Π2.1,Δ2.1). A small triangle inside a bigger one represents a subargument, and usually is presented in that way to show a disagreement subargument with the counterargument point where an edge ends. We will use solid edge with the arrowhead pointing from the proper defeater to the defeated argument, and edges with double pointed arrows to represent blocking defeaters.

Figure 1.

Dialectical tree T⟨A0,surf⟩.

A dialectical tree provides a useful structure for considering all possible acceptable argumentation lines that can be generated for deciding whether an argument is defeated. We call this tree dialectical because it represents an exhaustive dialectical analysis for the argument in its root.

Given a literal L and an argument ⟨A,L⟩, to decide whether the literal L is warranted, every node in the dialectical tree T⟨A,L⟩ is recursively marked as “D” (defeated) or “U” (undefeated), obtaining a marked dialectical tree T⟨A,L⟩∗. Nodes are marked by a bottom-up procedure that starts marking all leaves in T⟨A,L⟩∗ as “U”s. Then, for each inner node ⟨B,Q⟩ of T⟨A,L⟩∗, either:

Marked dialectical trees will be depicted as a tree where the nodes are triangles decorated with the result of the marking procedure and the directed edges denote the defeat relation. Figure 2 shows the marked dialectical tree for argument ⟨A0,surf⟩ of program (Π2.1,Δ2.1).

Figure 2.

Marked dialectical tree T⟨A,L⟩∗.

Given an argument ⟨A,L⟩ obtained from a program P, we will write Mark(T⟨A,L⟩∗)=U to denote that the root of T⟨A,L⟩∗ is marked as “U”; otherwise we will write Mark(T⟨A,L⟩∗)=D (if the root of T⟨A,L⟩∗ is marked as “D”). Thus, we can define warrant in terms of the marking procedure Mark:

A ground literal L is considered to be warranted if an argument A for L exists, and all the defeaters for ⟨A,L⟩ are defeated. Therefore, this marking procedure provides an effective way of determining if a DeLP-query L is warranted. It is important to note that given a DeLP-query L, there can be several arguments that support L; therefore, L will be warranted if there exists at least one argument A for L such that the root of a dialectical tree for ⟨A,L⟩ is marked as “U”.

It has been observed in Chesñevar and Simari (2007) that the order in which the defeaters are considered is irrelevant to the final result of the marking process, only the argumentation lines are important for the outcome. The different tree configurations obtained from the set of argumentation lines (called bundle set) lead to the same marking of the root.

In García (2000) and García and Simari (2004) it was proved that in DeLP any claim C that has a strict derivation is warranted. This is so because any literal C that has a strict derivation from a program (Π,Δ) has no posible counterargument voiding the possibility that a defeater could exist. The reason for this is that no argument that disagrees with C could be build because the definition of argument requires it to be non-contradictory with Π.

The interpreter of DeLP takes a program P, and a DeLP-query L as input. Then returns one of the following four possible answers: yes, if L is warranted from P; no, if the complement of L is warranted from P; undecided, if neither L nor its complement are warranted from P; or unknown, if L is not in the language of the program P.

As an illustrating example, from the program (Π2.1,Δ2.1) introduced in Example 2.1, the following answers can be obtained:

Observe that in the table above the literal beach_closed has the answer unknown, this is so because the literal beach_closed is not present in the signature of (Π2.1,Δ2.1). The answer for both ∼ many_surfers and many_surfers is undecided, because as it was shown in Example 4.1 the argument ⟨A10,many_surfers⟩ is a blocking defeater for ⟨A11,∼many_surfers⟩ and vice versa. Note that the literal ∼ working is the head of a strict rule and also has a strict derivation, therefore, the answer is yes. Finally, observe that few_surfers is the head of a strict rule but has no strict derivation, because the body of that particular strict rule can not be strictly derived from (Π2.1,Δ2.1). In this case, few_surfers has a defeasible derivation (defeasible rules are used in its derivation), and there is also an argument supporting it, but since there is a blocking defeater for that argument, no warrant for few_surfers is possible and the answer is undecided.

5.DeLP reasoning servers and contextual queries

In MASs, reasoning can be seen as a service that can be offered as part of a knowledge-based infrastructure providing a mechanism to exploit it. In this section we describe DeLP Servers, that are the support of argumentative reasoning services conceived for a MAS setting. In such an environment, DeLP-Servers, introduced in García et al. (2007), provide client agents that can be distributed in remote hosts with the ability to consult different reasoning services implemented as DeLP-Servers that can be distributed themselves. Figure 3 schematically depicts a situation with three servers and five client agents distributed in four hosts.

Figure 3.

Agents can query different services with different knowledge bases.

Common (or public) knowledge can be stored in a server and represented as a DeLP-program; then, client agents may send queries to a DeLP-server and receive the corresponding answer. To respond to a query, a DeLP-server uses the knowledge stored in it; but, the server offers the possibility of integrating the knowledge stored in it with ‘private’ knowledge the client making the query has the possibility to send as part of the query.

For example, consider a DeLP-server developed for a real-state application domain. A program can be stored in that server with some facts that represent the available properties for renting, and some defeasible rules that represent common knowledge modelling how to select a suited property. Then, client agents can consult for a property and submit, together with the query, some private information that represents its current situation or requirements (e.g. has children, works at home, has no car, cannot afford a rent of $ 3000 or more). If that is the case, this private knowledge is added temporarily to the knowledge stored in the server giving a particular context for the query. This context is private knowledge that the server will use for answering the query and will not affect other future queries. Thus, a client agent cannot make permanent changes to the public DeLP-program stored in a server. The temporal scope of the contextual information sent in a query is limited and it will disappear when the process performed by the DeLP-server to answer that query finishes. Continuing with our example, one client, Client₁, can consult if some property p is suited for her, providing the context that she is single and has a car. Other client, Client₂, can consult if p is suited for him, providing a different context: he has two children and work downtown. Since queries do not affect permanent changes in the program stored in a server, both contextual queries can be received and processed simultaneously, and one will not affect the answer of the other.

Below the concept of contextual query will be formalised. We will show that a contextual query provides to the server a particular DeLP-query, some contextual information in the form of DeLP-program and the information of how to integrate this contextual information with the public program stored in the server. To answer contextual queries, a DeLP-server uses both the common knowledge stored in it, and the context that clients can send attached to a query. The conceptual structure is described in Figure 4.

Figure 4.

Agents can query a DeLP-server creating a context.

Several agents can consult the same DeLP-server, and the same agent can consult several DeLP-Servers, as shown in Figure 3. For instance, in a particular medical application, dedicated DeLP-Servers can maintain different programs, supporting particular shared knowledge of specific specialties of the medical profession. Hence, an agent can pose the same contextual query to different servers, and obtain a different answer from each of the servers. Our approach does not impose any restriction over the type, architecture, or implementation language of the client agents. Next, we will formalise the above mentioned concepts introducing some examples.

Thus, a DeLP-Server ≪I,O,P≫ provides a DeLP-interpreter, the possibility of representing public knowledge in the form of a DeLP-program, and a set of operators that will handle the integration of the contextual information with the program stored P.

Consider, for example, a DeLP-server for the real state application mentioned above. This server will have some public knowledge represented by the program PRS=(ΠRS,ΔRS) shown below where we will use the following shorthand notation: av (available), br (bedroom), conv_br; (convenient number of bedrooms). The set Π_RS contains facts representing information about the name, number of bedrooms, location and price of the properties available for renting. For instance, av(p1,br(1),downtown,2000) represents that the property p1 is available, it has 1 bedroom, is located downtown, and its price is 2000.

These defeasible rules should interpreted as follows. A convenient number of bedrooms in any available property provide reasons for considering it as a suited property; observe that the reasons for and against a convenient number of bedrooms depends on the private information a client might send as a context. Properties are not considered suited if they are expensive; to determine if a property is expensive for a client, the amount the client can afford to expend has to be provided in the contextual query.

In the previous section we explained how a DeLP-interpreter takes a DeLP-program, a DeLP-query (a literal), and returns one of the four DeLP possible answers: yes, no, undecided, and unknown. To put this more clearly, let D be the domain of all possible DeLP-programs, and L is the domain of DeLP-queries, then a DeLP-interpreter can be seen as a function

A contextual query to a DeLP-Server involves two elements: a particular DeLP-query Q to be answered, and contextual information Co to be used together with the program stored in the DeLP-Server to answer Q. This contextual information consists of both private knowledge in the form of a DeLP-program to be consider by the interpreter and appropriate operators that state how to integrate the private information with the public program stored at the server. Formally:

In García et al. (2007) and Tucat et al. (2009) concrete examples of program operators were given. These operators are modular in the sense that each particular server can have a different set of operators that can be designed specifically for the application domain in use. Recall that in DeLP the set Π has to be non-contradictory; therefore, a DeLP-program operator must return a program where Π is non-contradictory. Below, we include, as an example, three simple and basic operators denoted by ⊕, ⊗, and ⊖, that will be used throughout the examples below.

To simplify the presentation, these three operator will be defined for a restricted DeLP-program (Π,Δ) where Π can have facts but no strict rules. We introduce auxiliary notation to use in their definition. Let x be a fact, we denote with x‾ the complement of x with respect to strong negation; that is a‾=∼a and ∼a‾=a. If X is a set of facts, the complement of X is defined as X‾={x‾∣x∈X}. Previously, we have mentioned that a DeLP-program operator can be seen as a function o:D×D↦D; with that in mind we define the operators ⊕, ⊗, and ⊖ as follows:

The first two operators, ⊕ and ⊗, integrate the defeasible part of the program representing the private knowledge and the defeasible part of the common knowledge stored in the server. The last one, ⊖, will eliminate the defeasible rules stored in the server that are in common with the defeasible part of the private knowledge present in the contextual query.

The first operator, denoted by ⊕, will integrate the private knowledge of an agent received as a DeLP-program (Πa,Δa) with the program stored in a server that contains (Π,Δ), giving priority to the information in Π_a. For instance, if the public knowledge in the server is (Π,Δ)=({a,b},Δ) and the private information received in a contextual query is (Πa,Δa)=({∼a,c},Δa), then

In contrast, the operator denoted by ⊗ gives priority to the facts that are part of the DeLP-program (Π,Δ) stored in the server. For instance, if the public knowledge in the server is as before (Π,Δ)=({a,b},Δ) and the received information is (Πa,Δa)=({∼a,c},Δa), then

Finally, the operator denoted by ⊖ was developed with the purpose of not considering for a particular query part of the public information maintained in the server. For instance, if the public knowledge in the server is (Π,Δ)=({a,b,p},Δ) and the received information is (Πa,Δa)=({a,b,∼p},Δa), then

To provide an answer for a particular contextual query (Co,Q), a DeLP-Server ≪I,O,P≫ has to consider first how the context Co is integrated with the stored program P. Since the context can be a sequence of pairs [({P1},o1),…,({Pn},on)], then we define:

It is important to note that a context is a sequence and it will be processed by the DeLP-server in the order it appears in that sequence. Hence, different answers could be obtained depending on the order of the pairs in the context. Consider a DeLP-server ≪I,{⊕,⊗,⊖},(ΠRS,ΔRS)≫ for the real state application already introduced. We include some contextual queries that clients could send to the server and show the answers that will be returned:

6.Explanations for answers

In this section we will discuss a direct application of DeLP-Servers to address an important topic in computational reasoning systems. The research included here has been reported in García, Rotstein, Chesñevar, and Simari (2009) and García et al. (2013), where more extensive presentations have been given.

Giving explanations regarding an answer coming from a computational system after a query is a question that has been addressed in several areas of Artificial Intelligence; quite naturally, the expert systems community Lacave and Diez (2004), Ye and Johnson (1995), and Guida and Zanella(1997) have explored possible solutions. Researchers in the area argumentation also have been concerned with providing their views (Belanger, 2007; Moulin, Irandoust, Bélanger, & Desbordes,2002; Walton, 2004); for instance, Walton (2004) has studied arguments and explanations from a philosophical point of view. He considers that the purpose of an argument is to get the hearer to come to accept something that is doubtful or unsettled, whereas the purpose of an explanation is to get the hearer to understand something that he already accepts as a fact.

In our approach, explanations aim to transfer the understanding of how the warrant status of a particular argument was obtained from a given argumentation framework. Thus, in our framework, an explanation (called δ-Explanation) will consist of a structure that reflects the analysis carried out in order to obtain such status, and it will contain those arguments and counterarguments that are considered in analysis leading to its warrant status.

In Lacave and Diez (2004), a review about explanations in heuristic expert systems is given and they offer the following definition:

Using the language in the fragment above to describe our approach, we will explain the warrant status of a claim by exposing the whole set of dialectical trees that was generated to study the warrant status of arguments related to the claim; this information is understandable from the receiver's point-of-view because all the arguments considered, their statuses (i.e. defeated/undefeated), and their interrelations are explicitly shown, and this information will be satisfactory for the receiver because it contains all the elements at stake in the dialectical analysis that supports the answer.

From the program (Π6.1,Δ6.1) the answer corresponding to the query go is no, and the answer for the query ∼ go is yes. As discussed previously, to obtain an answer for a DeLP-query Q, the interpreter goes through a dialectical process for warranting Q involving the construction and evaluation of the arguments that either support or interfere with the query under analysis. The generated arguments are affected by the defeat relation and they are organised in dialectical trees. Observe that given a DeLP-query Q, there might exist different arguments that support Q, and each argument will generate a separate dialectical tree. Therefore, as we will show below, the returned answer for Q will be only ‘the tip of the iceberg’ of a set of several dialectical trees that have been explored to support that answer; thus, to understand why a DeLP-query obtains a particular answer, it is essential to consider which arguments have been generated and what are the relations between them.

Since an explanation has to further the understanding of the warrant status of a DeLP-query Q, our approach to giving an explanation will consist of a structure that includes those marked dialectical trees that are considered for establishing such status. This will include both marked dialectical trees for arguments that support Q, and also marked dialectical trees for arguments that support Q‾ (the complement of Q with respect to strong negation). For instance, returning to our Example 6.1, it is possible to build two arguments for go and two arguments that support the complement ∼ go; therefore, the explanation should include these four trees. The following definition characterises two distinguished sets of marked dialectical trees that will be used to produce an explanation. Recall that we write Mark(T⟨A,L⟩∗)=U to denote that the root of T⟨A,L⟩∗ is marked as “U” and we write Mark(T⟨A,L⟩∗)=D if the root of T⟨A,L⟩∗ is marked as “D”.

As stated above, the purpose of an explanation is to transfer the understanding of how the warrant status of a particular argument is obtained from a given argumentation framework. Consequently, an explanation will consist of a structure that reflects the analysis carried out in order to obtain such status, and it will contain those arguments and counterarguments that are considered in this analysis, showing explicitly how they relate to one another. That is, a δ-Explanation EP(Q) for a claim Q from a DeLP-program P is a triplet (TU∗(Q),TU∗(Q‾),TD∗(Q)), where the first component is a (possibly empty) set of those marked dialectical trees from P that provide a warrant for Q. The second component of EP(Q)is a (possible empty) set of marked dialectical trees that provide a warrant for Q‾. Finally, the third component (TD∗(Q)) is a (possibly empty) set that contains those marked dialectical trees for Q or for Q‾ that provide no warrant, i.e. their roots are marked D (defeated).

Consider the program P6.1=(Π6.1,Δ6.1) of Example 6.1. The δ-Explanation for the query ‘∼ go’ is:

Figure 5.

Dialectical trees in the δ-Explanation for ‘∼ go’.