Bidirectional Preference-based Search for Multiobjective State Space Graph Problems
Lucie Galand, Anisse Ismaïli, Patrice Perny, Olivier Spanjaard · Base Institutionnelle de Recherche de l'université Paris-Dauphine (BIRD) (University Paris-Dauphine) · 2013
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.