SuperLoc

The Key to Robust LiDAR-Inertial Localization Lies in Predicting Alignment Risks

SuperLoc

SuperLoc: The Key to Robust LiDAR-Inertial Localization Lies in Predicting Alignment Risks

Shibo Zhao*, Honghao Zhu*, Yuanjun Gao, Beomsoo Kim, Yuheng Qiu, Aaron M. Johnson, Sebastian Scherer

*Equal contribution
Carnegie Mellon University

 đź“„Paper    arXiv    Code    Robustness Metrics  
Preview 1
Preview 2
Preview 3

Overview Video


About SuperLoc

Map-based LiDAR localization, while widely used in autonomous systems, faces significant challenges in degraded environments due to lacking distinct geometric features. This paper introduces SuperLoc, a robust LiDAR localization package that addresses key limitations in existing methods. SuperLoc features a novel predictive alignment risk assessment technique, enabling early detection and mitigation of potential failures before optimization (check out Why Predictive Alignment Risk). This approach significantly improves performance in challenging scenarios such as corridors, tunnels, and caves. Unlike existing degeneracy mitigation algorithms that rely on post-optimization analysis and heuristic thresholds, SuperLoc evaluates the localizability of raw sensor measurements. Experimental results demonstrate significant performance improvements over state-of-the-art methods across various degraded environments. Our approach achieves a 49.7% increase in accuracy and exhibits the highest robustness. To facilitate further research, we will release our implementation along with datasets from eight challenging scenarios.

SuperLoc Figure

SuperLoc is to our knowledge the first open-source LiDAR-inertial localization system that not only predicts alignment risks, and estimates the observability of scan, but also can actively incorporate pose priors from other odometry sources before failure occurs. The entire process doesn't require predefined heuristic thresholds to detect degeneration and it has been evaluated in various challenging environments including caves, long corridors, flat open areas, and staircases.

Why Predictive Alignment Risk?

â–Ľ

Dealing degeneracy with LiDAR-Inertial localization in SLAM (Simultaneous localization and mapping) community has been an active research topic for more than a decade. The motivation behind such research is to investigate failures in ICP (Iterative Closest Point), the principal algorithm used for LiDAR-Inertial localization. ICP calculates the optimal transformation between two sets of point clouds. As Censi[1] concluded, ICP failures occur due to three main reasons:

  1. Bad initial guess for ICP optimization
  2. Sensor Noise
  3. Degeneracy

To address the question Why Predict Alignment Risk?, we examine common approaches to detecting and preventing degeneracy in robotics and their limitations. Approaches from previous literature can be best categorized into two methods:

  1. Detect ICP failures under degeneracy through ICP hessian analysis[2][4][5] and use this analysis to constrain ICP pose solving.
  2. Fuse external sensor sources using pre-defined or ICP covariance[8] to prevent failures.

However, there are two limitations associate with using ICP hessian analysis and covariance-based sensor fusion:

  1. Degeneracy detection using ICP hessian is difficult to generalize across different sensor modalities and environments.
  2. Covariance under degeneracy is non-Gaussian.

This article will unfold these limitations in more details. But first, let's revisit how can we obtain ICP covariance and its hessian to detect degeneracy, using Prakhya et al.[4] and Tuna et al.[3] as reference.

ICP Covariance Modeling and Hessian Analysis

Let assume z be the measurements and x be the output of an function A that minimizes an objective function J i.e.,

\[\mathbf{x}=A(\mathbf{z})=\operatorname{argmin}_{\mathbf{X}} J(\mathbf{z}, \mathbf{x}) \tag{1}\]

Then the approximate value of the covariance of \(\mathbf{x}\) in terms of \(A(\mathbf{z})\) will be,

\[\operatorname{cov}(\mathbf{x})=\operatorname{cov}\left(\left.A(\mathbf{z})\right|_{\mathbf{z}=\mathbf{z}_o}\right) \approx \frac{\partial A}{\partial \mathbf{z}_o} \operatorname{cov}(\mathbf{z}) \frac{\partial A^T}{\partial \mathbf{z}_o}\tag{2}\]

Using the implicit function theorem:

\[\frac{\partial A}{\partial \mathbf{z}_o}=-\left(\frac{\partial^2 J}{\partial \mathbf{x}^2}\right)^{-1}\left(\frac{\partial^2 J}{\partial \mathbf{z} \partial \mathbf{x}}\right)\tag{3}\]

Rewrite the equation into:

\[\operatorname{cov}(\mathbf{x})=\left(\frac{\partial^2 J}{\partial \mathbf{x}^2}\right)^{-1}\left(\frac{\partial^2 J}{\partial \mathbf{z} \partial \mathbf{x}}\right) \operatorname{cov}(\mathbf{z})\left(\frac{\partial^2 J}{\partial \mathbf{z} \partial \mathbf{x}}\right)^T\left(\frac{\partial^2 J}{\partial \mathbf{x}^2}\right)^{-1}\tag{4}\]

The objective function for point-to-point ICP is formulated as:

\[J=\sum_{i=1}^n\left\|\mathbf{R} \mathbf{P}_{\mathbf{i}}+\mathbf{T}-\mathbf{Q}_{\mathbf{i}}\right\|^{\mathbf{2}}\tag{5}\]

where \(\{\mathbf{P}_{\mathbf{i}},\mathbf{Q}_{\mathbf{i}}\}\) are the point cloud correspondences, and \([\mathbf{R}, \mathbf{T}]\) is the homogeneous transformation estimated by ICP. The ICP covariance can be calculated using the above equation, where \(\mathbf{x}=\left[\begin{array}{@{}llllll@{}}x & y & z & r & p & y\end{array}\right]\) and \(\mathbf{z}\) represents \(n\) sets of correspondences \(\{\mathbf{P}_{\mathbf{i}},\mathbf{Q}_{\mathbf{i}}\}\). \(\frac{\partial^2 \mathbf{J}}{\partial \mathbf{x}^2}\) is the ICP hessian matrix \(\mathbf{H} \in \mathbb{R}^{6\times6}\).

Apply eigen-decomposition to \(\mathbf{H}\):

\[\boldsymbol{H}=\boldsymbol{V} \Sigma \boldsymbol{V}\tag{6}\]

where diagonal element of \(\Sigma \in\left\{\operatorname{diag}(\boldsymbol{v}): \boldsymbol{v} \in \mathbb{R}_{\geq 0}^n\right\}\) are eigenvalues and \(\boldsymbol{V} \in \mathbb{R}^{6 \times 6}\) are the eigenvectors in matrix form. The idea of degeneracy detection is to observe the null space of \(\mathbf{H}\). By examining \(\Sigma\), one can identify the least-constrained pose elements of \(\mathbf{x}\) by looking at the lowest eigenvalues.

Degeneracy detection using ICP hessian is difficult to generalize

The effectiveness of ICP hessian analysis for degeneracy detection varies significantly across different LiDAR sensors and environments. Nubert et al. [6] demonstrated this variability through an experiment comparing the lowest eigenvalues from two LiDAR sensors: Velodyne and Ouster, as shown in Fig. 1. Additional validation using the SuperLoc dataset (Cave03 and Floor01) revealed similar variations across different environments, as shown in Fig. 2. These large differences in lowest eigenvalues indicate that eigenvalue-based parameters cannot be over-applied across different sensor modalities or environments, limiting the Hessian’s generalizability. This makes constrained ICP using eigenvalue-based appraoch [5][6] less durable.

Eigenvalue comparison

Figure 1: Comparison between different LiDAR sensors (Nubert et al.)

Environment comparison

Figure 2: Comparison between different environments: Degeneracy period indicates the most degraded section of each dataset.

Covariance under degeneracy is non-Gaussian

A Gaussian noise model is crucial for performing sensor fusion. As mentioned earlier, sensor fusion with external sources such as visual odometry, GPS, etc. is a common method to prevent degeneracy. Sensor fusion is typically implemented using either Factor Graphs (GTSAM)[7] or Extended Kalman Filters (EKF). Both approaches solve for pose estimates based on the assumption that all sensor measurements follow a Gaussian noise model. In other words, the covariance matrix for each measurement needs to be non-singular or full rank. In SuperLoc, we use Factor Graphs, which inference Maximum a Posteriori (MAP) estimation with Gaussian noise models into a nonlinear least-squares problem.

Factor graph

Figure 3: Factor graph for the toy SLAM problem

\[X^{\text {MAP }} =\underset{X}{\operatorname{argmax}} \phi(X) =\underset{X}{\operatorname{argmax}} \prod_i \phi_i\left(X_i\right)\tag{7}\]

Here, \(\phi_i\left(X_i\right)\) are factors, represented by black dot in Fig. 3. Each factor is a function of state variable \(x_i\) and measurement \(z_i\). \(h_i\) is the measurement function that remap state variable \(x_i\) into measurement space.

\[\phi_i\left(X_i\right) \propto \exp \left\{-\frac{1}{2}\left\|h_i\left(X_i\right)-z_i\right\|_{\Sigma_i}^2\right\}\tag{8}\]

Take negative log of \(\underset{X}{\operatorname{argmax}}\) of Eq. 6, and drop \(\frac{1}{2}\) factor,

\[X^{\text {MAP }}=\underset{X}{\operatorname{argmin}} \sum_i\left\|h_i\left(X_i\right)-z_i\right\|_{\Sigma_i}^2\tag{9}\]

Rewrite the Mahalanobis norm as some term e:

\[\|e\|_{\Sigma}^2 \triangleq e^{\top} \Sigma^{-1} e=\left(\Sigma^{-1 / 2} e\right)^{\top}\left(\Sigma^{-1 / 2} e\right)=\left\|\Sigma^{-1 / 2} e\right\|_2^2\tag{10}\]

And with linearization of nonlinear problem,

\[h_i\left(X_i\right)=h_i\left(X_i^0+\Delta_i\right) \approx h_i\left(X_i^0\right)+H_i \Delta_i\tag{11}\]

where Jacobian \(H_i\) is \(\frac{\partial h_i\left(X_i\right)}{\partial X_i}\), and we can rewrite Eq. 9 into,

\[\begin{aligned} \Delta^* & =\underset{\Delta}{\operatorname{argmin}} \sum_i\left\|h_i\left(X_i^0\right)+H_i \Delta_i-z_i\right\|_{\Sigma_i}^2 \\ & =\underset{\Delta}{\operatorname{argmin}} \sum_i\left\|H_i \Delta_i-\left\{z_i-h_i\left(X_i^0\right)\right\}\right\|_{\Sigma_i}^2 \end{aligned}\tag{12}\]

Pre-multiply Jacobian \(H_i\) and prediction error by \(\Sigma^{-1 / 2}\) using Eq. 10,

\[\begin{aligned} A_i & =\Sigma_i^{-1 / 2} H_i \\ b_i & =\Sigma_i^{-1 / 2}\left(z_i-h_i\left(X_i^0\right)\right) \end{aligned}\tag{13}\]

The final standard least-squares problem,

\[\begin{aligned} \Delta^* & =\underset{\Delta}{\operatorname{argmin}} \sum_i\left\|A_i \Delta_i-b_i\right\|_2^2 \\ & =\underset{\Delta}{\operatorname{argmin}}\|A \Delta-b\|_2^2 \end{aligned}\tag{14}\]

To calculate Equation 10, one can either use a pre-defined covariance or ICP covariance. However, this covariance becomes non-Gaussian or rank-deficient under degeneracy. Our cave dataset demonstrates this through high condition numbers in the ICP covariance matrix just before localization failures, as shown in Fig. 4. This indicates imminent rank deficiency during degeneracy. Using rank-deficient covariance in factor graph optimization results in unconstrained pose estimates along the degenerate direction, as shown in Fig. 5. Therefore, maintaining a well-ranked ICP covariance is crucial for optimal sensor fusion.

Condition number

Figure 4: Large conditional number is present when degeneracy happened

Cost function

Figure 5: Visual representation of factor graph objective function: The red arrow indicates an unconstrained direction in the solution space for rank-deficient cases.

Conclusion

We have examined key limitations in using ICP hessian its covariance for degeneracy detection and prevention in LiDAR-inertial localization. First, we demonstrated that eigenvalue-based degeneracy detection lacks generalizability across different sensor modalities and environments, as evidenced by significantly varying eigenvalue patterns between different LiDAR sensors and testing environments. Second, we showed that ICP covariance becomes non-Gaussian under degeneracy, leading to unconstrained solutions in factor graph optimization. For our Predict Alignment Risk, we first detect degeneracy at front end rather then during ICP. Our method analyzes the geometric contribution of pointcloud features and quantify a scale between [0, 1], making it more applicable to different cases compared to eigenvalues. Next, we use this risk to formulate full rank covariance to allow sensor fusion with other sensors using our Active Sensor Fusion. This makes our Predict Alignment Risk more robust and reliable compare to ICP analysis approach.

References

A. Censi, "An accurate closed-form estimate of icp's covariance", in Proceedings 2007 IEEE international conference on robotics and automation
J. Zhang, M. Kaess, and S. Singh, "On degeneracy of optimization-based state estimation problems", in 2016 IEEE International Conference on Robotics and Automation (ICRA)
S. M. Prakhya, L. Bingbing, Y. Rui and W. Lin, "A closed-form estimate of 3D ICP covariance", 2015 14th IAPR International Conference on Machine Vision Applications (MVA), Tokyo, Japan
Tuna, T., Nubert, J., Nava, Y., Khattak, S., & Hutter, M. (2022). "X-ICP: Localizability-Aware LiDAR Registration for Robust Localization in Extreme Environments", arXiv preprint arXiv:2211.16335
W. Talbot et al., "Principled ICP Covariance Modelling in Perceptually Degraded Environments for the EELS Mission Concept," 2023 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Detroit, MI, USA
J. Nubert, E. Walther, S. Khattak and M. Hutter, "Learning-based Localizability Estimation for Robust LiDAR Localization," 2022 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Kyoto, Japan, 2022
M. Kaess, H. Johannsson, R. Roberts, V. Ila, J. Leonard and F. Dellaert, "iSAM2: Incremental smoothing and mapping with fluid relinearization and incremental variable reordering," 2011 IEEE International Conference on Robotics and Automation, Shanghai, China, 2011
W. Xu and F. Zhang, "FAST-LIO: A Fast, Robust LiDAR-Inertial Odometry Package by Tightly-Coupled Iterated Kalman Filter," in IEEE Robotics and Automation Letters, vol. 6, no. 2, pp. 3317-3324, April 2021

Cave

Multi-floor

Long Corridor

Comparison with other methods


To benefit the open community, our localization package also includes following features,

Robust Initialization

Transition between mapped and unmapped region

Ground Truth Map

Ground Truth Maps

To benefit the open community, we release the following ground truth maps for localization:

Dataset

All datasets from our paper is released as follow,

Name Source Location Robot Sensor Trajectory Duration Rosbag Calibration (Extrinsics) Calibration (Intrinsics) GT Map GT Traj.
Cave01 SuperLoc Laurel Craven Handheld RGB,LiDAR,IMU 416 838 link Google Baidu Google Baidu link link
Cave02 SuperLoc Laurel Craven Handheld RGB,LiDAR,IMU 475 986 link Google Baidu Google Baidu link link
Cave03 SubT-MRS Laurel Craven Handheld RGB,LiDAR,IMU 490 768 link Google Baidu Google Baidu link link
Cave04 SuperLoc Laurel Craven Handheld RGB,LiDAR,IMU 597 959 link Google Baidu Google Baidu link link
Corridor01 SubT-MRS Hawkins RC2 RGB,LiDAR IMU 617 279 link Google Baidu Google Baidu link link
Corridor02 SuperLoc Hawkins RC1 RGB,LiDAR IMU 690 893 link Google Baidu Google Baidu link link
Floor01 SubT-MRS Hawkins SP1 RGB,LiDAR,IMU 270 480 link Google Baidu Google Baidu link link
Floor02 (bonus) SuperLoc Hawkins SP1 RGB,LiDAR,IMU 410 2190 link Google Baidu Google Baidu link link

Ground truth trajecotry follows TUM format,

timestamp x y z q_x q_y q_z q_w

Acknowledgments

The authors would like to express sincere thanks to Guofei Chen for helping us collect the dataset. The authors would like to thank Professor Ji Zhang for letting us borrow the Diablo platform and offering constructive advice.

Citation

coming soon

Contacts

If you have any question or want to contribute this work, please feel free to send email to Shibo Zhao (shiboz@andrew.cmu.edu). Thank you! :)