On Preference-Based Search in State Space Graphs

Patrice Perny, LIP6 - University of Paris VI; Olivier Spanjaard, LAMSADE - University of Paris IX

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.

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.