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.
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.
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