You are viewing a javascript disabled version of the site. Please enable Javascript for this site to function properly.
Go to headerGo to navigationGo to searchGo to contentsGo to footer
In content section. Select this link to jump to navigation

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

Abstract

Argumentation represents a way of reasoning over a knowledge base containing possibly incomplete and/or inconsistent information, to obtain useful conclusions. As a reasoning mechanism, the way an argumentation reasoning engine reaches these conclusions resembles the cognitive process that humans follow to analyse their beliefs; thus, unlike other computationally reasoning systems, argumentation offers an intellectually friendly alternative to other defeasible reasoning systems. Logic Programming is a computational paradigm that has produced computationally attractive systems with remarkable success in many applications. Merging ideas from both areas, Defeasible Logic Programming offers 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. This combination of ideas brings about a computationally effective system together with a human-like reasoning model facilitating its use in applications.

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,1 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:

  • Facts are ground (objective) literals, e.g. guilty, price(100), alive. In DeLP facts are used for representing information that is considered to hold in the application domain. Hence, as it will be explained below, a ‘valid’ d.l.p. cannot contain two complementary facts.

  • Strict Rules represent a relation between a ground literal L0, or head of the rule, and a set of ground literals {Li}i>0, or body of the rule, and are denoted by L0L1,,Ln; strict rules correspond syntactically to basic rules in Logic Programming (Lifschitz, 1996). The use of the adjective ‘strict’ emphasises that the relation between the head and the body of the rule is such that if the body is accepted then the head must also be accepted. The examples of strict rules shown below can be understood as expressing that: if somebody is guilty then it is not innocent, cats are mammals, and if there are not many surfers then there are few surfers:

    innocentguiltymammalcatfew_surfersmany_surfers

  • Defeasible Rules are used to represent a weaker connection between pieces of information, they are denoted by L0L1,,Ln, and like strict rules, the head of the rule L0 is a ground literal and its body {Li}i>0 is a set of ground literals. Unlike strict rules, acceptance of the body of a defeasible rule does not always lead to the acceptance of the head. In defeasible rules, literals on the body can be preceded with the default negation symbol ‘not’ (see discussion below). Examples of defeasible rules follows, the first one represents that usually, mosquitoes are not dangerous, and the second says that reasons to believe mosquitoes are carrying dengue, justify the belief they are dangerous:

    dangerousmosquitodangerousmosquito,dengue

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 HB 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 ‘nicewaves’ 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 ‘nicerain’, 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 ‘nicewaves’ does not lead directly to the acceptance of the head.

Nevertheless, strict rules establish a strict connection between body and head; thus, the rule ‘workingvacation’ 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 notF’ 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 ‘alivenotdead’ 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 ‘guiltynotguilty’ 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

cross_railway_tracksnottrain_is_coming
can be understood as if we cannot be sure the train is not coming then there are (defeasible) reasons to believe we should not be crossing the railway tracks.

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.

Example 2.1

DeLP-program (Π2.1,Δ2.1)

Π2.1=mondaymondaycloudydry_seasonwavesgrass_grownhire_gardenervacationworkingvacationfew_surfersmany_surferssurfillΔ2.1=surfnice,spare_timenicewavesnicerainraincloudyraindry_seasonspare_timebusybusyworkingcoldwinterworkingmondaybusyyard_workyard_workgrass_grownyard_workhire_gardenermany_surferswavesmany_surfersmonday

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 Li is a fact in Π, or there exists a rule Ri in (Π,Δ) (strict or defeasible) with head Li and body B1,B2,,Bm such that every literal Bj,1jm, of the body is either an element Lk already appearing in the sequence preceding Li (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 (workingvacation) 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 raincloudy whereas the defeasible derivation of ∼ rain uses the defeasible rule raindry_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.

Definition 3.1

Let (Π,Δ) be a defeasible logic program and L a ground literal. We say that A is an argument for the conclusion L from (Π,Δ), denoted by A,L, if A is a minimal set of defeasible rules (AΔ), such that: (1) there exists a defeasible derivation for L from ΠA, (2) no pair of contradictory literals can be defeasibly derived from ΠA, and (3). If A contains some rule with an extended literal ‘not F’, then the literal F can not be in the defeasible derivation of L from ΠA.

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.

Example 3.2

From program (Π2.1,Δ2.1) introduced in Example 2.1 we can obtain several arguments:

A0,surf=surfnice,spare_timenicewavesspare_timebusybusyworking,surfA1,nice={(nicerain);(raincloudy)},niceA2,nice={nicewaves},niceA3,rain={raincloudy},rainA4,rain={raindry_season},rainA5,busy={(busyyard_work);(yard_workgrass_grown)},busyA6,yard_work={yard_workhire_gardener},yard_workA7,yard_work={yard_workgrass_grown},yard_workA8,spare_time={(spare_timebusy);(busyworking)},spare_timeA9,busy={busyworking},busyA10,many_surfers={many_surferswaves},many_surfersA11,many_surfers={many_surfersmonday},many_surfers

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:

Π3.2=nightat_marketat_homeat_marketΔ3.2={at_homenight}

Here, there exists a defeasible derivation for at_home from (Π3.2,Δ3.2), but the set Π3.2{at_homenight} 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={nicewaves,busyworking} (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 A2S 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 BA 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,Lat 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:

  • (a) D is a counter-argument for A with disagreement sub-argument B, and D is preferred to B, in this case D is a called a proper defeater for A, or

  • (b) D is a counter-argument for A with disagreement sub-argument B, and D is equally preferred to, or D is incomparable with B, in this case D is called a blocking defeater for A, or

  • (c) D is argument for the conclusion F and ‘not F’ is in some rule of A, in this case D is called an attack to an assumption of A.

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 ‘R1<R R2’ is that: the rule R2 is preferred over R1 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:

  • (1) there exists at least a rule raA1 and a rule rbA2 such that rb<R ra,

  • (2) and there is no rule rbA2, and raA1 such that ra′<R rb′.

Example 4.1

Consider the program (Π2.1,Δ2.1) introducing the following priorities over its rules:

(raincloudy)<R(raindry_season)(yard_workgrass_grown)<R(yard_workhire_gardener)

Lets discuss the relations between some of the arguments built from that program:

A0,surf=surfnice,spare_timenicewavesspare_timebusybusyworking,surfA1,nice={(nicerain);(raincloudy)},niceA3,rain={raincloudy},rain,andA4,rain={raindry_season},rain,A5,busy={(busyyard_work);(yard_workgrass_grown)},busy

Then, A4,rain is preferred over A3,rain. Since A4,rain is a counterargument for A1,nice with A3,rain as the disagreement subargument, then A4,rain is a proper defeater for A1,nice. Note that A4,rain is a also a proper defeater for A3,rain. Taking into account that A1,nice is a counterargument for A2,nice and viceversa, and A1,nice and A2,nice are not comparable in this criterion, it results that A1,nice is a blocking defeater for A2,nice and viceversa.

Observe that the argument A0,surf has two blocking defeaters: A1,nice at the counterargument point nice and A2,busy at the counterargument point ∼ busy. Since A6,yard_work is preferred to A7,yard_work then A6,yard_work is a proper defeater for both A7,yard_work and A5,busy. Finally, A10,many_surfers is a blocking defeater for A11,many_surfers and viceversa.

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 Ai1,Li1. The first element, A1,L1, becomes a supporting argument for L1, 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 ΠA0A1 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:

  • (1) Λ is a finite sequence.

  • (2) The set ΛS of supporting arguments (resp. ΛI) is concordant.

  • (3) No argument Ak,Lk in Λ is a disagreement subargument of an argument Ai,Li appearing earlier in Λ, i<k.

  • (4) For all i, such that Ai,Li is a blocking defeater for Ai1,Li1, if Ai+1,Li+1 exists, then Ai+1,Li+1 is a proper defeater for Ai,Li.

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

Λ1==[A0,surf,A1,nice,A4,rain],Λ2=[A0,surf,A5,busy,A6,yard_work].

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 TA1,L1 and is constructed as follows:

  • (1) The root of the tree is labelled with A1,L1.

  • (2) Let N be a node labelled An,Ln, and [A1,L1,,An,Ln] be the sequence of labels of the path from the root to N. Let {B1,Q1,B2,Q2,,Bk,Qk} be the set of all the defeaters for An,Ln from P. For each defeater Bi,Qi (1ik), such that the argumentation line Λ=[A1,L1,,An,Ln,Bi,Qi] is acceptable, the node N has a child Ni labelled Bi,Qi. If there is no defeater for An,Ln or there is no Bi,Qi such that Λ′ is acceptable, then N is a leaf.

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 TA0,surf.

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 TA,L is recursively marked as “D” (defeated) or “U” (undefeated), obtaining a marked dialectical tree TA,L. Nodes are marked by a bottom-up procedure that starts marking all leaves in TA,L as “U”s. Then, for each inner node B,Q of TA,L, either:

  • (a) B,Q will be marked as “U” iff every child of B,Q is marked as “D”, or

  • (b) B,Q will be marked as “D” iff it has at least a child marked as “U”.

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 TA,L.

Marked dialectical tree T⟨A,L⟩∗.

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

Definition 4.2

Let P be a DeLP-program and L a DeLP-query. We say that TA,L warrants L and that L is warranted from P if Mark(TA,L)=U.

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:

aac-5-869767-i001.jpg

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.

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, Client1, can consult if some property p is suited for her, providing the context that she is single and has a car. Other client, Client2, 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.

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.

Definition 5.1

A DeLP-Server is a triple I,O,P where I is a DeLP-interpreter, O is a set of DeLP-program operators and P is a DeLP-program.

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.

ΠRS=av(p1,br(1),downtown,2000)av(p2,br(2),suburbs,4000)av(p3,br(3),suburbs,5000)av(p4,br(3),downtown,15000)av(p5,br(2),suburbs,10000)av(p6,br(1),downtown,7000)ΔRS=suited(Property)av(Property,br(B),_,_),conv_br(B)suited(Property)expensive(Property)expensive(Property)av(Property,_,_,Price),afford(A),Price>Aconv_br(X)has_children,X2conv_br(X)couple,X1conv_br(X)single,X1has_childrengrown_childrenconv_br(2)grown_childrenconv_br(1)work_at_home

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

I:D×L{YES,NO,UNDECIDED,UNKNOWN}
Then DeLP-program operator oO, is a binary operator that will take two DeLP-programs P1 and P2, and it will return a new DeLP-program; this DeLP-program is the result of integrating P1 and P2 according to the definition of the operator o. Therefore, formally a DeLP-program operator can be seen as a function
o:D×DD

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:

Definition 5.2

A contextual query for a DeLP-Server I,O,P is a pair (Co,Q) where Q is a DeLP-query, and the context Co is a sequence [({P1},o1),,({Pn},on)], where Pi is a DeLP-program and oiO,1in.

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={xxX}. Previously, we have mentioned that a DeLP-program operator can be seen as a function o:D×DD; with that in mind we define the operators ⊕, ⊗, and ⊖ as follows:

(Π,Δ)(Πa,Δa)=((ΠΠa)Πa,ΔΔa)(Π,Δ)(Πa,Δa)=(Π(ΠaΠ),ΔΔa)(Π,Δ)(Πa,Δa)=(ΠΠa,ΔΔa)

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

({a,b},Δ)({a,c},Δa)=(({a,b}{a,c}){a,c},ΔΔa)=(({a,b}{a,c}){a,c},ΔΔa)=({b,a,c},ΔΔa)
Note that a contradiction could arise if the private information would have been added directly because Π would have contained a and ∼ a; by using this operator, since the received information has priority, the fact ∼ a will remain whereas a will be temporarily removed, and therefore ignored for answering the query.

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

({a,b},Δ)({a,c},Δa)=({a,b}({a,c}{a,b}),ΔΔa)=({a,b}({a,c}{a,b}),ΔΔa)=({a,b,c}ΔΔa)
That is, since the stored information has priority, the fact ∼ a will remain whereas a will not be considered for answering the query.

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

({a,b,p},Δ)({a,b,p},Δa)=({a,b,p}{a,b,p},ΔΔa)=({p},ΔΔa)

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:

PCo,as(onPnon1Pn1o2P2o1P1)(P),
where oiPj(Pk) is a simplification of oi(Pj,Pk). Recall that DeLP-interpreter can be seen as a function I:(D×L){YES,NO,UNDECIDED,UNKNOWN}.

Definition 5.3

Let I,O,P be a DeLP-server and (Co, Q) a contextual query. Then, an answer for (Co, Q) is I((PCo),Q).

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:

([({single,afford(3000)},)],suited(p1))answer: YES([({single,afford(3000)},)],suited(p2))answer: NO([({single,afford(4000)},)],suited(p2))answer: YES([({grown_children,afford(4000)},)],suited(p2))answer: NO([({grown_children,afford(9000)},)],suited(p3))answer: YES([({grown_children,afford(4000)},)],suited(p3))answer: NO([({grown_children,afford(4000)},),({conv_br(2)grown_children},)],suited(p2))answer: YES

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:

 … explaining consists in exposing something in such a way that it is understandable for the receiver of the explanation – so that he/she improves his/her knowledge about the object of the explanation – and satisfactory in that it meets the receiver's expectations.

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.

Example 6.1

Consider for instance the following scenario (García et al., 2013). Bob is an opera fan and there is an opera show tonight. Besides, today is Bob's birthday and he usually gets together with friends. Bob usually goes to the opera house with friends. However, today Bob's best friend is coming with her baby because of Bob's birthday, and is not a good idea to go to the opera with a baby. The DeLP-program (Π6.1,Δ6.1) represents the scenario just described. In this program, go, show_tonight, birthday, baby and friends stand for ‘go to the opera show’, ‘there is an opera show tonight’, ‘today is Bob's birthday’, ‘a friend is coming with her baby’, and ‘get together with friends’, respectively.

Π6.1={show_tonight,birthday,baby}Δ6.1=goshowTonightgoshowTonight,friendsfriendsbirthdaygoshowTonight,friends,babygofriends

This program contains three facts and five defeasible rules that represent tentative information. The first defeasible rule states that if there is an opera show tonight then there is a good reason to go to the opera house. The second defeasible rule represents that in his birthday Bob usually gets together with friends. The third one states that if friends are coming, Bob would probably stay at home. However, the fourth rule establishes that being with friends and the fact that there is an opera show that night will give a good reason to go to the opera. The fifth rule states that this situation changes if a friend is coming with a baby.

From program (Π6.1,Δ6.1) the following arguments can be obtained:

O1,go={goshowTonight},goO2,go={(gofriends),(friendsbirthday)},goO3,go={(goshowTonight,friends),(friendsbirthday)},goO4,go={(goshowTonight,friends,baby),(friendsbirthday)},go

Let's assume the following priorities over rules:

(gofriends)<R(goshowTonight,friends)(goshowTonight,friends)<R(goshowTonight,friends,baby)

From this program and the associated priorities, the argument O2,go represents a blocking defeater for O1,go and viceversa. The argument O3,go is a proper defeater for O2,go, due to the priority of the rules. The argument O4,go is a proper defeater for both O3,go and O1,go.

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(TA,L)=U to denote that the root of TA,L is marked as “U” and we write Mark(TA,L)=D if the root of TA,L is marked as “D”.

Definition 6.2

Let P be a DeLP-program and Q a DeLP-query.

Let T(Q)={A0,Q),,An,Q} be the set of all arguments for Q from P, and T(Q)={B0,Q),,Bm,Q} the set of all arguments for Q from P.

The sets TU(Q)T(Q), and TD(Q)T(Q)T(Q) are defined as follows:

TU(Q)={TA,LT(Q)Mark(TA,L)=U},TD(Q)={TA,L(T(Q)T(Q))Mark(TA,L)=D}.
Then, a dialectical explanation (δ-Explanation) for Q from P, denoted by EP(Q), is the tuple EP(Q)=(TU(Q),TU(Q),TD(Q)).

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:

EP6.1(go)=({TA,L},,{TA,L,TA,L,TA,L}).
Figure 5 shows all the marked trees included in this δ-Explanation.
Figure 5.

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

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

6.1Schematic queries and generalised δ-Explanations

A DeLP-schematic query to a DeLP-program is a literal that at least has one variable. It represents the set of DeLP-queries that unify with it only containing constants from the signature of the language of the program. Schematic queries introduce the possibility of asking questions that are more general than ground queries; for instance, consider the program introduced below in Example 6.3, the schematic query flies(X) represents the query ‘what are the individuals for which there exists a warranting argument supporting that they fly?’ Next, we will extend the definition of δ-Explanation to include schematic queries and we will define the notion of answer for schematic queries.

Example 6.3

Consider the DeLP-program (Π6.3,Δ6.3) where:

Π6.3=bird(X)chicken(X)chicken(little)chicken(tina)scared(tina)bird(rob)Δ6.3=flies(X)bird(X)flies(X)chicken(X),scared(X)flies(X)chicken(X)

Observe that potentially, the variable X contained in the the schematic query flies(X) has an infinite number of terms that unify with that variable. However, all queries produced unifying with terms that are not in the signature of the language of this program; e.g. flies(mac) in Example 6.3, will produce the answer unknown and therefore the explanation will be empty. Thus, the set of instances of a schematic query that will be considered for generating a generalised δ-Explanation will refer only to those instances of DeLP-queries that contain constants from the program signature. For instance, in the DeLP-program of Example 6.3, the schematic query flies(X) will only refer to flies(tina), flies(rob), and flies(little).

Schematic queries introduce the possibility of asking questions that are more general than ground queries. With this type of query we are not asking whether a certain piece of knowledge can be believed (warranted), instead we are asking if there exists an instance of that piece of knowledge (related to particular individuals) that can be warranted in the system. This approach could lead to a deeper kind of reasoning as we may pose a query, gather the warranted instances and continue the reasoning process with those individuals. As introduced next, an explanation for a schematic query will contain the explanation for the individual DeLP-queries it represents.

Definition 6.4

Let P be a DeLP-program and Q a schematic query. Let {Q1,,Qz} be the set of all ground instances of Q wrt the signature of P. Let EP(Qi) be the δ-Explanation for the DeLP-query Qi (1iz) from program P. Then, the generalised δ-Explanation for Q in P is

GEP(Q)={EP(Q1),,EP(Qz)}

It is interesting to observe that a δ-Explanation is a particular case of a Generalised δ-Explanation, where the set GEP(Q) is a singleton.

Consider again the DeLP-program (Π6.3,Δ6.3), and suppose that we want to know if from this program it can be warranted that a certain individual does not fly. If we pose the query ∼ flies(X), the answer is yes, because there is a warranted instance: flies(little). The supporting argument is (where ‘flies’ is abbreviated to ‘f’): B1,f(little)={f(little)chicken(little)},f(little). The trees corresponding to the generalised explanation are shown in Figure 6. This explanation also shows that the other instance (∼ f(tina)) is not warranted. Note that the answer for the schematic query f(X) is also yes, but with a different set of warranted instances: f(tina) and f(rob). The supporting argument for instance ‘X = tina’ was already discussed, and the undefeated argument for instance ‘X = rob’ is: C1,f(rob)={f(rob)bird(rob)},f(rob). The generalised δ-Explanation for f(X) is:

{({TA,L,TA,L},,{TA,L}),(,{TA,L},{TA,L}),({TA,L},,)}
Figure 6.

Dialectical trees associated with the explanation for ‘∼ f(X)’.

Dialectical trees associated with the explanation for ‘∼ f(X)’.

Consider a schematic query Q(X) and a DeLP-program P. Suppose that Q(X) represents the five (ground) DeLP-queries: Q(a),Q(b),Q(c),Q(d) and Q(e). As the reader may have noticed from the example above, it may happen that the answer for Q(a) from P is yes, the answer for Q(b) is no, the answer for Q(c) is yes, the answer for Q(b) is undecided, and the answer for Q(a) is no. Next, we define the answer for a schematic query taking into consideration the individual answers for each ground instance.

Let P be a DeLP-program and Q a schematic query. Let {Q1,,Qn} be all the ground instances of Q with respect to the signature of P. The answer for the schematic query Q is:

  • yes, if there exists an instance Qi{Q1,,Qn} such that the answer for the DeLP-query Qi is yes (i.e. TU(Qi)t=).

  • no, if for every instance Qi{Q1,,Qn}, the answer for Qi is no, (i.e. TU(Qi)forallQi).

  • undecided, if there is no instance Qi{Q1,,Qn} such that the answer for the DeLP-query Qi is yes, and there exists an instance Qk{Q1,,Qn} such that the answer for Qk is undecided.

  • unknown, if {Q1,,Qn}=

For example, let's assume that from a particular program P all the ground instances for p(X) with respect to the signature of P are {p(a),p(b),p(c)} and for t(X) are {t(a),t(b),t(c)}, for k(X) are {k(a),k(b),k(c)}, and for j(X) is the empty set. Consider that the following answers for ground queries are obtained:

p(a)YES,p(b)NO,p(c)UNDECIDED,t(a)NO,t(b)NO,t(c)UNDECIDED,k(a)NO,k(b)NO,k(c)NO.

The answer for p(X) is yes because there is an instance (p(a)) for which the answer is yes. The answer for t(X) is undecided because there is no warranted instance, and there is one instance (t(c)) for which the answer is undecided. The answer for k(X) is no because all the instances return no. The answer for j(X) is unknown.

Finally, note that from a DeLP programmer point-of-view, δ-Explanations provide a global idea of the interactions among arguments within the context of a query. This is an essential debugging tool while programming: whenever unexpected behaviour arises, the programmer can check the given explanations to detect errors.

7.Extensions and variations on DeLP

Several extensions of DeLP have been proposed and in this section we will briefly sketch a few of these developments. The following are some of these research lines that are more related to applications.

Possibilistic Defeasible Logic Programming (P-DeLP) (Alsinet, Chesñevar, Godo, Sandri, & Simari, 2008; Chesñevar, Simari, Alsinet, & Godo, 2004), is an extension of DeLP that allows the treatment of possibilistic uncertainty and fuzzy knowledge at object-language level in a logic programming language. In P-DeLP, knowledge representation features are formalised based on a possibilistic logic based on the Horn-rule fragment of Gödel fuzzy logic (PGL). Formulas in PGL are built over fuzzy propositional variables and the certainty degree of formulas is expressed with a necessity measure. The proof method for PGL, in a logic programming setting, is based on a complete calculus for determining the maximum degree of possibilistic entailment of a fuzzy goal. In a multiagent context, it is possible to use P-DeLP to encode the agents’ knowledge about the world, applying the argument and warrant computing procedure to obtain their inferences. In particular, we have also a number of argument-based consequence operators which allow us to model different aspects of the reasoning abilities in an intelligent agent which have been formalised and studied; the computational problem related to how answers to P-DeLP queries can be sped up by pruning the associated search space have been considered.

The representation of strength and time provide useful elements in many argumentation applications. The Strength and Time DeLP, ST-DeLP, is an instantiation of the abstract framework E-TAF (Budán, Gómez Lucero, Chesñevar, & Simari, 2012) based on DeLP that incorporates the representation of temporal availability and strength factors varying over time associated with the elements of the language of DeLP. It also specifies how arguments are built, and how the availability and strength of arguments are obtained from the corresponding information attached to the elements from which they are built. After determining the availability of attacks by comparing strength of conflicting arguments over time, E-TAF definitions are applied to establish temporal acceptability of arguments. Thus, the main contribution of this development is the integration of time and strength in the context of argumentation systems. Other lines of work related to this can be found in Pardo and Godo (2011).

In García, García, and Simari (2008) an argumentation-based planning formalism has been introduced. This system can be used by an agent to construct plans using partial order planning technics, In such a manner that the traditional POP algorithm is extended to consider arguments as planning steps. When actions and arguments are combined to construct plans, new types of interferences appear ant it is necessary to extend the standard notion of threat to consider: action-action, action-argument, and argument-argument threats. The resulting algorithm is called APOP, and extends the traditional POP algorithm to consider actions and arguments as planning steps and resolve the new types of threats using new methods.

A framework for ontology integration of DL ontologies based on DeLP was introduced in Gómez, Chesñevar, and Simari (2013). In this work, the limitations for reasoning in the presence of inconsistent ontologies that Description Logic (DL) ontologies suffer are addressed using defeasible argumentation to model different DL reasoning capabilities when handling inconsistent ontologies, resulting in so-called d-ontologies. ONTOarg, provides a decision support framework for performing local-as-view integration of possibly inconsistent and incomplete ontologies in terms of DeLP. This ontology integration system is able to handle inconsistent DL-based ontologies by performing a dialectical analysis in order to determine the membership of individuals to concepts.

Another recent line of research deals with the problem of massively built arguments from premises obtained from relational databases and compute warrant (Deagustini et al., 2013). In this setting, different databases can be updated by external, independent applications, leading to changes in the spectrum of available arguments. Algorithms for integrating a database management system with an argument-based inference engine have been designed and tested. The empirical results and running-time analysis associated with the approach show how, taking advantage of modern DBMS technologies, it is possible to efficiently implement processes that requiere massive argumentation. This provides an interesting possibility for developing new architectures for knowledge-based applications, such as Decision Support Systems and Recommender Systems, that could efficiently use argumentation as the underlying inference model.

Notes

1 We will use the term knowledge base and defeasible logic program interchangeably when no confusion may arise.

References

1 

Alferes, J.J., Pereira, L.M., & Przymusinski, T.C. (1996). Strong and explicit negation in nonmonotonic reasoning and logic programming. Lecture Notes in Computer Science, 1126, 143–163. doi: 10.1007/3-540-61630-6_10

2 

Alsinet, T., Chesñevar, C.I., Godo, L., Sandri, S., & Simari, G.R. (2008). Formalizing argumentative reasoning in a possibilistic logic programming setting with fuzzy unification. International Journal of Approximate Reasoning, 48, 711–729. doi: 10.1016/j.ijar.2007.07.004

3 

Baral, C., & Gelfond, M. (1994). Logic programming and knowledge representation. Journal of Logical Programming, 19/20, 73–148. doi: 10.1016/0743-1066(94)90025-6

4 

Belanger, M. (2007). Exploitation of argumentation models for mission analysis. In T. Roth-Berghofer, S. Schulz, D. Bahls & D.B. Leake (Eds.), Explanation-aware computing, papers from the 2007 AAAI workshop (pp. 64–67). Vol. WS-07-06 of AAAI Tech. Report. Vancouver, Canada: AAAI Press.

5 

Bench-Capon, T.J.M., & Dunne, P.E. (2007). Argumentation in artificial intelligence. Artificial Intelligence, 171, 619–641. doi: 10.1016/j.artint.2007.05.001

6 

Besnard, P., & Hunter, A. (2001). A logic-based theory of deductive arguments. Artificial Intelligence, 128, 203–235. doi: 10.1016/S0004-3702(01)00071-6

7 

Besnard, P., & Hunter, A. (2008). Elements of argumentation. Cambridge, MA: MIT Press.

8 

Bondarenko, A., Dung, P.M., Kowalski, R.A., & Toni, F. (1997). An abstract, argumentation-theoretic approach to default reasoning. Artificial Intelligence, 93, 63–101. doi: 10.1016/S0004-3702(97)00015-5

9 

Bondarenko, A., Toni, F., & Kowalski, R.A. (1993). An assumption-based framework for non-monotonic reasoning. In Logic Programming and Nonmonotonic Reasoning, Lisbon, Portugal (pp. 171–189), Boston, MA: The MIT Press.

10 

Budán, M.C., Gómez Lucero, M.J., Chesñevar, C.I., & Simari, G.R. (2012). Modelling time and reliability in structured argumentation frameworks. In G. Brewka, T. Eiter & S.A. McIlraith (Eds.), Principles of Knowledge Representation and Reasoning: Proceedings of the Thirteenth International Conference, Rome, Italy, 2012. Rome, Italy, AAAI Press (Menlo Park, CA), pp. 578–582.

11 

Chesñevar, C.I., Maguitman, A.G., & Loui, R.P. (2000). Logical models of argument. ACM Computing Surveys, 32, 337–383. doi: 10.1145/371578.371581

12 

Chesñevar, C.I., & Simari, G.R. (2007). A lattice-based approach to computing warranted beliefs in skeptical argumentation frameworks. In M.M. Veloso (Ed.), Proceedings of the 20th International Joint Conference on Artificial Intelligence, Hyderabad, India, January (pp. 280–285), AAAI Press (Menlo Park, CA), Hyderabad, India.

13 

Chesñevar, C.I., Simari, G.R., Alsinet, T., & Godo, L. (2004). A logic programming framework for possibilistic argumentation with vague knowledge. In D.M. Chickering & J.Y. Halpern (Eds.), UAI (pp. 76–84). Banff, Canada: AUAI Press.

14 

Deagustini, C.A.D., Fulladoza Dalibón, S.E., Gottifredi, S., Falapp. , M.A., Chesñevar, C.I., & Simari, G.R. (2013). Relational databases as a massive information source for defeasible argumentation. Knowledge-Based Systems (online).

15 

Dung, P.M. (1993). On the acceptability of arguments and its fundamental role in nonmonotonic reasoning and logic programming. In R. Bajcsy (Ed.), Proceedings of the 13th International Joint Conference on Artificial Intelligence. Chambéry, France (pp. 852–859), Morgan Kauffman (Burlington, MA), Chambéry, France.

16 

Dung, P.M. (1995). On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games. Artificial Intelligence, 77, 321–357. doi: 10.1016/0004-3702(94)00041-X

17 

Ferretti, E., Errecalde, M., García, A.J., & Simari, G.R. (2008). Decision rules and arguments in defeasible decision making. In P. Besnard, S. Doutre & A. Hunter (Eds.), Proc. 2nd Int. Conference on Computational Models of Arguments (COMMA) (pp. 171–182), Vol. 172 of Frontiers in Artificial Intelligence and Applications. Toulouse, France: IOS Press.

18 

García, A.J. (2000). Defeasible logic programming: Definition, operational semantics and parallelism (Ph.D. thesis). Computer Science and Engineering Department, Universidad Nacional del Sur, Bahía Blanca, Argentina.

19 

García, A.J., Chesñevar, C.I., Rotstein, N.D., & Simari, G.R. (2013). Formalizing dialectical explanation support for argument-based reasoning in knowledge-based systems. Expert Systems with Applications, 40, 3233–3247. doi: 10.1016/j.eswa.2012.12.036

20 

García, D.R., García, A.J., & Simari, G.R. (2008). Defeasible reasoning and partial order planning. In S. Hartmann & G. Kern-Isberner (Eds.), FoIKS (pp. 311–328). Vol. 4932 of Lecture Notes in Computer Science. Pisa, Italy: Springer.

21 

García, A.J., Rotstein, N.D., Chesñevar, C.I., & Simari, G.R. (2009). Explaining why something is warranted in defeasible logic programming. In ExaCt 2009 (pp. 25–36). Pasadena, CA: IJCAI.

22 

García, A.J., Rotstein, N.D., Tucat, M., & Simari, G.R. (2007). An argumentative reasoning service for deliberative agents. In Z. Zhang & J.H. Siekmann (Eds.), Proceedings of the Second International Conference on Knowledge Science, Engineering and Management, KSEM 2007, November 28–30 (pp. 128–139). Vol. 4798 of Lecture Notes in Computer Science. Melbourne: Springer.

23 

García, A.J., & Simari, G.R. (2004). Defeasible logic programming: An argumentative approach. Theory and Practice of Logic Programming, 4, 95–138. doi: 10.1017/S1471068403001674

24 

Gómez, S.A., Chesñevar, C.I., & Simari, G.R. (2013). ONTOarg: A decision support framework for ontology integration based on argumentation. Expert Systems with Applications, 40, 1858–1870. doi: 10.1016/j.eswa.2012.10.025

25 

Guida, G., & Zanella, M. (1997). Bridging the gap between users and complex decision support systems: The role of justification. In ICECCS ’97: Proc. 3rd IEEE Int. Conf. on Eng. of Complex Computer Systems (pp. 229–238). Washington.

26 

Lacave, C., & Diez, F.J. (2004). A review of explanation methods for heuristic expert systems. Knowledge Engineering Review, 19, 133–146. doi: 10.1017/S0269888904000190

27 

Lifschitz, V. (1996). Foundations of logic programs. In G. Brewka (Ed.), Principles of knowledge representation (pp. 69–128). Stanford: CSLI Pub.

28 

Lin, F., & Shoham, Y. (1989). Argument systems: A uniform basis for nonmonotonic reasoning. In R.J. Brachman, H.J. Levesque & R. Reiter (Eds.), Proceedings of the 1st International Conference on Principles of Knowledge Representation and Reasoning (KR’89) (pp. 245–255). Toronto, Canada: Morgan Kaufmann.

29 

Loui, R.P. (1987). Defeat among arguments: A system of defeasible inference. Computational Intelligence, 3, 100–106. doi: 10.1111/j.1467-8640.1987.tb00178.x

30 

Martínez, M.V., García, A.J., & Simari, G.R. (2012). On the use of presumptions in structured defeasible reasoning. In B. Verheij, S. Szeider & S. Woltran (Eds.), Computational Models of Argument, Proceedings of COMMA 2012 (pp. 185–196). Vol. 245 of Frontiers in Artificial Intelligence and Applications. Vienna, Austria: IOS Press.

31 

McCarthy, J. (1980). Circumscription – a form of non-monotonic reasoning. Artificial Intelligence, 13, 27–39. doi: 10.1016/0004-3702(80)90011-9

32 

McDermott, D.V., & Doyle, J. (1980). Non-monotonic logic I. Artificial Intelligence, 13, 41–72. doi: 10.1016/0004-3702(80)90012-0

33 

Modgil, S., & Prakken, H. (2013). A general account of argumentation with preferences. Artificial Intelligence, 195, 361–397. doi: 10.1016/j.artint.2012.10.008

34 

Moore, R.C. (1984). Possible-world semantics for autoepistemic logic. In Workshop on Nonmotononic Reasoning (pp. 344–354), AAAI Press (Menlo Park, CA), New Paltz, NY.

35 

Moulin, B., Irandoust, H., Bélanger, M., & Desbordes, G. (2002). Explanation and argumentation capabilities: Towards the creation of more persuasive agents. Artificial Intelligence Review, 17, 169–222. doi: 10.1023/A:1015023512975

36 

Nute, D. (1987). Defeasible reasoning. In Proceedings of the 20th Hawaii International Conference on System Science, Hawaii, USA (pp. 470–477).

37 

Nute, D. (1988). Defeasible reasoning: A philosophical analysis in Prolog. In J.H. Fetzer (Ed.), Aspects of artificial intelligence (pp. 251–288). Dordrecht, The Netherlands: Kluwer Academic Pub.

38 

Pardo, P., & Godo, L. (2011). t-DeLP: A temporal extension of the defeasible logic programming argumentative framework. In S. Benferhat & J. Grant (Eds.), SUM 2011 Proceedings of the 5th International Conference on Scalable Uncertainty Management (pp. 489–503). Vol. 6929 of Lecture Notes in Computer Science. Dayton, Ohio: Springer.

39 

Pollock, J.L. (1987). Defeasible reasoning. Cognitive Science, 11, 481–518. doi: 10.1207/s15516709cog1104_4

40 

Pollock, J.L. (1996). A general-purpose defeasible reasoner. Journal of Applied Non-Classical Logics, 6, 89–113. doi: 10.1080/11663081.1996.10510868

41 

Prakken, H. (2010). An abstract framework for argumentation with structured arguments. Argument & Computation, 1, 93–124. doi: 10.1080/19462160903564592

42 

Prakken, H., & Vreeswijk, G. (2002). Logics for defeasible argumentation. In D. Gabbay & F. Guenthner (Eds.), Handbook of philosophical logic (pp. 218–319). Dordrecht, The Netherlands: Kluwer Academic Pub.

43 

Rahwan, I., & Simari, G.R. (2009). Argumentation in artificial intelligence. Heidelberg, Germany: Springer.

44 

Reiter, R. (1980). A logic for default reasoning. Artificial Intellence, 13, 81–132. doi: 10.1016/0004-3702(80)90014-4

45 

Simari, G.R. (1989). A mathematical treatment of defeasible reasoning and its implementation. Washington University, Department of Computer Science (Saint Louis, MO: EE.UU.).

46 

Simari, G.R., Chesñevar, C.I., & García, A.J. (1994a). Focusing inference in defeasible argumentation. In IV Iberoamerican Conference on Artificial Intelligence, October, IBERAMIA’94, Caracas, Venezuela.

47 

Simari, G.R., Chesñevar, C.I., & García, A.J. (1994b). The role of dialectics in defeasible argumentation. In XIV International Conference of the Chilenean Computer Science Society, November, Sociedad Chilena de Ciencias de la Computacion, Concepcion, Chile.

48 

Simari, G.R., & Loui, R.P. (1992). A mathematical treatment of defeasible reasoning and its implementation. Artificial Intelligence, 53, 125–157. doi: 10.1016/0004-3702(92)90069-A

49 

Tucat, M., Garcia, A.J., & Simari, G.R. (2009). Using defeasible logic programming with contextual queries for developing recommender servers. In AAAI Fall Symposium Series, AAAI Press (Menlo Park, CA), Arlington, VA.

50 

Walton, D. (2004). A new dialectical theory of explanation. Philosophical Explorations, 7, 71–89. doi: 10.1080/1386979032000186863

51 

Ye, L.R., & Johnson, P.E. (1995). The impact of explanation facilities on user acceptance of expert systems advice. MIS Quarterly, 19, 157–172. doi: 10.2307/249686