Answer Set Optimization

1 Introduction

Answer set semantics [Gelfond and Lifschitz, 1991] de­ scribes the meaning of a logic program P in terms of sets of literals. The exact definition of answer sets depends on the kind of rules used in P, yet two properties are always re­ quired. Answer sets are closed under the rules of P, and they are grounded in P: each literal has a derivation using "appli­ cable" rules from P . Answer set programming has become a popular knowledge representation tool. There are several reasons for this:

1. Logic programs are expressive enough to model many typ­ ical knowledge representation problems in AI. In particu­ lar, the availability of default negation in the body of rules makes it possible to represent defeasible information.
2. Many problems in reasoning about actions, planning, diag­ nosis, belief revision and product configuration have ele­ gant formulations as logic programs so that models of pro­ grams, rather than proofs of queries, describe problem so­ lutions [Lifschitz, 2002; Soininen, 2000; Baral, 2003].
3. The semantics of answer sets is intuitive and avoids the pit­ falls of resolution-based systems like Prolog. For instance, it is independent of the order in which rules are written and correctly handles loops.

*The authors acknowledge the support of DFG grant Computa­ tionale Dialektik BR 1817/1-5, Academy of Finland grant 53695 and NSF grant IIS-0097278, respectively.

Miroslaw Truszczynski Dept. of Comp. Sci. Lexington, KY 40506-0046, USA mirek@cs.uky.edu

1. In the same time, the syntax of logic programs is restric­ tive enough to allow for fast implementations and several highly efficient answer-set provers have been developed. Most advanced among them are Smodels [Niemela and Si­ mons, 1997] and dlv [Eiter et al., 1998].

To increase the ease of use of logic programs in knowledge representation researchers have suggested and investigated several extensions to the basic formalism. Well-known ex­ amples of such extensions include disjunctive logic programs and programs with cardinality and weight constraints [Si­ mons et al., 2002].

An important issue for many applications is the represen­ tation of preferences and reasoning about them. Researchers have investigated preferences among program rules [Schaub and Wang, 2001], among program literals [Sakama and In­ oue, 2000], and context-dependent preferences among literals through the use of ordered disjunction [Brewka, 2002].

Representing and handling preferences in the formalism of logic programs is also the main topic of this paper. However, our approach differs from existing ones in an important as­ pect. Rather than specifying a preference relation among the rules or literals in a single logic program, we use two differ­ ent programs. The first program, Pgen, is used to generate answer sets, that is, define the space of acceptable solutions. Context-dependent preferences are described in a second pro­ gram, the preference program Ppref. These preferences are used to compare answer sets of Pgen, that is, to form a pref­ erence ordering of acceptable solutions. Intuitively, the rules of Pgen are hard constraints which specify conditions an an­ swer set must satisfy; the rules of Ppref are soft constraints describing conditions under which one answer set is to be considered better than another.

The decoupling of answer-set generation and answer-set comparison has at least two advantages:

1. The method for comparing answer sets is independent of the type of the generating program P 9 en. It may be any type of a logic program (for instance, normal, extended, disjunctive, involving cardinality or weight atoms), as long as it has a well-defined semantics given by a collection of sets of literals.
2. Preferences in Ppref (soft constraints) can be specified in­ dependently of Pgen (hard constraints). This makes pref­ erence elicitation easier since the task is broken into sepa-

rate and smaller subtasks. Moreover, it makes the overall setting better aligned with practical applications. Indeed, often what is possible is determined by external factors (available resources, constraints of the environment, de­ sign and engineering constraints for products) while what is preferred is described independently and by different agents (users, customers, groups of customers).

The rest of the paper is organized as follows. The next section introduces a new formalism, answer-set optimization programs, and defines their syntax and semantics. The subse­ quent section provides examples and additional observations on the basic formalism. In Section 4, we show how meta­ preferences, that is, preferences on the preference rules, can be introduced and dealt with. Next, we discuss complexity of computational problems arising in the context of our for­ malism and propose implementation techniques. Our work is related to the approach proposed in [Boutilier et al., 1999]. We investigate this relationship in Section 6. We conclude with additional discussion of other related work and possible extensions to the formalism presented here.

2 Optimization programs

We use two separate programs to describe the space of answer sets and preferences among them.

Definition 1 Let A be set of atoms. A preference program over A is a finite set of rules of the form

where the ais and b1s are literals (expressions x and ·X, where x is an atom in A), and the Cis are boolean combi­ nations over A (to be defined below).

The rule intuitively reads: if an answer set S contains a1 , ··. , an and does not contain any of the literals b1 , ... , bm then C1 is preferred over C2 , C2 over C3 , etc. (we will give a precise semantics later in this section).

A boolean combination over A is a formula built of atoms in A by means of disjunction, conjunction, strong ( ·) and de­ fault (not) negation, with the restriction that strong negation is allowed to appear only in front of atoms, and default nega­ tion only in front of literals. For example, a 1\ (b V not ·c) is a boolean combination, whereas ·(a V b) is not. Using boolean combinations rather than, say, literals in the heads of preference rules gives us additional expressiveness. Us­ ing conjunction we can express that certain combinations of properties are preferred over other combinations. Disjunction allows us to express that certain options are equally preferred. For instance, the rule a > (b V c) > d +- f says that in case off the best option is a; b and c are equally preferred second best options, and d is the least preferred option. Finally, we can use expressions like a > b > c > (not a 1\ not b 1\ not c) if we prefer to have one of properties a, b, c over not having any of them.

Definition 2 Let S be a set of literals. Satisfaction of a boolean combination C in S (denoted S f= C) is defined as:

We next define the notion of an optimization program.

Definition 3 An answer-set optimization ( ASO) program is a pair (Pgen , Ppref ) , where P gen is a logic program called the generating program, and Ppref is a preference program.

As we already mentioned earlier, the program P gen used for generating answer-sets can be of any type. We only require that the semantics be given in terms of sets of literals, or an­ swer sets, that are associated with programs.

The key question is: how does the preference program Ppref determine a preference ordering on the answer sets de­ scribed by the generating program Pgen? Let us consider an answer setS and a rule of the form (1). Given a set S of literals, three different situations are possible:

1. the body of r is not satisfied in S, that is, ai (/. S for some i E {1, . .. , n }, or some b1 E S, for j E {1 , . . . , m}
2. the body of r is satisfied in S and none of the Cis is satis­ fied inS
3. the body of r is satisfied inS and at least one Ci is satisfied in S .

In the case (1), the ruler is irrelevant to S because the rule does not apply. The case (2) is more subtle: the rule lists preferences among several options, yet none of the options holds. We consider this as another kind of irrelevance. Let us assume that a rule states that red is better than green, and S contains blue and no other color. In this case the preference of red over green appears irrelevant to S since S does not mention these two colors at all. In the case (3), the preference expressed in the rule is satisfied to some degree (as at least one Ci holds in S). Thus, we define the satisfaction degree of r inS, vs(r), by setting vs (r) = I, if r is irrelevant to S , and vs(r) = min{i: Sf= Ci}, otherwise.

Concerning the relationship between I and the other sat­ isfaction degrees, two viable options seem to exist. We can consider I as incomparable to other values, based on the view that "irrelevance" cannot be compared to proper satisfaction degrees. According to this view, selecting blue in the ex­ ample above is neither better nor worse than selecting green or red. But one can also argue that green violates prefer­ ences whereas blue does not, and that blue is thus preferable to green. We will adopt this latter view here and use the fol­ lowing preorder 2: to compare satisfaction degrees (Fig. 1):

The values I and 1 are regarded equally good (1 2: I and I 2: 1) and better than all others. In addition, for each x , we have x 2: x . We write x > y if xis strictly better than y .

Definition 4 Let Ppref = { r1, . . . , r n} be a preference pro­ gram and let S be an answer set. We say that S induces a satisfaction vector Vs = (vs(rl), ... , vs(rn)).

We extend the preorder on satisfaction degrees to preorders on satisfaction vectors and answer sets as follows:

Definition 5 Let 51 and 52 be answer sets. We write Vs 1 ~ Vs 2 if vs 1 (ri ) ~ Vs 2 (ri ),for everyi E {1, ... ,n}. We write Vs 1 > Vs 2 if Vs 1 ~ Vs 2 and for some i E {1, ... , n }, vs 1 (ri) > vs 2 (ri). In these cases we also write 51 ~ 52 and 51 > 52. respectively.

We refer to this ordering as the preference satisfaction order­ ing (or ps-ordering, for short).

Definition 6 A set of literals 5 is an optimal model of an A50 program (Pgen, Ppref) if 5 is an answer set of Pgen and there is no answer set 5 1 of Pgen such that 5 1 > 5.

3 Examples

The prototypical application for A50 programs are configu­ ration problems where P 9 en describes possible configurations and Ppref preferences among them. We use a dinner example similar to the one discussed in [Brewka, 2002]. It is conve­ nient to use programs with cardinality constraints to generate answer sets. Such programs allow for the use of special atoms of the form n{ a1 , ... , ak}m, where the ai are literals, to rep­ resent: at least n and at most m of the ai are true. Although rules built from cardinality constraints can, in principle, be replaced by sets of rules without such constraints, they make problem specifications much more concise and readable. For the precise definitions we refer the reader to [Simons et al., 2002].

Let us assume that Pgen consists of the rules:

1 {soup, salad} 1 1 {beef , fish} 1 1 {pie, ice- cream} 1

1 {red, white , beer} 1.

Each of these constraints enforces the selection of exactly one of the items it lists into an answer set. Thus, Pgen generates the space of 2 x 2 x 2 x 3 = 24 answer sets. Let us assume that Ppref is:

white > red > beer +- fish red V beer > white +- beef pie > ice-cream+- beer .

This preference program designates as non-preferred all an­ swer sets containing f ish but not white, all answer sets con­ taining bee f but not red or beer, and all answer sets contain­ ing beer and not pie. We note that the objective is not to have these answer sets eliminated, which could be accomplished simply by adding the three constraints

+-fish, not white +- beef, not red, not beer

+- beer, not pie.

to the original program. The role of the preference program is to define soft constraints and, moreover, to do so indepen­ dently of the generating program. For instance, if we later learn that constraints F = { +- red; +- white; +- pie} need to be included in Pgen, the additional constraints would lead to inconsistency. This does not happen in our approach. The answer sets generated by the extended program are:

51 = {ice-cream, beer , beef , soup} 52 = {ice-cream, beer, beef, salad} 53 = {ice-cream, beer , fish , soup} 54= {ice-cream, beer,fish, salad}

Their satisfaction vectors are V1 = (I, 1, 2) , V2 = (I , 1, 2), V3 = (3, I, 2), and V4 = (3,1, 2), respectively. Thus, 5 1 and 52 are equally good and are maximally preferred in the presence ofF to 53 and 54 , the latter two answer sets being also equally good.

4 Meta-preferences

The notion of optimality underlying our approach is some­ what weak. In general, many optimal answer sets may exist, and one often wants additional means to express that one pref­ erence (that is, one rule in the program Ppref) is more impor­ tant than another. Here is a generalization of A50 programs where it is possible to express such meta-preferences:

Definition 7 A ranked ASO program P is a sequence

consisting of a generating program Pgen and a sequence of pairwise disjoint preference programs P;ref·

The rank of a ruler E P:ref U ... U P;:ref· denoted rank(r), is the unique integer i for which r E P;ref ·

Intuitively, preference rules with lower rank are preferred over preference rules with higher rank. We can now mod­ ify the definition of preference among answer sets by taking preferences among rules into account:

Definition 8 Let P = ( Pgen, P:ref, . . . , P;:ref) be a ranked ASO program. Let 51 and 52 be answer sets of P 9 en· We define 51 ~rank 52 if for every preference ruler' such that vs 1 (r') ~ vs 2 (r') does not hold, there is a ruler" such that rank(r") < rank(r') and Vs 1 (r") > vs 2 (r").

Clearly, the preorder ~rank extends (is stronger than) the pre­ order ~. It is also easy to see that ~rank-optimal answer sets can be obtained in the following way: select all answer sets optimal wrt P1 , among those pick the ones optimal wrt P2 and so on.

A further generalization of ranked to partially ordered A 50 programs is straightforward and not presented here for lack of space. 1

In some cases a natural ordering of the preference rules can be derived from the structure of the preference program. For each preference program P we define its dependency graph G(P) as follows . The atoms appearing in P form the vertex set of G(P). There is a directed edge from a vertex b to a vertex a in G(P) if there is a ruler in P such that a appears in the head of r and b appears in the body of r.

If the graph G(P) is acyclic, there is a natural ranking of its atoms. Namely, we define the rank of an atom a, rank( a) , recursively as follows: rank(a) = 0 for every atom a that has no predecessors in G(P); otherwise, we define rank(a)

1 Another possible extension concerns the setting of weighted preference rules. To compare answer sets one could use weighted sums of the violation degrees of preference rules.

as the maximum of the ranks of all predecessors of a in G (P) incremented by 1.

The ranking of atoms implies the ranking of rules. Namely, we define the rank of a preference rule r, rank ( r), as the maximum rank of an atom appearing in the head of r.

We call preference programs with acyclic dependency graphs acyclic preference programs. They are important for two reasons:

1. They commonly appear in practice as preferences are of­ ten described according to some partial order on features defining answer sets, with some features being more im­ portant than others. For instance, in the dinner example, most users will start with the preferences concerning the main course. They could then condition their preferences concerning the appetizer and the beverage on the choice of the main course. And, finally, they may describe their pref­ erences concerning the dessert based on earlier choices of the main course, appetizer and beverage.
2. As we just demonstrated, in the case when G(P) is acyclic, there exists a natural ranking on the rules. This ranking is implied by the program itself and allows us to strengthen our ordering relation on answer sets, as de­ scribed above in Definition 8. We call the resulting order­ ing determined by an acyclic preference program - the canonical ps-ordering.

5 Complexity and implementation

The complexity of ASO programs depends on the class of generating programs. To simplify the treatment we con­ sider here only generating programs where deciding exis­ tence of an answer set is NP-complete. This class of pro­ grams includes ground normal programs (possibly extended with strong negation or weight and cardinality constraints) [Simons et at., 2002].

The following two results indicate that allowing prefer­ ences adds an extra layer of complexity.

Theorem 1 Let P = (Pgen, Ppref) be an ASO program and San answer set of Pgen· Then deciding whether S is optimal is coNP-complete.

Theorem 2 Given an ASO program Panda literal[ decid­ ing whether there is an optimal answer set S such that l E S is :E~ -complete.

The complexity results imply that (unless the polynomial hierarchy collapses) preference rules cannot be translated to generating rules in polynomial time, i.e., the problem of find­ ing an optimal answer set for an ASO program cannot be mapped in polynomial time to a problem of finding an answer set of a program obtained by translating the ASO program to a set of generating rules only.

However, in [Brewka et at., 2002] an implementation tech­ nique for computing optimal answer sets for logic programs with ordered disjunction on top of a standard answer set prover has been developed. A similar technique has earlier been used in [Janhunen et at., 2000] to compute stable models of disjunctive logic programs using Smodels. The computa­ tion is based on a tester program that takes as input an answer set and generates a strictly better one if such an answer set exists. The computation starts with an arbitrary answer set generated by the generator. This answer set is given to the tester program. If the tester fails to generate a strictly better one, we have found an optimal answer set and we are done. If a strictly better answer set is discovered, the tester is run with the new answer set as input. This continues until an optimal answer set is reached.

This technique can be adapted for computing optimal an­ swer sets of an ASO program (Pgen, Ppref) by choosing a suitable tester program Pr for a given answer set So . The tester program Pr is constructed by adding the following rules to the generator program Pgen : 2

1. For each preference r E Ppref include a fact vo(r, d) ~ where dis the satisfaction degree of r in S0 .
2. Include rules
3. Add facts geq( di, d2 ) ~ giving the preorder 2: on the set {irr, 1, 2, ... } .
4. For each Boolean combination Ci in Ppref (and its non­ atomic subexpressions) introduce a new atom Ci and add rules capturing the conditions under which the expression is satisfied. For example, if Ci is a disjunction Ch V Ct, then add rules Ci ~ Ch and Ci ~ Ct.
5. For each preference r E Ppref of the form (I) add rules

~ not better better ~ vo(R, Vo), VI (R, VI), geq(VI, Vo), not geq(Vo, VI) ~ vo(R, Vo),vi(R, VI), not geq(VI , Vo).

body(r) ~ a I, ... , an, not bi, . .. , not bm heads(r) ~ Ci (for each Ci) VI (r, irr) ~ not body(r) vi(r, irr) ~ not heads(r), body(r) VI(r, 1) ~ CI,body(r) vi(r,2) ~ not VI (r, 1), c2 , body(r) vi(r,k) ~ not VI (r, 1), ... , not VI (r, k- 1), ck, body(r).

If Pr has an answer set S, then S restricted to the original language of Pgen is an answer set for Pgen that is strictly preferred to S0 , and if Pr has no answer set, no such answer set exists.

6 Relationship to CP-networks

An important approach to the problem of eliciting and ap­ proximating preferences is that of CP-networks proposed and developed in [Boutilier et at., 1999]. We will now review this approach and show how it relates to our work.

The approach of CP-networks is concerned with compar­ ing vectors of feature values that we call configurations. Let A = {AI, . . . , Ak} be a set of features (attributes). For each feature Ai, let Di be its domain, that is, a finite and non­ empty set of values or selections for Ai. We assume that all domains are pairwise disjoint. A configuration is a k-tuple (vi, . . . ,vk) suchthatvi E Di, 1 ::=; i:::; k.

2 We follow the Pro log convention that terms starting with capital letters are variables and write irr rather than I to avoid confusion.

The user prefers some configurations to others. Since the number of configurations is, in general, exponential in I U~=l Dil, it may be impractical to directly elicit and store the user's preference ordering on the set of all configurations. Thus, the task is to identify partial (and, in some sense, basic) information about the user's preferences, and develop ways to approximate the preference ordering implied by this par­ tial information. The formalism of CP-networks [Boutilier et al., 1999] is an approach to accomplish that.

A CP-network over a set of features A is a pair (G, P), where G is a directed graph whose vertices are features from A. The edges of the graph G determine dependencies among features: preferences for a value for a feature A depend only on values selected for the parents of A in the network. Thus, for each feature A and for each selection of values for the parent features for A, a CP-network specifies a total ordering relation on the domain of A. All these total orderings form the component P of a CP -network 3 .

The information contained in a CP-network implies pref­ erences among configurations. A configuration V is one-step preferred to a configuration W if for some feature A (given a configuration U, by U(A) we denote the value from the domain of A selected to U):

1. V(B) = W(B) for every feature B E A\ {A} (that is, for every feature other than A), and
2. V(A) is strictly preferred to W(A) in the ordering of the domain D of A specified by the network for the selection for the parents of A as given by V (or, equivalently, by W).

The configuration V is CP-preferred to W if V can be ob­ tained from W by a sequence of one-step improvements. It is easy to see that for acyclic CP-networks (acyclic networks seem to arise in most situations occurring in practice) this or­ dering is indeed a partial ordering; we call it a CP-ordering 4 .

We will now show that the information represented by a CP-network N (with features A = {A1 , ... , Ak}) can be represented by means of ASO programs. First, we specify the space of all configurations as answer sets to the program Pgen (N) that, for each feature Ai E A (1 ;:; i ;:; k) contains the following rule (we assume here that Di = { d1 , . .. , dn} ):

As already discussed in Section 3, such rule enforces the se­ lection of exactly one of the listed values to an answer set. Thus, answer sets of the program Pgen(N) are precisely the configurations of N.

To specify preferences, we proceed as follows. Let A be a feature and let B = { B1 , ... , Br} be the set of its par­ ents in the CP -network. For every selection ( v1, ... , Vr) of values of features B1 , ... , Br, respectively, the network specifies an ordering, say d1 > ... > dn, on the domain D = { d1 , ... , dn} of A. We represent that fact by including a rule

3 The restriction that domains be totally ordered can be dropped. We adopt it, following [Boutilier et al., 1999) to keep the discussion simple.

4 This ordering captures the intuition ceteris paribus or all other things being equal, the aspect that is discussed in detail in [Boutilier et al., 1999).

in the preference program Ppret(N).

Thus, at the level of syntax, our approach extends that of CP-nets. In particular, [Boutilier et al., 1999] is concerned only with one fixed space of all configurations that contain for every feature exactly one value from its domain. In contrast, in our approach we have a substantial flexibility in defining answer sets by varying the generator program.

In addition, our approach is more robust when user prefer­ ences are inconsistent, the situation that often occurs in prac­ tice. For instance, the user may specify a preference rule a > b +- body1 and b > a +- body2 unaware of situations where both body 1 and body 2 are satisfied. Such inconsisten­ cies cannot be modeled by CP-networks. In our approach they can with the effect that one of the preference rules will be violated whenever both bodies are true.

The key question is that of the relationship between the semantics of the two approaches. First, we observe that they are different. Let us consider the following example from [Boutilier et al., 1999]. There are two features A and B with values a, a', and b, b', respectively. Feature B depends on feature A and the preferences are specified as follows (we give them in the notation of ASO programs):

a> a'

b > b' +-a

b' > b +-a'.

In the CP -ordering, S1 = {a, b'} is preferred over S2 = {a'' b'} as there is a one-step improvement leading from s2 to S1 . On the other hand, none of S1 and S2 is strictly pre­ ferred over the other in the ps-ordering (the corresponding satisfaction-degree vectors are: (1, 2, I) and (2, I , 1), respec­ tively). The reason is that the meaning of the rules in the two approaches is slightly different. In the CP-net approach, x > x' +- body means (x and x' form the domain of a fea­ ture X): among all answer sets satisfying body, answer set S1 is better than S2 if both agree on all features except X and sl makes X true and s2 makes x' true. In our approach x > x' +- body is more like a soft constraint expressing: whenever body is true there is a reason to prefer x over x'. Here, among the answer sets satisfying body, an answer set sl is preferred over s2 if X E Sl, x' E S2, and the other rules of the program are satisfied at least as well in S1 as in S2 . In a sense, what is different is the interpretation of the ceteris paribus - other things being equal - phrase, more precisely, the interpretation of what is meant by the "other things" that have to be equal. In the CP-network approach the "other things" are the selections of values for other fea­ tures which have to be the same. In our approach it is the degree of satisfaction of the other rules in the program.

In general, our basic approach yields a weaker ordering. Namely, we have the following theorem.

Theorem 3 Let N be an acyclic CP-network and let V and W be two configurations. If V is strictly preferred to W under the ps-ordering determined by the ASO program (Pgen(N), Ppret(N)), then Vis strictly preferred toW un­ der the CP-ordering implied by N.

It is easy to see that the representation of an acyclic CP­ network in our syntax results in an acyclic preference pro­ gram. In this case, we have the following result.

Theorem 4 Let N be an acyclic CP -network and let V and W be two configurations. IfV is strictly preferred toW un­ der the CP-ordering determined by the CP-net N, then Vis strictly preferred to W under the canonical ps-ordering de­ termined by the ASO program (Pgen(N), Ppret(N)) .

These two theorems show that we can approximate the CP-ordering by means of orderings implied by our approach. It is important as the relationship between two answer sets with respect to (ranked) ps-ordering can be verified in poly­ nomial time, while it is not known whether polynomial time algorithms exist in the case of the CP-ordering (in fact, there are examples of configurations that require an exponentially long chain of one-step improvements to demonstrate that one is preferred to the other).

7 Further related work and conclusions

In this paper we have introduced ASO programs which com­ bine a generating program with a preference program. The combination allows us to specify possible solutions of a prob­ lem (answer sets) together with preferences among specific aspects of solutions. The preference program orders the an­ swer sets according to the satisfaction degrees of its prefer­ ence rules.

Numerous papers which introduce preferences to logic pro­ gramming exist in the literature. For an overview of some of them see for instance [Schaub and Wang, 2001]. Closest to ours is the proposal in [Brewka, 2002; Brewka et al., 2002]. Here, preferences are expressed through ordered disjunction. Ordered disjunction is a non-commutative kind of disjunction which gives preference to the first disjunct over the second. The approach presented here differs from ordered disjunction in the following respects:

1. generation and comparison of answer sets are separated,
2. preference handling works independently of the type of program used for answer set generation,
3. more general preferences can be stated due to our use of boolean combinations.

In fact, it is not difficult to show that logic programs with ordered disjunction (LPODs) are a special case of our ap­ proach. Let P be an LPOD, Pgen a logic program possess­ ing the same answer sets as P, and let

The preferred answer sets of P under the Pareto criterion (cf. [Brewka et al., 2002]) and those of the correspond­ ing ASO program coincide. We can also capture the inclu­ sion based preference criterion from [Brewka et al., 2002] using appropriate ranked ASO programs. For each rule c1 x .. . x Cn f- body E P and for each i ~ n we have to include c1 V . .. V Ci > T f- body in the preference program P;ref. This gives us exactly the inclusion-preferred answer sets of P.

In future work we plan to investigate further generaliza­ tions of our approach where rule heads may contain arbitrary partial orders on boolean combinations. We intend also to study in depth the distinction between options being "equally good" and "incomparable". Finally, we will study extensions of the one-step improvement concept from CP-networks to the setting of general ASO programs.