Preference Reasoning in Constraint-based Systems

约束和偏好在各种各样的现实问题中共存，包括调度、计划、车辆路径、资源分配和地理信息系统(GIS)应用。约束是指必须满足的问题要求，而偏好可以是定性的，也可以是定量的，并反映出需要尽可能满足的愿望和选择。在一些应用中，例如城市规划和机器人运动规划，这些约束和偏好可以是时间的、空间的或两者兼而有之。在后一种情况下，我们将不得不处理在时间和空间上占据给定位置的实体。时空数据可以是符号的，也可以是数字的，并且可以对应于多个层次的细节。*提出的研究计划的主要目标是通过开发新技术来扩展当前约束求解系统的特征，从而产生一种忠实地代表真实世界工业应用的技术。在这方面，我们计划开发一个独特的框架及其相关算法，用于在不断发展的环境中管理上述类型的约束和偏好。*给定一个现实世界中约束和偏好下的应用，该框架的主要任务是以有效的方式返回满足所有约束和优化所有偏好的最佳结果。目前的求解系统基于环境稳定性的理想化假设。我们提出的框架将能够以增量的方式在任何时候添加或删除约束或偏好时保持这组最优解。在处理在高度动态和不可预测的环境条件下运行的应用程序时，此功能将克服当前解决系统的限制。通过这种动态特性，以及我们提出的约束和偏好学习算法，我们的框架将具有与用户交互的能力，并允许用户在约束和偏好下对给定问题进行建模。这将解决用户在使用当前解算器对这些问题进行建模时必须面对的挑战。事实上，当前的系统需要逻辑、传统编程技能以及重要的约束编程背景，以便最终用户对即使是简单的问题进行建模。*我们的框架将具有处理由于缺乏知识、丢失信息或由自然控制的事件引起的变异性而具有不确定性的约束和偏好的能力。这将通过将概率和可能性理论扩展到一般以及时空约束和偏好来实现。*最后，通过实现所提出的研究计划，我们将成功地解决各种复杂的工业问题，包括反应调度、城市规划、时间表、机器人、交通、配置和电子商务。**

Constraints and preferences co-exist in a wide variety of real world problems, including scheduling, planning, vehicle routing, resource allocation and Geographic Information Systems (GIS) applications. Constraints refer to problem requirements that must be met, while preferences can be either qualitative or quantitative and reflect desires and choices that need to be satisfied as much as possible. In some applications such as urban planning and robot motion planning, these constraints and preferences can be temporal, spatial or both. In this latter case, we will have to deal with entities occupying a given position in time and space. Spatio-temporal data can be symbolic or numeric and may correspond to multiple levels of detail.***The main goal of the proposed research program is to extend the features of the current constraint solving systems by developing new techniques leading to a technology that faithfully represents real world industrial applications. In this regard, we plan to develop a unique framework and its related algorithms for managing the above types of constraints and preferences in an evolving environment.***Given a real world application under constraints and preferences, the main task of this framework is to return, in an efficient way, the best outcomes satisfying all the constraints and optimizing all the preferences. The current solving systems work based on idealized assumptions of environment stability. Our proposed framework will be able to maintain, in an incremental way, this set of optimal solutions anytime a constraint or a preference is added or removed. This feature will overcome the limitations of the current solving systems when tackling applications operating under highly dynamic and unpredictable environmental conditions. Through this dynamic feature, as well as the constraint and preference learning algorithms we propose, our framework will have the ability to interact with the user and allows him or her to model a given problem under constraints and preferences. This will address the challenge that users have to face when modelling these problems using the current solvers. Indeed, the current systems require logic, traditional programming skills, as well as a significant background in constraint programming for the end-user to model even simple problems.***Our framework will have the ability to handle constraints and preferences with uncertainty due to lack of knowledge, missing information or variability caused by events which are under nature's control. This will be achieved by extending the probability and the possibility theories to general as well as spatio-temporal constraints and preferences.***Finally, by achieving the proposed research program we will successfully address diverse complex industrial problems, including reactive scheduling, urban planning, timetabling, robotics, transportation, configuration and E-commerce. **