=Paper=
{{Paper
|id=Vol-1440/paper9
|storemode=property
|title=Towards an MDD-based Representation of Preferences
|pdfUrl=https://ceur-ws.org/Vol-1440/Paper9.pdf
|volume=Vol-1440
|dblpUrl=https://dblp.org/rec/conf/ijcai/AribiKL15
}}
==Towards an MDD-based Representation of Preferences ==
https://ceur-ws.org/Vol-1440/Paper9.pdf
Towards an MDD-based representation of preferences
Noureddine Aribi1 , Souhila Kaci2 , Nadjib Lazaar2
1
University of Oran 1, Lab. LITIO, Oran, Algeria
2
CNRS, University of Montpellier, LIRMM, Montpellier, France
aribi.noureddine@univ-oran.dz, {kaci,lazaar}@lirmm.fr
The last decade witnessed a considerable number of com- Example 1. Consider three variables X1 (Color), X2 (Size)
pact representations of knowledge (beliefs or preferences) and X3 (Print) with finite domains: D1 = {0 : black, 1 :
which encode an ordering relation (partial/total (pre)orders) white, 2 : red, 3 : blue}, D2 = {0 : small, 1 : medium, 2 :
over a set of outcomes. The need for such representations large} and D3 = {0 : M IB, 1 : ST W }. Suppose we have
is motivated by two main reasons: (1) the set of outcomes the following hard constraints: C1 : X3 = 0 ⇒ X1 = 0 and
is generally exponential which causes problems from repre- C2 : X2 = 0 ⇒ X3 6= 1.
sentational and spacial points of view, and (2) it is cogni- Therefore we have 11 feasible outcomes. Fig.1.(a) depicts an
tively hard for users to provide an ordering over the whole MDD Compiling the two constraints. Notice that this is an
set of outcomes. Rather, they are more willing to express non-reduced MDD. A nice property (among many others) of
knowledge over partial descriptions of outcomes. The state MDD is the ability to merge isomorphic subgraphs (Fig.1.(b)
of the art fully addressed item (2) covering various ways and (c)).
of expressing partial descriptions of outcomes. Therefore X1 u1
we distinguish between weighted logics, conditional logics 0 1 2 3
and Bayesian-like networks. Given a compact representation X2 u2 u3 u4 u5
of knowledge, several queries can be answered: comparing 0 1 2 1 2 1 2 1 2
two outcomes, computing (constrained) optimal outcomes or X3 u6 u7 u8 u9 u10 u11 u12 u13 u14
rank-ordering a set of outcomes. Nevertheless, although ex- 1 0 1 1 1 1 1 1 1
0 0
isting representations make important advances in knowledge (a) t
representation and reasoning, we do believe that item (1) is
u1 u1
still not fully addressed. More precisely, when it comes to 3
0 1 2 0 3
manipulate the whole set of outcomes the problem of its rep- 12
u2 {u3 , u4 , u5 } u2 u3
resentation is posed again. In particular when we need to 1 2 2 2
0 1 2 0 1 1
show the explicit set of outcomes to users during an interac- u6 {u7 , u8 } {u9 , ..., u14 } u4 u5 u6
tion process. 0 1
0 1 0 0 1 1
In a purely constraint programming (CP) context, Ander-
(b) t (c) t
sen et al. [Andersen et al., 2007] proposed to use the Multi-
valued Decision Diagram structure (MDD) to replace the do-
main store where constraints have an MDD-Based presenta- Figure 1: Reduced MDDs induced from Figure (a); (b) merging iso-
tion. An MDD is graphically represented by a (rooted) di- morphic subgraphs (c) the final MDD. t is a node used to regognize
rected acyclic graph of an ordered list of variables, and can a solution.
be exponentially smaller than the extensional version of fea- In an ongoing work, we intend to address the following
sible outcomes. Each outcome is encoded as a path in the research questions:
graph, and each edge in the path encodes a variable assign- i) Given a set of constraints, how do we determine the order
ment. Additionally, an MDD comes with a fast and effective over variables that leads to a compact MDD?
GAC algorithm [Cheng and Yap, 2010], that has time com- ii) An MDD is close to a CP-net representation [Boutilier
plexity linear to the size of the MDD, and achieves full incre- et al., 2004], investigate whether an MDD can be extended
mentality in constant time. with preferential information. This allows us to: (1) improve
To take advantage of MDDs we consider the case of prefer- the search for the set of non-dominated outcomes, (2) find the
ence constrained problems. That is, not all possible outcomes shortest flipping sequence that can be used to answer domi-
are feasible. In this proposal, we attempt to address the prob- nance queries, (3) Negate preference statements.
lem of outcomes representation using MDDs where, in our iii) How can we go beyond CP-nets and extend MDDs with
context, domain store represents all possible outcomes and preferential information expressed in other preference rep-
constraints are constraints restricting the feasibility of out- resentation languages (e.g. conditional logics and weighted
comes. logics).