不规则六边形网格覆盖路径规划基准数据集

该数据集由智利阿道夫·伊巴涅斯大学与智利海军联合创建，包含10,000个具有不同形态特征的不规则六边形区域实例，涵盖紧凑型、细长型和不规则型三类拓扑结构。数据通过合成方法生成，每个实例均经过深度优先搜索验证其哈密顿可行性，确保评估结果的可靠性。数据集专门用于对比分析17种经典确定性启发式算法在稀疏六边形图上的性能表现，包括覆盖成功率、路径长度、航向变化等指标。其应用领域聚焦于海事监测、搜索救援等无人系统覆盖路径规划任务，旨在解决不规则地形下算法鲁棒性评估的基准缺失问题。

This dataset was jointly created by Adolfo Ibáñez University of Chile and the Chilean Navy. It contains 10,000 instances of irregular hexagonal regions with diverse morphological characteristics, covering three types of topologies: compact, slender, and irregular. All data are generated via synthetic methods, and each instance has been verified for Hamiltonian feasibility using Depth-First Search (DFS) to ensure the reliability of subsequent evaluation results. This dataset is specifically designed for comparative performance analysis of 17 classic deterministic heuristic algorithms on sparse hexagonal graphs, with evaluation metrics including coverage success rate, path length, heading change, and others. Its application scenarios focus on coverage path planning tasks for unmanned systems such as maritime monitoring and search and rescue, aiming to address the shortage of benchmarks for algorithm robustness evaluation in irregular terrain.

搜集汇总

数据集介绍

构建方式

在海洋覆盖路径规划领域，不规则六边形网格因其各向同性的连接特性和对圆形传感足迹的近似能力而备受关注。该数据集的构建采用了系统化的生成流程：首先从三种形态类别中采样多边形区域，包括紧凑型、细长型和不规则型；随后在定向边界框框架内建立六边形镶嵌，并通过移除内部单元来模拟岛屿、浅滩和瓶颈走廊等海洋环境特征。每个实例经过严格的连通性后处理，确保消除离散化带来的拓扑伪影，最终形成包含28至46个可访问单元的稀疏六边形图。所有实例均通过深度优先搜索进行哈密顿可行性审计，仅保留可证明存在零重访路径的实例，从而构建了包含10000个已验证实例的基准数据集。

特点

该数据集的核心特征在于其针对海洋应用场景的专门化设计。其形态多样性涵盖了从开放巡逻区域到狭窄海峡等多种地形，能够有效评估算法在不同拓扑结构下的鲁棒性。数据集中的所有实例均经过精确的哈密顿可行性验证，确保了算法失败源于自身局限性而非实例内在不可解性。稀疏六边形图的构造模拟了实际海洋环境中的导航约束和瓶颈通道，为研究松弛覆盖与零重访遍历之间的权衡提供了理想平台。此外，数据集附带了统一的评估协议和17种经典启发式算法的实现，支持对哈密顿成功率、覆盖完成率、重访次数、路径长度和计算延迟等多维度指标进行可重复比较。

使用方法

该数据集主要作为经典确定性覆盖路径规划启发式算法的受控测试平台。研究人员可利用提供的评估脚本，在统一的图模型和起止点约定下，系统比较不同算法家族在稀疏不规则六边形图上的性能表现。数据集支持对松弛覆盖和哈密顿覆盖两种任务目标的评估，有助于揭示算法在保证完全覆盖与实现零重访之间的性能差异。具体使用时，可将新提出的启发式算法、精确算法或基于学习的方法与数据集中的17种基线算法进行对比，通过分析形态特异性行为、失败模式和实现敏感性，深入理解算法在复杂几何图上的内在机制。数据集的开源特性确保了实验的可重复性和结果的可靠性。

背景与挑战

背景概述

在海洋监测、搜索救援与环境勘测等领域，覆盖路径规划技术旨在引导无人载具高效遍历目标区域。传统研究多聚焦于矩形网格或小规模特例，缺乏对不规则拓扑结构的系统性评估。为此，智利阿道夫·伊瓦涅斯大学的Carlos S. Sepúlveda与Gonzalo A. Ruz于2026年提出了不规则六边形网格覆盖路径规划基准数据集，该数据集包含一万个经过哈密顿可行性验证的实例，涵盖紧凑型、细长型与不规则型三类形态。通过构建可复现的评估框架，该数据集为经典启发式算法在稀疏几何图上的性能比较提供了标准化测试平台，推动了海事覆盖规划领域的算法透明性与可重复性研究。

当前挑战

该数据集致力于解决不规则六边形网格上覆盖路径规划的核心挑战：如何在存在狭窄通道与瓶颈结构的稀疏图中实现零重复访问的哈密顿遍历。其构建过程面临双重困难：在领域问题层面，经典启发式算法在松弛覆盖任务中表现稳健，却难以在保持路径连续性的同时避免单元格重复访问；在数据集构建层面，需确保每个实例均具备哈密顿可行性，同时维持六边形网格的近各向同性连接特性与海事场景的几何动机。生成流程需精确控制形态分布，并通过深度优先搜索审计排除内在不可行实例，从而将算法失效归因于启发式策略局限而非数据缺陷。

常用场景

经典使用场景

在海洋监测与无人系统路径规划领域，不规则六边形网格覆盖路径规划基准数据集为经典启发式算法的性能评估提供了标准化测试平台。该数据集通过生成一万个具有紧凑、细长和不规则形态的海事兴趣区域实例，并确保每个实例均满足哈密顿可行性，使得研究者能够在统一图模型和评估协议下，系统比较十七种确定性启发式算法在稀疏六边形图上的表现。这一经典使用场景不仅揭示了算法在零重访路径规划中的成功率差异，还凸显了端点处理策略对算法性能的关键影响，为海事覆盖任务中的路径规划方法提供了可靠的基准参考。

解决学术问题

该数据集有效解决了覆盖路径规划研究中长期存在的算法比较标准化问题。传统研究往往基于小型特例或矩形网格进行算法评估，难以全面反映算法在复杂不规则拓扑结构下的鲁棒性。通过提供大规模、形态多样且经过哈密顿可行性审计的六边形图实例，该数据集使得学术界能够精确量化经典启发式算法在稀疏几何图上的性能边界，特别是明确了松弛覆盖任务与零重访哈密顿覆盖任务之间的本质差异。这一贡献不仅提升了算法比较的可复现性，还深化了对图遍历启发式中关键设计选择（如残差度策略）的理论理解。

衍生相关工作

基于该基准数据集，一系列经典研究工作得以衍生并深化了覆盖路径规划领域的探索。例如，研究聚焦于Warnsdorff启发式变体在端点保留策略下的性能分析，揭示了残差度定义方式对算法成功率的决定性影响。同时，该数据集促进了松弛覆盖与哈密顿覆盖任务分离的量化研究，推动了针对稀疏图瓶颈结构的专用算法设计。此外，相关研究还将基准比较扩展至学习型方法与传统启发式的融合，为海事路径规划的算法演进提供了持续的动力与验证基础。