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

University Of Kentucky Research Foundation, Lexington KY

Investigators

Abstract

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.