Bidirectional Preference-based Search for Multiobjective State Space Graph Problems

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 domi-nance. In this context, multiobjective preference-based search (MOPBS) aims at computing the preferred fea-sible solutions according to a predefined preference model, these preferred solutions being a subset (pos-sibly the entire set) of Pareto optima. Standard algo-rithms for MOPBS perform a unidirectional search de-veloping the search tree forward from the initial state to a goal state. Instead, in this paper, we focus on bidirectional search algorithms developing simultane-ously one forward and one backward search tree. Al-though bi-directional search has been tested in vari-ous single objective problems, its efficiency in a mul-tiobjective setting has never been studied. In this pa-per, we present several implementations of bidirectional preference-based search convenient for the multiobjec-tive case and investigate their efficiency