Extending Answer Set Programming using Generalized Possibilistic Logic

Abstract

Answer set programming (ASP) is a form of logic programming in which negation-as-failure is defined in a purely declarative way, based on the notion of a stable model. This short paper briefly explains how a recent generalization of possibilistic logic (GPL) can be used to characterize the semantics of answer set programming. This characterization has several advantages over existing characterizations of the stable model semantics. First, unlike reduct-based approaches, it does not rely on a syntactic procedure: we can directly characterize answer sets based on the minimally specific models of a GPL theory. Second, GPL enables us to study extensions of ASP in an intuitive way: unlike in existing generalizations of ASP such as equilibrium logic and autoepistemic logic, all formulas in GPL have a meaning which is intuitively clear. Finally, being based on possibilistic logic, GPL offers a natural way of dealing with uncertainty in answer set programs.

-

a1 _ ::: _ an b1 ^ ::: ^ bm ^ not c1 ^ ::: ^ not cr (1) where a1; :::; an; b1; :::; bm; c1; :::; cr are propositional literals, i.e. either atomic propositions from a given finite set At or the negation of such atomic propositions. We call a1 _ ::: _ an the head of the rule while b1 ^ ::: ^ bm ^ not c1 ^ ::: ^ not cr is called the body. An extended literal is a literal or an expression of the form not ci (with ci a literal). Intuitively, (1) states that if we cannot derive that any of c1; :::; cr are true and we can derive that all of b1; :::; bm are true, then we should assume that one of a1; :::; an must be true. Formally, the semantics of an answer set program is defined in terms of the Gelfond-Lifschitz reduct [ 10 ]. In particular, given a set of literals M , the reduct P M of an answer set program P is defined as follows: P M = a1 _ ::: _ an

b1 ^ ::: ^ bm j M \ fc1; :::; crg = ;; exist a model M 0 of P M such that M 0 M . Intuitively, the condition not ci is satisfied if ci cannot be derived from the program. However, what literals can be derived depends on which assumptions we make about what other literals can be derived, which introduces a circular dependency. When using the Gelfond-Lifschitz reduct, this dependency is broken by making a guess M about what literals can be derived, and then verifying that M indeed coincides with the set of literals that can be derived.

A large number of equivalent characterizations of answer sets have been proposed [ 15 ]. For example, autoepistemic logic (AEL [ 16 ]), the logic of minimal belief and negation as failure (MBNF [ 14 ]) and equilibrium logic (EL [ 18 ]) can be used to define answer sets in a model-theoretic way. Moreover, MBNF and EL can be used to define answer sets of arbitrary propositional combinations of extended literals (e.g. containing disjunctions of rules, negation as failure in the head of rules, etc.).

In this paper, we show how a recent generalization of possibilistic logic (GPL [5; 7; 8]) can be used to characterize answer sets. This characterization has several advantages over existing characterizations, in particular w.r.t. how it enables us to extend ASP. For example, GPL has the advantage over MBNF and EL that its models can be naturally interpreted as the epistemic state of an agent, which allows us to give an intuitive interpretation to answer set programs in which not c1 means that “the agent does not know that c1 is true”. As a result, even when the syntax of ASP is extended to arbitrary propositional combinations of extended literals, the corresponding GPL formulas still have an intuitive meaning. In contrast, the intuitive meaning of EL formulas is not always clear. Moreover, since every propositional formula in GPL is encapsulated by a modal operator (see Section 2), we can distinguish between situations in which “the agent knows that either a or b holds” from “either the agent knows a or the agent knows b”, whereas EL can only model the latter. The GPL characterization also ensures that all answer sets are minimal, i.e. that there cannot be two answer sets M1 and M2 such that M1 M2. While this is true for any characterization of ASP when only rules of the form (1) are considered, existing characterizations do not guarantee minimality when negation-as-failure is allowed in the head of rules [ 13 ]. Finally, as the semantics of GPL is based on possibility distributions, the proposed characterization can be naturally extended to give a semantics to answer set programs in which rules can have uncertain conclusions.

In the next section, we briefly recall the syntax and semantics of GPL. Section 3 then explains how answer sets can be characterized using GPL, and how GPL can be used to define extensions of ASP. Finally, in Section 4 we consider uncertain answer set programs, and show how GPL can be used to define the possibilistic answer sets of such programs. 2

Generalized possibilistic logic

Let k = f0; k1 ; :::; 1g be the considered set of certainty degrees and let k+ = k n f0g. GPL formulas are then defined as follows:

If 2 k+ and is a propositional formula, then N ( ) is a GPL formula; if and are GPL formulas, then so are : and ^ .

As usual, we use ! and _ as abbreviations for :( ^ : ) and :(: ^ : ). Furthermore we write ( ) as an abbreviation for :Nn( )(: ), where n( ) = 1 + k1 for 2 k+. GPL is useful to reason about the knowledge of another agent. Intuitively N ( ) means that the agent knows with certainty , while ( ) means that the agent considers possible to the degree . An expression of the form N ( ) or ( ) will be called a meta-literal.

The semantics of GPL is defined in terms of possibility distributions. Let be a normalized possibility distribution over the set of possible worlds , i.e. is a mapping from to [0; 1] such that (!) = 1 for at least one ! in . Then is said to satisfy the GPL formula N ( ), written j= N ( ), iff

N ( ) = minf1 (!) j ! 2 ; ! j= : g where N denotes the necessity measure from possibility theory. The satisfaction relation j= is extended to arbitrary GPL formulas in the usual way, i.e. j= ^ iff j= and j= , while j= : iff 6j= . A possibility distribution is called a model of a set of GPL formulas if satisfies every formula in . An axiomatization of GPL has been presented in [ 7 ].

Let 1 and 2 be two possibility distributions over . We say that 1 is less specific than 2, written 1 2, if 1(!) 2(!) for all ! 2 . If 1 2 and 1 6= 2, we write 1 2. We say that is a minimally specific model of a set of GPL formulas if is a model of and there is no model 0 of such that 0 . Let be a GPL formula and let be a set of GPL formulas. The following three inference relations are considered in GPL: standard entailment model of .

j= cautious entailment j=c iff mally specific models of .

iff

is satisfied by every is satisfied by all minibrave entailment j=b iff is satisfied by at least one minimally specific model of .

The problems of checking whether j= , j=c and j=b hold are respectively coNP-complete, 2P -complete and 2P -complete [ 8 ].

GPL generalizes standard possibilistic logic [4; 6] in that the latter only allows sets of meta-literals of the form N ( ), which are usually written as weighted propositional formulas of the form ( ; ). At the semantic level, a theory in possibilistic logic corresponds to a single possibility distribution, which is the unique minimally specific model of that theory, whereas theories in GPL can have several minimally specific models. 3

Characterizing and extending ASP using GPL Given an answer set program P , we let P be the GPL theory which contains for each rule of the form (1) in P the following formula:

N1(b1) ^ ::: ^ N1(bm) ^ 1(:c1) ^ ::: ^ 1(:cr) ! N1(a1) _ ::: _ N1(an) (2) In other words, the body of a rule of the form (1) is satisfied if the agent knows each bi with maximal certainty and moreover the agent considers :cj fully possible for each j. Note that 1(:cj ) is equivalent to :N 1 (cj ).

k

The transformation in (2) is by itself not enough, as ASP is based on the idea of forward chaining and in particular does not allow contrapositive reasoning (e.g. from the rule a b and the fact :a we should not derive :b). To see how forward chaining could be enforced using GPL, first note that there are three ways in which the formula (2) can be satisfied by a minimally specific model of P : 1. one of the meta-literals N1(bi) is not satisfied by ;

2. one of the meta-literals

N 1 (ci) is satisfied by ;

k 3. one of the meta-literals N1(ai) is satisfied by .

1(ci) is not satisfied by , i.e.

The first case intuitively corresponds to an answer set which does not include bi, i.e. to a situation in which the rule (1) does not apply. The third case intuitively corresponds to an answer set in which ai has been included to make the rule (1) satisfied, i.e. to a situation in which ai has been derived using (non-deterministic) forward chaining. The second case, however, intuitively corresponds to a contrapositive inference, i.e. (1) has been satisfied by making ci true. The latter inference is not allowed in ASP and the second case should thus be excluded. To this end, we take advantage of the fact that it is only in the second case that certainty degrees other than 0 or 1 are needed. Note that here we do not use degrees for modelling uncertainty, but intuitively for differentiating between literals that are assumed to be true and literals that can effectively be derived. In particular, it turns out that answer sets correspond to the minimally specific models of P in which only the certainty degrees 0 and 1 occur. Formally, the requirement that only these certainty degrees occur is encoded by the GPL formula , defined as follows: ^ N1(a) _ N1(:a) _ ( 1(a) ^ 1(:a)) (3) a2At The formula expresses that for every atom a, the agent is either fully certain about the truth value of a (in which case N1(a) _ N1(:a) holds) or the agent is completely ignorant about a (in which case 1(a) ^ 1(:a) holds). It turns out that the answer sets of P correspond to the minimally specific models of P that satisfy . In particular, assuming that k 2 (i.e. j kj 3), it holds that P has a consistent answer set iff Moreover, for each consistent answer set M of P , it holds that the following possibility distribution M is a minimally specific model of P which satisfies :

M (!) = 1 if ! satisfies every literal in M 0 otherwise Conversely, for every minimally specific model of P which satisfies , it holds that the following set of literals M is an answer set of P :

M

= fl j N (l) = 1g where N is the necessity measure induced by . Note that it follows that a literal l is included in at least one answer set of P iff and that that l is included in all answer sets of P iff This means in particular that the main reasoning tasks from ASP correspond to the standard forms of GPL inference.

This characterization of answer sets in GPL can be straightforwardly generalized to arbitrary propositional combinations of extended literals. When negation-as-failure in the head is considered, however, our characterization deviates from the existing characterizations in terms of EL and MBNF. This is illustrated in the next example.

Example 1. We consider a single atom a, in which case = f;; fagg, where we identify models with the set of atoms they make true. Consider the formula a_not a, and the corresponding GPL encoding N1(a) _ 1(:a). Clearly, the latter formula has a unique minimally specific model , defined by (;) = (fag) = 1. In other words, the only answer set we find for a _ not a is the empty set. However, both the characterization of ASP in MBNF [ 14 ] and the characterization in EL [ 18 ] find two answer sets for this example, viz. M1 = ; and M2 = fag.

As the intuition behind the stable model semantics is based on the idea of minimal commitment, the GPL semantics appears more natural.

The use of the modal operators N in GPL allows us to further extend ASP. In the standard semantics of ASP, rules with disjunctions in the head intuitively correspond to a nondeterministic choice, e.g. a _ b c means that when the agent knows c then either it knows a or it knows b. When modelling epistemic reasoning, however, it often seems more natural to interpret a _ b as “the agent knows that either a or b is true (but may not know which is the case)”. This latter reading was referred to as weak disjunction in [ 2 ], where the inference problems resulting from interpreting ASP rules in this way have been investigated. Using GPL, the ASP rule a_b c can be modelled as N1(c) ! N1(a_b) when weak disjunction is considered, and as N1(c) ! N1(a) _ N1(b) otherwise.

Finally, the use of possibilistic logic enables us to consider uncertain answer set programs. This is discussed in more detail in the next section. 4

Modelling uncertain answer set programs An uncertain ASP rule is an expression of the form

b1 ^ ::: ^ bm ^ not c1 ^ ::: ^ not cr (4) where is a certainty degree from k+. An uncertain answer set program is a set of uncertain ASP rules. As has been observed in [ 1 ], there are two fundamentally different ways to interpret uncertain ASP rules. On the one hand, we may view as reflecting the certainty that the corresponding ASP rule is valid. This interpretation leads us to view an uncertain ASP program as a possibility distribution over classical ASP programs; at the semantic level, we can then consider a possibility distribution over classical answer sets. On the other hand, we may view as reflecting the certainty with which we can derive the head of the rule, given that its body is satisfied. This view leads to a semantics in which answer sets correspond to weighted epistemic states, which are modelled as possibility distributions. Note that a similar distinction is often made in first-order probabilistic logics [ 11 ] and in firstorder conditional logics [ 9 ]. The former interpretation of uncertain ASP programs has been considered in [ 1 ] and [ 12 ]. The latter interpretation has been considered, among others, in [ 17 ], [ 2 ] and [ 3 ].

Modelling the former type of uncertain ASP programs in GPL would require nested modalities, encapsulating formulas of the form (2) with a modality of the form N . As nested modalities are not allowed in GPL, this would require us to define a variant of GPL in which every (standard) GPL formula would be encapsulated by a modality, similar to how propositional formulas are encapsulated in standard GPL. At the semantic level, models would then correspond to possibility distributions over possibility distributions over possible worlds.

Here we focus on modelling the second type of uncertain ASP programs in GPL. Let us first consider rules without negation-as-failure: l k

N i (b1) ^ ::: ^ N i (bm) ! N i (a1) _ ::: _ N i (an) k k k k l ^ Let P be an uncertain ASP program without negation-asfailure and let P be the set of corresponding GPL formulas. It is not hard to see that a possibility distribution is a possibilistic answer set of P in the sense of [ 2 ] iff is a minimally specific model of P . In absence of negation-asfailure, the semantics from [ 1 ] moreover coincides with the semantics from [ 17 ].

To deal with negation-as-failure, [ 2 ] and [ 17 ] rely on a generalization of the Gelfond-Lifschitz reduct. Consider a rule of the following form: The reduct of this rule w.r.t. a possibility distribution , according to the semantics from [ 2 ], is given by: where = min( kl ; (:c1); :::; (:cr)), for the possibility measure induced by . The reduct considered in [ 17 ] boils down to choosing = kl if (:c1) = ::: (:cr) = 1 and = 0 otherwise (where rules whose certainty is 0 are simply omitted).

Using GPL, we can avoid the use of a reduct, if we assume that k is even and only certainty degrees from f k2 ; k4 ; :::; 1g are used in the uncertain ASP program P . We can always ensure that this assumption is satisfied by replacing the set of certainty degrees k by the set 2k, since every element from k is equal to 2lk for some even value of l. The GPL theory P corresponding to P is then obtained by replacing every rule of the form (4) by the following formula:

N i (b1) ^ ::: ^ N i (bm) ^ k k ki (:c1) ^ ::: ^

ki (:cr) ! N i (a1) _ ::: _ N i (an) k k (6) where we assume = kl . We again need to exclude models which intuitively rely on contrapositive reasoning. Similar as in Section 3, these correspond to minimally specific models which make (6) satisfied by making one of the meta-literals i (:c1) false, i.e. by making a meta-literal N k i+1 ( c1) k k true. Noting that k i + 1 is odd iff i is even, we find that it suffices to exclude models in which certainty degrees kl are used with l odd. Such models can be avoided by considering the following GPL formula k k k 2 ^ ^ a2At i=1

N 2i 1 (a) ! N 2i (a))

k k ^ (N 2ik 1 (:a) ! N 2ki (:a) Note that 2 is equivalent to the formula defined in (3). We propose the following definition: is a possibilistic answer set of P iff is a minimally specific model of P which satisfies k. As in Section 3, we can then formulate the main reasoning tasks for possibilistic ASP in terms of standard entailment in GPL. For example, checking whether the certainty of a is at least kl (with l even) in every possibilistic answer set of P corresponds to: We can show that the proposed definition of possibilistic answer set corresponds to the reduct-based definition from [ 2 ]. We have shown how generalized possibilistic logic (GPL) can be used to characterize answer sets without the need for a reduct operation, and how this characterization allows us to consider a range of different extensions of ASP in a natural way. In particular, the GPL characterization enables us to define answer sets for arbitrary propositional combinations of extended literals (while keeping the intuition of minimal commitment), for modelling weak disjunction, and for defining answer sets of uncertain programs.

Acknowledgment

Steven Schockaert has been supported by a grant from the Leverhulme Trust (RPG-2014-164).

References

[1] K. Bauters , S. Schockaert , M. De Cock , and D. Vermeir . Semantics for possibilistic answer set programs: Uncertain rules versus rules with uncertain conclusions . International Journal of Approximate Reasoning , 55 ( 2 ): 739 - 761 , 2014 .

[2] K. Bauters , S. Schockaert , M. De Cock , and D. Vermeir . Characterizing and extending answer set semantics using possibility theory . Theory and Practice of Logic Programming , 15 ( 1 ): 79 - 116 , 2015 .

[3] R. Confalonieri , J. C. Nieves , M. Osorio , and J. Va ´zquezSalceda. Dealing with explicit preferences and uncertainty in answer set programming . Annals of Mathematics and Artificial Intelligence , 65 ( 2-3 ): 159 - 198 , 2012 .

[4] D. Dubois , J. Lang , and H. Prade . Possibilistic logic . In D. N. D. Gabbay , C. Hogger J . Robinson, editor, Handbook of Logic in Artificial Intelligence and Logic Programming , volume 3 , pages 439 - 513 . Oxford University Press, 1994 .

[5] D. Dubois and H. Prade . Generalized possibilistic logic . In Proceedings of the 5th International Conference on Scalable Uncertainty Management , pages 428 - 432 , 2011 .

[6] D. Dubois and H. Prade . Possibilistic logic - An overview . In D. M. Gabbay , J. Siekmann , and J. Woods, editors, Handbook of the History of Logic , Vol. 9 : Computational Logic , pages 283 - 342 . Elsevier, 2014 .

[7] D. Dubois , H. Prade , and S. Schockaert . Stable models in generalized possibilistic logic . In Proceedings of the Thirteenth International Conference on Principles of Knowledge Representation and Reasoning , pages 519 - 529 , 2012 .

[8] D. Dubois , H. Prade , and S. Schockaert . Reasoning about uncertainty and explicit ignorance in generalized possibilistic logic . In Proceedings of the 21st European Conference on Artificial Intelligence , pages 261 - 266 , 2014 .

[9] N. Friedman , J. Y. Halpern , and D. Koller . First-order conditional logic for default reasoning revisited . ACM Transactions on Computational Logic , 1 ( 2 ): 175 - 207 , 2000 .

[10] M. Gelfond and V. Lifschitz . The stable model semantics for logic programming . In Proceedings of the Fifth International Conference and Symposium on Logic Programming , pages 1081 - 1086 , 1988 .

[11] J. Y. Halpern . An analysis of first-order logics of probability . Artificial Intelligence , 46 ( 3 ): 311 - 350 , 1990 .

[12] J. Hu , M. Westphal , and S. Wo¨lfl. Towards a new semantics for possibilistic answer sets . In Proceedings of the 37th Annual German Conference on AI , pages 159 - 170 . 2014 .

[13] K. Inoue and C. Sakama . Negation as failure in the head . The Journal of Logic Programming , 35 ( 1 ): 39 - 78 , 1998 .

[14] V. Lifschitz . Minimal belief and negation as failure . Artificial Intelligence , 70 ( 1-2 ): 53 - 72 , 1994 .

[15] V. Lifschitz . Twelve definitions of a stable model . In Proceedings of the 24th International Conference on Logic Programming , pages 37 - 51 , 2008 .

[16] R. C. Moore . Semantical considerations on nonmonotonic logic . Artificial Intelligence , 25 ( 1 ): 75 - 94 , 1985 .

[17] P. Nicolas , L. Garcia , I. Ste´phan, and C. Lefe`vre. Possibilistic uncertainty handling for answer set programming . Annals of Mathematics and Artificial Intelligence , 47 : 139 - 181 , 2006 .

[18] D. Pearce . Equilibrium logic . Annals of Mathematics and Artificial Intelligence , 47 : 3 - 41 , 2006 .