Preference-Based Search and Multi-Criteria Optimization

Ulrich Junker

Many real-world AI problems (e.g. in configuration) are weakly constrained, thus requiring a mechanism for characterizing and finding the preferred solutions. Preference-based 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.

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.