A Hierarchical Path Planning Framework for Large-Scale Sparse Environments: Layered Grid Refinement and Bidirectional Shortcuts With Application to Offshore Wind Farm Inspection

This paper addresses the computational scalability challenges in automating inspection tasks across large-scale spatial domains, where a fundamental trade-off exists between modeling fidelity for obstacle avoidance and planning tractability. While motivated by the autonomous inspection of offshore wind farms using Unmanned Surface Vessels (USVs), the proposed hierarchical framework offers a generalizable solution for navigating vast environments with sparse obstacles. Existing planners often suffer from prohibitive computational costs when processing environments with millions of grid cells. To overcome this, we present a novel multi-stage framework integrating hierarchical environment modeling with optimized search techniques. The core contributions are threefold: (1) A layered refinement grid strategy that unlike generic hierarchical structures, optimizes memory efficiency for extreme scale disparities to reduce the total grid count by 99.9%; (2) A hexagonal grid compression method that further decreases search nodes by over 95%, thereby mitigating directional bias and preserving topological clustering fidelity; and (3) A bidirectional shortcut-embedded A algorithm that executes efficient local detour planning within constrained corridors. Experimental validation in a large-scale real-world scenario (54 turbines) demonstrates the framework’s efficacy. The proposed method achieves hierarchically-refined path inspection paths in 1.21 seconds, significantly outperforming a baseline approach (5.97 seconds). This work provides a scalable, computationally efficient solution applicable to broad classes of automated inspection and logistics systems.