A Language-Independent Framework for Reasoning About Preferences for Declarative Problem Solving

Automated decision making often requires solving difficult and primarily NP-hard problems. In many AI applications (e.g., planning, robotics, recommender systems, etc.), users can assist decision making by specifying their preferences over some domain of interest. To take preferences into account, we take a model-theoretic approach to computationally hard problems with preferences. Computational problems are characterized as Model Expansion, that is, the logical task of expanding an input structure to satisfy a set of specifications. The uniformity of the model-theoretic approach allows us to combine computational problems with preferences regardless of the syntax of their specifications. We introduce a formalism to represent preferences of users associated with computationally hard problems. We introduce Prioritized Model Expansion, which is Model Expansion based on preferences. We investigate properties of Prioritized Model Expansion and conduct a thorough study of the impact of introducing preferences on the computational complexity of Sigma(P)(k)-complete Model Expansion problems. We also discuss how Prioritized Model Expansion is related to other preference-based declarative approaches, such as SAT with preferences and preference-based Logic Programming.