Real-Time Parallel-Serial LiDAR-Based Localization Algorithm with Centimeter Accuracy for GPS-Denied Environments

Jakub Niedzwiedzki, Adam Niewola, Piotr Lipinski, Piotr Swaczyna, Aleksander Bobinski, Pawel Poryzala, Leszek PodsedkowskiSensors 2020 · DOI

TL;DR

This paper introduces a novel real-time localization algorithm for robots operating in GPS-denied environments like caves and mines. By fusing LiDAR and IMU data and employing a unique parallel-serial Extended Kalman Filter (EKF) approach with a triangular mesh map, the algorithm achieves centimeter-level accuracy, outperforming existing methods.

What Problem Does This Paper Address?

Precise robot localization is crucial for autonomous systems, but GPS is unreliable in many environments, such as underground mines, caves, and building interiors. These "GPS-denied" areas present a significant challenge for navigation. While various localization techniques exist, achieving centimeter-level accuracy in complex, feature-poor 3D environments like mines and caves in real-time remains an open problem. Existing LiDAR-based methods often struggle with computational complexity or lack the required precision for such demanding applications.

Methods

The core of the proposed solution is a real-time parallel-serial algorithm that leverages LiDAR and Inertial Measurement Unit (IMU) data. The key innovations include:

  • Triangular Mesh Map: Instead of using dense point clouds, the algorithm uses a 3D triangular mesh as a reference map. This significantly reduces storage requirements while maintaining accuracy.
  • Per-Scan Point EKF: A modified Extended Kalman Filter (EKF) is applied to each LiDAR scan point, calculating its position relative to the triangular mesh. This approach avoids the computational burden of full point cloud comparisons.
  • Parallel-Serial EKF Implementation: To achieve real-time performance, the authors developed a hybrid parallel-serial EKF. The initial prediction and map search steps are parallelized, while the Kalman gain calculation and update are performed serially. This hybrid approach avoids the computationally expensive inversion of large matrices inherent in purely parallel EKF methods.

Datasets

The experiments were conducted in two real-world GPS-denied environments: a mine gallery and a cave. Triangular mesh maps were generated from point clouds captured by stationary FARO scanners. These maps served as the ground truth for localization. The paper also mentions using Gaussian mixture maps for comparison with a reference algorithm.

Key Insights and Ideas

  • Triangular Meshes are Sufficient: The research demonstrates that a triangular mesh representation of the environment, while less dense than a full point cloud, is sufficient for achieving centimeter-level localization accuracy in complex 3D spaces. This is a significant finding for reducing computational and storage overhead.
  • Parallel-Serial EKF for Real-Time: The hybrid parallel-serial EKF is crucial for achieving real-time performance. By parallelizing computationally intensive parts and serializing others strategically, they bypass the bottleneck of large matrix inversions common in purely parallel EKF approaches.
  • Centimeter Accuracy in Challenging Environments: The ability to achieve centimeter-level accuracy in environments like caves and mines, which are notoriously difficult for localization, is a major breakthrough. This opens doors for more sophisticated robotic operations in such settings.

Key Results

  • Centimeter-Level Accuracy: The proposed parallel-serial algorithm achieved centimeter-level accuracy, with RMSE values as low as 1.07 cm in the mine gallery and 2.96 cm in the cave.
  • Outperforms State-of-the-Art: The algorithm demonstrated a significant improvement in accuracy compared to a reference Gaussian Mixture Model (GMM) algorithm, achieving approximately twice the accuracy.
  • Real-Time Performance: The parallel-serial implementation achieved real-time performance, processing up to 250,000 points per second on an NVIDIA Jetson TX2 and 450,000 points per second on a Jetson Xavier.

Limitations and Future Work

  • LiDAR-to-Processing Speed Mismatch: The algorithm's performance can be affected if the LiDAR scanning speed exceeds the computer's processing speed, leading to some scan points being omitted.
  • Map Resolution Dependence: The accuracy of localization is influenced by the resolution of the triangular mesh map.
  • Future Work: The authors suggest that the parallel-serial localization algorithm is general in nature and can be extended to other applications. Further research could explore increasing the kernel size for GPUs with more processing units and investigating its applicability in other complex environments.

Summary updated

BibTeX
@article{niedzwiedzki2020real,
  author = {Jakub Niedzwiedzki and Adam Niewola and Piotr Lipinski and Piotr Swaczyna and Aleksander Bobinski and Pawel Poryzala and Leszek Podsedkowski},
  title = {{Real-Time Parallel-Serial LiDAR-Based Localization Algorithm with Centimeter Accuracy for GPS-Denied Environments}},
  journal = {Sensors},
  year = {2020},
  doi = {10.3390/s20247123},
}
Figure