On Preference-Based Search in State Space Graphs

The aim of this paper is to introduce a general framework for preference-based search in state space graphs with a focus on the search of the preferred solutions. After introducing a formal definition of preference-based search problems, we introduce the PBA∗ algorithm, a generalization of the A∗ algorithm, designed to process quasi-transitive preference relations defined over the set of solutions. Then, considering a particular subclass of preference structures characterized by two axioms called Weak Preadditivity and Monotonicity, we establish termination, completeness and admissibility results for PBA∗. We also show that previous generalizations of A∗ are particular instances of PBA∗. The interest of our algorithm is illustrated on a preference-based web access problem.

Authors

• Patrice Perny Sorbonne University

Keywords

No keywords are indexed for this paper.