Preference-based (temporal) constraint solving under change and uncertainty

点击翻译按钮获取中文摘要

Solving real life constraint problems naturally implies tackling the challenging task of constraint processing in the presence of change, various kinds of uncertainty and preferences, as well as different aspects of time. In the past years several techniques have been developed to tackle each of these challenges separately. However, these latter challenges often co-exist and need to be handled together within the same problem. Failing to do so will prevent us from faithfully representing and solving many real world constraint problems. My main objective is to develop a unique constraint solving framework with the ability to manage, in a dynamic manner: problem requirements as well as user preferences, temporal information, and uncertainty due to missing information, lack of knowledge or variability caused by events which are under nature's control. In addition to being expressive and efficient, the framework should be implemented as a GUI-based solving tool that does not require strong skills in constraint programming from the user. This tool should be capable of guiding and assisting the user during the solving process and providing him/her with justifications and explanations taking preferences into account (for instance, by providing the reason why it is impossible to get a better solution to a given problem). In order to meet these objectives, I propose a constraint-based approach where problem requirements are hard constraints while user preferences are expressed through the C-semiring and the CP-nets, and can be quantitative, qualitative or conditional as in ``if Condition then I like A more than B''. Through the extension of the Allen Interval Algebra, both the numeric and the symbolic aspects of time are managed together with temporal granularities and periodic data. The uncertainty is handled with both the probability and the possibility theories. The reasoning mechanism relies on new solving techniques that I will develop based on branch and bound and metaheuristics. The success of this research program will achieve significant advances in the state of the art and will be very beneficial to efficiently solving a wide range of problems under constraints including configuration, reactive scheduling and planning, transportation and space missions.