Managing Qualitative Preferences and Constraints in a Dynamic Environment

1 Introduction

Preference reasoning is a topic of great interest to many research areas including Artificial Intelligence (AI), economics and social science [Goldsmith and Junker, 2008]. Mostly, this is due to the fact that preferences provide an intuitive mean to reason about user desires and wishes in the given problem. This makes it a fundamental part in the decision making process. Most of the work done in the literature adopts the quantitative (numeric) measurement of the preference. Examples of this line of work include utility functions, Multi Attribute Utility Theory (MAUT) and soft constraints. However, the last decade shows a great interest in adopting qualitative preferences instead of the numeric ones [Doyle and Thomason, 1999]. This was derived by the observation that users usually face difficulties in specifying their preferences quantitatively. Therefore, different preference representations have been proposed trying to remove this burden from the users and handle qualitative preferences adequately. One notable representation for handling qualitative preferences is the Conditional Preference Networks (CP-Nets) [Boutilier et al., 2004]. The CP-Net is a graphical model exploiting conditional qualitative preferences independencies in a way similar to the Bayesian Network (BN) representation for the conditional probabilistic independencies. Constraint processing, on the other hand, is a well established research topic in AI

∗The author's research is supported by Ministry of Higher Education, Saudi Arabia.

community. Constraint Satisfaction Problems (CSPs) is an intuitive framework to represent and reason about constrained problems [Kumar, 1992].

Preferences and constraints co-exist naturally in different application areas [Boutilier et al., 2001; Rossi et al., 2008] including product configurations and recommender systems. Thus, handling both of them is of great interest to many applications. Preference constrained optimization [Boutilier et al., 2001] concerns studying such problems and efficiently finding pareto solutions (or outcomes) that are satisfied by the set of constraints and optimal according to the given preferences. A feasible solution is pareto optimal if it is not dominated by any other feasible solution. Finding the set of pareto optimals for such problems is known to be a hard problem in general [Prestwich et al., 2004].

2 Preference Constrained Optimization

The problem of finding assignments that satisfy a set of constraints and maximize the corresponding set of qualitative preferences is what we are tackling in this work. Initially, we assume a static environment where constraints and preferences are represented through CSPs and CP-nets respectively. Then, we study the problem in a dynamic setting where variables are expected to be included or excluded from the given problem. Specifically, in our research, our goal is to answer the following questions:

• How could we benefit from the existing constraint solving techniques in simplifying and efficiently solving the constrained CP-Net problem 1 ?
• How could we handle the problem in a dynamic setting?
• Are metaheuristics (evolutionary techniques, SLS...etc) applicable in practice for these types of problems? if yes, under what settings?

In the first question, our goal is to benefit from the existing techniques available in constraint processing literature and verify their usefulness in the context of constrained CP-Nets. For instance, it has been shown that using propagation techniques over the problem can, in some cases, drastically reduce the search space. Also, we aim to study different heuristic functions to prune unpromising branches in the search space and guide the search effectively towards the set of pareto optimals. In the second question, we are interested in extending the current semantics of CP-Nets to handle changes over the network. In order to do so, we first assume that the dynamic aspect is simply mapped to variable inclusion and exclusion and the set of changes are known in advance. This naturally arises in the configuration problems where different possible combination requirements are known before the process starts. The goal from studying and trying to answer the last question stems from the fact that non systematic searching methods have proved, in practice, their usefulness in many problems.

1 We use both terms Preference Constrained Optimization and constrained CP-Net interchangeably.

3 Progress

Our work so far considers two aspects of the problem. First, we study the problem of propagating consistent values over the CP-Net structure using constraint propagation techniques. This results in simplifying the problem and reducing the search space needed when looking for the optimal outcome. Therefore, we propose a method that removes inconsistent values from the CP-Net using the Arc Consistency (AC) technique [Mackworth, 1977]. The result is a new arc consistent CP-net. Experimental tests over randomly generated constrained CP-Net problems shows a large savings in finding the optimal when AC is used before and during the search..

Second, we consider extending the CP-Net semantics to handle dynamic settings. The CP-Net is a fixed representation for reasoning about qualitative conditional preferences. Given a decision problem P involving n attributes, the CPNet N over P is always the same (i.e. the set of variables v ⊆ n participating in N are fixed beforehand). In other words, the solutions for the CP-Net N are always defined over the same domain space. While this is acceptable in some static problems, it is not the case in interactive and configuration applications. In the latter, users are usually interested in different subsets of n satisfying certain requirements. Moreover, the user interests in one attribute might be conditional upon the existence of other attributes. For example, consider a PC configuration domain where the user explicitly states her preferences qualitatively. Assume, in the case of buying a PC online, the user is interested in the type of screen only if high performance graphic card is chosen as part of the configuration. In this situation, it is clear that there is no need to include the screen type preference for all configurations. Therefore, we propose a framework (Preference Conditional Constraints Satisfaction Problem (PCCSP)) which extends the CP-Net to handle activity constraints defined through a conditional CSP instance. A direct application to the PCCSP framework is configuring the webpage content where qualitative preferences and constraints co-exist over different webpage components.

4 Conclusion and FutureWork

This research concerns the problem of constraints and qualitative preferences co-existence over static and dynamic settings. This is an optimization problem guided by the set of qualitative preferences. Although the problem has been intensively studied during the last decade, much work remains to be done. Examples include examining different heuristic methods to quickly find the pareto optimals, utilizing the constraint structure to find a good variable ordering over the CP-Net structure and extending the semantics of CP-nets to handle dynamic settings. Our research goal is to contribute to the current literature through advanced techniques and algorithms to solve the constrained CP-Net problem effectively. The initial results were promising and we aim to continue working on different ideas mentioned in this paper towards successfully finishing the thesis work.

In the near future, we plan to empirically evaluate different existing methods for the constrained CP-Net problem. We investigate the problem trying to find out under which CP-Net and CSP structures does one method outperforms another. Moreover, the response time is an important factor for many constrained CP-Net applications. For example, the response time is very important in interactive applications under constraints and preferences. This motivates us to investigate the applicability of different evolutionary algorithms to the problem and examine its usefulness. Also, investigating the problem under uncertainty is one of our planned research directions. This might result in a new representation where some variables in the CP-Net are associated with probability distributions and potentially incorporate inference algorithms to reason about their values.