Combining Preference Elicitation and Search in Multiobjective State-Space Graphs

Nawal Benabbou, Patrice PernyIJCAI 2015

Abstract

Multiobjective pathfinding often results in an overwhelming number of Pareto-optimal solutions, making it difficult for decision-makers to select the best option. This paper presents a novel framework that interweaves state-space search with incremental preference elicitation. By using minimax regret to guide both the search and the query process, the proposed algorithms efficiently find near-optimal solutions for both linear and non-linear utility models while minimizing the cognitive load on the user.

Introduction

In many real-world search problems, such as route planning or product configuration, multiple conflicting objectives (e.g., time, cost, and risk) must be balanced. Standard algorithms like A* are designed for single objectives, while multiobjective variants often return a massive set of solutions that can overwhelm a user. Traditional preference elicitation typically happens before the search, which is often inefficient because it asks for information that may be irrelevant to the specific problem instance. This work proposes an interactive approach: asking the user a few comparison questions during the search process to narrow down the optimal path.

Methodology

The authors focus on two classes of utility models: Additive Utilities (standard weighted sums) and Choquet Integrals (non-linear models that capture interactions between criteria).

Minimax Regret and Pruning

The algorithm maintains a set of "admissible" weights based on user feedback. It employs Minimax Regret (MMR) to identify solutions that minimize the worst-case loss if the wrong path is chosen. To maintain efficiency, the authors introduce new pruning rules based on $\delta_\Omega$-dominance and $\epsilon_\Omega$-dominance. These rules allow the search to discard sub-paths that are guaranteed to result in high regret, regardless of the user's true weights.

The $R^*_\epsilon$ Algorithm

A key innovation is the $R^*_\epsilon$ algorithm, an approximate version of the search. By allowing a small, bounded error ($\epsilon$) during dominance checks, the algorithm can prune the search space much more aggressively. This leads to massive computational speedups while still providing a formal guarantee on the final solution's quality.

Experimental Results

The approach was evaluated using synthetic 1000x1000 grid graphs with costs drawn from Gaussian distributions. The experiments tested scalability across 2 to 10 objectives and varying graph sizes.

Performance and Efficiency

The approximate algorithm $R^*_\epsilon$ proved to be significantly faster than the exact $R^*$ version. In a 2-objective scenario with a regret threshold of $\delta = 0.1$, $R^*_\epsilon$ achieved a speedup of over 3,000 times compared to the exact method.

Comparison of performance between the exact $R^*$ and approximate $R^*_\epsilon$ algorithms across different objective counts ($q$) and regret thresholds ($\delta$).

Scalability and Query Burden

Even in high-dimensional spaces with 10 objectives using the complex Choquet model, the algorithm required only a modest number of queries—typically between 30 and 50—to reach a near-optimal decision. The results also demonstrate that the query burden remains manageable as the number of nodes in the graph increases, indicating strong scalability.

Performance metrics (time and queries) for different utility models ($U^v$ for additive, $C^v$ for Choquet) across varying numbers of objectives and graph sizes.

Conclusion

This research demonstrates that search and preference elicitation are highly synergistic. By focusing on the trade-offs that appear during the search, the algorithm avoids unnecessary queries and focuses the user's attention on the most relevant decisions. The $R^*_\epsilon$ algorithm, in particular, offers a practical way to solve complex multiobjective problems with formal performance guarantees. Future work will explore eliciting individual utility functions and more advanced active learning strategies for query selection.

Summary updated

BibTeX
@inproceedings{benabbou2015combining,
  author = {Nawal Benabbou and Patrice Perny},
  title = {{Combining Preference Elicitation and Search in Multiobjective State-Space Graphs}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure