=Paper=
{{Paper
|id=None
|storemode=property
|title=Preferences
and Priorities in ASP
|pdfUrl=https://ceur-ws.org/Vol-857/paper_f04.pdf
|volume=Vol-857
|dblpUrl=https://dblp.org/rec/conf/cilc/CostantiniF12
}}
==Preferences
and Priorities in ASP==
https://ceur-ws.org/Vol-857/paper_f04.pdf
Preferences and Priorities in ASP
Stefania Costantini1 and Andrea Formisano2
1
Università di L’Aquila
Dipartimento di Ingegneria e Scienze dell’Informazione e Matematica (DISIM)
Via Vetoio Loc. Coppito, I-67010 L’Aquila, Italy
stefcost@di.univaq.it
2
Università di Perugia
Dipartimento di Matematica e Informatica
via Vanvitelli, 1, I-06123 Perugia, Italy
formis@dmi.unipg.it
Abstract. In this paper we extend our previous work concerning preferences in
Answer Set Programming (ASP), and integrate this work with PDL, a well-
known approach to answer set optimization. We thus obtain a powerful language
for expressing preferences in ASP.
Key words: Answer set programming, preferences, priorities.
1 Introduction
Logic programming under the answer set semantics (Answer Set Programming, for
short ASP) is nowadays a well-established programming paradigm, with applications in
many areas, including problem solving, configuration, information integration, security
analysis, agent systems, semantic web, and planning (see among many [2, 1, 19, 24, 16]
and the references therein).
As ASP has proved useful in formalizing many forms of commonsense reasoning,
and as in turn many forms of commonsense reasoning rely more or less explicitly upon
some form of preferences, preferential reasoning has also been studied in relation to
ASP (cf., e.g., [14, 6, 3, 5, 4, 8, 10]).
In this paper we consider the work of [4] about answer set optimization, that pro-
poses the language PDL for describing complex preferences among answer sets, so as
to rank answer sets according to several criteria, and find the optimal ones. We compare
the basic building blocks of PDL, preference rules, with RASP rules that we have pro-
posed in [8, 10]. First we show that our rules fit into the PDL framework to which they
bring some useful extension. Then, elaborating on our past work and on principles dis-
cussed in [25, 20], we further improve the forms of preferences that can be expressed.
The reader may refer to e.g., [14, 6, 4, 8, 10] and to the references therein for recent
overviews and discussion of the many existing approaches to preferences in ASP and
more generally in Computational Logic. In [4, 8, 10] the relationship of the approaches
treated here with related work is also widely discussed.
The paper is organized as follows. In Section 2 we briefly introduce Answer Set
Programming and PDL, and in Section 3 we illustrate RASP. In Section 4 we propose
how the two approaches could be usefully integrated, and in Section 5 we propose
extensions to the language for expressing preferences. Finally, in Section 6 we conclude.
2 Background on ASP and PDL
Answer Set Programming is the well-established logic programming paradigm adopt-
ing Datalog programs with default negation under the answer set semantics, briefly
discussed below.
A program Π in this setting (cf. [17, 18]) is a collection of rules of the form
H ← L1 , . . . , Lm , not Lm+1 , . . . , not Lm+n .
where H is an atom, m ≥ 0 and n ≥ 0, not is default negation and each Li is either
an atom or the classical negation (also called strong negation) of an atom (as defined
in [18]). Atoms and their classical negation and literals not Li will be called in the fol-
lowing “ASP literals”, to make a distinction w.r.t. the extensions that will be proposed.
The left-hand side and the right-hand side of the clause are called head and body,
respectively. A rule with empty body is called a fact. A rule with empty head is a
constraint, where a constraint of the form
← L1 , ..., Ln .
states that ASP literals L1 , . . . , Ln cannot be simultaneously true.
Various extensions to the basic paradigm exist, that we do not consider here as they
are not essential in the present context.
In the rest of the paper, whenever it is clear from the context, by “a (logic) program
Π” we mean an answer set program (ASP program) Π, and we will implicitly refer
to the “ground” version of Π. The ground version of Π is obtained by replacing in all
possible ways the variables occurring in Π with the constants occurring in Π itself, and
is thus composed of ground atoms, i.e., atoms which contain no variables.
The answer sets semantics [17, 18] considers logic programs as sets of inference
rules (more precisely, default inference rules). Alternatively, one can see a program as
a set of constraints on the solution of a problem, where each answer set represents a
solution compatible with the constraints expressed by the program.
Consider the simple program {q ← not p. p ← not q.}. For instance, the first rule
is read as “assuming that p is false, we can conclude that q is true.” This program has
two answer sets. In the first one, q is true while p is false; in the second one, p is true
while q is false.
Given a subset M of BΠ that does not contain both A and ¬A for any atom A,
M is an answer set of Π if it coincides with the least model of the reduct P M of
P with respect to M . This reduct is obtained by deleting from Π all rules containing a
condition not a, for some a in M , and by deleting all negative conditions from the other
rules. Answer sets are minimal supported models. Referring to the original terminology
of [17], answer sets are sometimes called stable models. As usual, a set of atoms S
satisfies a rule if S satisfies its head H, i.e., H ∈ S, whenever it satisfies the body, i.e.,
all positive conditions are in S and none of the negative conditions is in S.
Unlike other semantics, a program may have several answer sets, or may have no
answer set, because conclusions are included in an answer set only if they can be justi-
fied. The following program has no answer set: {a ← not b. b ← not c. c ← not a.}.
The reason is that in every minimal model of this program there is a true atom that de-
pends (in the program) on the negation of another true atom, which is strictly forbidden
in this semantics, where every answer set can be considered as a self-consistent and
self-supporting set of consequences of given program. A program with no answer sets
is called inconsistent. In the ASP paradigm, each answer set is seen as a solution of
given problem, encoded as an ASP program. To find these solutions, an ASP-solver is
used. Several solvers have became available, see [23], and can be freely downloaded by
potential users.
The expressive power of ASP and its computational complexity have been exten-
sively investigated. The interested reader can refer, for instance, to [12]. The reader can
also see [2] and [15], among others, for a presentation of ASP as a tool for declara-
tive problem-solving. For the applications of ASP, the reader can refer for instance to
[2, 1, 19, 24, 16].
PDL is a language aimed at describing complex preferences among answer sets.
The approach has been proposed in [4] and further generalized in [7]. The basic in-
gredients of PDL, as introduced in [4, Def. 5], are the so-called preference rules. A
preference rule has the form
h1 > · · · >hk ← L1 , . . . , Lm , not Lm+1 , . . . , not Lm+n . (1)
where each hi is of the form Ci :pi and Ci is a Boolean combination, that is, a formula
built of atoms by means of disjunction, conjunction, strong and default negation, while
pi is an integer number, intended to be the “weight” or the “penalty” associated to Ci ,
i.e., a measure of the degree of (dis)satisfaction in the choice of that option. A preference
rule thus establishes a ranking of the answer sets, or, more precisely, a preorder between
answer sets that satisfy the body of the rule.
Preference rules constitute the sub-language PDLp of PDL made of the simplest
PDL expressions. In turn, complex PDL expressions can be built out of PDLp expres-
sions by means of operators that specify how to impose and order upon answer sets of
given programs based upon the preorders expressed as base step by the preference rules
(then, nested PDL expressions are also allowed). Among the PDL operators there are
Pareto ordering, lexicographic ordering and others. More specifically, we recall the
following definition from [4]:
Definition 1. [Def. 7 of [4]] PDLp and PDL expressions are inductively defined as
follows:
1. if r is a preference rule, then r ∈ PDLp ,
2. if e1 , . . . , ek are expressions in PDLp , then (psum e1 , . . . , ek ) ∈ PDLp ,
3. if r ∈ PDLp then r ∈ PDL,
4. if e1 , . . . , ek are expressions in PDLp , then (incr e1 , . . . , ek ), (rincr e1 , . . . , ek ),
(card e1 , . . . , ek ), and (rcard e1 , . . . , ek ) are in PDL,
5. if e1 , . . . , ek are in PDL, then (pareto e1 , . . . , ek ) and (lex e1 , . . . , ek ) are in
PDL.
As said before, PDL expressions allow one to specify a rank among answer sets accord-
ing to several criteria (e.g., Pareto ordering). Optimal answer sets w.r.t. such a ranking,
are said to be solutions of the answer set optimization problem as defined below.
Definition 2. [Def. 4 of [4]] An answer set optimization problem (AOP) is a pair O =
(P, prex ) where P is a program and prex a PDL expression.
A solution of O is an answer set of P which is optimal according to the preorder
represented by prex .
Hence, a solution of an answer set optimization problem is a non-dominated answer
set, that is, an answer set such that no strictly better answer set exists. (The reader is
referred to [4] for a more detailed treatment of PDL.)
The approach to “qualitative preferences” based on PDL is particularly interesting
because several existing preference handling methods turn out to be special cases of
it, where it is now well-known that many AI problems have natural formulations as
optimization problems. An advantage of the approach is that PDL expressions can be
compiled into logic programs that can be used as tester programs in a methodology for
finding optimal answer sets. Moreover, as a further demonstration of its applicability,
the approach has been generalized from ASP to many other optimization contexts in [7].
3 Previous Work on Preferences Revisited
In our work on RASP (ASP with Resources and Preferences) [9, 8, 11] we have pro-
posed an approach to expressing preferences in ASP programs, and then [10] also in
Weight Constraints (which are a well-known useful construct of ASP [21, 22]).
In particular, we allow any occurrence of a positive literal in ASP rules to be re-
placed by a p-list, defined below. p-lists make sense in the head of a rule, to state what
one prefers to derive (equivalently, which atom one prefers to be included in an answer
set). However, p-lists make sense in the body of rules as well, to specify which condi-
tions one would prefer to exploit for reaching a conclusion. As seen below, preferences
in the body are particularly interesting when they are conditional, that is, they should
be applied only when some precondition is satisfied.
Definition 3. Let s1 , . . . , sk (k > 0) be either distinct constants or distinct atoms.
Then,
– a basic preference-list (p-list, for short) is an expression of the form s1 > · · · >sk .
Each component si (i ≤ k) has degree of preference i in the p-list.
– a conditional p-list (cp-list, for short) is an expression of the following form:
(r pref when L1 , . . . , Ln ),
where r = s1 > · · · >sk is a p-list and L1 , . . . , Ln are ASP literals.
Intuitively, a cp-list (r pref when L1 , . . . , Ln ) specifies that if all L1 , . . . , Ln are
satisfied, then the choice among the si s occurring in r is ruled by the preference ex-
pressed through r. Otherwise, if any of the Li is not satisfied, then no preference is
expressed.
In general, there might be cases in which useful (conditional) preferences are not
expressible as a linear order on a set of alternatives. This may originate from lack of ade-
quate knowledge or expertise in modeling a piece of knowledge, or from incapability to
completely describe total comparative relations, in presence of uncertainty. Moreover,
preferences might depend on specific contextual conditions that are not foreseeable in
advance.
P-sets are a generalization of p-lists that allows one to use any binary relation (not
necessarily a partial order) in expressing (collections of alternative) p-lists.
Definition 4. Let q1 , . . . , qk be k > 0 atoms and let pred be a binary predicate. A p-set
is of the form
{q1 , . . . , qk | pred }.
Predicate pred is supposed to be defined elsewhere in the program where the p-set
occurs. Considering any given model of the program, such a binary predicate is intended
to (possibly) have pairs of the form hqi , qj i as elements of its extension. This allows the
programmer to describe preferences among the qi s, that are computed contextually to
any specific answer set. The intuitive semantics of a p-set can be grasped by considering
a particular extension for the predicate pred (namely, a set of pairs ha, bi assumed to be
true in a certain situation, that is, in a certain model of the program). Let X be the set of
atoms {q1 , . . . , qk }. Consider the binary relation R ⊆ X × X obtained by restricting to
X the extension of pred . R is interpreted as a preference relation over X: namely, for
any qi , qj ∈ X the fact that hqi , qj i ∈ R models a preference of qi over qj .
In general, there might exist many total orders on the set {q1 , . . . , qk } that are com-
patible (i.e., do not contradict) such a generic relation R. Any of these total orders
describes one different, alternative, p-list. Hence, simple p-lists, as introduced in Defi-
nition 3, are particular cases of p-sets, obtained when R describes a total order.
As mentioned, R does not need to be a partial order, e.g., for instance, it may imply
cycles. In such cases, those resources that belong to the same cycle in R are considered
equally preferable. On the other hand, R might be a partial relation. So, there might
exist elements of X that are incomparable. In this paper, for the sake of simplicity we
assume that R defines a partial order.
Compound preferences are allowed in RASP. For lack of space in this paper we do
not consider compound preferences and thus we do not report the full definition, how-
ever p-lists (and cp-lists) are generalized so that preferences can be expressed among
sets.
A RASP rule (for short r-rule) has the following form, whereas a RASP program is
a set of RASP rules:
Definition 5. Let an a-literal be either an atom or a p-list, a cp-list, or a p-set, and let
an r-literal be either an ASP literal or an a-literal. An r-rule γ has the form
H ← B1 , . . . , B m . (2)
where B1 , . . . , Bm are r-literals, H is either an atom or an a-literal (a generalization
where H is a set of a-literals is easily feasible, though not treated here).
Let a proper RASP rule be a RASP rule involving a-literals (otherwise a RASP rule
is identical to an ASP rule).
Definition 6. Let Π Pref be the subprogram of RASP program Π composed of all the
proper RASP rules occurring in Π.
The following example, related to preparation of desserts, should demonstrate the
expressivity of RASP. In preparing the dessert, one might employ, e.g., either skim-milk
or whole milk. The cp-list
skimmilk > wholemilk pref when diet
states that, if on a diet, the former is preferred. Then, to spice the dessert, one would
choose, by the p-set
{chocolate, nuts, coconut | less caloric},
the least caloric among chocolate, nuts, and coconut.
Previous examples show instances of “extrinsic preferences”, i.e., preferences which
come with some kind of “reason”, or “justification” [20]. Notice that, in RASP, extrin-
sic preferences may change even non-monotonically as the knowledge base evolves in
time, as the justification can be any conjunction of literals.
Below is a RASP program fragment representing dessert preparation with the pref-
erences outlined above. Notice that the preference among the ingredients chocolate,
nuts, and coconut, occurring in the p-set has to be determined by referring to the exten-
sion that the predicate less caloric has in the particular model at hand. The first rule
states that if one has eggs and sugar, milk (preferably skim milk if one is on a diet)
and one of chocolate, nuts and coconut (choosing the less caloric) one can prepare ei-
ther ice-cream or zabaglione, but preferably one would prepare ice-cream (consider that
some constraint stated elsewhere in the program might forbid any of the two).
icecream > zabaglione ← egg, sugar,
(skimmilk > wholemilk pref when diet),
{chocolate, nuts, coconut | less caloric}.
less caloric(X, Y ) ← calory(X, A), calory(Y, B), A < B.
calory(nuts, 2).
calory(coconut, 3).
calory(X, Y ) ← ...
In full RASP, resource management is provided, so that one can, in the above ex-
ample, associate quantities to the various produced and consumed items. We do not
consider this feature here, so in the rest of the paper we will implicitly consider RASP
programs without quantities. In summary, in the rest of the paper we consider RASP
programs without quantities and without compound preferences.
We may notice that RASP rules can be seen (within the above restrictions) as a
particular case (on the one hand) and a generalization (on the other hand) of preference
rules as introduced in Definition 1.
RASP rules are a special case of preference rules in that arbitrary formulas are not
allowed in the elements of p-lists, and the (implicit) weight is always 1. They are a
generalization, in that various forms of conditional preferences are allowed, also in the
body of rules. We showed in [8] how RASP rules can be restated in terms of rules with
preferences expressed only in the head (we considered precisely the LPOD approach [3,
5]). The re-writing however was not trivial and involved transforming a single RASP
rule into a set of rules. In the following sections we intend first to show how RASP
fits into the PDL framework. Then, elaborating on our past work and on principles
discussed in [25, 26, 13, 20], we further improve the forms of preferences expressible
in preference rules.
4 PDL and RASP: Integration
We may notice that a PDL program can be added on top of an ASP program, and as
said above it produces an ordering of the answer sets in terms of given preferences. The
advantage is that the same ASP program may be transformed, by adding different PDL
parts, into different optimization problems. The disadvantage is that a programmer can-
not use complex preferences within the ASP program. RASP is thus complementary
to PDL: in fact, in an integration part of the preferences (in the form of RASP rules)
might be expressed within the program, and part in the external (one may say “upper”)
PDL layer.
The integration with RASP would then bring to PDL the advantage of more general
and flexible preference rules definable directly in the ASP program. However, RASP
would profit from being integrated into PDL as the method of eliciting partial orders
from preference rules and combining them (based upon other PDL rules) allows for
further significant extensions, like the one that we propose below. In the integration,
semantics of RASP programs can be defined differently from [9, 8, 11]. In fact, a RASP
program Π can be transformed into an ASP program Π 0 where each r-rule (as defined
in Definition 2) is replaced by a set of rules as defined below.
Definition 7. An ASP rule γ 0 derived from RASP rule γ
H ← B1 , . . . , Bm .
is of the form
A ← L1 , . . . , Lm .
where: A = H if H is a ASP atom, and for i ≤ m Li = Bi if Bi is a ASP literal;
whenever H or, respectively, Bi (for i ≤ m) is a p-list r = s1 > · · · >sk or a cp-list
(r pref when L1 , . . . , Ln ), then A = sj , or, respectively, Li = sj , j ≤ k; if Bi is a
p-set {q1 , . . . , qk | pred }, then Li = qr , r ≤ k.
Hence, derived rules are obtained by non-deterministically selecting one of the options
among the a-literals. By relying on the usual notion of satisfaction of (ground) ASP
rules, we can state the following notion of satisfaction for derived rules.
Definition 8. Given a set of atoms S and a RASP rule γ, S satisfies γ if and only if S
satisfies some γ 0 derived from γ. In this case we write S |= γ.
The next definition will be useful in what follows.
Definition 9. Given RASP program Π, the program Π 0 composed of all the derived
rules obtainable from rules of Π, is called the ASP program derived from Π.
We now extend PDL by including proper RASP rules in PDL expressions. (Recall
that PDL expressions are built out of basic PDLp expressions by means of preference
operators.) The following definition introduce a further case to extend Definition 1:
Definition 10 (Extension of Def. 1). PDLp and PDL expressions are inductively
defined as in Definition 1, by considering also the following case:
10 . If r is a proper RASP rule then r ∈ PDLp .
The new semantics for RASP programs, also corresponding to an extension to PDL
that includes proper RASP rules as preference rules, can be defined as follows (cf.,
Definition 2).
Definition 11. Given RASP program Π, an extended answer set optimization problem
(EAOP) is a pair OE = (Π 0 , prex ) where Π 0 is the ASP program derived from Π and
prex is a PDL expression involving among the preference rules all rules of Π Pref .
What remains to be done is to extend the semantics of PDL expressions defined
in [4, pp. 4-5] so as to accommodate RASP rules. This semantics introduces a pre-
order on answer sets (i.e., a reflexive and transitive relation) that specifies which answer
set is preferred over which other. Below we enrich the definition of [4]. Notice that
given expression prex , pen(S , prex ) is the penalty associated to the expression prex
w.r.t. answer set S, and Ord (prex ) is the preorder associated with prex . The objective
of the definition is to state in which cases we have (S1 , S2 ) ∈ Ord (prex ) based on
pen(S1 , prex ) and pen(S2 , prex ). By abuse of notation, we consider a-literals (which
are not in themselves PDLp expressions) as a base case of Ord (prex ).
Definition 12. Given RASP program Π and EAOP (Π 0 , prex ), and given the answer
sets of Π 0 S, S1 , S2 (clearly, if Π 0 has none or just one answer set the EAOP is trivially
solved) then, in addition to what defined in [4], we define the following.
– If prex is a p-list of the form s1 > · · · >sk then pen(S , prex ) = j where j =
min{i|S |= si }. pen(S , prex ) = ∞ otherwise.
– If prex is a cp-list of the form s1 > · · · >sk pref when L1 , . . . , Ln then pen(S , prex ) =
j where j = min{i|S |= si } if S |= L1 , . . . , Ln . pen(S , prex ) = ∞ otherwise.
– If prex is a p-set of the form {q1 , . . . , qk | pred } then pen(S , prex ) = j where
j = min{i|∀j ≤ k, j 6= i, S |= pred (qi , qj )}. pen(S , prex ) = ∞ otherwise.
– Given a RASP rule r, we have (S1 , S2 ) ∈ Ord (r ) iff for each a-literal s occurring
in r, pen(S1 , s) ≤ pen(S2 , s).
Notice that in the above definition we apply a lexicographic ordering within the
preorders induced by the a-literals occurring in a RASP rule. Other choices would be of
course possible. We might state more generally that (S1 , S2 ) ∈ Ord (r ) iff (S1 , S2 ) ∈
Ord (Op a1 , . . . , an ) where Op is one of the ordering operators provided by PDL,
applied to the a-literals a1 , . . . , an occurring in r (i.e., to the preorders induced by them).
It is easy to extend complexity results reported in [4] to our extended setting. I.e.,
finding solutions to AOP’s is a difficult problem but our extensions, though providing
features that may help programmers to declaratively encode the situation at hand, do
not add further complexity.
Theorem 1. Let O = (Π 0 , prex ) be an extended answer set optimization problem and
S an answer set of Π 0 . Deciding whether S is a solution of O is coNP-complete.
Theorem 2. Let O = (Π 0 , prex ) be an extended answer set optimization problem and
A be either an atom or the “classical negation” of an atom. Deciding whether there is
a solution S of O such that A ∈ S is Σ2P -complete.
5 Extensions
As discussed in [25, 26, 13, 20], one may prefer one option over others for reasons
of various kinds: from general principles to specific facts. Several reasons or criteria
may justify one single preference, where however criteria are often ordered according
to some kind of priority. By adapting the example proposed in [20], if one wants to
buy a house (s)he may consider several aspects, say the price, the neighborhood where
the house is situated, and the quality of the building. These aspects may be ordered
according to their importance, i.e., they are given a certain priority. In [20], a method
is proposed to elicit a strict order among options from a given priority sequence of the
form, say,
C1 (X) >> C2 (X) >> . . . >> Cn (X)
i.e., in the above example,
good neighborhood(X) >> reasonable price(X) >> good quality(X).
A way of combining preferences is also proposed in [20, Def. 3.2]. This method is
reported below, and adopted in the present setting.3 Given a priority sequence of length
n, strict preference of x over y between two objects x and y, Pref (x, y), is defined,
according to [20], as follows:
Pref 1 (x, y) ::= C1 (x) ∧ ¬C1 (y)
Pref k+1 (x, y) ::= Pref k (x, y) ∨ (Eq k (x, y) ∧ Ck+1 (x) ∧ ¬Ck+1 (y)), k < n
Pref (x, y) ::= Pref n (x, y)
where the auxiliary binary predicate Eq k (x, y) is the conjunction of equivalences
(C1 (x) ↔ C1 (y)) ∧ · · · ∧ (Ck (x) ↔ Ck (y)).
In simple words, x is preferred over y whenever there is at least one of the Ci s that
x enjoys while y does not. Consequently, if both x and y enjoy the Ci s in the same way,
none of them is preferred over the other.
Referring to the example, one may find it very important to live in a good neighbor-
hood, of some importance to keep the cost reasonable and less important (but relevant
anyway) to buy a house in a building of good quality. For instance, if we have two
houses h1 and h2 which are both in a good neighborhood but none of them has a rea-
sonable price, then the one of good quality will be preferred. If both are of good quality,
3
Refining both the form and the meaning of priority sequences in the direction of more flexibil-
ity can be a subject of future work.
they will be equally preferred. If both are in a good neighborhood, and the first one
has reasonable price while the other one does not, then the former will be preferred,
whatever the quality of both. RASP, in the context of the integration with PDL, might
be extended so as to allow rules such as the following:
buy(X) ← house(X),
good neighborhood >> reasonable price >> good quality.
In this paper we limit the conclusion of such a rule to be an atom (as defined in
ASP), while in perspective it might be an a-literal. The priority sequence is defined over
predicates, each of which is applicable on the variables occurring in the head (thus, if
the predicate in the head is n-ary, so are the predicates in each priority list). For the sake
of simplicity, below we restrict ourselves to unary predicates. The atom in the head, in
the ground version of the rule, becomes a disjunction, one for each option that can be
possibly chosen. In the example, if house(X) returns, e.g., h1 , h2 and h3 , the ground
version of the rule will be (where, as customary in ASP, ’;’ indicates disjunction):
buy(h1 ) ; buy(h2 ) ; buy(h3 ) ←
good neighborhood >> reasonable price >> good quality.
We extend the definition of RASP rules as follows. As before, in the definitions we
refer to ground atoms and rules.
Definition 13. A priority list is an expression of the form
p1 >> . . . >> pn
where each of the pi ’s is a predicate.
Definition 14. A RASP priority rule ρ is of the form:
H ← B1 , . . . , Bm .
where B1 , . . . , Bm are either r-literals or priority lists, and H is a disjunction of atoms
of the form h(c1 ); . . . ; h(cr ), r ≥ 0, where the ci s are constants.
As far as non-ground rules are considered, a ground priority rule can be obtained
from a non-ground rule of the form h(X) ← d(X), B1 , . . . , Bm where d(X) provides
the values for instantiating X (d might be for instance a domain predicate.4 )
We define a notion of degree of satisfaction of a priority list in the context of a set
of atoms by rephrasing the above-mentioned definition introduced in [20].
Definition 15. A priority list l = p1 >> . . . >> pn is satisfied with degree k w.r.t. a
disjunction of atoms d = h(c1 ); . . . ; h(cr ) and a set of atoms S (we write sat(S, l, d) =
k) iff S |= h(ci ), i ≤ r, where S |= p1 (ci ) ∧ . . . ∧ S |= pk (ci ) and 6 ∃cj , j 6= i such that
S |= h(cj ) and S |= p1 (cj ) ∧ . . . ∧ S |= pt (cj ) with t > k.
4
The subset of given program defining domain predicates consists of domain rules, syntactically
restricted so as to admit a unique answer set that should be relatively efficiently computable.
All the other rules in the program are required by most answer set solvers to be domain-
restricted in the sense that every variable in a rule must appear in a domain predicate which
occurs positively in the body of the rule.
To accommodate priority lists, we further extend Definition 12 as follows.
Definition 16.
– Given a RASP priority rule r with head d, we have (S1 , S2 ) ∈ Ord (r ) iff for each
a-literal s occurring in r, pen(S1 , s) ≤ pen(S1 , s) and for each priority list l
occurring in r, sat(S1 , l, d) ≥ sat(S2 , l, d).
6 Concluding Remarks
In this paper we coped with expressing preferences in Answer Set programs. In par-
ticular, we have proposed an integration of RASP (that has been defined in previous
work) and PDL, previously proposed by G. Brewka. We argued that both approaches
may profit from the integration in that RASP fits into the more general semantic PDL
framework, and RASP enriches PDL with more expressive preference rules. To show
this, we have further extended the formalism by means of priority rules that express a
kind of preference that could not be directly expressed before, without affecting com-
plexity. Precisely, deciding whether an answer set S is a solution of an answer set opti-
mization problem is coNP-complete, and deciding whether there is a solution implying
given literal l is ΣP2 − complete. Immediate future work concerns the implementation
of the integrated approach. Other future work can be related to further enriching the
language for expressing preferences.
References
[1] C. Anger, T. Schaub, and M. Truszczyński. ASPARAGUS – The Dagstuhl Initiative. ALP
Newsletter, 17(3), 2004. See http://asparagus.cs.uni-potsdam.de.
[2] C. Baral. Knowledge representation, reasoning and declarative problem solving. Cam-
bridge University Press, 2003.
[3] G. Brewka. Logic programming with ordered disjunction. In Proc. of AAAI-02, Edmonton,
Canada, 2002.
[4] G. Brewka. Complex preferences for answer set optimization. In D. Dubois, C. A. Welty,
and M.-A. Williams, editors, Principles of Knowledge Representation and Reasoning:
Proc. of the Ninth International Conference (KR2004), June 2-5, 2004, pages 213–223,
2004.
[5] G. Brewka, I. Niemelä, and T. Syrjänen. Logic programs with ordered disjunction. Com-
putational Intelligence, 20(2):335–357, 2004.
[6] G. Brewka, I. Niemelä, and M. Truszczyński. Preferences and nonmonotonic reasoning.
AI Magazine, 29(4), 2008.
[7] G. Brewka, M. Truszczynski, and S. Woltran. Representing preferences among sets. In
M. Fox and D. Poole, editors, Proc. of the Twenty-Fourth AAAI Conference on Artificial
Intelligence, AAAI 2010, Atlanta, Georgia, USA, July 11-15, 2010, pages 273–278. AAAI
Press, 2010.
[8] S. Costantini and A. Formisano. Modeling preferences and conditional preferences on
resource consumption and production in ASP. J. of Algorithms in Cognition, Informatics
and Logic, 64(1):3–15, 2009.
[9] S. Costantini and A. Formisano. Answer set programming with resources. J. of Logic and
Computation, 20(2):533–571, 2010.
[10] S. Costantini and A. Formisano. Weight constraints with preferences in ASP. In Proc. of
LPNMR’11, number 6645 in LNCS, pages 229–235. Springer, 2011.
[11] S. Costantini, A. Formisano, and D. Petturiti. Extending and implementing RASP. Funda-
menta Informaticae, 105(1-2):1–33, 2010.
[12] E. Dantsin, T. Eiter, G. Gottlob, and A. Voronkov. Complexity and expressive power of
logic programming. ACM Computing Surveys, 33(3):374–425, 2001.
[13] D. de Jongh and F. Liu. Preference, priorities and belief. In T. Grüne-Yanoff and S. O.
Hansson, editors, Preference Change, Theory and Decision Library, pages 85–108. 2009.
[14] J. Delgrande, T. Schaub, H. Tompits, and K. Wang. A classification and survey of pref-
erence handling approaches in nonmonotonic reasoning. Computational Intelligence,
20(12):308–334, 2004.
[15] A. Dovier, A. Formisano, and E. Pontelli. An empirical study of constraint logic program-
ming and answer set programming solutions of combinatorial problems. J. of Experimental
and Theoretical Artificial Intelligence, 21(2):79–121, 2009.
[16] M. Gelfond. Answer sets. In Handbook of Knowledge Representation, chapter 7. Elsevier,
2007.
[17] M. Gelfond and V. Lifschitz. The stable model semantics for logic programming. In Proc.
of 5th ILPS conference, pages 1070–1080, 1988.
[18] M. Gelfond and V. Lifschitz. Classical negation in logic programs and disjunctive
databases. New Generation Computing, 9:365–385, 1991.
[19] N. Leone. Logic programming and nonmonotonic reasoning: From theory to systems and
applications. In C. Baral, G. Brewka, and J. Schlipf, editors, Proc. of the 9th International
Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR’07), volume
4483 of LNCS, page 1. Springer, 2007.
[20] F. Liu. Von Wright “The Logic of Preference” revisited. Synthese, 175(1):69–88, 2009.
[21] I. Niemelä, P. Simons, and T. Soininen. Stable model semantics of weight constraint rules.
In Proc. of the 5th International Conference on Logic Programming and Nonmonotonic
Reasoning (LPNMR’99), number 1730 in LNCS, pages 317–331. Springer, 1999.
[22] P. Simons, I. Niemelä, and T. Soininen. Extending and implementing the stable model
semantics. Artificial Intelligence, 138(1-2):181–234, 2002.
[23] Solvers URLs. Clasp: http://potassco.sourceforge.net;
Cmodels: http://www.cs.utexas.edu/users/tag/cmodels;
DLV: http://www.dbai.tuwien.ac.at/proj/dlv;
Smodels: http://www.tcs.hut.fi/Software/smodels.
[24] M. Truszczyński. Logic programming for knowledge representation. In V. Dahl and
I. Niemelä, editors, Proc. of the 23rd International Conference on Logic Programming
(ICLP’07), volume 4670 of LNCS, pages 76–88. Springer, 2007.
[25] J. van Benthem, P. Girard, and O. Roy. Everything else being equal: A modal logic for
ceteris paribus preferences. J. Philos. Logic, 38:83–125, 2009.
[26] J. van Benthem and F. Liu. Dynamic logic of preference upgrade. J. of Applied Non-
Classical Logics, 17(2):157–182, 2007.