Soft constraint problems with uncontrollable variables
Preferences and uncertainty are common in many real-life problems. In this article, we consider preferences modelled via soft constraints that allow for the representation of quantitative preferences. Moreover, we consider uncertainty modelled via uncontrollable variables, that is, variables whose value cannot be decided by us. We also assume that some information is provided for such variables in the form of a possibility distribution over their domains. Possibilities provide a way to model imprecise probabilities, and give us a way to know which values are more possible than others for the uncontrollable variables. For such problems, the aim is to find a solution with a high preference which is also very robust with respect to the uncontrollable part. To tackle such problems, we adopt an existing approach that eliminates the uncertain part of the problem while adding some constraints in the remaining part, and then solves the resulting problem. However, contrarily to the specific methods present in the literature, we formulate several desirable properties, on the robustness of the problem's solutions and its relationship with their preferences, that should be satisfied by any specific method based on this approach. We also define several semantics to order the solutions according to different attitudes to risk, and we discuss which of the desirable properties are satisfied by each of the considered semantics. Finally, we present a solver for this kind of problems, and we show some experimental results of its application over the classes of such problems.
preferences uncertainty constraint programming possibility theory