=Paper=
{{Paper
|id=Vol-1517/JOWO-15_ontolp_paper_1
|storemode=property
|title=Extending Answer Set Programming using Generalized Possibilistic Logic
|pdfUrl=https://ceur-ws.org/Vol-1517/JOWO-15_ontolp_paper_1.pdf
|volume=Vol-1517
|dblpUrl=https://dblp.org/rec/conf/ijcai/DuboisPS15
}}
==Extending Answer Set Programming using Generalized Possibilistic Logic==
https://ceur-ws.org/Vol-1517/JOWO-15_ontolp_paper_1.pdf
Extending Answer Set Programming using Generalized Possibilistic Logic
Didier Dubois Henri Prade Steven Schockaert
Université Paul Sabatier, CNRS Université Paul Sabatier, CNRS Cardiff University
IRIT, Toulouse, France IRIT, Toulouse, France United Kingdom
dubois@irit.fr prade@irit.fr SchockaertS1@cardiff.ac.uk
Abstract We say that M is a model of P M if for each rule a1 ∨ ... ∨
an ← b1 ∧ ... ∧ bm in P M such that {b1 , ..., bm } ⊆ M it
Answer set programming (ASP) is a form of logic holds that M ∩ {a1 , ..., an } =6 ∅. We say that M is an an-
programming in which negation-as-failure is de- swer set of P M if M is a model of P M and there does not
fined in a purely declarative way, based on the no- exist a model M 0 of P M such that M 0 ⊂ M . Intuitively, the
tion of a stable model. This short paper briefly ex- condition not ci is satisfied if ci cannot be derived from the
plains how a recent generalization of possibilistic program. However, what literals can be derived depends on
logic (GPL) can be used to characterize the seman- which assumptions we make about what other literals can be
tics of answer set programming. This characteriza- derived, which introduces a circular dependency. When us-
tion has several advantages over existing character- ing the Gelfond-Lifschitz reduct, this dependency is broken
izations of the stable model semantics. First, un- by making a guess M about what literals can be derived, and
like reduct-based approaches, it does not rely on a then verifying that M indeed coincides with the set of literals
syntactic procedure: we can directly characterize that can be derived.
answer sets based on the minimally specific mod-
A large number of equivalent characterizations of answer
els of a GPL theory. Second, GPL enables us to
sets have been proposed [15]. For example, autoepistemic
study extensions of ASP in an intuitive way: unlike
logic (AEL [16]), the logic of minimal belief and negation as
in existing generalizations of ASP such as equilib-
failure (MBNF [14]) and equilibrium logic (EL [18]) can be
rium logic and autoepistemic logic, all formulas in
used to define answer sets in a model-theoretic way. More-
GPL have a meaning which is intuitively clear. Fi-
over, MBNF and EL can be used to define answer sets of ar-
nally, being based on possibilistic logic, GPL offers
bitrary propositional combinations of extended literals (e.g.
a natural way of dealing with uncertainty in answer
containing disjunctions of rules, negation as failure in the
set programs.
head of rules, etc.).
In this paper, we show how a recent generalization of pos-
1 Introduction sibilistic logic (GPL [5; 7; 8]) can be used to characterize an-
swer sets. This characterization has several advantages over
An answer set program is a set of rules of the form:
existing characterizations, in particular w.r.t. how it enables
a1 ∨ ... ∨ an ← b1 ∧ ... ∧ bm ∧ not c1 ∧ ... ∧ not cr (1) us to extend ASP. For example, GPL has the advantage over
MBNF and EL that its models can be naturally interpreted
where a1 , ..., an , b1 , ..., bm , c1 , ..., cr are propositional liter- as the epistemic state of an agent, which allows us to give
als, i.e. either atomic propositions from a given finite set At or an intuitive interpretation to answer set programs in which
the negation of such atomic propositions. We call a1 ∨...∨an not c1 means that “the agent does not know that c1 is true”.
the head of the rule while b1 ∧ ... ∧ bm ∧ not c1 ∧ ... ∧ not cr is As a result, even when the syntax of ASP is extended to ar-
called the body. An extended literal is a literal or an expres- bitrary propositional combinations of extended literals, the
sion of the form not ci (with ci a literal). Intuitively, (1) states corresponding GPL formulas still have an intuitive meaning.
that if we cannot derive that any of c1 , ..., cr are true and we In contrast, the intuitive meaning of EL formulas is not al-
can derive that all of b1 , ..., bm are true, then we should as- ways clear. Moreover, since every propositional formula in
sume that one of a1 , ..., an must be true. Formally, the se- GPL is encapsulated by a modal operator (see Section 2), we
mantics of an answer set program is defined in terms of the can distinguish between situations in which “the agent knows
Gelfond-Lifschitz reduct [10]. In particular, given a set of that either a or b holds” from “either the agent knows a or
literals M , the reduct P M of an answer set program P is de- the agent knows b”, whereas EL can only model the latter.
fined as follows: The GPL characterization also ensures that all answer sets
are minimal, i.e. that there cannot be two answer sets M1 and
P M = a1 ∨ ... ∨ an ← b1 ∧ ... ∧ bm | M ∩ {c1 , ..., cr } = ∅,
M2 such that M1 ⊂ M2 . While this is true for any charac-
(a1 ∨ ... ∨ an ← b1 ∧ ... ∧ bm ∧ not c1 ∧ ... ∧ not cr ) ∈ P terization of ASP when only rules of the form (1) are consid-
ered, existing characterizations do not guarantee minimality brave entailment Θ |=b α iff α is satisfied by at least one
when negation-as-failure is allowed in the head of rules [13]. minimally specific model of Θ.
Finally, as the semantics of GPL is based on possibility dis- The problems of checking whether Θ |= α, Θ |=c α and
tributions, the proposed characterization can be naturally ex- Θ |=b α hold are respectively coNP-complete, ΠP 2 -complete
tended to give a semantics to answer set programs in which and ΣP 2 -complete [8].
rules can have uncertain conclusions. GPL generalizes standard possibilistic logic [4; 6] in that
In the next section, we briefly recall the syntax and seman- the latter only allows sets of meta-literals of the form Nλ (α),
tics of GPL. Section 3 then explains how answer sets can be which are usually written as weighted propositional formulas
characterized using GPL, and how GPL can be used to define of the form (α, λ). At the semantic level, a theory in possi-
extensions of ASP. Finally, in Section 4 we consider uncer- bilistic logic corresponds to a single possibility distribution,
tain answer set programs, and show how GPL can be used to which is the unique minimally specific model of that theory,
define the possibilistic answer sets of such programs. whereas theories in GPL can have several minimally specific
models.
2 Generalized possibilistic logic
Let Λk = {0, k1 , ..., 1} be the considered set of certainty de- 3 Characterizing and extending ASP using
grees and let Λ+
k = Λk \ {0}. GPL formulas are then defined
GPL
as follows: Given an answer set program P , we let ΘP be the GPL theory
• If λ ∈ Λ+
k and α is a propositional formula, then Nλ (α)
which contains for each rule of the form (1) in P the follow-
is a GPL formula; ing formula:
• if α and β are GPL formulas, then so are ¬α and α ∧ β. N1 (b1 ) ∧ ... ∧ N1 (bm ) ∧ Π1 (¬c1 ) ∧ ... ∧ Π1 (¬cr )
As usual, we use α → β and α ∨ β as abbreviations for → N1 (a1 ) ∨ ... ∨ N1 (an ) (2)
¬(α ∧ ¬β) and ¬(¬α ∧ ¬β). Furthermore we write Πλ (α)
as an abbreviation for ¬Nn(λ) (¬α), where n(λ) = 1 − λ + k1 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
for λ ∈ Λ+ k . GPL is useful to reason about the knowledge of the agent considers ¬cj fully possible for each j. Note that
another agent. Intuitively Nλ (α) means that the agent knows Π1 (¬cj ) is equivalent to ¬N k1 (cj ).
α with certainty λ, while Πλ (α) means that the agent con-
siders α possible to the degree λ. An expression of the form The transformation in (2) is by itself not enough, as ASP is
Nλ (α) or Πλ (α) will be called a meta-literal. based on the idea of forward chaining and in particular does
The semantics of GPL is defined in terms of possibility not allow contrapositive reasoning (e.g. from the rule a ← b
distributions. Let π be a normalized possibility distribution and the fact ¬a we should not derive ¬b). To see how forward
over the set of possible worlds Ω, i.e. π is a mapping from Ω chaining could be enforced using GPL, first note that there
to [0, 1] such that π(ω) = 1 for at least one ω in Ω. Then π is are three ways in which the formula (2) can be satisfied by a
said to satisfy the GPL formula Nλ (α), written π |= Nλ (α), minimally specific model π of ΘP :
iff 1. one of the meta-literals N1 (bi ) is not satisfied by π;
N (α) = min{1 − π(ω) | ω ∈ Ω, ω |= ¬α} ≥ λ 2. one of the meta-literals Π1 (ci ) is not satisfied by π, i.e.
N k1 (ci ) is satisfied by π;
where N denotes the necessity measure from possibility the-
ory. The satisfaction relation |= is extended to arbitrary GPL 3. one of the meta-literals N1 (ai ) is satisfied by π.
formulas in the usual way, i.e. π |= α ∧ β iff π |= α and The first case intuitively corresponds to an answer set which
π |= β, while π |= ¬α iff π 6|= α. A possibility distribution does not include bi , i.e. to a situation in which the rule (1)
π is called a model of a set of GPL formulas Θ if π satis- does not apply. The third case intuitively corresponds to an
fies every formula in Θ. An axiomatization of GPL has been answer set in which ai has been included to make the rule (1)
presented in [7]. satisfied, i.e. to a situation in which ai has been derived using
Let π1 and π2 be two possibility distributions over Ω. We (non-deterministic) forward chaining. The second case, how-
say that π1 is less specific than π2 , written π1 π2 , if ever, intuitively corresponds to a contrapositive inference, i.e.
π1 (ω) ≥ π2 (ω) for all ω ∈ Ω. If π1 π2 and π1 6= π2 , (1) has been satisfied by making ci true. The latter inference
we write π1 ≺ π2 . We say that π is a minimally specific is not allowed in ASP and the second case should thus be ex-
model of a set of GPL formulas Θ if π is a model of Θ and cluded. To this end, we take advantage of the fact that it is
there is no model π 0 of Θ such that π 0 ≺ π. Let α be a GPL only in the second case that certainty degrees other than 0 or
formula and let Θ be a set of GPL formulas. The following 1 are needed. Note that here we do not use degrees for mod-
three inference relations are considered in GPL: elling uncertainty, but intuitively for differentiating between
literals that are assumed to be true and literals that can effec-
standard entailment Θ |= α iff α is satisfied by every
tively be derived. In particular, it turns out that answer sets
model of Θ.
correspond to the minimally specific models of ΘP in which
cautious entailment Θ |=c α iff α is satisfied by all mini- only the certainty degrees 0 and 1 occur. Formally, the re-
mally specific models of Θ. quirement that only these certainty degrees occur is encoded
by the GPL formula Φ, defined as follows: agent knows c then either it knows a or it knows b. When
^ modelling epistemic reasoning, however, it often seems more
Φ≡ N1 (a) ∨ N1 (¬a) ∨ (Π1 (a) ∧ Π1 (¬a)) (3) natural to interpret a ∨ b as “the agent knows that either a or
a∈At b is true (but may not know which is the case)”. This latter
reading was referred to as weak disjunction in [2], where the
The formula Φ expresses that for every atom a, the agent is
inference problems resulting from interpreting ASP rules in
either fully certain about the truth value of a (in which case
this way have been investigated. Using GPL, the ASP rule
N1 (a) ∨ N1 (¬a) holds) or the agent is completely ignorant
a∨b ← c can be modelled as N1 (c) → N1 (a∨b) when weak
about a (in which case Π1 (a) ∧ Π1 (¬a) holds). It turns out
disjunction is considered, and as N1 (c) → N1 (a) ∨ N1 (b)
that the answer sets of P correspond to the minimally specific
otherwise.
models of ΘP that satisfy Φ. In particular, assuming that
k ≥ 2 (i.e. |Λk | ≥ 3), it holds that P has a consistent answer Finally, the use of possibilistic logic enables us to consider
set iff uncertain answer set programs. This is discussed in more de-
ΘP |=b Φ tail in the next section.
Moreover, for each consistent answer set M of P , it holds
that the following possibility distribution πM is a minimally
4 Modelling uncertain answer set programs
specific model of ΘP which satisfies Φ: An uncertain ASP rule is an expression of the form
1 if ω satisfies every literal in M λ : a1 ∨ ... ∨ an ← b1 ∧ ... ∧ bm ∧ not c1 ∧ ... ∧ not cr (4)
πM (ω) =
0 otherwise
where λ is a certainty degree from Λ+ k . An uncertain answer
Conversely, for every minimally specific model π of ΘP set program is a set of uncertain ASP rules. As has been
which satisfies Φ, it holds that the following set of literals observed in [1], there are two fundamentally different ways
Mπ is an answer set of P : to interpret uncertain ASP rules. On the one hand, we may
view λ as reflecting the certainty that the corresponding ASP
Mπ = {l | N (l) = 1} rule is valid. This interpretation leads us to view an uncertain
where N is the necessity measure induced by π. Note that it ASP program as a possibility distribution over classical ASP
follows that a literal l is included in at least one answer set of programs; at the semantic level, we can then consider a pos-
P iff sibility distribution over classical answer sets. On the other
ΘP |=b Φ ∧ N1 (l) hand, we may view λ as reflecting the certainty with which
we can derive the head of the rule, given that its body is sat-
and that that l is included in all answer sets of P iff isfied. This view leads to a semantics in which answer sets
ΘP |=c Φ → N1 (l) correspond to weighted epistemic states, which are modelled
as possibility distributions. Note that a similar distinction is
This means in particular that the main reasoning tasks from often made in first-order probabilistic logics [11] and in first-
ASP correspond to the standard forms of GPL inference. order conditional logics [9]. The former interpretation of un-
This characterization of answer sets in GPL can be straight- certain ASP programs has been considered in [1] and [12].
forwardly generalized to arbitrary propositional combinations The latter interpretation has been considered, among others,
of extended literals. When negation-as-failure in the head is in [17], [2] and [3].
considered, however, our characterization deviates from the Modelling the former type of uncertain ASP programs in
existing characterizations in terms of EL and MBNF. This is GPL would require nested modalities, encapsulating formu-
illustrated in the next example. las of the form (2) with a modality of the form Nλ . As nested
Example 1. We consider a single atom a, in which case modalities are not allowed in GPL, this would require us to
Ω = {∅, {a}}, where we identify models with the set of atoms define a variant of GPL in which every (standard) GPL for-
they make true. Consider the formula a∨not a, and the corre- mula would be encapsulated by a modality, similar to how
sponding GPL encoding N1 (a) ∨ Π1 (¬a). Clearly, the latter propositional formulas are encapsulated in standard GPL. At
formula has a unique minimally specific model π, defined by the semantic level, models would then correspond to possi-
π(∅) = π({a}) = 1. In other words, the only answer set we bility distributions over possibility distributions over possible
find for a ∨ not a is the empty set. However, both the charac- worlds.
terization of ASP in MBNF [14] and the characterization in Here we focus on modelling the second type of uncertain
EL [18] find two answer sets for this example, viz. M1 = ∅ ASP programs in GPL. Let us first consider rules without
and M2 = {a}. negation-as-failure:
As the intuition behind the stable model semantics is based l
on the idea of minimal commitment, the GPL semantics ap- : a1 ∨ ... ∨ an ← b1 ∧ ... ∧ bm
k
pears more natural.
The use of the modal operators Nλ in GPL allows us to The corresponding GPL formula is given by
further extend ASP. In the standard semantics of ASP, rules l
with disjunctions in the head intuitively correspond to a non-
^
N ki (b1 ) ∧ ... ∧ N ki (bm ) → N ki (a1 ) ∨ ... ∨ N ki (an )
deterministic choice, e.g. a ∨ b ← c means that when the i=1
Let P be an uncertain ASP program without negation-as- of a is at least kl (with l even) in every possibilistic answer set
failure and let ΘP be the set of corresponding GPL formu- of P corresponds to:
las. 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 ΘP |=c Φk → N l (a)
k
minimally specific model of ΘP . In absence of negation-as-
We can show that the proposed definition of possibilistic an-
failure, the semantics from [1] moreover coincides with the
swer set corresponds to the reduct-based definition from [2].
semantics from [17].
To deal with negation-as-failure, [2] and [17] rely on a gen-
eralization of the Gelfond-Lifschitz reduct. Consider a rule of 5 Conclusions
the following form: We have shown how generalized possibilistic logic (GPL) can
be used to characterize answer sets without the need for a
l
: a1 ∨ ... ∨ an ← b1 ∧ ... ∧ bm ∧ not c1 ∧ ... ∧ not cr reduct operation, and how this characterization allows us to
k consider a range of different extensions of ASP in a natu-
The reduct of this rule w.r.t. a possibility distribution π, ac- ral way. In particular, the GPL characterization enables us
cording to the semantics from [2], is given by: to define answer sets for arbitrary propositional combinations
of extended literals (while keeping the intuition of minimal
λ : a1 ∨ ... ∨ an ← b1 ∧ ... ∧ bm (5) commitment), for modelling weak disjunction, and for defin-
ing answer sets of uncertain programs.
where λ = min( kl , Π(¬c1 ), ..., Π(¬cr )), for Π the possibility
measure induced by π. The reduct considered in [17] boils Acknowledgment
down to choosing λ = kl if Π(¬c1 ) = ...Π(¬cr ) = 1 and
λ = 0 otherwise (where rules whose certainty is 0 are simply Steven Schockaert has been supported by a grant from the
omitted). Leverhulme Trust (RPG-2014-164).
Using GPL, we can avoid the use of a reduct, if we assume
that k is even and only certainty degrees from { k2 , k4 , ..., 1} References
are used in the uncertain ASP program P . We can always [1] K. Bauters, S. Schockaert, M. De Cock, and D. Vermeir. Se-
ensure that this assumption is satisfied by replacing the set of mantics for possibilistic answer set programs: Uncertain rules
certainty degrees Λk by the set Λ2k , since every element from versus rules with uncertain conclusions. International Journal
l
Λk is equal to 2k for some even value of l. The GPL theory of Approximate Reasoning, 55(2):739–761, 2014.
ΘP corresponding to P is then obtained by replacing every [2] K. Bauters, S. Schockaert, M. De Cock, and D. Vermeir. Char-
rule of the form (4) by the following formula: acterizing and extending answer set semantics using possibility
l
theory. Theory and Practice of Logic Programming, 15(1):79–
^ 116, 2015.
N ki (b1 ) ∧ ... ∧ N ki (bm ) ∧ Π ki (¬c1 ) ∧ ... ∧ Π ki (¬cr )
[3] R. Confalonieri, J. C. Nieves, M. Osorio, and J. Vázquez-
i=1
Salceda. Dealing with explicit preferences and uncertainty in
→ N ki (a1 ) ∨ ... ∨ N ki (an ) answer set programming. Annals of Mathematics and Artificial
(6) Intelligence, 65(2-3):159–198, 2012.
[4] D. Dubois, J. Lang, and H. Prade. Possibilistic logic. In D. N.
where we assume λ = kl . We again need to exclude models D. Gabbay, C. Hogger J. Robinson, editor, Handbook of Logic
which intuitively rely on contrapositive reasoning. Similar as in Artificial Intelligence and Logic Programming, volume 3,
in Section 3, these correspond to minimally specific models pages 439–513. Oxford University Press, 1994.
π which make (6) satisfied by making one of the meta-literals [5] D. Dubois and H. Prade. Generalized possibilistic logic. In
Π ki (¬c1 ) false, i.e. by making a meta-literal N k−i+1 ( c1 ) Proceedings of the 5th International Conference on Scalable
k
true. Noting that k − i + 1 is odd iff i is even, we find that Uncertainty Management, pages 428–432, 2011.
it suffices to exclude models in which certainty degrees kl are [6] D. Dubois and H. Prade. Possibilistic logic - An overview. In
used with l odd. Such models can be avoided by considering D. M. Gabbay, J. Siekmann, and J. Woods, editors, Handbook
the following GPL formula Φk of the History of Logic, Vol. 9: Computational Logic, pages
k
283–342. Elsevier, 2014.
2
^ ^ [7] D. Dubois, H. Prade, and S. Schockaert. Stable models in gen-
Φk ≡ N 2i−1 (a) → N 2ik (a)) eralized possibilistic logic. In Proceedings of the Thirteenth
k
a∈At i=1 International Conference on Principles of Knowledge Repre-
sentation and Reasoning, pages 519–529, 2012.
∧ (N 2i−1 (¬a) → N 2ik (¬a)
k
[8] D. Dubois, H. Prade, and S. Schockaert. Reasoning about
Note that Φ2 is equivalent to the formula Φ defined in (3). We uncertainty and explicit ignorance in generalized possibilistic
propose the following definition: φ is a possibilistic answer logic. In Proceedings of the 21st European Conference on Ar-
set of P iff π is a minimally specific model of ΘP which sat- tificial Intelligence, pages 261–266, 2014.
isfies Φk . As in Section 3, we can then formulate the main [9] N. Friedman, J. Y. Halpern, and D. Koller. First-order condi-
reasoning tasks for possibilistic ASP in terms of standard en- tional logic for default reasoning revisited. ACM Transactions
tailment in GPL. For example, checking whether the certainty 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 Inter-
national 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. Wö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 Proceed-
ings of the 24th International Conference on Logic Program-
ming, 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. Stéphan, and C. Lefè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 Ar-
tificial Intelligence, 47:3–41, 2006.