In this paper, we extend our previous work where we have introduced the possibility of defining and using resources in ASP. In fact, in P-RASP (Resourced ASP with Preferences) one can define resources with their amounts. Available resources can be used for producing other resources, thus consuming either all or just a part of the available amount. The remaining amount, if any, can be used in a different way. It is possible to express preferences about which resources should be either consumed or produced. Moreover, conditional preferences, of three different forms, allow one to express preferences according to certain conditions, that are to be evaluated “dynamically.”, namely, with respect to the specific answer set at hand. The semantic rendering of P-RASP with conditional preferences is in terms of plain P-RASP, though the translation is not straightforward and thus the new features are not syntactic sugar.
Recently (cf. [
We are convinced that many of the applications of ASP (that nowadays
include declarative problem solving, configuration, information integration,
security analysis, agent systems, semantic web, and planning for which the reader
can see, e.g., [
In the present paper, we discuss the possibility of expressing contextual preferences i.e., preferences that apply only if certain conditions hold. This extension can be particularly useful in applications when preferences may depend on contextual elements that are not foreseeable in advance.
Let us briefly recall syntax and intended semantics of P-RASP programs through a simple example. We will then modify such example to informally introduce preferences. A P-RASP program is composed of r-facts and r-rules, where numbers associated with the heads of r-facts and rules indicate which amount of a certain resource is respectively: – available, in case of r-facts; – produced, in case of r-rules, where production can take place if required resources are either available or have been produced.
As resources that are either available or produced can be in turn consumed, then numbers (quantities) can be associated to atoms occurring in the bodies of r-rules as well, as shown below.
The example concerns the preparation of desserts. We may notice that different solutions stem in this case from the fact that, with the available ingredients, one may prepare either a cake or an ice-cream, but not both. Atoms of the form q:a are called amount atoms, where the amount symbol a states which is the quantity of that resource which is either produced (if the amount atom is in the head of a rule), or consumed (if it is in the body), or available (if it is a fact), respectively. In P-RASP one can specify that any given rule can be repeatedly fired, where the writing [N -M ]: prefixed to a rule indicates the minimum N and the maximum M of times a rule can be used (here, to produce from 1 to 3 cakes). Clearly, a suitable quantity of required resources must be available for each firing of a rule. cake:1 ← egg :3, flour :4, sugar :3. ice cream:1 ← egg :2, sugar :2, milk :2. egg :3. flour :8. sugar :6. milk :3.
In general, usual ASP literals (possibly involving negation-as-failure) may occur in rules. Semantics of a P-RASP program is determined by interpreting usual literals as in ASP (i.e., by exploiting stable model semantics) and amount-atoms in an auxiliary algebraic structure (that supports operations and comparisons).
RASP already offers some constructs that can be used to express basic forms
of preferences on rule firing and resource consumption/production by
specifying whether the firing of a rule, whenever sufficient resources are available, is
either forced or optional. These and other features are fully dealt with in [
In this paper, we introduce conditional preferences of various kinds. Assume, e.g., that one prefers skim milk when on a diet. The last rule above may become: ice cream:1>zabaglione:2 ← (skim milk :2>whole milk :2 IF diet ), egg :2, sugar :3. If diet does not hold, then the preference list reduces to a disjunction, i.e. either skim milk or whole milk can be indistinctly used. The above rule becomes equivalent to the couple of rules: ice cream:1>zabaglione:2 ← skim milk :2, egg :2, sugar :3.
ice cream:1>zabaglione:2 ← whole milk :2, egg :2, sugar :3.
This generalizes to several p-lists, that we now call cp-lists, for “conditional” p-lists, like in the example below: (ice cream:1>zabaglione:2 IF summer ) ← (skim milk :2>whole milk :2 IF diet ), egg :2, sugar :3.
Assume now that one would like to add either vanilla or cinnamon, but this is not possible in case of allergy. The example above may become: ice cream:1>zabaglione:2 ← (skim milk :2>whole milk :2 IF diet ), (vanilla:1>cinnamon:1 WHEN not allergy ), egg :2, sugar :3.
If allergy holds, and then the WHEN condition is false, the p-list is ignored. This means that a WHEN cp-list specifies the additional level of preference which implies including or not the given p-list according to the condition.
Moreover, as we will see in Section 5, in both IF and WHEN cp-lists one may order the inner p-list according to the value of a binary predicate: in the above examples, among the ingredients listed in a p-list one will be able to prefer, e.g., the less caloric, the less expensive, the one with most vitamins, etc. This is in our opinion a significant improvements of wide applicability.
The plan of the paper is the following: in Sections 2 and 3 summarize the basic P-RASP syntax and semantics, without considering conditional preferences. In Section 4 conditional preferences are introduced, and their semantic rendering in terms of plain P-RASP is discussed. In Section 5, a further extension is defined which allow preferences to be dynamically established according to the value of a binary predicate which determines an order among the alternatives. The semantic rendering of this extension is again in terms of plain P-RASP. Notice however that the translation is not straightforward and thus the new features cannot be considered syntactic sugar. Finally, we draw some conclusions. 2
To accommodate the new language expressions that involve resources and their quantities, the underlying language of RASP is partitioned into P rogram symbols and Resource symbols. Precisely, let hΠ, C, Vi be an alphabet where Π = ΠP ∪ ΠR is a set of predicate symbols such that ΠP ∩ ΠR = ∅, C = CP ∪ CR is a set of symbols of constant such that CP ∩ CR = ∅, and V is a set of variable symbols. The elements of CR are said amount-symbols, while the elements of ΠR are said resource-predicates. A program-term is either a variable or a constant symbol. An amount-term is either a variable or an amount-symbol.
Amount-atoms are introduced in addition to plain ASP atoms, here called program atoms. Let A(X, Y ) denote the collection of all atoms of the form p(t1, . . . , tn), with p ∈ X and {t1, . . . , tn} ⊆ Y . Then, a program atom is an element of A(ΠP , C ∪ V). An amount-atom is a writing of the form q:a where q ∈ ΠR ∪ A(ΠR, C ∪ V) and a is an amount-term. Let τR = ΠR ∪ A(ΠR, C). We call elements of τR resource-symbols. E.g., in the two expressions p:3 and q(2):b, p and q(2) are resource-symbols (with p, q ∈ ΠR and 2 ∈ C) aimed at defining two resources which are available in quantity 3 and b, resp., (with 3, b ∈ CR amount-symbols). Expressions such as p(X):V where V, X are variable symbols are also allowed, as quantities can be either directly defined as constants or derived. Notice that the set of variables is not partitioned, as the same variable may occur both as a program term and as an amount-term. Ground amountatoms contain no variables. As usual, a program-literal L is a program-atom A or the negation not A of a program-atom (intended as negation-as-failure).1 If L = A (resp., L = not A) then L denotes not A (resp., A).
Below we introduce the possibility of expressing preferences: Definition 1. A preference-list of amount-atoms ( p-list, for short) is a writing of the form q1:a1> · · · >qh:ah, where h > 2 and the qi’s are distinct amountatoms involving distinct resource-symbols. We say that the amount-atom qi:ai has degree of preference i in the p-list.
We now extend the definition of literal, including the new syntactic elements: Definition 2. A P-RASP resource-literal (r-literal) is either a program-literal or an amount-atom or a p-list. 1 We will only deal with negation-as-failure. Though, classical negation of program literals could be used in (P-)RASP programs and treated as usually done in ASP.
Therefore, we do not allow negation of amount-atoms. (See [
Definition 3. A resource-proper-rule has the form
Idx :
H ← B1, . . . , Bk where B1, . . . , Bk, k > 0 are r-literals and H is either a program-atom or a (nonempty) list of amount-atoms. Idx is of the form [N1,1-N1,2, . . . , Nh,1-Nh,2], with h > 1, and each Nj,` is a variable or a positive integer number.
Intuitively, when all the Nj,` s are integers, Idx denotes the union of h (possibly void) intervals in N+ = N \ {0}. It is intended to restrain the number of times the rule can be used: such number must be in Idx or the rule cannot be used at all. For the sake of generality, we admit that each Nj,` is a variable. Then, after grounding (see below), each Nj,` has to be instantiated to a positive integer.
A piece of notation: we will not write the list Idx when all Nj,` s are intended to be the constant 1 (meaning that at most one use of the rule is admitted). Without loss of generality, in what follows we always assume h = 1 in resourceproper-rules. The treatment of the general case is essentially the same.
The following definition introduces the notion of resource-facts. Resourcefacts that are not supposed to be iterable, since they are intended to model the fixed amount of resources that are available “from the beginning”. Definition 4. A resource-fact ( r-fact, for short) has the form H is an amount-atom q:a and a is an amount-symbol.
H ← , where According to the definition, the amount of an initially available resource has to be explicitly stated. Thus, in an r-fact the amount-term a cannot be a variable. Definition 5. A resource-rule ( r-rule, for short) can be either a resourceproper-rule or a resource-fact. A RASP-rule ( rule, for short) γ is either a program-rule or a resource-rule. An r-program is a finite set of RASP-rules. The grounding of a P-RASP program P is the set of all ground instances of rules of P , obtained through ground substitutions over the constants occurring in P . As it is well-known, ASP solvers produce the grounding of the given program as a first step, as they are able to find the answer sets of ground programs only.2 3
Semantics of a (ground) P-RASP program is determined by interpreting
program-literals as in ASP and amount-atoms in an auxiliary algebraic
structure that supports operations and comparisons. For lack of space, here we have
2 Work is under way both theoretically and practically to overcome at least partially
this limitation. However, at present almost all ASP solvers perform the grounding.
to summarize many semantic aspects. The reader may refer to [
In order to define semantics of r-programs, we have to fix an interpretation
for amount-symbols. This is done by choosing a collection Q of quantities, and
the operations to combine and compare quantities. A natural choice is Q = Z:
thus, we consider given a mapping κ : CR → Z that associates integers to
amount-symbols. Positive (resp. negative) integers will be used to model
produced (resp. consumed) amounts of resources (see [
Notation. Before going on, we introduce some useful notation. Given two sets
X, Y , let F M(X) denote the collection of all finite multisets3 of elements of X,
and let Y X denote the collection of all (total) functions having X and Y as
domain and codomain, respectively. For any (multi)set Z of integers, P(Z)
denotes their sum. E.g., P({[
Given a collection S of (non-empty) sets, a choice function c(·) for S is a function having S as domain and such that for each s in S, c(s) is an element of s. In other words, c(·) chooses exactly one element from each set in S.
In order to deal with the disjunctive aspect of p-lists, we mark each resource amount with an integer index. Such indices are intended to model the degree of preference of the amount-atoms occurring in p-lists. So, any amountatom will be represented as a pair in N × Q that we call an amount couple. Then, for each p-list, the composing amount-atoms will be associated from left to right with successive indices starting from 1; for simple amount-atoms, the index will always be 0. For instance: for amount-atom egg :2 the representation is h0, 2i where the first element is the degree of preference (which in this case is 0 as no preference is involved) and the second element is the quantity; for plist skim milk :2>whole milk :2 the representation involves the couples h1, 2i and h2, 2i, where one can see the increasing degree of preference. The representation can be extended to entire rules and to the entire program.
Given an amount couple r = hn, xi ∈ N × Q, let degree(r) = n and amount (r) = x. Notice that the amount can in principle be negative (e.g., if 3 A multiset (or bag) is a generalization of a set, where repeated elements are allowed.
Then, a member of a multiset can have more than one membership.
Q = Z). We extend such a notation to sets and multisets of amount couples, as
one expects: namely, if X is a multiset then degree(X) is defined as the
multiset {[ n | hn, xi is in X ]}. E.g., if X = {[ h1, 2i, h2, 3i, h3, 1i, h0, 1i, h1, 2i ]} then
degree(X) is {[
Let ` be either an amount-atom or a p-list in a resource-rule γ. Let setify (`) =
{h0, q, ai} {h1, q1, a1i, . . . , hh, qh, ahi} if ` is q:a if ` is q1:a1> · · · >qh:ah
We will use setify to represent the amount-atoms of rules as triples denoting: the position in each preference list where they occur; the resource-symbol they contain; the amount that is required for this resource-symbol in that preference list. We generalize the notion to any multiset X of amount-atoms and p-lists: setify (X) = {[ setify (`) | ` in X ]}.
Let r-head (γ) and r-body (γ) denote the multiset of amount-atoms or p-lists occurring in the head and in the body of γ, respectively. In order to distinguish, in the representation, between amount-atoms occurring in heads and in bodies, we define setify b (γ) and setify h (γ) as the multisets {[ setify (x) | x ∈ r-body (γ) ]} and {[ setify (x) | x ∈ r-head (γ) ]}, respectively.
Interpretation of P-RASP Programs. In what follows, we will apply a syntactical restriction on the form of the r-rules. Namely, we impose that each amount-atom cannot occur in more than one p-list within the same rule. (Clearly, a q:a can occur in several p-lists of different rules.) Though this restriction is not strictly needed, for the sake of simplicity we focus on this simplified case.
We introduce now the notion of r-interpretation for r-programs. An interpretation of a (ground) r-program P must determine an allocation of amounts for all occurrences of such symbol in rules of P : in fact, below we introduce the first step of an interpretation, i.e., the actual assignment of amounts to the amount-atoms that occur in r-rules.
Since amounts and resource-symbols are used to model production and consumption of “real world” objects, we must take into account the obvious constraint that any resource cannot be consumed if it is not produced. Thus, we restrain to those allocations having (for each resource) a non-negative global balance. In fact,, we define a collection SP of all potential allocations—for any single resource-symbol occurring in the program P (considered as a set of rules)— with the following role. Let q be a given resource-symbol. Each element F ∈ SP is a function that associates to every rule γ ∈ P a (possibly empty) multiset F (γ) of amount couples, assigning certain amounts to each occurrence of amount-atoms q:a in γ. All such F s must satisfy the only requirement that, considering the entire P , the global sum of all the quantities F assigns must be non-negative. As we will see later, only some of these allocations will actually be acceptable as a basis for a model.
To interpret an r-program, we select a collection of elements of SP , one element for each resource-symbol in τR. More formally, an r-interpretation of a ground r-program P is defined by providing a mapping μ : τR → SP . Such a function μ determines, for each resource-symbol q ∈ τR, a mapping μ(q) ∈ SP . In turn, each mapping μ(q) assigns to each rule γ ∈ P a multiset μ(q)(γ) of quantities. The use of multisets allows us to handle multiple copies of the same amount-atom. Each of these copies must be taken into account, since it corresponds to a different amount of resource.
Let B(X, Y ) denote the collection of all ground atoms built up from predicate
symbols in X and terms in Y . We have the following definition.
Definition 6. An r-interpretation for a (ground) r-program P is a triple I =
hI, μ, ξi, with I ⊆ B(ΠP , C), μ : τR → SP , and ξ a mapping ξ : P → N+.
Intuitively: I plays the role of a usual answer set assigning truth values to
program-literals; μ describes an allocation of resources; ξ associates to each rule
an integer representing the number of times the (iterable) rule is used. By little
abuse of notation, we consider ξ to be defined also for program-rules and r-facts.
For this kind of r-rules we assume the interval [N1-N2] = [
Clearly, the firing of an r-rule (which may involve consumption/production of resources) can happen only if the truth values of the program-literals satisfy the rule. We reflect the fact that the satisfaction of an r-rule γ depends on the truth of its program-literals by introducing a suitable fragment of ASP program γ. b
Def. 7, to be seen, states that in order to be a model, an r-interpretation that allocates non-void amounts to the resource-symbols of γ, has to model the ASP-rules in γ. Some preliminary notion is in order.
b
We associate to each r-rule γ, the following set R(γ) of multisets. Each element of R(γ) represents a possible admissible selection of one amount-atom from each of the p-lists in γ and an actual allocation of an amount, taken in Q via the function κ, to the amount-symbol occurring in it. Notice that the quantities associated to amount-atoms occurring in the body of γ are negative, as these resources are consumed.4 Vice versa, the quantities associated to amount-atoms occurring in the head are positive, as these resources are produced.
R(γ) = n{[ hi, q, κ(a)i | hi, q, ai = c1(S1) and S1 in setify h (γ) ]}
∪ {[ hi, q, −κ(a)i | hi, q, ai = c2(S2) and S2 in setify b (γ) ]} | for c1 and c2 choice functions for setify h (γ) and setify b (γ), resp.o where c1 (resp. c2) ranges on all possible choice functions for setify h (γ) (resp. for setify b (γ)). In order to account for multiple firing of rules, we need to be able to “iterate” the allocation of quantities for a number n of times: to this aim, for any n ∈ N+ and q ∈ τR, let
Rn(γ) =
n [ {[ X1, . . . , Xn ]} | {[ X1, . . . , Xn ]} ∈ F M R(γ) o
4 To be precise, the assigned quantity corresponds to the negation, in Q, of the amount
occurring in an amount-atom of the body. One may also specify negative byproducts
in the body, which are produced and not consumed: in such a case, the assigned
quantity will be positive (cf., [
Rn(q, γ) = n
{[ hi, vi | hi, q, vi is in X ]} | X ∈ Rn(γ)o Definition 7. Let I = hI, μ, ξi be an r-interpretation for a (ground) r-program P . I is an answer set for P if the following conditions hold: – for all rules γ ∈ P ∀ q ∈ τR μ(q)(γ) = ∅
∨ ∀ q ∈ τR μ(q)(γ) ∈ Rξ(γ)(q, γ) ∧ N1,16ξ(γ)6N1,2 – I is a stable model for the ASP-program Pb, so defined
Pb = [
γ is a program-rule in P, or γ b γ is a resource-rule in P and ∃ q ∈ τR μ(q)(γ) 6= ∅ The two disjuncts in the formula in Def. 7 correspond to the two cases: a) the rule γ is not fired, so null amounts are allocated to all its amount-symbols; b) the rule γ is actually fired ξ(γ) times and all needed amounts are allocated (by definition this happens if and only if ∃ q ∈ τR μ(q)(γ) 6= ∅ holds). Notice that case b) imposes that the amount couples assigned by μ to a resource q in a rule γ reflect one of the possible choices in Rξ(γ)(q, γ).
Finally, we say that an r-interpretation I is an answer set of an r-program P if it is an answer set for the grounding of P .
Note that, the above definition however does not in general fulfill the preferences expressed through p-lists.
In order to impose a preference order on the answer sets of an r-program, we need to provide a preference criterion to compare answer sets. Such a criterion should impose an order on the collection of answer sets by reflecting the (preference degrees in the) p-lists. Any criterion PC has to take into account that each rule determines a (partial) preference ordering on answer sets. In a sense, PC should aggregate/combine all “local” partial order to obtain a global one.
In [
Let us extend the syntax of r-rules by admitting p-lists (or amount-atoms) whose activation is subject to the truth of a conjunctive condition. We will call cplists (standing for conditional p-list) the construct for expressing conditional preferences in P-RASP.
Definition 8. A cp-list is a writing of the form (r if L1, . . . , Lm), where r is a p-list q1:a1> · · · >qh:ah, or simply an amount-atom, and L1, . . . , Lm are program-literals.
The intended meaning of a cp-list occurring in the body of a r-rule γ (the case of the head is analogous) is that whenever γ is fired, one of the resources occurring in r has to be consumed. If the firing occurs in correspondence of an answer set that satisfies L1, . . . , Lm, then the choice of which resource to consume is determined by the preference expressed by the p-list. Otherwise, if any of the Li is not satisfied, a non-deterministic choice is performed. (Hence the conjunction L1, . . . , Lm need not to be satisfied in order to fire γ.) More precisely, if L1, . . . , Lm does not hold, the r-rule containing the cp-list becomes equivalent to h r-rules, each containing exactly one of the qj :aj ’s, in place of the cp-list.
Such an extension of P-RASP can be treated by translating the rules involving cp-lists into regular r-rules. For instance, the rule
H ← B1, . . . , Bk, (r if L1, . . . , Lm) is translated into this fragment of r-program: (1) (2) (3) (4) (5) p ← not np. ← np, L1, . . . , Lm.
H ← B1, . . . , Bk, r, p.
H ← B1, . . . , Bk, qj :aj , pqj , np. npqi ← pqj .
np ← not p. ← p, Li. pqj ← not npqj . where p, np, npqj and pqj (for each j ∈ {1, . . . , h}) are fresh program atoms. In particular, p and np are used to discriminate between application of preference list and non-deterministic choice of one resource, respectively. In the latter case, the truth of each atom pqj (for j ∈ {1, . . . , h}) enables the firing of the jth rule listed at line (4). Note that at most one of such rules can be fired. In fact, rules at line (5) determine that at most one of the atoms pqj (for j ∈ {1, . . . , h}) can be true in any answer set of the program.
Consequently, the semantics of cp-lists is given in terms of that of p-lists.
If more than one cp-list occurs in a rule, then the above translation has to be generalized by introducing distinct fresh atoms for each cp-list.
A slightly modified translation must be used to handle multiple firing of a rule. Consider a rule of the form (assuming 1 6 N1 6 N2 be natural numbers):
H ← B1, . . . , Bk, (r if L1, . . . , Lm). Together with rules (1)–(2) we need the following substitutes for rules (3)–(5): np z ← not np nz, np. np nz ← not np z, np. u:N2. low ← np z. low ← v:N1, np nz. ← not low , np.
H ← B1, . . . , Bk, r, p.
H ← B1, . . . , Bk, qj :aj , np nz, u:1, v: –1. for j ∈ {1, . . . , h}
where u, v are fresh resource symbols, while low , np z, and np nz are fresh
atoms. The rationale in this translation is as follows. As before, atoms p and
np discriminate, respectively, between the cases in which the preference list is
used and those in which a non-deterministic choice of one resource is performed.
Considering those answer sets in which np is true, the atom np z (resp., np nz)
is used to distinguish the cases in which none (resp., some) of h rules in line (11)
is fired. The auxiliary resource symbol u is used to bound the overall maximum
number of firings of rules defined in line (11), because each of these firings
consumes one instance of resource u, while rule (7) makes at most N2 of such
instances available. The lower bound N1 on the number of firings is imposed
through the balance on the (auxiliary) resource v. Notice that each firing of
rules (11) actually produces one instance of such resource (because the amount
is negative, cf., [
Let us now introduce another form of cp-lists with a slightly different semantics. We want to model a preference that imposes use of resources only when a condition holds. More specifically, we introduce a conditional p-list of the form (r when L1, . . . , Lm) With the following intended meaning: let such a cp-list occur in the body of a r-rule γ (the case of the head is analogous). Whenever γ is fired in correspondence of an answer set that satisfies all of the literals L1, . . . , Lm, the firing of the rule has to consume an amount of a resource from r. Which resource is determined by the preference expressed through the p-list. As before, the conjunction L1, . . . , Lm needs not be satisfied in order to fire γ. In case some Li does not hold, the firing can still be performed but this does not require any consumption of resources in r.
Also this extension of the P-RASP language can be treated by translating the rules involving cp-lists into regular r-rules. Again, the semantics of cp-lists is given in terms of p-lists. As an example consider the rule
[N1-N2] : H ← B1, . . . , Bk, (r when L1, . . . , Lm).
It is translated into this fragment of r-program: [N1-N2] :
H ← B1, . . . , Bk, r, p.
H ← B1, . . . , Bk, np. where, as before, p and np are fresh program atoms.
Both forms of cp-lists can be admitted in the same program. In translating rules involving more that one cp-list, the above described translations have to be generalized and combined to take into account the different combinations of truth values for the auxiliary atoms (e.g., p, np, etc.) associated to each cp-list5. 5
In general, there might be cases in which (conditional) preferences are not expressible as a linear order on a set of resources. Moreover, the preferences might depend on specific contextual conditions that are not foreseeable in advance.
A simple example: for reaching my office, I prefer walking both to driving a car and catching a bus. But I have no preference between car and bus. This is a simple case of a preference order that, being not linear, cannot be modeled by a p-list.
We introduce now a generalization of p-lists, named p-sets, that allows one to use a partial order in expressing (collections of) p-lists. A p-set may occur in any place where a p-list does and is a writing of the form: {q1:a1, . . . , qk:ak | p} where p is a binary program predicate (defined elsewhere in the program).
Considering a specific answer set M , a particular extension is defined for the predicate p (namely, the set of pairs ha, bi such that p(a, b) is true in M ). Let X be the set of resource symbols {q1, . . . , qk}. We consider the binary relation R ⊆ X2 obtained by restricting to X the extension of p in M . 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 on qj . The case of p-lists is a particular case of p-sets, obtained when R describes a total order.6
Notice that, in general, R needs not to be a partial order, e.g., for instance, it may involve cycles. In such cases we consider equivalent (w.r.t. preferences) those resource symbols that belongs to the same cycle in R. Moreover, there 5 A naive way of proceeding consist in selecting a cp-list and in applying the described translation. This generates a number of new rules that involve the remaining cp-lists.
Then one simply repeats the same step until no more cp-lists occur. 6 Notice that, here, we are introducing a change in the syntax of RASP programs.
Namely we are admitting resource symbols as arguments of program predicates. might exist elements on X that are incomparable (cf., driving a car and catching a bus, in the above mentioned example).
Because of the presence of incomparable resources and equivalent resources, R can be seen as a representation of a collection of p-lists, one of them originating from an alternative total order on X compatible with R.
In order to take into account of all such possible total orders, a p-set in a P-RASP program is translated into a fragment of RASP as follows. domp(qi). nump(i). for i ∈ {1, . . . , k} clp(X, Y ) ← p(X, Y ), X 6= Y. clp(X, Y ) ← domp(X), domp(Y ), domp(Z), clp(X, Z), clp(Z, Y ), X 6= Y. eqp(T1, T2) ← clp(T1, T2), clp(T2, T1), domp(T1), domp(T2). 1{idxp(T, N ) : nump(N )}1 ← domp(T ). usedp(N ) ← domp(T ), idxp(T, N ), nump(N ). ← domp(T ), idxp(T, N ), nump(N ), N > 1, N1 = N − 1, not usedp(N1). ← domp(T1), domp(T2), idxp(T1, N1), idxp(T2, N2), nump(N1), nump(N2), clp(T1, T2), not clp(T2, T1), N2 6 N1, T1 6= T2. ← not eqp(T1, T2), domp(T1), domp(T2),
idxp(T1, N ), idxp(T2, N ), nump(N ), T1 6= T2. idxp(T2, N ) ← eqp(T1, T2), domp(T1), domp(T2), idxp(T1, N ), nump(N ). orderp(T, N ) ← idxp(T, N ), not otherp(T, N ), domp(T ), nump(N ). otherp(T, N ) ← orderp(T2, N ), T 6= T2, domp(T ), domp(T2), nump(N ). where: line (12) defines two domain predicates that enumerate the (relevant) arguments of p (the elements in X) and a collection of possible indices (as we will see, different indices represent different preference degrees), respectively. Rules at lines (13)–(14) evaluate the transitive closure of the relation R defined by p. Line (15) determines the equivalences between resource symbols. Rules at lines (16)–(18) index the elements of X with consecutive (possibly repeated) integers. Lines (19)–(21) restrict the possible indexing to those that do not violate the (closure of) the relation R: elements are assigned equal indices if and only if they are equally preferred (i.e., equivalent in R). Higher indices are assigned to less preferred resource symbols. Finally, rules (22)–(23) generate (compatibly with the extension of p) all admissible orders for X. Each of these orders admits a corresponding p-list. Such indexing of resource symbols can be used, in the context of a specific answer set, while applying a preference criterion, e.g., PC1 as described in Section 3 (page 9).
Let us consider the last example mentioned in the Introduction. Assume that, in making ice-cream or zabaglione, among some ingredients, e.g., chocolate, nuts and coconut, one would prefer the less caloric. This can be so formalized: ice cream:1>zabaglione:2 ← (skim milk :2>whole milk :2 IF diet ), (vanilla:1>cinnamon:1 WHEN not allergy ), {chocolate:1, nuts:1, coconut :1 | lesscaloric}, egg :2, sugar :3. lesscaloric(X, Y ) ← calory (X, A), calory (Y, B), A < B. calory (X, Y ) ← ... That is, the preference among chocolate, nuts and coconut , i.e., a particular plist, is determined depending on the extension of the predicate lesscaloric, which might be different for different answer sets and has to be established dynamically. 6
According to our study of related work (cf. [
RASP and basic P-RASP have been implemented (cf. [
Since conditional preferences can be expressed by means of P-RASP program fragments, the implementation of RASP can be plainly completed so to process conditional preferences (some small modifications are due to marginal differences in syntax).
As regards an analysis of complexity of RASP, this is an issue still under
investigation. Preliminary results indicate that the complexity of RASP is the
same of that of LPOD [