Multi-objective shortest-path (MOSP) algorithms traditionally rely on single-valued heuristics (SVHs), which associate each state with a single admissible cost vector. While SVHs provide safe lower bounds, they fail to capture the trade-off structure of the Pareto frontier and often yield weak search guidance. Multi-valued heuristics (MVHs) address this limitation by mapping states to sets of cost estimates, enabling a richer approximation of possible trade-offs.
Modern MOSP algorithms rely heavily on dimensionality reduction (DR) techniques to efficiently perform dominance checks. However, integrating MVHs with DR introduces subtle correctness challenges. We show that naively combining DR with MVHs destroys the ordering invariants required for DR, leading to unsound and incomplete search. To address this issue, we develop the first theoretical frameworks for safely integrating MVHs with DR.
First, we introduce NAMOA*dr-mvh, a theoretical baseline that restores search correctness by enforcing heuristic consistency. Recognizing the practical limitations of this approach, we then introduce our primary contribution, L-NAMOA*dr-mvh. This algorithm employs a "lazy", optimistic approach to DR, preserving exact correctness with only an admissible MVH by dynamically detecting and repairing local ordering violations. Empirical evaluation across a range of benchmarks demonstrates that L-NAMOA*dr-mvh successfully combines the stronger guidance of MVHs with the powerful pruning capabilities of DR, yielding in certain settings a speedup of over 10x compared to existing state-of-the-art MOSP algorithms.