Bridging the Evaluation Gap: Standardized Benchmarks for Multi-Objective Search
作者: Hadar Peer, Carlos Hernandez, Sven Koenig, Ariel Felner, Oren Salzman
分类: cs.AI
发布日期: 2026-03-25
💡 一句话要点
提出多目标搜索标准化评测基准，弥合评估差距，促进算法公平比较。
🎯 匹配领域: 支柱一：机器人控制 (Robot Control)
关键词: 多目标搜索 标准化基准 评估方法 Pareto优化 路径规划
📋 核心要点
- 现有MOS评估依赖异构实例和不兼容的目标，缺乏统一标准，难以进行跨研究比较。
- 构建包含真实道路网络、合成图、游戏网格环境和机器人运动规划路线图的标准基准套件。
- 提供固定图实例、标准化查询和参考Pareto最优解集，覆盖不同目标交互，确保评估的稳健性。
📝 摘要（中文）
多目标搜索(MOS)的经验评估一直存在碎片化的问题，依赖于具有不兼容目标定义的异构问题实例，这使得跨研究比较变得困难。DIMACS道路网络作为该领域历史默认基准，也表现出高度相关的目标，无法捕捉多样化的Pareto前沿结构，进一步加剧了这种标准化差距。为了解决这个问题，我们引入了第一个全面的、标准化的精确和近似MOS基准套件。我们的套件涵盖了四个结构多样的领域：真实世界的道路网络、结构化的合成图、基于游戏的网格环境和高维机器人运动规划路线图。通过提供固定的图实例、标准化的起点-目标查询以及精确和近似的参考Pareto最优解集，该套件捕捉了从强相关到严格独立的目标交互的完整范围。最终，该基准提供了一个共同的基础，以确保未来的MOS评估是稳健的、可重复的和结构上全面的。
🔬 方法详解
问题定义：多目标搜索(MOS)算法的评估缺乏统一的标准，导致不同算法在不同数据集上的表现难以直接比较。现有的DIMACS道路网络基准存在目标高度相关的问题，无法充分测试算法在处理复杂Pareto前沿结构时的能力。这阻碍了MOS领域的发展和算法的公平比较。
核心思路：论文的核心思路是构建一个标准化的、全面的MOS基准套件，该套件包含多个具有不同结构和目标交互的领域，并提供固定的图实例、标准化的查询和参考Pareto最优解集。通过提供一个共同的评估平台，可以促进MOS算法的公平比较和性能提升。
技术框架：该基准套件包含四个主要领域：真实世界的道路网络、结构化的合成图、基于游戏的网格环境和高维机器人运动规划路线图。每个领域都包含多个固定的图实例和标准化的起点-目标查询。此外，论文还提供了精确和近似的参考Pareto最优解集，用于评估算法的性能。研究者可以使用该基准套件来评估其MOS算法在不同领域和目标交互下的表现。
关键创新：该论文的关键创新在于构建了一个全面的、标准化的MOS基准套件，该套件涵盖了多个具有不同结构和目标交互的领域。与现有的评估方法相比，该基准套件提供了一个更公平、更可靠的评估平台，可以促进MOS算法的公平比较和性能提升。此外，该基准套件还提供了精确和近似的参考Pareto最优解集，可以用于评估算法的近似性能。
关键设计：该基准套件的关键设计包括：选择具有不同结构和目标交互的领域，例如真实世界的道路网络（目标可能高度相关）和高维机器人运动规划路线图（目标可能相对独立）；提供固定的图实例和标准化的起点-目标查询，以确保评估的可重复性；提供精确和近似的参考Pareto最优解集，用于评估算法的性能。
🖼️ 关键图片
📊 实验亮点
该研究构建了包含四个不同领域的标准化MOS基准套件，提供了固定的图实例、标准化的查询和参考Pareto最优解集。该基准套件能够更全面地评估MOS算法的性能，并促进算法之间的公平比较。实验结果表明，现有的MOS算法在不同领域和目标交互下的表现存在显著差异，突显了该基准套件的价值。
🎯 应用场景
该研究成果可广泛应用于路径规划、资源分配、任务调度等领域，尤其是在需要同时优化多个目标且目标之间存在冲突的场景。标准化的评估基准能够促进多目标优化算法的研发和应用，提升决策效率和系统性能，例如在自动驾驶、物流优化、机器人控制等领域具有重要价值。
📄 摘要（原文）
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.