Bidirectional Preference-based Search for Multiobjective State Space Graph Problems
Galand, Lucie; Ismaili, Anisse; Perny, Patrice; Spanjaard, Olivier (2013), Bidirectional Preference-based Search for Multiobjective State Space Graph Problems, in Malte Helmert, Gabriele Röger, Proceedings of the 6th Annual Symposium on Combinatorial Search (SoCS 2013), AAAI Press : Palo Alto (USA), p. 80-88
TypeCommunication / Conférence
Book titleProceedings of the 6th Annual Symposium on Combinatorial Search (SoCS 2013)
Book authorMalte Helmert, Gabriele Röger
MetadataShow full item record
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.
Subjects / KeywordsMultiobjective search; Bidirectional search; Preference-based search
Showing items related by title and author.
Bidirectional versus Unidirectional Heuristic Search for Multiojective Optimization in State Space Graphs Galand, Lucie; Ismaili, Anisse; Perny, Patrice; Spanjaard, Olivier (2013) Communication / Conférence