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

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.