Modular Systems with Preferences

1 Introduction

Combining knowledge bases (KBs) is very important when common sense reasoning is involved. For example, in planning, we may want to combine temporal and spatial reasoning, or reasoning from the point of view of several agents. Here, we focus on search problems, i.e., the problems where some input is given, and we are looking for a solution (e.g. a schedule, a trajectory, a business plan) according to a KB or a combination of KBs. Search problems are formalized as the task of Model Expansion (MX) [Mitchell and Ternovska, 2005], which is the task of expanding a given structure 1 (that represents an instance of the problem) with interpretations of new relations and functions (that represent solutions) to satisfy a specification in some logic, e.g. first-order logic, Answer Set Programming, etc. For example, consider the problem of constructing a trajectory of a falling ball. The input structure represents the initial conditions, and it is expanded with interpretation of a function (or a predicate) that represents spatial coordinates of the ball over a time interval, to satisfy an axiomatization of the trajectory. Another example is, given initial situation on the input, construct a plan of

1 A structure, e.g. A = (A, RA 1 , ...,RA n , f A 1 , ..., f A m, cA1 , ..., cAl ) is a domain A together with an interpretation function I of relations (R) such that RA = I(R) ⊆ An , function symbols (f) where f A = I(f) : Am → A, and constants (c) where cA = I(c) ∈ A.

actions for an agent to satisfy a certain goal, by taking into account action preconditions and effects.

Modular Systems (MS) [Tasharrofi and Ternovska, 2011] is an extension to the MX framework. Each module (and a combination of them) is an MX task. Modules are combined through the operators of composition, union, projection, complementation and feedback. The framework is able to specify multi-component problems where their constituents are characterized in different languages. An algorithm for solving MSs was proposed in [Tasharrofi et al., 2011]. An improvement of the algorithm, in the same paper, uses approximations to reduce the search space. Connections to Satisfiability Modulo Theory and other systems were discussed in [Tasharrofi et al., 2011].

An important aspect of knowledge representation systems is the capability to represent preferences. The literature presents a variety of approaches to formalize preferences, e.g. [Brafman and Domshlak, 2009], [Santhanam et al., 2011], [Delgrande et al., 2003], [Brewka et al., 2010], [Sohrabi et al., 2008], [Boutilier et al., 2004a], [Delgrande et al., 2007], [Wilson, 2004], and [Faber et al., 2013]. Several surveys have appeared in recent years categorizing preference formalisms from various perspectives. For example, in [Baier and McIlraith, 2008], a set of preference formalisms for planning have been introduced. The authors of [Delgrande et al., 2004] classified preference frameworks in non-monotonic reasoning.

Preferences in database systems have been broadly investigated by different researchers such as [Kiessling, 2002], [Borzsony et al., 2001] and [Stefanidis et al., 2011]. A primary well-known preference language in database systems was proposed in [Kiessling, 2002]. In this language, some preference constructors were introduced to express basic preference terms. For example, POS is a constructor that given two n-arity tuples A = (a1, ..., an), B = (b1, ..., bn) and a set called POS, A is preferred to B (notation A >P B) with respect to ith attribute (column) in the database table if and only if A[i] ∈ POS and B[i] /∈ POS. Logical connectives can be also applied on basic preferences. This language offers operators for combining preferences to construct complex preference terms. Pareto and prioritized accumulation are two operators broadly used in several frameworks. Prioritized accumulation (notation &) gives priority to a preference. Let A and B be tuples of the same relational schema R. A is preferred to B (notation A >P1&P2 B) if and only if A >P1 B ∨ (A ≯P1 B ∧ B ≯P1 A ∧ A <P2 B). Pareto operator combines two preferences such that A is preferred to to B with respect to composition of P1 and P2 (P = P1⊗P2) if and only if (A >P1 B ∧ ¬(B >P2 A) ∨ (A >P2 B ∧¬B >P1 A).

However, the main principles behind combinations of preference formalisms (possibly written in different languages) have not been fully formalized yet. Here are some key challenges of current formalisms: First, they cannot combine preferences in systems consisting of intricate interconnected parts (see feedback connection in Example 1 below). Second, preference terms are written in the same language such as [Ross, 2007] or [Kiessling, 2002] that use first-order logic to express preferences. They are not able to formalize preference composition in heterogeneous data systems. The following example clarifies the complexity of formalizing a modular system with preferences.

Example 1. A Logistic Service Provider (LSP) is a modular system that can be used by a company such as Oracle. It decides how to pack goods and deliver them. It solves two NP-complete tasks interactively, - Multiple Knapsack (module MK) and Travelling Salesman Problem (module MT SP ). The system takes orders from customers (items Items(i) to deliver, their profits p(i), weights w(i)), and the capasity of trucks available c(t), decides how to pack Pack(i, t) items in trucks, and for each truck, solves a TSP problem. The feedback about solvability of TSP is sent back to MK. Module MTSP takes a candidate solution from MK, together with the graph of cities and routes with distances, allowable distance limit and destinations for each product. The output of this module is the route, for each truck Route(t, n, c), where t is a truck, n is the number in the sequence, and c is a city. The Knapsack problem is written, in, e.g. Integer Linear Programming (ILP), and TSP in Answer Set Programming (ASP). The modules MK and MTSP are composed in sequence, with a feedback going from an output of MTSP to an input of MK. A solution to the compound module, MLSP , to be acceptable, must satisfy both sub-systems. The company may have preferences for packing and delivery of products. E.g. if a fragile item is packed in a truck, it may be preferred to exclude heavy items. Among certain routes with equal costs, some of them may be preferred to others. It is possible that preferences in the Knapsack problem are formalized by cp-nets [Boutilier et al., 2004a] and the TSP's preferences are represented in preference-based Answer Set Programming framework [Brewka et al., 2003]. In Figure 1, Pk denotes the preferences of the knapsack module and PTSP denotes the TSP module's preferences. Formalizing this modular problem with preferences is not easy because: 1) the Knapsack and the TSP are axiomatized in different languages, 2) preferences of each module are represented by a different formalism, 3) preference formalisms use different languages than the axiomatizations of the modules themselves, 4) two modules communicate in a complex way that includes a feedback loop fromMTSP toMK.

Contributions

We propose model-theoretic foundations for combining KBs with preferences in modular systems. On the logic level, each module is represented by a KB in some logic L2 , and its preferences (and meta-preferences) are represented by (strict) partial orders on partial structures in a preference formalism named P-MS. Different logics and preference formalisms can be used for modules in the same system. Operations for combining modules are generalized to combine preferences of each module. We prove that our formalism is robust in the sense that the operations for combining modules preserve the notion of a preference-based modular system. Our formalism is consistent with (and extends) the model-theoretic semantics of modular systems [Tasharrofi and Ternovska, 2011]. In model theoretic semantics, an MX task is viewed as a set of structures, where each input is expanded with solutions. We also prove that our formalism represent cp-nets and preference-based planning. Thus we can combine them in one modular system.

Novelty

With our formalism, each module can be formalized in a different framework. To our knowledge, this is the first multilanguage preference formalism. This generality is achieved through the model-theoretic semantics of modular systems. Another novelty is the ability of handling preferences in complexly structured systems. For instance, in Example 1, there is a complex combination of Knapsack and TSP problems (feedback from TSP to Knapsack). In contrast, these complex systems were not representable in previous work. E.g., in [Kiessling, 2002].

2 Preliminaries

A vocabulary (denoted, e.g. τ, σ, ε) is a set of non-logical (predicate and function) symbols. A τ-structure is a domain (a set), and interpretation of vocabulary symbols in τ .

In [Tasharrofi and Ternovska, 2011], the authors formalize combinatorial search problems as the task of model expansion (MX), the logical task of expanding a given structure with new relations. Formally, the user axiomatizes the problem in some logic L. This axiomatization relates an instance of the problem (a finite structure), and its solutions (expansions of that structure with new relations or functions). Logic L corresponds to a specification/modelling language. It could be an ASP program, or a specification in a language from the CP community, or even a Java program, as long as modeltheoretic semantics can be provided.

2 Any logic with model-theoretic semantics can be used, including logic programs.

Definition 1 (Model Expansion task). Given: a formula φ in logic L with a vocabulary σ ∪ ε, such that σ ∩ ε=∅ and σ-structure A. Find: structure B that expands A to σ ∪ ε and satisfies φ. We call σ instance and ε expansion vocabularies.

Definition 2 (Module). A module is a set (class) of σ ∪ εstructures, where σ ∩ ε=∅.

A module can be given by any decision procedure, be a set of models of a KB, be given by an inductive definition, a C or an ASP program, or by an agent making decisions. Modules of [Tasharrofi et al., 2011] were introduced as model expansion tasks. The view of Definition 2 is equivalent. In modular systems, information propagation happens through vocabulary symbols that are equal. Modules are combined using the following algebraic operations. Projection (πν(M)) hides some vocabulary of a module. Composition (M1 ▷M2) connects outputs of M1 to inputs of M2. Union (M1 ∪ M2) models choice. Complementation (M) does "the opposite" of what M does. Feedback (M[R=S]) connects output S of M to its input R and was inspired by feedbacks in logical circuits. Intuitively, the operations correspond to conjunction, disjunction, negation and existential quantifier. Feedback represents fixpoints (not necessarily minimal) of modules viewed as operators. One can introduce other operations, e.g. least fixpoints or combinations of the operations above.

We now define the syntax of the algebra of modular systems. Following [J¨arvisalo et al., 2009], we say modules M1 and M2 are composable if εM1 ∩ εM2 =∅ (no output interference). ModuleM2 is independent fromM1 if σM2 ∩εM1 =∅ (no cyclic dependencies). A module is primitive if the only sub-module (algebraic sub-formula) of it is itself. Wellformed modular systems MS(σ, ε), with instance (σ) and expansion (ε) vocabularies, are defined recursively.

• If M is a primitive module with instance (input) vocabulary σ and expansion (output) vocabulary ε, then M∈MS(σ, ε).
• If M∈MS(σ, ε), τ⊆σ∪ε, then πτ (M)∈MS(σ∩τ, ε∩τ).
• If M∈MS(σ, ε), M ′ ∈MS(σ′ , ε′ ), M is composable with and independent from M ′ , then (M ▷M ′ )∈MS(σ ∪ (σ′ \ ε), ε ∪ ε′ ).
• If M∈MS(σ, ε), M ′ ∈MS(σ′ , ε′ ), and they are independent, then (M ∪M ′ )∈MS(σ ∪ σ′ , ε ∪ ε′ ).
• If M∈MS(σ, ε), R∈σ, S∈ε, and R and S are of the same type and arity, then M[R=S]∈MS(σ \ {R}, ε ∪ {R}).
• If M∈MS(σ, ε) then M∈MS(σ, ε).

A modular system is given by an algebraic formula, with input-output vocabulary specified for each primitive module. Subsystems correspond to sub-formulas and are modules themselves.

Model-theoretic semantics associates, with each modular system, a set of structures. Each such structure is called a model of the modular system. The semantics does not put any finiteness restriction on the domains. Thus, the framework works for modules with infinite structures. We assume that the domains of all structures are included in a (potentially infinite) universal domain U.

Definition 3 (Models of a Modular System). Let M∈ MS(σ, ε) be a modular system and B be a (σ ∪ ε)-structure. We construct the set M mt of models of module M by structural induction on the structure of a module.

Primitive Module: B is a model of M if B∈M.

• Projection: B is a model of M:=π(σ∪ε)(M ′ ) (with M ′ ∈ MS(σ′ , ε′ )) if a (σ′ ∪ ε′ )-structure B′ exists such that B′ is a model of M ′ and B′ expands B.
• Composition: B is a model of M:=M1 ▷M2 (with M1∈ MS(σ1, ε1) and M2∈MS(σ2, ε2)) if B|(σ1∪ε1) is a model of M1 and B|(σ2∪ε2) is a model of M2.

Feedback: B is a model of M:=M ′ [R=S] (with M ′ ∈ MS(σ′ , ε′ )) if RB =SB and B is model of M ′ .

To save space, we skip union and complementation.

E.g. the Knapsack-TSP system in Example 1 is formalized as MLSP =[MK ▷ MTSP ]B=B′ .

Partial structures allow interpretation of some vocabulary symbols to be partially specified. The algorithm for solving modular systems [Tasharrofi et al., 2011] constructs expansions incrementally, by adding information to partial structures.

Definition 4. B is a τp-partial structure over vocabulary τ if: (1) τp⊆τ, (2) B gives a total interpretation to symbols in τ\τp, and (3) for each n - ary symbol R in τp , B interprets R using two sets R+ and R- such that R+ ∩ R- =∅, and R+ ∪ R- ̸=[dom(B)]n .

Definition 5. For two partial structures B and B′ over the same vocabulary and domain, we say that B extends B′ if all undefined symbols in B are also undefined in B′ .

Notation 1. Let V ={a1, a2, ..., an} be a set of vocabulary symbols. Let A be a partial structure that interprets a subset X⊆V such that V -X is undefined. Each ai∈X can be interpreted as false, represented by a-i , or as true, represented by ai or a+i . Suppose Y is a set of the form {aAi |ai∈X} where aAi =a+i or a-i is interpretation of ai by A. We assume that set Y is representation of partial structure A.

3 P-MS: Preference-basedModular Systems

In this section we introduce Preference-based Modular Systems (P-MS). To have a formalism compatible with model theoretic semantics of modular systems, we define preference statements based on the concept of structures. However, using structures to model preferences is not always practical. Formally speaking, some interpreted symbols may be preferred to others, and there could not be enough information to decide about the rest. Unlike structures, partial structures interpret a subset of vocabulary symbols, while interpretation of other symbols is unknown. The idea of partial structures originates from the notion of three-valued logic that a truth value of a statement can be true, false, or unknown [Kleene, 1952]. In our formalism, a preference statement can be represented by a partial order over a set of partial structures when certain conditions hold. First, we explain the meaning of strict partial order.

Definition 6. A strict partial order O over a set S is a pair O:=(S, ≺) such that ≺ is a binary relation over elements of S that is anti-reflexive, asymmetric and transitive.

Now, we define one preference statement for a primitive module (single model expansion task).

Definition 7. Let M be a primitive module and vocab(M)= τ. A τo-preference (or simply called preference) P=(O, Γ) in M is a pair where O=(S, ≺) is a strict partial order over S that is the set of all τo-partial structures inM where τo⊆τ . As well, Γ={C1, C2, ..., Cm} is a set of τpi -partial structures, 1≤i≤m, inM that τpi ⊆τ.

In practical domains, preferences are usually represented by conditional statements. In the above definition, we utilize a set of partial structures Γ to express the premises of a preference statement, and O represents the conclusion. Once the preference has been defined, a preferred structure is introduced as follows:

Definition 8. Let M be a primitive module, and B, B′ be two structures in M. Given preference P=(O, Γ) in M, let ∆ be a set of all structures in M that extend at least one member of Γ. We say structure B is preferred to B′ with respect to P (denoted by B≻PB′ ) if 1) B, B′ ∈∆, 2) there are partial structures Bi and Bj over vocab(M) that can be extended to structures in M such that Bi≻Bj , and B is an extension of Bi, where B′ extends Bj , and 3) there are no partial structures Bk and Bm such that B and B′ extend them respectively and Bm≻Bk.

This definition states that when a part of B is preferred to B′ , if a condition specified by Γ is satisfied by both structures, we can conclude that B is preferred to B′ . It makes no difference how the rest of the vocabulary is interpreted because it is irrelevant to P.

Example 2. In Example 1, consider that safety of delivering items is an important preference for the company. So, it is preferred to avoid packing heavy and light items together to reduce the risk of damage to the light items. Let Psafe= (Osafe, Γsafe) be the safety preference where Osafe=(S, ≺ ) is a partial order over S that is the set of all items. Relation "≺" is defined as {pack-(i)≺pack(i)|w(i)≤W}; it means that for each item i that is lighter than a constant weight W, it is preferred to not put i in the pack. According to Notation 1, pack-(i) is representation of a partial structure that interprets ground atom pack(i) as false. The premise of the conditional statement is formalized by Γsafe={C1, C2, ..., Cm} where Ci={item(i),w(i)} such that w(i)≥W ′ . This states when there is an item with weight not less than W ′ , it is preferred to not include items lighter than W in the pack.

Definition 9. For two structures B, B′ ∈M, if a) neither B≻P B′ nor B′ ≻PB, b) for any B′′ ∈M, if B′′ ≻PB then B′′ ≻P B′ , and c) if B≻PB′′ then B′ ≻PB′′ , they are called equally preferred with respect to P and are represented by B≈PB′ . If one of the conditions (b) or (c) do not hold, then, B and B′ are incomparable and are represented by B∼PB′ . Also, B⪰PB′ means that B≻PB′ or B≈PB′ .

Considering that a module is defined as a set of structures, we can conclude the following.

Proposition 1. Given a preference P=(O, Γ) in module M, the pair (M,≺P) is a strict partial order, ≈P is an equivalence relation over structures of M, and ⪰P is a transitive and reflexive binary relation over structures of M.

Meta-Preferences

In practice, each module may have more than one preference. Some of them may be preferred to others. The question then arises how a preferred structure is defined in this case. The notion of meta-preference addresses this question.

Definition 10. Given a module M and a set of preferences Π={P1,P2, ...,Pn}, let Ωi :={Pj∈Π|(Pi≻Pj) ∨ (Pj≻ Pi)} be a subset of Π such that its elements have order relation with Pi. Assume OMP =(Π,≺) is a strict partial order over elements of Π. Binary relation ≻MP ∗ over structures of M is defined as:

B≻MP ∗B′ if there is a preference Pi∈Π such that B≻Pi B′ and

• there does not exist Pj∈Ωi that Pj≻Pi with respect to OMP and B′ ≻Pj B, and
• there is no a preference Pk∈Π\Ωi that B′ ≻Pk B.

Meta-preference MP is characterized as MP :=OMP . We say structure B is preferred to B′ with respect to binary relation ≻MP ⊆M × M (notation B≻MPB′ ) whenever if ∃B′′ ∈M; B′ ≻MP ∗B′′ , then B′′ ⊁MP ∗B.

This definition states that structure B is preferred to B′ with respect to MP if we can find a preference such as Pi that B≻Pi B′ and there is no preference that makes B′ preferred to B. If there is a preference Pj such that B′ ≻Pj B then B is not preferred to B′ with respect to the meta-preference unless Pi is preferred to Pj. Also, the definition prevents conflicts may happen between a mix of preferences, though it does not guarantee transitivity of ≻MP. If B is preferred to B′ with respect toMP, and if B′ is preferred to B′′ , then B′′ cannot be preferred to B with respect toMP.

Example 3. In Example 1, assume that the company has more than one preference. If an expensive item is selected for delivery, it is not secure to have another precious item in the pack that is specified by Psecurity. Assume we have a meta-preference MP such that ΠK ={Psaf e, Psecurity} and MP={Psafe≺Psecurity}. To have a preferred packing for the Knapsack module, when there is a heavy and expensive item in the pack, it is preferred to not include another heavy item, but it is fine to have two expensive items in the pack.

Preference-based Modular Systems

Up to now, we defined a preference P in a single primitive module. In what follows, we study how a preference in a modular system is modelled when preferences of its components are given.

Definition 11. Let M=M1 ▷ M2 be a modular system, vocab(M1)=τ1, and vocab(M2)=τ2. Given P1=(O1, Γ1) in M1 and P2=(O2, Γ2) in M2, for B, B′ ∈M, B is preferred to B′ with respect to P1 and P2, and is represented by B≻P1▷P2 B′ when B|τ1 ≻P1 B′ |τ1 and B|τ2 ≻P2 B′ |τ2 , where B|τi is restriction of B to τi.

Informally, B is preferred to B′ with respect to P=P1 ▷P2, if B is preferred to B′ with respect to P1 when they are restricted to the vocabulary of M1 and with respect to P2 when they are restricted to the vocabulary of M2.

Example 4. In Example 1, for module Mtsp, suppose that if cities c1, c2, c3, c4 are in the set of destinations, there is a path from c1 to c4 through c2 that is preferred to the path from c1 to c4 through c3. This can be formalized by preference Ptsp=(Otsp, Γtsp) where Otsp=(Stsp, ≺) is a partial order over Stsp that is the set of all possible routes. For a positive integer k and truck t,

{Route(k, c1, t), Route(k + 1, c2, t), Route(k + 2, c4, t)≻ Route(k, c1, t), Route(k+1, c3, t), Route(k+2, c4, t)} and Γtsp = {Dest(1, c1), Dest(2, c2), Dest(3, c3), Dest(4, c4)}. A preferred plan of packing and delivery with respect to Psafe ▷ Ptsp is the one where heavy and light items are not in the same pack and if the truck is supposed to visit cities c1, c2, c3, c4, then taking road (c1, c2) is preferred to (c1, c3).

We now extend this notion to meta-preferences.

Definition 12. Let M=M1 ▷ M2 and let's assume that vocab(M1)=τ1 and vocab(M2)=τ2. Assume that Π1 is a set of preferences in M1 and MP1 is a meta-preference over Π1. Similarly, Π2 and MP2 are a set of preferences and a meta-preference respectively in M2. For B, B′ ∈M, B is preferred to B′ with respect to MP1 and MP2, and is represented by B≻MP1▷MP2 B′ when B|τ1 ≻MP1 B′ |τ1 and B|τ2 ≻MP2 B′ |τ2 .

We proceed to the union operator.

Definition 13. Let M=M1 ∪M2 be a modular system. Suppose vocab(M1)=τ1 and vocab(M2)=τ2. Assume P1 and P2 are preferences in M1 and M2 respectively. For B, B′ ∈ M, if B|τ1 ≻P1 B′ |τ1 or B|τ2 ≻P2 B′ |τ2 then B is preferred to B′ with respect to P1 ∪ P2 and is denoted by B≻P1∪P2 B′ .

For meta-preferences we have:

Definition 14. Let M=M1 ∪M2 be a modular system. Suppose vocab(M1)=τ1 and vocab(M2)=τ2. Let Π1 be a set of preferences in M1 and MP1 is a meta-preference over Π1, and let Π2 be a set of preferences in M2 and MP2 a meta-preference over Π2. For B, B′ ∈M, B is preferred to B′ with respect toMP1 andMP2 ( notation B≻MP1∪MP2 B′ ) when B|τ1 ≻MP1 B′ |τ1 or B|τ2 ≻MP2 B′ |τ2 .

Let us comment briefly on the feedback operator. Let M be a σ ∪ ε modular system, R∈σ, and S∈ε. If R and S are two vocabulary symbols of the same type and arity, then M[R= S] is a (σ \ {R}) ∪ (ε ∪ {R}) modular system. The feedback operator does not change the vocabulary of a module. Hence, definition of a preference remains unchanged. When B≻P B′ holds in M, if B and B′ are also structures of M ′ , we conclude that B is preferred to B′ inM ′ .

Definition 15. Let's assume M ′ =M[R=S] and P=(O, Γ) are preferences in M. For B, B′ ∈M, whenever RB =SB and RB′ =SB′ , if B≻PB′ , then for Bf , B′f ∈M ′ , Bf≻PB′f holds where Bf =B and B′f =B′ .

This definition says that if two structures B and B′ are in M, and B is preferred to B′ with respect to P then B remains preferred to B′ in module M ′ that is module M with feedback.

The following definition introduces meta-preferences in a module with feedback operator.

Definition 16. Assume M ′ =M[R=S], Π is a set of preferences in M, and MP is a meta-preference over Π. Assume that B, B′ ∈M, andB, B′ ∈M ′ . If B≻MPB′ inM, then B≻MPB′ inM ′ .

In the model expansion task, in a general sense, there are vocabulary symbols (notation εh) that are hidden from outer observers while they are interpreted by the structures of the module. By considering the fact that projection operator hides some visible vocabulary symbols of the module, we present the following definition.

Definition 17. Let us assume M ′ =πτ ′(M), where vocab(M)=τ and vocab(M ′ )=τ ′ (τ and τ ′ are visible vocabularies). For Bπ, B′π ∈M ′ , if there are structures B and B′ in M such that B|τ ′=Bπ and B′ |τ ′=B′π and B≻PB′ , then we say Bπ≻PB′π on the condition that for all vocabulary symbols R∈(τ\τ ′ )⊆ε′h the following holds: RB =RBπ and RB′ =RB′ π .

Intuitively, given two structures Bπ and B′π in M ′ , if we can find two structures B and B′ in M such that they expand Bπ and B′π , if B is preferred to B′ with respect to MP, we can conclude that Bπ is also preferred to B′π . We proceed to metapreferences.

Definition 18. Let M ′ =πτ ′(M), vocab(M)=τ, and vocab(M ′ )=τ ′ (τ and τ ′ are visible vocabularies). Assume Bπ, B′π ∈M ′ , if there are structures B and B′ in M such that B|τ ′=Bπ and B′ |τ ′=B′π and B≻MPB′ , then we say Bπ≻MPB′π on the condition that for all vocabulary symbols R∈(τ\τ ′ )⊆ε′h the following holds: RB =RBπ and RB′ =RB′π .

A preferred modular system P-MS is a modular system with a partial order over its preferences.

Definition 19. A modular system MS with a set of preferences Π is a preferred modular system, notation P-MS, if it is specified by a pair (≺MP,MS) where MP is a metapreference inMS.

The following statement shows the robustness of our notions and is proven by structural induction.

Theorem 1. Assume for some n, a modular systemMS is obtained fromM1,M2, ...,Mn , where Mis, 1≤i≤n are modular systems, by using operations in modular systems including composition, union, feedback, and projection. For all 1≤i≤n, if Mi is P-MS thenM is also P-MS.

4 Relation with Two Preference Formalisms

We now describe two preference formalisms and show how they can be related to our formalism.

CP-Nets

Ceteris pairbus (cp) network is a graphical representation of conditional preferences with reasoning capability [Boutilier et al., 2004b]. The idea underlying cp-nets is to compare different assignments to a set of variables as some of these variables are conditionally dependent on each other. Each node represents an attribute (variable) connected to its parents through directed edges. A preference over domain values of a variable is dependent on all of its parents value. The dependency is shown by a Conditional Preference Table (CPT) represented as an annotation for each node. There exists an induced graph derived from each cp-net that shows ordering relation between a subset of outcomes. Each node in the induced graph represents an outcome and each directed edge exhibits ordering relation between nodes. An outcome o1 is preferred to o2 if in the induced graph, there is a path from o1 to o2. An induced graph comprises all information about preferences over outcomes that can be derived from a cp-net.

From the syntactic point of view, P-MS is able to capture the notion of attributes in cp-nets. Each attribute can be viewed as an interpreted predicate symbol in the context of P-MS. Therefore, an outcome in a cp-net can be represented by a structure that interprets vocabulary symbols. The relation between cp-nets and P-MS in this way implies that the space of all outcomes in a cp-net can be modelled by a set of structures interpreting vocabulary symbols in P-MS. A preference statement visualized by a cp-net over a set of variables V ={V1, ..., Vn} is an ordering over domain values of a variable that may or may not be dependent on some other variables, and a preference in P-MS is defined as P=(O, Γ) where O is a partial order given a set of partial structures Γ. In a sense, a partial structure in P-MS is a combination of some interpreted vocabulary symbols. Thus, a partial structure can stipulate a value assigned to an attribute. Orderings over partial structures in our formalism are in fact orderings over attribute values in cp-nets when partial structures in O are assumed to interpret only one vocabulary symbol. Transforming the condition part of the preference statement in a cp-net is straightforward. Order relation holds for partial structures which extend Γ. Therefore, parents of each cp-net attribute can be represented by Γ.

In order to establish the correspondence between the semantic of cp-nets and P-MS, first we explain the concept of flip-over in cp-nets. In an induced graph derived from a cpnet, each outcome node has one attribute value preferred to its child's while other attributes are assumed to be fixed. Therefore, by moving from a node to its children one attribute value is changed that is called a flip-over. A path in an induced graph is a chain of flip-overs between two outcomes. Hence, an outcome is preferred to another when single or multiple flip-over(s) exist between them. Now, we show how a flipover can be represented in P-MS. Consider two structures B and B′ ; if B⪰MPB′ (⪰MP means that ≻MP or ≈MP that is an equivalence relation), we have enough information to know that B is preferred to B′ at least at one vocabulary symbol interpretation or they are equally preferred. The concept of a single flip-over can be specified by ⪰MP when OMP =∅ (there is no meta-preference in cp-nets). In this case, ⪰MP has the transitivity property and a chain of flip-overs can be modelled by P-MS as well. If OMP is not empty, MP represents the notion of relative importance (meta-preference) in TCP-net [Brafman et al., 2006] that is an extension of cp-nets to model meta-preferences. This reasoning leads us to the following theorem, relating cp-nets and the P-MS formalism.

Theorem 2. Let G be a cp-net andMP be the representation of G in the context of P-MS. If an outcome o1 is preferred to outcome o2 in the induced graph of G, then, for o1 and o2 that are transformed into the P-MS, we have o1⪰MP o2.

Preference-based Planning

In what follows, we show how P-MS is able to assert preference statements expressed in PP [Son and Pontelli, 2004] that is a preference language for planning problems. While we do not discuss the full details of PP here, we recall the main definitions found in [Son and Pontelli, 2004]. Given a set of fluent symbols F and a set of actions A, a state is defined as a subset of F. A planing problem is a triple 〈D, I, G〉 where D indicates pre-conditions and effects of actions, I is the initial state, and G stands for the goal state. A solution to a planing problem, that is called a plan, is a chain of actions and states I, a1, ...an,G that starts from I and ends to G. A basic desire φ is identified as one of the following: 1) a certain action occurs in the plan denoted by φ≡occ(a), 2) a set of certain fluents are satisfied that is denoted by φ≡(fi ∧ ... ∧ fi+n), 3) any combination of basic desires by using classical logic connectives (e.g. ∧, ∨, and ¬) or temporal connective stemmed from temporal logic such as Next(φ1), Until(φ1, φ2), Always(φ), and Eventually(φ).

[Son and Pontelli, 2004] state that a planning problem 〈D, I,G〉 can be reduced to an Answer Set Programming (ASP) problem Π(D, I,G) such that for a feasible plan pM there is an answer set M in program Π. In the context of answer set programming, a formula φ is satisfied in M if it is a subset of vocabulary symbols that M makes true. For two plans p1 and p2, we say p1 is preferred to p2 with respect to a basic desire φ if φ is satisfied in p1 but not in p2. In the context of ASP, if M1 and M2 are two answer sets of p1 and p2 respectively, M1 satisfies φ but M2 does not.

To express basic desires in P-MS, it suffices to show that answer sets can be translated to structures in the context of modular systems. Consider a vocabulary {a1, ..., an} and an answer set M={a1, ..., ak} (k≤n). As it can be observed from the notion of answer sets, M can be viewed as a structure that interprets each atom ai, i≤k, as true and for all aj, k<j≤n, as false. Having the same argument, a basic desire φ is a partial structure in modular systems such that a subset of atoms in M is true. As a result, a planning problem 〈D, I,G〉 with preferences can be translated to answer sets and then to modular systems. Assume that structure B represents plan p1 , structure B′ is translation of p2, and formula φ is translated to partial structure Bφ. A plan p1 is preferred to p2 with respect to φ when B is preferred to B′ with respect to Bφ. This completely coincides with our definition of preferences in modular systems. The following result follows from what we discussed.

Theorem 3. Let p1 and p2 be two feasible plans of a planning problem 〈D, I,G〉 that can be translated to ASP program Π(D, I,G). Let Mp1 and Mp2 be ASP translation of p1 and p2 respectively. Suppose that Mp1 is translated to structure B andMp2 to structure B′ in the context of P-MS. Given a basic desire φ, if p1 is preferred to p2 with respect to φ in language PP, then B≻MPφ B′ in P-MS whereMPφ is translation of φ into P-MS.

5 Conclusion and FutureWork

We proposed an abstract framework for unifying preference languages in modular systems. We introduced the notion of preference-based modular systems (P-MS). We demonstrated that a system obtained through combination of some P-MS is also a P-MS. We studied how preferences expressed in other languages (two languages as examples) can be translated to our framework. Examples included two common preference languages: cp-nets and planning with preferences (PP). Our future work will address expressivity and computational issues of the framework. We will continue our study of practical aspects of our framework in AI applications, in particular, Business Processes that have complex modular structures and different users may communicate through different formal languages.