On preference-based Search in State Space Graphs - Université Pierre et Marie Curie Accéder directement au contenu
Communication Dans Un Congrès Année : 2002

On preference-based Search in State Space Graphs

Olivier Spanjaard

Résumé

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.
Fichier principal
Vignette du fichier
pub_146_1_aaai02.pdf (220.02 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01534532 , version 1 (30-06-2017)

Identifiants

  • HAL Id : hal-01534532 , version 1

Citer

Patrice Perny, Olivier Spanjaard. On preference-based Search in State Space Graphs. 18th National Conference on Artificial Intelligence (AAAI 2002), Jul 2002, Edmonton, Canada. pp.751-756. ⟨hal-01534532⟩
38 Consultations
25 Téléchargements

Partager

Gmail Facebook X LinkedIn More