Date
2013
Notes
Leavenworth, Washington USA, July 11–13, 2013
Dewey
Recherche opérationnelle
Sujet
Multiobjective search; Bidirectional search; Preference-based search
Book title
Proceedings of the 6th Annual Symposium on Combinatorial Search (SoCS 2013)
Author
Malte Helmert, Gabriele Röger
Publisher
AAAI Press
Publisher city
Palo Alto (USA)
Year
2013
Author
Galand, Lucie
Ismaili, Anisse
Perny, Patrice
Spanjaard, Olivier
Type
Communication / Conférence
Item number of pages
80-88
Abstract (EN)
In multiobjective state space graph problems, each solution-path is evaluated by a cost vector. These cost vectors can be partially or completely ordered using a preference relation compatible with Pareto dominance. In this context, multiobjective preference-based search (MOPBS) aims at computing the preferred feasible solutions according to a predefined preference model, these preferred solutions being a subset (possibly the entire set) of Pareto optima. Standard algorithms for MOPBS perform a unidirectional search developing the search tree forward from the initial state to a goal state. Instead, in this paper, we focus on bidirectional search algorithms developing simultaneously one forward and one backward search tree. Although bi-directional search has been tested in various single objective problems, its efficiency in a multiobjective setting has never been studied. In this paper, we present several implementations of bidirectional preference-based search convenient for the multiobjective case and investigate their efficiency.