RI: Small: Effective Preference Reasoning over Combinatorial Domains: Principles, Problems, Algorithms, and Implementations

偏好是人类推理和决策的基本属性。每当要在两种选择之间作出选择时，它们就会出现。偏好推理的理解和自动化是人工智能领域的一个重要问题，对于自主式智能决策支持系统的设计尤为重要。如果有几个选择，他们之间的偏好可以显式表示和偏好推理通常是容易的。然而，在实践中，决策者面临的选择数量在许多情况下可能令人生畏。 在这种情况下，建模和表示决策者的偏好，并自动化的偏好推理模型的基础上是具有挑战性的。为了应对这一挑战，该项目将研究偏好聚合和优化的原理和特性，以及支持偏好推理任务的算法;将开发偏好学习和近似方法，以支持建立偏好模型;并将实现有效的偏好建模和推理软件。知识表示，计算的社会选择，约束解决体现的答案集编程和可满足性测试等领域将通知这些研究。该项目将产生一个理论和算法框架的偏好推理的组合域，在软件工具，有效的偏好推理，并在方法，将它们集成到人工智能决策支持系统，在工业，科学和政府应用中变得越来越普遍。该项目将假设空间的替代品是由一个组合域，其中的替代品表示的相关决策的属性值。虽然组合域的属性数量呈指数级增长，但单个属性的值集通常很小。这打开了一种可能性，表达偏好的属性值和属性之间的关系方面的组合域中的元素。这是该项目的设置，偏好树，CP网和答案集优化程序作为组合域偏好的正式表示。该项目将侧重于偏好汇总和偏好优化。寻找最优和接近最优的替代方案，寻找在某种意义上不同（或相似）的最优或接近最优的替代方案的集合，以及聚合仅部分已知的偏好，这些都是我们将要考虑的具体问题的一些例子。由于在大的领域中手工建立偏好模型是不可行的，该项目将研究学习偏好模型（例如，偏好树）的方法，并开发模型近似的方法（不同的模型具有不同的计算特性，"硬“模型与”易“模型的近似可能证明对前者的推理是有效的）。 最后，该项目将为几个关键的偏好推理任务开发一个软件套件。该实现将利用答案集编程和可满足性的进步。由此产生的软件将根据来自实际应用或由实际应用激发的基准进行系统评估。

Preferences are fundamental attributes of human reasoning and decision making. They appear whenever a choice between alternatives is to be made. Understanding and automating preference reasoning is a major problem of artificial intelligence, especially important for the design of autonomous intelligent decision support systems. If there are few alternatives, preferences between them can be represented explicitly and preference reasoning is typically easy. However, in practice the number of alternatives facing the decision maker can be daunting in many cases. In such cases, modeling and representing preferences of the decision maker, and automating preference reasoning based on the model are challenging. To respond to the challenge, the project will study principles and properties of preference aggregation and optimization over large domains of alternatives, and algorithms to support preference reasoning tasks; will develop methods for preference learning and approximation in support of building preference models; and will implement software for effective preference modeling and reasoning. Areas such as knowledge representation, computational social choice, and constraint solving embodied by answer-set programming and satisfiability testing will inform these studies. The project will result in a theoretical and algorithmic framework for preference reasoning over combinatorial domains, in software tools for effective preference reasoning, and in methods to integrate them into artificial intelligence decision support systems that are becoming pervasive in industrial, scientific and governmental applications. The project will assume that the space of alternatives is modeled by a combinatorial domain, where alternatives are represented in terms of values of attributes relevant to decision making. While combinatorial domains are exponentially large in the number of attributes, the sets of values of individual attributes are typically small. This opens a possibility of expressing preferences over elements in a combinatorial domain in terms of preferences on attribute values and relations between the attributes. This is the setting for the project, with preference trees, CP-nets and answer set optimization programs as formal representations of preferences over combinatorial domains. The project will focus on preference aggregation and preference optimization. Finding optimal and near-optimal alternatives, finding collections of optimal or near-optimal alternatives that are in some sense diverse (or similar), and aggregating preferences that are only partially known are some examples of specific problems we will consider. As building manually preference models over large domains is infeasible, the project will study methods to learn preference models (for instance, preference trees), and develop methods for model approximation (different models have varying computational properties, and close approximations of ``hard'' models with ``easy'' ones may prove effective for reasoning with the former). Finally, the project will develop a software suite for several key preference reasoning tasks. The implementation will exploit advances in answer-set programming and satisfiability. The resulting software will be systematically evaluated on benchmarks coming from or motivated by practical applications.