Kilometer-Scale GNSS-Denied UAV Navigation via Heightmap Gradients: A Winning System from the SPRIN-D Challenge

Technical Summary: Kilometer-Scale GNSS-Denied UAV Navigation via Heightmap Gradients

Problem Definition
Reliable long-range navigation for Unmanned Aerial Vehicles (UAVs) in Global Navigation Satellite System (GNSS)-denied environments remains a significant challenge. Standard odometry methods, such as Visual-Inertial Odometry (VIO) and LiDAR-Inertial Odometry (LIO), accumulate unbounded drift over time, particularly in previously unseen areas where loop closures are unavailable. While deep learning-based geolocalization offers high accuracy, it is often computationally prohibitive for real-time execution on embedded, resource-constrained platforms. Conversely, existing odometry-only systems are efficient but fail to maintain bounded error over kilometer-scale trajectories. The core problem addressed is how to manage drift using available geodata on a low-altitude UAV with limited computational power, specifically without relying on prior dense mapping or pre-recorded maps of the specific mission area.

Methodology
The authors present a fully onboard system developed for the SPRIN-D Funke Fully Autonomous Flight Challenge, designed to navigate a 9 km sequence of waypoints below 25 m Above Ground Level (AGL) without GNSS. The system integrates perception, mapping, planning, and control into a cohesive architecture running on CPU-only hardware (Intel NUC i7).

• Hardware and Perception: The UAV utilizes a heterogeneous sensor suite including a Livox Mid-360 LiDAR for dense point clouds, an Intel RealSense D435 for short-range obstacle perception, and a Bluefox RGB camera paired with an IMU for VIO (using OpenVINS). To ensure VIO reliability, the IMU and camera are mechanically decoupled from the airframe via 3D-printed silent blocks to attenuate high-frequency vibrations.
• Localization Pipeline: The core innovation is a lightweight drift-correction method that fuses odometry with prior geodata.
  • Heightmap Generation: A local occupancy map is generated from LiDAR data and converted into a 2D heightmap (1 m resolution) representing the maximum heights of obstacles within bins.
  • Gradient-Based Matching: Instead of matching absolute elevations (which are unreliable due to barometric noise and ground slope), the system matches the gradients of the local heightmap against a prior geo-referenced Digital Elevation Model (DEM). Only gradients with absolute values greater than 5 m are considered, filtering out small or transient objects and emphasizing stable structures like trees and buildings.
  • Template Matching: A non-normalized correlation coefficient is used to compare the binarized edge maps of the local heightmap against the prior map.
  • Clustered Particle Filter: The similarity scores are fused with odometry and compass data in a particle filter. To handle perceptual aliasing and odometry noise, the system employs K-means clustering on the particle set, selecting the centroid of the largest cluster as the final position estimate.
• Mission Control: A finite-state machine manages the mission, transitioning between navigation, waypoint detection (using a lightweight YOLOv8n model trained on synthetic and real data), and search patterns if a waypoint is not immediately detected.

Key Contributions

1. Full Onboard System: The authors demonstrate a complete UAV system capable of kilometer-scale GNSS-denied flight below 25 m AGL, operating entirely onboard without dedicated GPU acceleration.
2. Novel Drift-Correction Method: They introduce a specific localization technique based on template matching of LiDAR-derived heightmap gradients. This approach bridges LiDAR-based structural cues and semantic information, offering a computationally efficient and robust solution for mixed urban-forest environments.
3. Field Validation: The system was validated in the SPRIN-D Challenge across diverse environments (urban, forest, open fields), achieving substantial drift reduction compared to raw odometry.

Results
The system was evaluated during the SPRIN-D Challenge on the Erding airbase.

• Performance: The team achieved first place in the competition. The system successfully executed multiple kilometer-scale flights (up to ~1.3 km per flight) with an overall localization Root Mean Square Error (RMSE) below 11 m. In contrast, compass-aligned odometry alone exhibited RMSEs up to 53 m.
• Drift Correction: In test flights where the localization was intentionally initialized 32 m off the true position, the system successfully re-localized and reduced the error to approximately 4 m by the end of the flight.
• Environmental Robustness: The method performed particularly well in urban environments with distinct features. In open fields with fewer features, the system relied more heavily on odometry, though the gradient matching still provided corrections when distinctive structures were encountered.
• Limitations: Flights were primarily terminated due to battery constraints or hardware issues (e.g., WiFi card failures) rather than localization drift, indicating that the localization algorithm was not the primary bottleneck for mission range.

Significance and Claims
The paper claims that the proposed system provides a foundational blueprint for resilient GNSS-denied autonomy. The authors emphasize that for long-range missions, the ability to recover from periods of high uncertainty and re-localize is more critical than maintaining consistently low instantaneous RMSE. They highlight that no single sensor is fully reliable (noting compass drift near reinforced concrete) and that sensor fusion is essential. The work demonstrates that lightweight, gradient-based geodata matching can effectively correct odometry drift in diverse, unseen environments on resource-constrained hardware, enabling practical deployment of autonomous UAVs in scenarios where GNSS is unavailable.