A Novel Hierarchical Topology-Metric Road Graph (HTMRG) Construction for UGV Navigation

Autonomous navigation in complex environments requires efficient and reliable road-network representations for fast path planning. However, traditional grid and skeleton-based approaches often suffer from high computational cost and limited path quality. This paper proposes a Hierarchical Topology-Metric Road Graph (HTMRG) framework for autonomous navigation of unmanned ground vehicles (UGVs). The method automatically constructs a hierarchical road graph from grid maps by identifying key intersection structures and generating smooth corridor and intersection connections. In addition, a dedicated start–goal insertion strategy is developed to enable efficient graph-based path planning in previously unexplored scenarios. Extensive simulations and real-world experiments demonstrate that the proposed method can automatically construct hierarchical road graphs and generate smooth, high-quality paths with improved planning efficiency and robustness. The HTMRG framework has also been successfully integrated into a UGV system, validating its effectiveness and practicality in real-world navigation scenarios.