ML Anthology

On Preference-Based Search in State Space Graphs

Patrice Perny, Olivier Spanjaard
AAAI 2002 pp. 751-756
/aaai/2002/perny2002aaai-preference/

Abstract

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. 1

PDF AAAI Semantic Scholar

Cite

Text

Perny and Spanjaard. "On Preference-Based Search in State Space Graphs." AAAI Conference on Artificial Intelligence, 2002.

Markdown

[Perny and Spanjaard. "On Preference-Based Search in State Space Graphs." AAAI Conference on Artificial Intelligence, 2002.](https://mlanthology.org/aaai/2002/perny2002aaai-preference/)

BibTeX

@inproceedings{perny2002aaai-preference,
  title     = {{On Preference-Based Search in State Space Graphs}},
  author    = {Perny, Patrice and Spanjaard, Olivier},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year      = {2002},
  pages     = {751-756},
  url       = {https://mlanthology.org/aaai/2002/perny2002aaai-preference/}
}