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.