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.