Towards efficient LiDAR mapping for robotics

Abstract

Mobile robots have been increasingly popular as a replacement for human labor, especially in hazardous or challenging environments. Recent advancements in LiDAR technologies have greatly enhanced the sensing ability of mobile robots with longer range, denser measurements, and higher accuracy. This presents great potential for mapping systems to achieve a more comprehensive understanding of the environment. However, improved sensing ability of LiDAR sensors (e.g., dense measurements) also poses significant efficiency challenges in real-time scenarios to create a general and consistent representation of the environments. This thesis addresses critical challenges related to computational efficiency in LiDAR mapping, with a focus on two typical modules in robotics: simultaneous localization and mapping (SLAM) and occupancy mapping.

The contributions of this thesis are as follows:

Firstly, this thesis proposes a new data structure, the incremental k-d tree (ikd-Tree), to efficiently manage LiDAR point clouds. The ikd-Tree supports incremental updates including point-wise and box-wise operations of insertion, delete, and re-insertion, providing a high level of flexibility for mapping and navigation in robotic applications. To ensure the efficiency of incremental updates and nearest neighbor search, the ikd-Tree employs a twin-threaded re-balancing mechanism that partially rebuilds unbalanced (sub-)trees after each update. The efficiency of the proposed ikd-Tree is validated with a theoretical time complexity analysis as well as benchmark experiments, which demonstrate its superior performance compared to static k-d trees.

Secondly, this thesis presents FAST-LIO2, a fast, accurate, and versatile LiDAR-inertial framework. FAST-LIO2 takes advantage of the high efficiency of ikd-Tree to incrementally register raw points into a point cloud map, eliminating the need for extracting geometric features (e.g., planes and edges) and fully exploiting subtle environmental features. This approach results in significantly improved accuracy and robustness in cluttered environments. Moreover, the removal of the feature extraction module enables FAST-LIO2 to be adaptive to a wide range of emerging LiDAR sensors with different scanning patterns. This thesis also presents exhaustive experiments for validation, including benchmark comparison of accuracy and efficiency against state-of-the-art methods, as well as real-world applications on both handheld and aerial platforms. The results demonstrate the superior performance of FAST-LIO2 compared to other methods and highlight its generality in various challenging scenarios.

Finally, this thesis introduces D-Map, an efficient occupancy mapping framework for high-resolution LiDAR sensors with three key novelties. Firstly, D-Map utilizes a depth image for occupancy state determination as an alternative to ray casting. Secondly, an on-tree update strategy is proposed on a tree-based map structure that reduces the amount of redundant updates. Thirdly, D-Map takes advantage of the low false-alarm rate of LiDAR sensors to directly remove known cells from the map, resulting in a decreasing map size that improves computational and memory efficiency due to the decreasing map size. This thesis presents extensive benchmark experiments to validate the superior efficiency of D-Map compared to existing methods and demonstrates its effectiveness in real-world applications for real-time occupancy mapping using high-resolution LiDAR sensors.