Combining Preference Elicitation and Search in Multiobjective State-Space Graphs

The aim of this paper is to propose a new approach interweaving preference elicitation and search to solve multiobjective optimization problems. We present an interactive search procedure directed by an aggregation function, possibly non-linear (e.g. an additive disutility function, a Choquet integral), defining the overall cost of solutions. This function is parameterized by weights that are initially un-known. Hence, we insert comparison queries in the search process to obtain useful preference informa-tion that will progressively reduce the uncertainty attached to weights. The process terminates by rec-ommending a near-optimal solution ensuring that the gap to optimality is below the desired thresh-old. Our approach is tested on multiobjective state space search problems and appears to be quite effi-cient both in terms of number of queries and solu-tion times.