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

变化和不确定性下基于偏好的（时间）约束求解

• 批准号: 228156-2010
• 负责人: Mouhoub, Malek
• 金额: $ 1.46万
• 依托单位: University of Regina
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2012
• 资助国家: 加拿大
• 起止时间: 2012-01-01 至 2013-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=508053
• 关键词: Preference; based; temporal; constraint; solving

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.

解决真实的生活约束问题自然意味着在存在变化、各种不确定性和偏好以及时间的不同方面的情况下处理约束处理的挑战性任务。在过去的几年里，已经开发了几种技术来分别应对这些挑战。然而，这些挑战往往同时存在，需要在同一问题中一并处理。不这样做将使我们无法忠实地代表和解决许多真实的世界约束问题。 我的主要目标是开发一个独特的约束求解框架的能力，管理，在一个动态的方式：问题的要求，以及用户的喜好，时间信息，和不确定性，由于丢失的信息，缺乏知识或变化所造成的事件是在自然的控制。除了表现力和效率，该框架应该实现为一个基于GUI的解决工具，不需要强大的技能，从用户的约束编程。这一工具应能够在解决过程中指导和协助用户，并在考虑到偏好的情况下为用户提供理由和解释（例如，提供无法更好地解决某个问题的原因）。为了满足这些目标，我提出了一个基于约束的方法，其中问题的要求是硬约束，而用户的喜好表示通过C-半环和CP-网，可以是定量的，定性的或有条件的“如果条件，那么我喜欢A比B”。通过对艾伦区间代数的扩展，将时间的数值和符号方面与时间粒度和周期数据一起管理。不确定性是用概率论和可能性理论来处理的。推理机制依赖于新的解决技术，我将开发基于分支和界限和元分析。该研究计划的成功将在最先进的水平上取得重大进展，并将非常有利于有效地解决各种约束条件下的问题，包括配置，反应调度和规划，运输和空间任务。