Skip to main content

A language-independent framework for reasoning about preferences for declarative problem solving

Resource type
Thesis type
(Thesis) Ph.D.
Date created
Automated decision making often requires solving difficult (e.g., NP-hard) problems. In many AI applications (e.g., planning, formal verification, robotics, etc.), users can assist decision making by specifying their preferences over some domain of interest. We take a language-independent, i.e., model-theoretic approach to preferences. Decision and search problems are abstractly formalized as Model Expansion, that is, the logical task of expanding an input structure to satisfy a specification. The specification can be in any language with a model-theoretic semantics, e.g. Answer Set Programming, Constraint Programming, etc. Preferences are defined as binary relations on (sets of) partial models. We prove that introducing preferences even in the simplest formulation leads to a significant rise of the computational complexity. We develop a model-theoretic approach of combining specifications written in multiple languages with preferences. We demonstrate relationships with several preference frameworks in the literature, such as CP-nets, Answer Set Optimization, Preference-based planning, etc. We propose an algorithm that solves Model Expansion problems with preferences using abstract solvers empowered by propagators. A solver provides symbolic explanations for rejecting and accepting models, and follows a preferred computation path to prune the search space. Finally, we develop a preference-based approach to finding approximate solutions of over-constrained problems. The specifications of such problems may have several parts, potentially written in different languages, that may be not satisfiable in combination. We demonstrate how an approximate solution can be constructed, based on selecting models that are the closest to the models of more preferable specifications.
Copyright statement
Copyright is held by the author.
This thesis may be printed or downloaded for non-commercial research and scholarly purposes.
Scholarly level
Supervisor or Senior Supervisor
Thesis advisor: Ternovska, Eugenia
Member of collection

Views & downloads - as of June 2023

Views: 0
Downloads: 0