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

解决现实生活中的约束问题自然意味着在变化、各种不确定性和偏好以及时间的不同方面处理约束处理的挑战性任务。在过去的几年里，已经开发了几种技术来分别应对这些挑战。然而，后几个挑战通常是共存的，需要在同一个问题中一起处理。如果做不到这一点，我们将无法忠实地表现和解决许多现实世界的约束问题。我的主要目标是开发一个独特的约束解决框架，能够以动态的方式管理：问题要求以及用户偏好、时间信息，以及由于自然控制下的事件导致的信息缺失、知识匮乏或变异性造成的不确定性。除了具有表现力和效率之外，该框架还应该实现为一个基于图形用户界面的求解工具，它不需要用户具备很强的约束编程技能。这一工具应该能够在解决过程中指导和协助用户，并向他/她提供考虑到偏好的理由和解释(例如，通过提供不可能对给定问题获得更好解决方案的原因)。为了满足这些目标，我提出了一种基于约束的方法，其中问题需求是硬约束，而用户偏好通过C-半环和CP-网来表达，并且可以是定量的、定性的或有条件的，例如：如果条件，那么我更喜欢A而不是B。通过对Allen区间代数的扩展，将时间的数值和符号方面与时间粒度和周期数据一起管理。不确定性是用概率理论和可能性理论来处理的。推理机制依赖于我将基于分支定界和元启发式开发的新的求解技术。这一研究计划的成功将取得最先进水平的重大进步，并将非常有益于有效地解决包括配置、反应性调度和规划、交通和空间任务在内的各种约束条件下的问题。

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.