Bridging the Evaluation Gap: Standardized Benchmarks for Multi-Objective Search
This addresses the standardization gap for researchers in multi-objective search, though it is incremental as it builds on existing domains without new algorithmic methods.
The paper tackled the problem of fragmented and incomparable evaluations in multi-objective search by introducing the first comprehensive, standardized benchmark suite spanning four diverse domains, which enables robust and reproducible comparisons.
Empirical evaluation in multi-objective search (MOS) has historically suffered from fragmentation, relying on heterogeneous problem instances with incompatible objective definitions that make cross-study comparisons difficult. This standardization gap is further exacerbated by the realization that DIMACS road networks, a historical default benchmark for the field, exhibit highly correlated objectives that fail to capture diverse Pareto-front structures. To address this, we introduce the first comprehensive, standardized benchmark suite for exact and approximate MOS. Our suite spans four structurally diverse domains: real-world road networks, structured synthetic graphs, game-based grid environments, and high-dimensional robotic motion-planning roadmaps. By providing fixed graph instances, standardized start-goal queries, and both exact and approximate reference Pareto-optimal solution sets, this suite captures a full spectrum of objective interactions: from strongly correlated to strictly independent. Ultimately, this benchmark provides a common foundation to ensure future MOS evaluations are robust, reproducible, and structurally comprehensive.