Bridging the Evaluation Gap: Standardized Benchmarks for Multi-Objective Search

Hadar Peer; Carlos Hernandez; Sven Koenig; Ariel Felner; Oren Salzman

cs.AIMar 25, 2026

Bridging the Evaluation Gap: Standardized Benchmarks for Multi-Objective Search

Authors: Hadar Peer, Carlos Hernandez, Sven Koenig, Ariel Felner, Oren Salzman

Organizations: Technion – Israel Institute of Technology · Universidad San Sebastián · University of California, Irvine · Ben-Gurion University

Abstract

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, reference exact Pareto-optimal solution sets, and a standardized approximate ( $\varepsilon$ -dominance) evaluation protocol, 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.

Figures & tables

Family	Benchmark	Vertices	Edges	Timeout	$\|\Pi^{*}\|$				Med. (s)	Max (s)
Family	Benchmark	Vertices	Edges	Timeout	Min	Max	Med.	Mean	Med. (s)	Max (s)
F1	DIMACS-NY_2	264,346	733,846	0/100	3	808	94	157	0.04	0.90
	DIMACS-FLA_2	1,070,376	2,712,798	0/100	2	3,856	241	511	0.16	17.52
	DIMACS-Extended-NY_3	264,346	733,846	0/100	14	352,448	9,291	32,510	12.33	3.81K
	DIMACS-Extended-NY_4	264,346	733,846	31/100	24	1,226,887	47,458	167,685	75.94	29.2K
	DIMACS-Extended-NY_5	264,346	733,846	40/100	24	1,695,842	69,567	212,460	63.89	17.6K

Table 1: Summary of benchmark instances and exact Pareto-set statistics, computed using NWMOA ∗ . Timeout reports the number of queries that reached the 24-hour timeout; Pareto cardinalities and runtimes are computed over completed queries only. Grid statistics are aggregated over multiple instances of varying sizes. Large counts, runtimes of 1,000s or more, and mean/median cardinalities are rounded; exact values are available in the repository.

Figure 1: Illustration of the NetMaker graph construction for $|V|=20$ , $a_{\min}=1$ , $a_{\max}=4$ , and $I_{\text{vertex}}=4$ . Blue and red edges correspond to $E_{\mathrm{cyc}}$ and $E_{\mathrm{loc}}$ , respectively. Vertices are arranged according to the Hamiltonian cycle for visualization; since locality is defined in vertex-ID space rather than cycle order, some locality edges appear to connect distant vertices in the drawing.

Panel of Figure 2 — Figure 2: Two representative Games benchmark environments (of 12 total). Black regions denote obstacles. Red intensity reflects cost magnitude with darker red indicating regions observed by multiple guards.

Panel of Figure 3 — Figure 3: (a) RRG benchmark environment of a Franka Emika Panda manipulator in a tabletop scene featuring vertical support pillars and box-shaped obstacles. (b) Illustration of link-specific clearance distances ( $d_{1}$ , $d_{2}$ , $d_{3}$ ), 2D setting. Unlike an aggregated clearance model collapsing safety into a minimum-distance penalty (here, $d_{2}$ ), a per-link formulation preserves the geometric risk profile across the manipulator.

Panel of Figure 4 — Figure 4: Pareto-front cardinality across queries as a function of the approximation parameter $\varepsilon$ for representative benchmarks from all benchmark families. Each point corresponds to a start–goal query.

Panel of Figure 5 — Figure 5: Representative exact two-objective Pareto fronts for single queries from different benchmark families. The examples highlight substantial variation in objective-space geometry across the benchmark suite.

Benchmark Design

Benchmark design creates tasks, datasets, metrics, and protocols that make AI capabilities measurable and comparisons credible.

See all 391 papers

Bridging Multi-Valued Heuristics and Dimensionality Reduction in Multi-Objective Search
Jun 5, 2026Maya Wolff, Ariel Felner, Oren SalzmanDimensionality Reduction Multi-Objective Optimization
Department of Computer Science, Technion – Israel Institute of Technology, Haifa, Israel · Faculty of Computer and Information Science, Ben-Gurion University of the Negev, Beer-Sheva, Israel
Approximate Multi-Objective Search Under Rulebooks
Aug 5, 2026Omar Muhammetkulyyev, Oren Salzman, Tichakorn WongpiromsarnTree Search Multi-Objective Optimization
Iowa State University, Ames IA 50010, USA · Technion - Israel Institute of Technology, Haifa 3200003, Israel
Graph Instance Landscapes: When Structural Similarity Does (Not) Reflect Shortest-Path Performance
Jun 1, 2026Maryam Gholami Shiri, Ivana Krminac, Marko Djukanović +3Benchmark Design
Jožef Stefan Institute, Ljubljana, Slovenia · Jožef Stefan International Postgraduate School, Ljubljana, Slovenia · Faculty of Natural Science and Mathematics, University of Banja Luka, Banja Luka, Bosnia and Herzegovina +3

Jun 5, 2026J/K move · Enter open · S save

Bridging Multi-Valued Heuristics and Dimensionality Reduction in Multi-Objective Search

Maya Wolff, Ariel Felner, Oren Salzman

Department of Computer Science, Technion – Israel Institute of Technology, Haifa, Israel · Faculty of Computer and Information Science, Ben-Gurion University of the Negev, Beer-Sheva, Israel

Dimensionality Reduction Multi-Objective Optimization

Open paper AskPDF arXiv

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 are highly dependent 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

\text{NAMOA}^*{\text{dr}\text{-}\text{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,

\text{L}\text{-}\text{NAMOA}^*{\text{dr}\text{-}\text{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. Across a range of benchmarks,

\text{L}\text{-}\text{NAMOA}^*{\text{dr}\text{-}\text{mvh}}

matches or improves over state-of-the-art MOSP algorithms, and achieves speedups of over 10x in instances where the additional guidance provided by the MVH translates into stronger pruning.

Abstract

Benchmark Design

Explore similar work

Bridging Multi-Valued Heuristics and Dimensionality Reduction in Multi-Objective Search

Approximate Multi-Objective Search Under Rulebooks

Graph Instance Landscapes: When Structural Similarity Does (Not) Reflect Shortest-Path Performance