Preference-Based Search and Multi-Criteria Optimization

Many real-world AI problems (e. g. in configuration) are weakly constrained, thus requiring a mechanism for characterizing and finding the preferred solutions. Preferencebased search (PBS) exploits preferences between decisions to focus search to preferred solutions, but does not efficiently treat preferences on defined criteria such as the total price or quality of a configuration. We generalize PBS to compute balanced, extreme, and Pareto-optimal solutions for general CSP’s, thus handling preferences on and between multiple criteria. A master-PBS selects criteria based on trade-offs and preferences and passes them as optimization objective to a sub-PBS that performs a constraint-based Branch-and-Bound search. We project the preferences of the selected criterion to the search decisions to provide a search heuristics and to reduce search effort, thus giving the criterion a high impact on the search. The resulting method will particularly be effective for CSP’s with large domains that arise if configuration catalogs are large.

Authors

• Ulrich Junker

Keywords

No keywords are indexed for this paper.