text:
\section{Introduction}
\label{sec:intro}

Autonomous navigation is key to a large set of mobile robot applications, such as self-driving vehicles on the road~\cite{liu2021role} and agricultural robots in farming~\cite{pretto2020building}. To achieve this, robot localization is an indispensable part of basically any navigation system. Today's tasks of mobile robots require such systems to work in large-scale and ever-changing environments, bringing potential challenges to robot localization and mapping.

Global navigation satellite system (GNSS) is a widely used facility for robot navigation outdoors. GNSS benefits robot localization mainly in two aspects. First, GNSS-fused methods can track the robot \textit{local} motion continuously with limited error, e.g., GNSS-aided simultaneous localization and mapping (SLAM)~\cite{cao2022gvins}. The other underlying point is that GNSS can provide information on \textit{global} position. This information can help the robot initialize its position on earth and recover its position if robot localization fails. Actually, both aspects are related to the two typical localization problems: \textit{pose tracking} and \textit{global localization}, which are introduced in the well-known Probabilistic Robotics~\cite{thrun2002probabilistic}. Different from the pose tracking problem, global localization requires a robot to localize itself globally on a given map from scratch. Thus the pose space is generally larger than that in the pose tracking problem, resulting in a challenging problem to solve.

GNSS heavily relies on data quality sent from satellites, making it impracticable in GNSS-unfriendly areas, like indoors, in dense urban environments or in forests. In such environments, ultra-wideband (UWB) and other signal emitters~\cite{ito2014w} can be deployed for global localization. External markers and tags~\cite{olson2011apriltag} can also provide global position and orientation information for visual-aided localization. These methods rely on the distribution of external infrastructures and modifying the environments is often not desired. Using onboard sensors without environment modification is a more general solution for mobile robots. Visual images are informative-rich and are easily obtained from cameras. Early approaches use cameras to achieve global visual localization~\cite{lowry2015visual}. Global visual localization is a topic of significant relevance and has attracted lots of research interests~\cite{garg2021your}.

Light detection and ranging (LiDAR) sensors have been developed dramatically in the last 25 years. Early laser scanner only provides 2D laser points with low resolution and range~\cite{thrun2002probabilistic}. The development of sensor technology promoted LiDAR sensing from 2D to 3D, and from sparse to fairly dense point clouds. In the 2007 DARPA Urban Challenge, Velodyne HDL-64E sensor was mounted on five of the six automated vehicles that finished the race~\cite{buehler2009darpa}. LiDAR sensors are becoming standard equipment in the robotics community. LiDAR sensors directly provide distance measurements via emitting and receiving light. Compared to visual images from cameras, these long-range measurements are more robust to illumination and appearance changes, making global LiDAR localization more practicable in large-scale and ever-changing environments. This drives us to provide a comprehensive review of global localization using LiDAR sensors.

\subsection{Problem Formulation and Scope}
\label{sec:terms}

Global localization aims at estimating a robot pose on a prior map using single scans or sequential data. The prior map is built using SLAM or other similar techniques. Given one single LiDAR point cloud as input or measurement, we name this problem as a \emph{single-shot} global localization. Note that this measurement could be one LiDAR \textit{scan} at one timestamp~\cite{chen2021overlapnet} or an accumulated LiDAR \textit{submap} with a robot moving~\cite{dube2020segmap}. In this survey, both of them are LiDAR point clouds in this survey and can be regarded as one measurement for a single-shot global localization system. We do not make a specific distinction between these two kinds of measurements although single-shot global localization with a sparse LiDAR scan is more challenging compared to with a dense LiDAR submap. When given a continuous stream of scans or submaps as measurements, this problem is then converted to \emph{sequential} global localization. The difference between single-shot and sequential global localization is that the latter takes multiple LiDAR point clouds as inputs, and sometimes also uses additional odometry information to enhance the global localization performance~\cite{pepperell2014all}. The sequential LiDAR measurements could be sequential scans or sequential submaps.

Global localization methods are related to three situations as follows.
\subsubsection{Loop Closure Detection}
In a SLAM system, loop closure detection (LCD) detects whether a robot has returned to a previously visited location or place. Therefore, this is often called place recognition. More strictly, knowing re-visited locations is not enough for performing loop closing in SLAM. The relative transformation between the current location and previous ones is typically needed, e.g., loop closing for a graph-based consistent mapping~\cite{kummerle2011g,dellaert2012factor}. In the context of this paper, we use LCD and loop closing alike. Both contain revisited location detection and relative transformation estimation.

\subsubsection{Re-localization} Re-localization can help a robot recover when pose tracking failed or the robot has been kidnapped. It can also help wake the robot up at the start of navigation. The core difference between LCD and re-localization is in the data sequence: LCD is a \emph{intra-sequence} problem, which means measurements and a map are in the same sequence; re-localization is a \emph{inter-sequence} problem that measurements and a map are collected from different data sequences~\cite{knights2022wild}. Re-localization might be applied to long-term multi-session sequences. In such a case, environmental changes might exist if re-localization is tested on an outdated map.

\subsubsection{Cross-robot Localization}
Multiple maps can be generated from multiple robots using incremental SLAM or other offline mapping techniques. These maps might be with partial overlap but are under their own coordinate. Cross-robot localization, or multiple-robot mapping, aims to localize a robot globally on another robot's map. Multiple isolated maps could be merged together using cross-robot localization. This problem is mathematically identical to the single-robot re-localization~\cite{thrun2002probabilistic} but in a \textit{multi-robot} or parallel manner. Online cross-robot localization is performed on a single-session sequence incrementally collected by multiple robots, and perspective changes will happen under this condition.

Figure~\ref{fig:applications} sketches these three typical situations. They all have one thing in common: \emph{a robot needs to globally estimate relative transformations between its current measurements and the own or other's map}. We name this ability as global localization. In general, global localization works with different sensors and with fused sensor modalities. This survey focuses on the global LiDAR localization problem and relevant techniques.

\begin{figure}[t]
\centering
\includegraphics[width=9cm]{figure/applications.pdf}
\caption{Three typical situations. From top to down: single-robot intra-sequence LCD (loop closing); single-robot inter-sequence re-localization; cross-robot inter-sequence localization. Green-filled boxes and black border boxes indicate the measurement and map, respectively. Orange lines are possible relative transformations for global localization problems.}
\label{fig:applications}
\end{figure}

\begin{figure*}[t]
\centering
\includegraphics[width=\linewidth]{figure/organization.pdf}
\caption{Fish-shaped paper structure. This survey starts the problem formulation and related introduction at the fish head. Then the fish body part contains the main subtopics of the global LiDAR localization problem: map framework, single-shot/sequential global localization and cross-robot localization. Finally, an extended discussion on open problems is presented at the fish tail.}
\label{fig:framework}
\end{figure*}

\subsection{Paper Organization}

Our paper structure is similar to a fish, as illustrated in Figure~\ref{fig:framework}. Section~\ref{sec:intro} details the global localization problem and the scope of this survey. Before introducing methods for this problem, we present three types of map frameworks in Section~\ref{sec:map} that are commonly used for global localization. Section~\ref{sec:single} and Section~\ref{sec:sequential} then provide an overview of existing methods based on the number of measurements: single-shot or sequential. The former focuses on matching a single LiDAR point cloud on a given map, while the latter takes sequential measurements to approximate the ground truth pose. Methods in Section~\ref{sec:single} and Section~\ref{sec:sequential} have been validated in single-robot LCD and re-localization applications. Then in Section~\ref{sec:apply}, the global localization problem is extended to the multi-robot cross-localization. Finally, Section~\ref{sec:discussion} provides discussions about open challenges and emerging issues of global LiDAR localization. A conclusion of this survey is presented in Section~\ref{sec:conclusion}.

\subsection{Relationship to Previous Surveys}

Lowry \emph{et al.}~\cite{lowry2015visual} provide a thorough review on visual place recognition in 2015. They start by discussing the ``place'' definition and introduce related techniques for visual place recognition.
A general place recognition survey~\cite{yin2022general} reviews the place recognition topic from multiple perspectives, including sensor modalities, challenges and datasets. However, place recognition determines whether a robot revisits a previous place by retrieval, which is not equal to the concept of global localization. Toft \textit{et al.}~\cite{toft2020long} review the long-term visual localization and make evaluations on state-of-the-art approaches, such as visual place recognition (image-retrieval)-based and structure-based camera pose estimation. Elhousni \textit{et al.}~\cite{elhousni2020survey} presents a LiDAR localization survey, focusing on LiDAR-aided pose tracking for autonomous vehicles. LiDAR place recognition and pose estimation are not reviewed explicitly in these survey papers~\cite{lowry2015visual,yin2022general,toft2020long,elhousni2020survey}. From the view of global LiDAR localization, we present a complete survey that covers relevant topics, like the ones~\cite{lowry2015visual,toft2020long} on vision.

Cadena \emph{et al.}~\cite{cadena2016past} present a history of SLAM and promising research directions in 2016. SLAM has supported various robotic applications. A recent article by Ebadi \textit{et al.}~\cite{ebadi2022present} surveys recent progress on challenging underground SLAM. Specifically, SLAM aims to incrementally estimate pose and construct maps, while global localization estimates a global pose on a prior map. These two problems have a certain relevance. More concretely, LCD is a key characteristic of modern-day SLAM algorithms, as introduced in the Handbook of Robotics~\cite{stachniss2016simultaneous}. The absence of loop closing or place recognition will reduce SLAM to ~\cite{cadena2016past}. We believe this survey paper will help users make LiDAR SLAM systems more robust and accurate.

\section{Maps for Global Localization}
\label{sec:map}

Before reviewing the methodology part, it is necessary to introduce maps for robot localization. This section mainly focuses on maps that support global localization. The general-use maps are classified into three primary clusters: global metric map, feature-based map and keyframe-based submaps. The classification is based on the map's structure and its representations inside.

\subsection{Global Metric Map}
\label{sec:GMM}

A global metric map is a single map with dense metric representations describing a working environment. Generally, metric and explicit representations include 2D/3D points~\cite{lee2022learning}, grids~\cite{hess2016real},  voxels~\cite{wurm2010octomap}, and meshes~\cite{chen2021range}. The global metric map is easy to use and can provide high-precision geometric information.

But localization, whether pose tracking or global localization, is only one block in common autonomous navigation systems. In large-scale environments, the global metric map can be a burden for resource-constrained mobile robots. One might suggest that we could downsample or compress dense points while keeping the main geometric property~\cite{labussiere2020geometry,yin20203d}. But as pointed out by~\cite{chang2021map}, localization performances drop as the map size budget decreases using raw points. There are two solutions to tackle this problem: one is to use sparse local features rather than dense representations; another is to split the map space into submaps or keyframe-based submaps. We discuss these two solutions in the following two subsections.

It is worth noting that implicit map representations are becoming highly popular, including non-learning~\cite{saarinen2013normal,wolcott2015fast} and learning-based ones~\cite{kuang2022ir}. One famous work is normal distribution transform (NDT), which uses probability density functions as representations. Implicit representations use fewer parameters compared with explicit ones~\cite{lee2022learning,hess2016real,wurm2010octomap,chen2021range}.

\subsection{Global Feature Map}
\label{sec:GFM}

A global feature map keeps sparse local feature points to describe the environments. Early SLAM systems extract landmarks from laser data to support mapping and localization, like tree trunks in the Victoria Park dataset~\cite{guivant2001optimization}. These landmarks are essentially low-dimensional feature points. Nowadays, LiDAR feature points are generally with high-dimensional information~\cite{dube2017segmatch}. Hence, feature correspondence-based matching can be directly used for relative transformation estimation. More importantly, local features are sparse and easy to manage, making the navigation system more lightweight.

The main challenge of applying such maps is generating and maintaining stable feature points. For instance, a high-definition map (HD map) is a typical global feature map for self-driving vehicles. HD-map construction involves multiple onboard sensors and high-performance computation, and maintaining a global HD map is costly. As for the LiDAR-only global feature map, a powerful front-end feature extractor is necessary to ensure the map quality.

\begin{figure*}[t]
\centering
\subfigure[Section~\ref{sec:PR}: Place recognition only]{
	\includegraphics[width=8.5cm]{figure/PR.pdf}}
\subfigure[Section~\ref{sec:PRPE}: Place recognition followed by local pose estimation]{
	\includegraphics[width=8.5cm]{figure/PRPE.pdf}} \\
\subfigure[Section~\ref{sec:PEPR}: Pose estimation-coupled place recognition]{
	\includegraphics[width=8.5cm]{figure/PEPR.pdf}}
\subfigure[Section~\ref{sec:PE}: One-stage global pose estimation]{
	\includegraphics[width=8.5cm]{figure/PE.pdf}}
\caption{ Four types of single-shot global localization. $\mathcal{P}_{input}$ indicates an input data (LiDAR point cloud). $\mathcal{M}_{key}$ and $\mathcal{M}_{global}$ represent prior keyframe-based submaps and a global metric/feature map respectively. $\mathcal{M}_{ret}$ and $\mathbf{T}_{ret}$ represent a keyframe and a robot pose by place retrieval in the keyframe-based submaps. $\mathbf{T}_{est}$ is a robot pose output by pose estimation module.
}
\label{fig:single-shot}
\end{figure*}

\subsection{Keyframe-based Submaps}
\label{sec:KM}

The above two subsections describe one global map maintaining dense metric points or sparse local features, which may be impracticable when robots work in large-scale scenes.
Researchers propose to split the entire map space into submaps, and we name them keyframe-based submaps in this survey. A typical keyframe-based map contains a robot pose and aligned submap, and a topological (geometrical) connection between keyframes as additional information~\cite{lowry2015visual}. The keyframe-based submaps are easy to maintain and suitable for downstream navigation tasks~\cite{tang2019topological}.

This kind of discrete map is naturally suitable for place retrieval since each keyframe can be regarded as one ``place'' for mobile robots. The data in one keyframe could be a global descriptor for retrieval, metric grids/points for geometric registration, or with a \textit{hybrid} form containing multiple representations. Note that the distance between keyframe poses is a key factor in practice. For example, if this distance is large, or the keyframe resolution is low, fewer keyframes are needed for lightweight robot navigation. But there is a risk that localization may fail in such challenging conditions. On the other side, dense keyframes will make the map redundant.

In summary, three kinds of maps are introduced in this section. These map structures and their representations inside are the foundations that can support global LiDAR localization in the following Section~\ref{sec:single} Section~\ref{sec:sequential}. Map representation is a basic but critical topic for SLAM and other navigation-related applications. We recommend reading a review by Rosen \textit{et al.}~\cite{rosen2021advances} for readers interested in this topic.

\section{Single-shot Global Localization: \\Place Recognition and Pose Estimation}
\label{sec:single}

Single-shot global localization methods solve pose estimation using a \emph{single} point cloud only. More concretely, this point cloud could be a single LiDAR scan or a submap generated with multiple LiDAR scanners. We categorize the approaches considering their degree of \textit{place recognition}  and relative \textit{pose estimation}, as follows:
\begin{itemize}
    \item \emph{Place Recognition Only} approaches retrieve the most similar place using descriptors. The pose of a retrieved place (keyframe) is regarded as the estimated pose.
    \item \emph{Place Recognition Followed by Local Pose Estimation} first achieves place recognition and then estimates the robot pose via a customized pose estimator.
    \item \emph{Pose Estimation-coupled Place Recognition} tightly couple the two stages together. Place recognition and pose estimation benefit from a shared representation or feature space.
    \item \emph{One-stage Global Pose Estimation} directly estimates the global pose on a global map without retrieving places.
\end{itemize}

Figure~\ref{fig:single-shot} presents four types of combinations between the place recognition module and the pose estimation module.
From the perspective of maps, in Section~\ref{sec:PR}, \ref{sec:PRPE} and ~\ref{sec:PEPR}, methods generally rely on keyframe-based submaps. While in Section~\ref{sec:PE}, global localization is generally based on a global metric or feature map.

It is worth noting that the boundaries are not so clear for these four types of approaches. For instance, there are no global descriptors in several place recognition systems~\cite{bosse2009keypoint}. Local feature-based pose estimation plays an important part in place recognition. We consider they lie in the boundary of coupled methods (Section~\ref{sec:PEPR}) and one-stage methods (Section~\ref{sec:PE}), and will present them in Section~\ref{sec:PEPR} for clearance.

\subsection{Place Recognition Only}
\label{sec:PR}

Place recognition-only approaches solve the global localization problem by retrieving places in a pre-built map. This type of approach is based on keyframe-based submaps, and each keyframe generally consists of a global descriptor and a robot pose. Essentially, the core problem is to \emph{extract global descriptors and measure the similarities between them}. More specifically, these global descriptors should have a certain discriminativeness: be discriminative for different places but keep similar for places close to each other. Figure~\ref{fig:lpdnet} presents a place recognition-only approach for better understanding.

Compared to visual images, raw point clouds from LiDAR are textureless and in an irregular format, sometimes with an uneven density. These properties all bring difficulties for global descriptors extraction. We categorize current LiDAR place recognition based on how to handle LiDAR data pre-processing.

\subsubsection{Dense Points or Voxels-based} \label{sec:dense}
Dense points and dense voxels-based works refer to those that generate global descriptors directly on dense representations. Early laser scanners can only provide 2D laser points for robotic localization. Granstr{\"o}m \textit{et al.}~\cite{granstrom2009learning} design a global descriptor that consists of 20 features in a 2D laser scan, such as a covered area and a number of clusters in range data. Then handcrafted descriptors and labels are fed into a weak classifier Adaboost~\cite{freund1997decision} for training. The learning-based approach is extended to 3D laser features in~\cite{granstrom2011learning}. Instead of extracting features, Fast Histogram~\cite{rohling2015fast} encodes the range distribution of 3D points into a one-dimensional histogram for place retrieval. Earth Mover's distance is employed to measure the similarity of different histograms, which differs from Euclidean distance or Cosine distance in most place recognition methods. Inspired by~\cite{rohling2015fast}, Yin \textit{et al.}~\cite{yin2017efficient} build a 2D image-like representation based on divisions of altitude and range in a 3D LiDAR scan. Then the problem can be converted to an image classification problem that can be solved by training a 2D convolutional neural network with a basic contrastive loss~\cite{hadsell2006dimensionality}. Aside from using the range information of LiDAR scanners, DELIGHT~\cite{cop2018delight} utilizes the histograms of LiDAR intensity as the descriptor for place recognition followed by geometry verification.

\begin{figure}[t]
\centering
\includegraphics[width=9cm]{figure/LPDNet.pdf}
\caption{From LPDNet~\cite{liu2019lpd}. LPD-Net is a place recognition-only approach for global LiDAR localization. Global descriptors are extracted as place descriptions for place retrieval.}
\label{fig:lpdnet}
\end{figure}

All the methods above design handcrafted 2D or 1D histograms for LiDAR-based place recognition. This is because deep learning for 3D point clouds was not so mature then. In 2017, Qi \textit{et al.}~\cite{qi2017pointnet} proposed PointNet, which can learn local and global features for 3D deep learning tasks. Novel encoders also boost the performance of point cloud processing, like KPconv~\cite{thomas2019kpconv} for point convolution. PointNetVLAD~\cite{uy2018pointnetvlad} utilizes PointNet to extract features of 3D point clouds and aggregates them into a global descriptor via NetVLAD~\cite{arandjelovic2016netvlad}. But limited by PointNet, PointNetVLAD ignores the local geometry distribution in 3D point clouds. To address this problem, LPDNet~\cite{liu2019lpd} designs an adaptive local feature extraction module based on ten handcrafted local features, and a graph-based neighborhood aggregation module to generate a global descriptor. With the appearance of Transformer~\cite{vaswani2017attention} in diverse tasks to achieve long-range dependencies, the attention mechanism has been increasingly used to select significant local features for place recognition. PCAN~\cite{zhang2019pcan} takes local features into account and computes an attention map to determine each feature's significance. SOE-Net by Xia \emph{et al.}~\cite{xia2021soe} uses a point orientation encoding module to generate point-wise local features and feeds them into a self-attention network aggregating them to a global descriptor. Nevertheless, these methods cannot fully extract the point-wise local features around the neighbors. Hui \emph{et al.} propose a pyramid point cloud transformer network named PPT-Net~\cite{hui2021pyramid}. PPT-Net could learn the local features at different scales and aggregate them to a descriptive global representation by a pyramid VLAD. Recent work~\cite{linse} utilizes SE(3)-equivariant networks to learn global descriptors, making place recognition more robust to the rotation and translation changes. Despite the network structure design, a local consistency loss is proposed in~\cite{vidanapathirana2022logg3d} to guarantee the consistency of local features extracted from point clouds at the same place. To save memory and improve transmission efficiency, Wiesmann \textit{et al.}~\cite{wiesmann2022retriever} propose a compressed point cloud representation aggregated by an attention mechanism for place recognition. Authors also design a novel architecture for more efficient training and inference in~\cite{wiesmannkppr}.

Another popular pipeline is to voxelize the 3D point clouds first, and then extract global descriptors for place recognition. The voxeling process can make the raw 3D point clouds more regular. This makes 3D point clouds close to 3D image-like representations, i.e., each grid (2D) or cube (3D) can be regarded as one image patch. Magnusson \emph{et al.}~\cite{magnusson2009appearance,magnusson2009automatic} classify local cells into planes, lines and spheres, and then aggregate them all into a vector as a global descriptor for place recognition. The classification criteria are based on the local distributed probability density function, i.e., NDT. In the deep learning age, Zhou \emph{et al.}~\cite{zhou2021ndt} propose NDT-Transformer, which transforms the raw point cloud into NDT cells and uses the attention module to enhance the discrimination. VBRL proposed by Siva \emph{et al.}~\cite{siva2020voxel} introduces a voxel-based 3D representation that combines multi-modal features in a regularized optimization formulation. Oertel \emph{et al.} proposes AugNet~\cite{oertel2020augmenting}, an augmented image-based place recognition method that combines appearance and structure features. Komorowski \emph{et al.} introduce MinkLoc3D~\cite{komorowski2021minkloc3d}, which extracts local features on a sparse voxelized point cloud by feature pyramid network and aggregates them into a global descriptor by pooling operations. After that, they propose MinkLoc3Dv2~\cite{komorowski2022improving} as the enhancement of MinkLoc3D~\cite{komorowski2021minkloc3d}, which leverages deeper and wider network architecture with an improved training process.

\subsubsection{Sparse segments-based} \label{sec:segment}
Segmentation-based approaches refer to works that perform place recognition based on point segments, which leverage the advantages of both local and global representations. Seed~\cite{fan2020seed} segments the raw point cloud to segmented objects and encodes the topological information of these objects into the descriptor. SGPR~\cite{kong2020semantic} proposed by Kong \emph{et al.} exploits both semantic and topological information of the raw point cloud and uses a graph neural network to generate the semantic graph representation. Locus~\cite{vidanapathirana2021locus} encodes the temporal and topological information to a global descriptor as a discriminative scene representation. Gong \textit{et al.}~\cite{gong2021two} utilize spatial relations of segments in both high-level descriptors search and low-level geometric search. Overall, segmentation-based approaches are close to what our human beings think about place recognition, i.e, using high-level representations rather than low-level geometry. On the other hand, these methods heavily rely on the segmentation quality and other additional semantic information. 3D point cloud segmentation approaches have typically been time-consuming and resource intensive.

\subsubsection{Projection-based} \label{sec:proj}
Projection-based methods, in contrast to the aforementioned two categories, do not generate the descriptor directly on 3D point clouds or segments; instead, these methods project a 3D point cloud to 2D planes first and then achieve global descriptor extraction. He at al.~\cite{he2016m2dp} propose M2DP that projects the raw point cloud into multiple 2D planes, constructing the signature with descriptors from different planes. LiDAR Iris~\cite{wang2020lidar} encodes the height information of a 3D point cloud into a binary LiDAR-Iris image and converts it into a Fourier domain to achieve rotation invariance. RINet proposed by Kong \emph{et al.}~\cite{li2022rinet} converts a point cloud to a scan context image encoded by semantic information first and designs a rotation-invariant network for learning a rotation-invariant representation. Yin \textit{et al.}~\cite{yin2022fast} propose a multi-layer spherical projection via discrete 3D space. Then VLAD layer~\cite{arandjelovic2016netvlad} and spherical convolutions~\cite{cohen2018spherical} are integrated as SphereVLAD based on spherical projections. SphereVLAD can learn a viewpoint-invariant global descriptor for place recognition.

\textbf{Summary.} Early approaches in Section \ref{sec:dense} and \ref{sec:proj} tried to design handcrafted global descriptors from a traditional data processing viewpoint. With the development of neural network techniques, data-driven descriptors are becoming more and more popular, resulting in high performance on place recognition (\textgreater95\% on Recall@1 in~\cite{xu2021transloc3d,komorowski2022improving}). Several approaches have achieved fully rotation-invariant descriptors for place retrieval, like handcrafted Fast Histogram in~\cite{rohling2015fast} and learning-based SphereVLAD in~\cite{yin2022fast}. We can conclude that global descriptor extraction of 3D LiDAR point clouds has reached a level of success. However, there still remain several challenges and issues, e.g., generalization ability, that will discuss in Section~\ref{sec:generalization}.

All the methods in this subsection only provide retrieved places as output. The global localization performance is evaluated under machine learning metrics, like precision-recall curves and F-1 score. In this context, the translation precision of pose (place) is decided by the resolution of keyframes (25m for evaluation on Oxford RobotCar Dataset~\cite{maddern20171}); the precision of rotation estimation is not considered or evaluated. In practice, this actually can not meet the demand of most high-precision global localization tasks, e.g., building a consistent global map with relative transformations, or waking the robot up with a precise location.

From another point of view, global descriptors are highly compressed representations of raw LiDAR data, and there exists information loss in the compression process, especially for those end-to-end deep learning methods. This kind of representation is naturally suitable for nearest neighbor search in place retrieval but can not be used in geometric pose estimation. In the following section, we present a review of the local transformation estimation that metric representation involves.

\subsection{Place Recognition Followed by Local Pose Estimation}
\label{sec:PRPE}

This section reviews local pose estimation methods for high-precision transformation estimation. Note that this local pose estimation is independent of place recognition in this subsection. These two components are seen as separated and the global localization is achieved in a coarse-to-fine manner: first achieve place retrieval on keyframe-based submaps, then apply local pose estimation via matching input LiDAR to map data attached on the retrieved keyframe. Hence, for this group of approaches, the keyframe includes not only global descriptors for nearest neighbor search (place retrieval), but also metric representations for local pose estimation. Conventionally, the local pose estimation is achieved by precise point cloud registration.

Point cloud registration, or named scan matching, is a popular topic in robotics and computer vision. It aims at estimating the optimal transformation by minimizing the error function as follows:
\begin{equation} \label{eq:pointreg}
\mathbf{T} = \argmin_{\mathbf{T}\in\text{SE(3)}} \left( e\left(\mathcal{M}, \mathbf{T}\mathcal{P}\right) \right),
\end{equation}
in which $\mathbf{T}$ is the relative transformation (pose) to be estimated; $\mathcal{P}$ and $\mathcal{M}$ are the source points (input LiDAR measurement) and target points (prior map) respectively; $e\left( \cdot\right)$ is an error function to minimize. This subsection mainly focuses on the \textit{global} point cloud registration. Specifically, point cloud registration approaches can be categorized into two types based on whether using correspondences between these two point clouds.

\subsubsection{Correspondence-based}

If correspondences (data associations) between query measurements and map are known, the registration problem can be solved in a closed form~\cite{horn1987closed,arun1987least}. Unfortunately, the initial correspondences are unknown in practice. The most well-known algorithm to scan registration is Iterative Closest Point (ICP)~\cite{besl1992method}, which considers a basic point-to-point correspondence search and finds the optimal solution at each iteration. The ICP family follows an expectation-maximization framework that alternates between finding correspondence and optimizing pose. Despite its widespread use in point cloud registration, the quality of the registration result is limited by the presence of noise and outliers. An effective real-time registration system based on ICP is KISS-ICP~\cite{vizzo2022kiss}. To improve the original ICP algorithm, many variants have been designed. Probabilistic methods Generalized-ICP~\cite{segal2009generalized} and NDT~\cite{biber2003normal} define Gaussian models for points or voxels and perform registration in a distribution-to-distribution manner, therefore reducing the influence of noise. We recommend interested readers consider a registration review for mobile robotics~\cite{pomerleau2015review}.

However, ICP and its variants might fall into local minima, making it inapplicable for global registration. Go-ICP by Yang \textit{et al.}~\cite{yang2013go} provides a global solution to the registration problem defined by ICP in 3D using branch-and-bound (BnB) theory. Go-ICP, however, is time-consuming on resource-constrained platforms, especially when the pose space is large for BnB search. If the transformation is in a limited space, BnB-based scan matching is more efficient to use, like LCD in Cartographer~\cite{hess2016real} and vehicular pose tracking on a Gaussian mixture maps~\cite{wolcott2015fast}.

For ICP and its variants, the local minima are caused by the assumption of nearest-neighbor correspondence in Euclidean space. Local feature-based approaches have emerged to extract robust features for correspondence search in a feature space. With the correspondence determined, the transformation can be calculated in the closed form, or with an additional outlier filter. But compared to 2D image descriptors like SIFT~\cite{lowe1999object} or ORB~\cite{rublee2011orb}, the study on LiDAR feature extraction and description is less extensive. The nature of range data is different from image data. Extracting and describing repeatable features in LiDAR scans is still an open problem. The less accurate correspondences provided by feature matching will cause a much higher outlier rate than their 2D counterparts. To address these issues, there are mainly two lines of research in recent years: one is to study the effective LiDAR features; the other is to configure a robust estimator that can handle high outlier rates. We will address these two lines as follows.

The feature extraction of 2D laser scans follows the pipeline in computer vision: first detect interest points (keypoints), and then compute a distinctive signature for each of them (local descriptors)~\cite{nielsen2022survey}. Tipaldi and Arras~\cite{tipaldi2010flirt} propose a fast laser interest region transform
(FLIRT) fo feature extraction, which adopts the theory in SIFT~\cite{lowe1999object}. FALKO~\cite{kallasi2016fast} is also an effective keypoint detection that specialized in 2D range data. BID by Usman \textit{et al.}~\cite{usman2019extensive} uses B-spline to fit the data along keypoints that are detected by FALKO~\cite{kallasi2016fast}. Then the spline is formulated into the descriptors for feature matching. As for 3D range data, early approaches to extract 3D features are mainly handcrafted~\cite{guo2016comprehensive}, such as FPFH~\cite{fpfh2009}, NARF~\cite{steder2010narf} and SHOT~\cite{salti2014shot}. These methods are designed for dense point clouds obtained by RGBD cameras, which lack generalization and robustness against noise. Deep learning has drawn much attention in recent years, and many learning-based features have been proposed. 3DMatch~\cite{zeng20173dmatch} takes 3D local patches around arbitrary interest points and extracts 3D features using a 3D convolutional neural network. PPF-net~\cite{deng2018ppfnet} utilizes PointNet~\cite{qi2017pointnet} to extract local patch features and further fuse the global context into this feature. FCGF~\cite{choy2019fully} utilizes a fully convolutional network to capture global information. It also adopts sparse convolution to efficiently extract local features.

These methods focus on the local feature extraction from interest points; however, interest point or keypoint detection is also important. The stable keypoints that are highly repeatable on 3D point clouds under arbitrary transformation are essential for the registration task. There is a comprehensive review of 3D keypoint detection that evaluates most handcrafted 3D keypoints~\cite{tombari2013performance}. The common trait of these methods is their reliance on local geometric information, which discards the important global context. To address these problems, USIP~\cite{li2019usip} proposes an unsupervised framework to detect keypoints. SKD~\cite{tinchev2021skd} uses saliency estimation to determine the keypoints. Some works~\cite{yew20183dfeat, bai2020d3feat} also jointly learn the keypoint detector and descriptor.

The limitation of correspondence-based methods is the robustness of the estimator with respect to outliers and low overlaps. Then we shift from the ``3D features'' line to the ``robust estimator'' line. Several research works tried to address this problem from different perspectives. Random sample consensus (RANSAC)~\cite{fischler1981random} is a widely used robust estimator for outlier pruning. FGR~\cite{zhou2016fast} regards this problem as an optimization problem. FGR implements a Geman-McClure cost function and leverages second-order optimization to reach global registration of high accuracy. DGR~\cite{choy2020deep} proposes a differentiable Weighted Procrustes algorithm for closed-form pose estimation and a robust gradient-based SE(3) optimizer for pose refinement. TEASER by Yang \textit{et al.}~\cite{TeaserTRO2021} is the first certifiable registration algorithm that can achieve acceptable results with a large percentage of outliers. A powerful maximum clique finder~\cite{eppstein2010listing} is an important module for handling outliers in TEASER. With pruned correspondences, graduated nonconvexity~\cite{yang2020graduated} is then used for robust pose estimation. Actually, the \textit{maximum clique} problem can also be formulated as a graph-theoretic optimization problem. Parker \textit{et al.}~\cite{lusk2021clipper} present CLIPPER to solve this optimization by continuous relaxation. PointDSC~\cite{bai2021pointdsc} utilizes a spatial-consistency guided nonlocal module for feature learning and proposes a differentiable neural spectral matching for outlier removal. Different robust kernels are considered for point cloud registration. An elegant formulation based on Barron's kernel family~\cite{barron2019general} has been proposed by Chebrolu \textit{et al.}~\cite{chebrolu2021adaptive}.

Instead of applying an off-the-shelf robust estimator after learned descriptors, some works convert the entire pose estimation into the end-to-end training pipeline. Deep Closest Point (DCP)~\cite{wang2019deep} revises the original ICP pipeline to a differentiable one that can learn from data. DeepGMR~\cite{yuan2020deepgmr} is the first learning-based method that leverages point-to-distribution correspondences for registration. Recently, the attention mechanism is also adopted to replace the role of feature matching and outlier filtering and thus can be used in end-to-end frameworks~\cite{predator21,shi2021keypoint,yew2022regtr}. This data-driven works~\cite {wang2019deep,yuan2020deepgmr,predator21,shi2021keypoint,yew2022regtr} are trained and validated on public point cloud datasets. More data are necessary to ensure the robustness and generalization ability needed by global localization on mobile robotics.

\subsubsection{Correspondence-free}

The main idea of correspondence-free methods is to register point clouds based on feature similarity. With the convergence considered, existing methods can be divided into locally convergent and globally convergent methods. The locally convergent methods stem from the optical flow in the image domain. Instead of using 3D coordinates, PointNetLK~\cite{aoki2019pointnetlk} uses PointNet~\cite{qi2017pointnet} to learn the local feature of each point and then iteratively align the learned features. There also exist improved versions of PointNetLK framework~\cite{li2021pointnetlk,huang2020feature}. One disadvantage of this class of approaches is the iterative solver, which is sensitive to initialization and may mislead the feature learning.

Globally convergent approaches are mainly based on the idea of correlation. Like the image registration pipeline, Bulow \emph{et al.}~\cite{bulow2018scale} utilize 3D Fourier-Mellin transform to achieve globally convergent 3D registration. PHASER~\cite{bernreiter2021phaser} generates spherical frequency spectrum using  Fourier transform and Laplace fusion and registers point cloud by calculating correlation. Zhu \emph{et al.}~\cite{zhu2022correspondence} propose to learn an embedding for each point cloud in a feature space that preserves the SO(3)-equivariance property. The global convergence mostly contributed to the correlation, an inherently exhaustive search that can be evaluated effectively by spectrum decoupling.

\textbf{Summary.} Point cloud registration is a popular topic but there still remain some issues for mobile robotic applications, e.g., generalization ability under an end-to-end framework and alignment with less overlap.
In certain applications, only local pose estimation can also provide global localization results, e.g., LiDAR LCD with ICP registration if the current pose is close to previous ones. If we combine approaches introduced in Section~\ref{sec:PR} and~\ref{sec:PRPE}, a complete global localization framework can be obtained in a coarse-to-fine manner: \textit{first global place recognition then followed by local pose estimation.}

Compared to place recognition-only approaches, the coarse-to-fine framework can provide precise poses for global localization tasks. The cost is that the map needs to include both global descriptors for retrieval and local metric points for state estimation. This makes the framework impracticable in large-scale environments, e.g., self-driving cars in city-scale environments for commercial use. Additionally, if place recognition fails, local pose estimation will suffer from this failure. We will introduce pose estimation-coupled place recognition to address these problems.

\subsection{Pose Estimation-coupled Place Recognition}
\label{sec:PEPR}

For the approaches explained in Section~\ref{sec:PRPE}, two individual steps are needed to handle place recognition and local pose estimation. One possible improvement is to design a shared feature embedding or representation that place recognition and pose estimation can benefit from it. Thus, \textit{place recognition and local pose estimation should share the same processing pipeline}. This could make the map more concise and the state estimator tighter. We name this kind of approach pose estimation-coupled place recognition, or coupled methods for clearance.

Note that many methods in this section use the same pre-processing approaches in Section~\ref{sec:PR}: \textit{dense points/voxel-based}, \textit{sparse segments-based and projection-based}. These methods can be classified based on the dimension of output poses, stated as follows.

\subsubsection{3-DoF pose estimation}

For mobile robots working on planar surfaces, pose estimation mainly focuses on three degrees of freedom (3-DoF): position and heading (yaw angle). One of the well-known methods is scan context~\cite{kim2018scan}. The 3D point clouds are divided into azimuthal and radial bins, in which the value is assigned to the maximum height of the points in it. The similarity is the sum of cosine distances between all the column vectors at the same indexes. As the column would shift when the viewpoint of the LiDAR changes, the authors propose a rotation-invariant descriptor extracted from scan context for top-k retrieval during place recognition, then further calculated the similarity and azimuth by column shift. The rotation here is the yaw angle or the heading for mobile robots moving on planar.

Some following methods are designed to improve the discriminability and invariance of the original scan context~\cite{wang2020intensity, li2021ssc, SCI2019, wang2020lidar, xu2021disco}. For example, Wang \emph{et~al.}~\cite{wang2020intensity} utilize the maximum intensity within each bin as the descriptor. Li \emph{et~al.}~\cite{li2021ssc} introduce the semantic labels of the point clouds. Researchers also extract deep learning-based features from scan context for better performance~\cite{SCI2019, xu2021disco}. Besides feature extraction, other methods improve the efficiency of the similarity calculation process by taking advantage of the circular cross-correlation property in scan context representation. Wang \emph{et~al.}~\cite{wang2020lidar} utilized Fourier transform to estimate the translation shift along the azimuth-related axis. Xu \emph{et~al.}~\cite{xu2021disco} proposed a differentiable phase correlation method based on Fourier transform to make the place recognition and pose estimation (rotation) trained in an end-to-end manner.

Different from the scan context family that projects 3D point clouds into 2D polar bird's-eye view (BEV) images, some methods transform point clouds into range images based on a spherical projection model. OREOS~\cite{schaupp2019oreos} utilizes a convolutional neural network to extract features on the range images and generates two vectors for place recognition and azimuth estimation simultaneously. OverlapNet~\cite{chen2021overlapnet} estimates the overlap between two range images by calculating all possible differences for each pixel and calculating the azimuth taking advantage of the circular cross-correlation. An improved version, OverlapTransformer~\cite{ma2022overlaptransformer} is also proposed with a rotation-invariant representation and faster inference. The advantage of OverlapTransformer is the missing ability to provide yaw angle estimation. It is worth mentioning that the OverlapNet family uses the overlap of range images for loss function construction, which is different from the location-based loss in other learning-based methods, like contrastive loss in~\cite{yin2017efficient}, triplet and quadruplet loss in~\cite{uy2018pointnetvlad}.

Though many place recognition methods are rotation-invariant, they cannot achieve translation invariance due to the egocentric modeling process~\cite{sino22}. And few of these methods are able to calculate the translation drift between the query and retrieved point clouds. To relieve these limitations, scan context~\cite{kim2018scan} augments the query point cloud with root-shifted point clouds. And later in scan context++~\cite{kim2021scan}, Kim \textit{et al.} propose the Cartesian BEV-based descriptor for translation estimation.
RING by Lu \textit{et al.}~\cite{lu2022one} propose a non-egocentric Cartesian BEV-based descriptor with both rotational and translational invariance. Besides place recognition and azimuth estimation, translation can also be estimated with this unified descriptor.

\subsubsection{6-DoF pose estimation}

Many visual global localization frameworks extract local descriptors on images for both place recognition and the following pose estimation. Generally, the local features are aggregated into a global descriptor using methods such as bag-of-words (BoW)~\cite{galvez2012bags}, VLAD~\cite{VLAD2010}, or ASMK~\cite{asmk2013}. Meanwhile, 6-DoF poses are often extracted from visual data from using Perspective-n-Point (PnP) algorithms~\cite{Lepetit2009} based on the matched local features. Inspired by visual image matching, some methods converted LiDAR point clouds into images and applied similar techniques to the transferred images. Shan \emph{et~al.}~\cite{shan2021robust} utilize the traditional BoW algorithm in visual place recognition for LiDAR-based global localization. Specifically, they transform the intensity of the high-resolution lidar point cloud into images and extracted features based on Oriented FAST and rotated BRIEF (ORB)~\cite{rublee2011orb}.  The visual matching technique is also tested on~\cite{di2021visual}. However, works by Shan \textit{et al.}~\cite{shan2021robust} and Giammarino et al.~\cite{di2021visual} require a high-resolution LiDAR scanner (64 and 128 rings) to guarantee the extraction and description of local features. In BVMatch~\cite{luo2021bvmatch}, sparse LiDAR scans are first projected to BEV images and then visual matching techniques are applied. The cost is that the final pose is actually with 3-DoF~\cite{luo2021bvmatch}.

Visual-inspired matching needs a projection to reduce the dimensionality of 3D point clouds. Some researchers propose to design discriminative 3D features for local matching and global descriptor encoding. It is becoming a new research trend in the last three years (2019-2022). DH3D by Du \textit{et al.}~\cite{dh3d2020} uses flex convolution and squeeze-and-excitation block as the feature encoder and applies a saliency map for keypoint detection. Then the local features were aggregated into a global descriptor for place recognition. EgoNN by Komorowski \textit{et al}.~\cite{komorowski2021egonn} transforms the point clouds into a cylindrical occupancy map, and develops a 3D convolutional architecture based on MinkLoc3D~\cite{komorowski2021minkloc3d} for keypoint regression and description. A structure-aware registration network is introduced in~\cite{qiao2021registration} and it is trained in a virtual LiDAR dataset while tested in real-world environments. Cattaneo \textit{et al.}~\cite{cattaneo2022lcdnet} propose an end-to-end LCDNet that can achieve both place recognition and pose estimation. LCDNet modifies PV-RCNN~\cite{shi2020pv} for local feature extraction and builds a differentiable unbalanced optimal transport~\cite{chizat2018scaling} for feature matching. BoW3D~\cite{cui2022bow3d} utilizes 3D point cloud feature LinK3D~\cite{cui2022link3d} for feature extraction and adapted BoW for global localization. Instead of point-level features, GOSMatch~\cite{zhu2020gosmatch} utilizes high-level semantic objects for global localization. The authors propose a histogram-based graph descriptor and vertex descriptor taking advantage of the spatial locations of semantic objects for place recognition and local feature matching. Similarly, BoxGraph~\cite{pramatarov2022boxgraph} encodes a semantic object and its shape of a 3D point cloud into a vertex of a fully-connected graph. The graph is used for both similarity measure and pose estimation. Yuan \textit{et al}.~\cite{yuan2022std} propose a novel triangle-based global descriptor, stable triangle descriptor (STD) for place recognition and relative pose estimation. STD keeps a hash table as the global descriptor, and place recognition is achieved by voting of triangles in the table.

All the methods above achieve place recognition by nearest neighbor search or exhaustive comparisons on global descriptors. Several works only use local keypoints or features to build coupled methods, and there are no global descriptors for place retrieval. Bosse and Zlot~\cite{bosse2009keypoint,bosse2013place} extract and describe keypoints for both place candidate voting and 6-DoF pose estimation. Inspired by the work of Bosse and Zlot~\cite{bosse2013place}, Guo \textit{et al.}~\cite{guo2019local} design an intensity-integrated keypoint and also propose a probabilistic voting strategy. Steder \textit{et al.}~\cite{steder2010robust} propose to match point features on range images and score potential transformations for final pose estimation. Instead of extracting features on point clouds, Millane \textit{et al.}~\cite{millane2019free} introduce a SIFT-inspired~\cite{lowe1999object} local feature based on the distance function map of 2D LiDAR submaps. Experiments validate that using free space for submap matching performs better compared with using occupied grids.

\textbf{Summary.} Pose estimation-coupled place recognition outputs not only place retrievals but also a 3-DoF (or with only a 1-DoF yaw angle) or a full 6-DoF pose. Common evaluation metrics include both precision-recall for retrieval and quantitative errors compared to ground truth orientation or position.

One might ask about the advantages of using such methods compared to the previous two-step pipeline using place retrieval (Section~\ref{sec:PR}) followed by precise pose estimation (Section~\ref{sec:PRPE}). The potential advantages are three folds:
\begin{itemize}
\item Lightweight map. Dense point maps limit mobile robotic applications in large-scale environments, especially for resource-constrained vehicles. If place recognition and pose estimation share the same feature or representation, fewer data and sparser keyframes could support global localization in such conditions, making the entire map more lightweight to use.
\item Geometric verification. For place recognition methods, a key issue is to verify whether a retrieved place is correct. Pose estimation results can be used as geometric verification to filter incorrect places. This filtering strategy has been applied in several coupled methods~\cite{zhu2020gosmatch,yuan2022std}.
\item Initial guess for refinement. If an accurate pose is required, a local point cloud registration (Section~\ref{sec:PRPE}) is necessary for pose refinement. Coupled approaches can provide an initial guess for such refine modules, thus improving the accuracy and efficiency of pose estimation. As reported in LCDNet~\cite{cattaneo2022lcdnet}, the initial guess significantly reduces runtime and metric errors when applying ICP alignment.
\end{itemize}
Overall, the pose estimation and place recognition are coupled in this subsection, but keyframes or places are still needed in a pre-built map database. A one-stage global localization will be presented in the following subsection.

\subsection{One-stage Global Pose Estimation}
\label{sec:PE}

The two-stage methods using place recognition and pose estimation techniques have shown successful operations in various datasets and applications. Thus a natural question is raised: can we achieve global localization by directly matching on a global map without separating the map space? The answer is yes and some approaches can achieve one-stage global pose estimation. The majority of these approaches can be classified into two categories based on how to estimate the pose: in a traditional closed form or in an end-to-end manner.

\subsubsection{Feature-based matching}

One representative work is SegMatch proposed by Dub{\'e} \emph{et~al.}~\cite{dube2017segmatch} in 2017, with results illustrated in Figure~\ref{fig:segmatch}. SegMatch first segments dense LiDAR map points to clusters with ground removal and then extracts features based on eigenvalues and shapes of segments. Random forest classifier is trained and applied to boost feature matching. Finally, matched candidates are fed into RANSAC for 6-DoF pose estimation. The handcrafted descriptors were extended to data-driven SegMap~\cite{dube2018segmap} with the help of deep neural networks. In~\cite{cramariuc2021semsegmap}, SemSegMap is proposed by integrating visual information into point cloud segmentation and feature extraction. SegMatch and its ``family members'' are validated and evaluated in urban and disaster environments.

Inspired by SegMatch scheme, Tinchev \emph{et~al.}~\cite{tinchev2018seeing} propose Natural Segmentation
and Matching (NSM)  for global localization in a more natural environment. The insight is a novel hybrid descriptor and is more robust to different points of view than the baseline SegMatch. Similarly, NSM has also been extended to a deep learning version in~\cite{tinchev2019learning}. In these feature-based global matching methods~\cite{dube2017segmatch,dube2018segmap,cramariuc2021semsegmap,tinchev2018seeing,tinchev2019learning}, point cloud segments are aligned with low-dimensional and distinctive descriptors for global matching. The global segment-based maps can support not only loop closing for consistent mapping but also pose tracking for online localization.

Generally, these segmentation-based approaches rely on the point segmentation results, as mentioned in Section~\ref{sec:segment}. A robot traveling is a good choice to accumulate dense 3D point clouds first, and then segmentation and segment matching are performed. Hence, these methods are less efficient compared to two-stage approaches in some specific tasks, like fast re-localization with sparse scans. In addition, the reliance on segments could make these methods fail in some challenging scenes, e.g., in a featureless flat field or a man-made environment with too many repetitive structures.

\begin{figure}[t]
\centering
\includegraphics[width=9cm]{figure/SegMatch.pdf}
\caption{From SegMatch~\cite{dube2017segmatch}. SegMatch achieves global localization at the level of segments rather than conventional keypoints. Different colors represent the segmentation results. Segment matches are indicated with green lines.}
\label{fig:segmatch}
\end{figure}

\subsubsection{Deep regression}

With the popularity of deep learning, several researchers propose to regress global robot pose directly in an end-to-end fashion, just like PoseNet~\cite{kendall2015posenet} for visual re-localization.
Similarly, Wang \emph{et~al.}~\cite{wang2021pointloc} propose a learning-based PointLoc for LiDAR global pose estimation. The backbone is an attention-aided PointNet-style architecture~\cite{qi2017pointnet} for 6-DoF pose regression. This end-to-end manner is completely data-driven without conventional pose estimation processing. Lee \emph{et~al.} ~\cite{lee2022learning} convert the global localization as an unbalanced point registration problem, and propose a hierarchical framework UPPNet to solve this problem. Specifically, UPPNet first searches the potential subregion in a large point map and then achieves pose estimation via local feature matching in this subregion. UPPNet can also be trained in an end-to-end fashion.

\textbf{Summary.} Feature-based one-stage approaches do not use discrete places or locations for place recognition. They are suitable for loop closure detection in a small area. However, the downside is that it is challenging to re-localize a robot from scratch using partial local features in a large feature map.

As for one-stage deep regression approaches, though LiDAR scanner provides rich structural information, the metric estimation is not competitive~\cite{wang2021pointloc,lee2022learning} compared to conventional two-stage methods in Section \ref{sec:PRPE} and \ref{sec:PEPR}. We consider one-stage pose regression is a promising research direction in the era of big data, but still remain many issues to solve, e.g., how to improve the interpretability and generalization ability of these end-to-end methods.

\section{Global Localization \\using Sequential Measurements}
\label{sec:sequential}

Section~\ref{sec:single} reviews related single-shot global localization approaches that take a single LiDAR scan or point cloud as the input. LiDAR sensor provides high-frequency point measurements, and sequential point clouds can be obtained when the robot travels a distance. This section reviews methods that use sequential LiDAR inputs for global pose estimation. Note that certain single-shot methods in Section~\ref{sec:single} can be integrated as a front-end matching in frameworks of this section.

Sequential global localization can be divided into two categories determined by its map and output poses. One is \textit{sequential place matching} on keyframe-based submaps and the other is \textit{sequential-metric global localization} on metric maps. The former provides a retrieved place as a localization result, the latter outputs an accurate pose on a metric map. Both of them can enhance the capability of robot global localization compared with single-shot global localization.

Inspired by the organization of State Estimation for Robotics
~\cite{barfoot2017state}, we consider that sequential-based approaches can also be classified into two categories: \emph{recursive} and \emph{batch} methods. The difference is how to handle sequential information for global pose estimation: r. Recursive methods estimate the pose under Bayesian filtering or similar techniques; batch methods handle a batch of information at multiple timestamps. We will also talk about this taxonomy in the following two subsections.

\subsection{Sequential Place Matching}
\label{sec:seqMatch}

Probabilistic or sequential matching can help improve the visual localization success rate, which has been validated in several classical visual systems: FAB-MAP~\cite{cummins2008fab}, SeqSLAM~\cite{milford2012seqslam,milford2015sequence}, the work of Naseer \textit{et al.}~\cite{naseer2018robust}, and Vysotska and Stachniss~\cite{vysotska2019effective}. FAB-MAP first builds an appearance-based BoW for single image retrieval and then formulates recursive Bayesian filtering for global localization. An extended version FAB-MAP 3D~\cite{paul2010fab} also models spatial information to improve the robustness of the framework. The filtering technique of FAB-MAP family could handle sequential measurements, but will easily crash when single-shot place recognition fails in challenging scenes. In SeqSLAM~\cite{milford2012seqslam}, a sequence-to-sequence matching strategy is proposed to find the location candidates in an image similarity matrix. SeqSLAM processes a batch of images compared to filtering-based methods, making the whole system more robust. The SeqSLAM family has demonstrated its success in both handcrafted features~\cite{milford2012seqslam} and data-driven features~\cite{milford2015sequence}. Naseer \textit{et al.}~\cite{naseer2018robust} propose to use a network flow to handle batch image matching and maintain multiple route hypotheses in parallel. Global visual matching method is also proposed in~\cite{vysotska2019effective} for re-localization, in which the map database contains multiple sequences for graph-based search.

The LiDAR-based sequential matching has been inspired by visual methods in recent years. Liu \emph{et~al.}~\cite{liu2019seqlpd} propose to use LPD-Net~\cite{liu2019lpd} for front-end place recognition, and design a coarse-to-fine sequence matching strategy for global localization. The designed strategy improves the place retrieval performance compared with single-shot LPD-Net. Yin \emph{et~al.}~\cite{yin2022fast} present a particle-aided fast matching scheme in large-scale environments based on sequential place recognition results, which is generated by SphereVLAD in Section~\ref{sec:proj}. From the viewpoint of state estimation,~\cite{liu2019seqlpd} handles batch information while~\cite{yin2022fast} recursively estimates the locations. Recent work SeqOT~\cite{ma2022seqot} generates one global descriptor for a sequence of range images, rather than multiple descriptors in its previous version~\cite{ma2022overlaptransformer}. Specifically, a novel end-to-end transformer is built to handle spatial and temporal information fusion.

All these methods above, visual- or LiDAR-based, aim at estimating the most likely (highest probability) match on topological keyframe-based submaps (Section~\ref{sec:KM}). The evaluation of these methods is the same with place recognition-only approaches in Section~\ref{sec:PR}.

\subsection{Sequential-Metric Localization}

If the map has a geometric representation, like occupancy grids and landmarks, it can enable metric pose estimation for mobile robots, making sequential global localization more practical.

Particle filter localization, also known as sequential Monte Carlo Localization (MCL) in the robotics community, is a widely used recursive state estimation back-end~\cite{dellaert1999monte}. Unlike the Kalman filters family, MCL is non-parametric Bayesian filtering without assuming the distributions of robot states. More specifically, it uses a group of samples to represent the robot state, which is naturally suitable for global localization tasks especially when the robot pose has a multi-modal distribution. Researchers have proposed multiple extended versions to improve the robustness and efficiency of the original MCL. Maintaining a large set of particles is computationally expensive. Adaptive MCL~\cite{fox2001kld} is able to sample particles in an adaptive manner using the Kullback–Leibler divergence. In~\cite{stachniss2005mobile}, segmented patch maps are integrated into MCL framework, making it applicable in indoor non-static environments. Most LiDAR sensors can also intensity information as reflection properties of surfaces. Bennewitz \textit{et al.}~\cite{bennewitz2009utilizing} use these reflection properties to improve the observation model of MCL, and it achieves faster convergence for re-localization. Recent work~\cite{zimmerman2022robust} also integrates human-readable text information into MCL for localization, making it more robust to structural changes in buildings. Due to its simplicity and effectiveness, MCL is also used in various low-dimensional navigation tasks beyond global localization, such as robotic pose tracking~\cite{yin2022radar} and exploration tasks~\cite{stachniss2005information}.

Currently, MCL is one of the gold standards in multiple robot navigation toolkits~\cite{montemerlo2003perspectives,zheng2021ros}. Indoor LiDAR MCL is well studied and has been widely deployed for commercial use, e.g., applying to a home cleaning robot. A recent trend of indoor LiDAR localization is to use building architectures as maps, e.g., structural computer-aided design (CAD)~\cite{boniardi2017robust,zimmerman2023ral} and semantic building information modeling (BIM)~\cite{yin2023semantic,hendrikx2021connecting}. These maps are easy to obtain and keep sparse but critical information of environments, like walls and columns. The use of such maps makes the localization free of pre-mapping for long-term operations. MCL can also be used for localization on floor plan maps~\cite{boniardi2017robust,zimmerman2023ral}. Experiments show that such cheap maps can also support indoor robot localization.

For global localization in outdoor environments, Yin \emph{et~al.}~\cite{yin2018locnet} propose to use the Gaussian mixture model to fuse multiple place recognition results, and then integrate it into the MCL system as a measurement model. With the convergence of MCL, a coarse pose can be generated as an initial guess for accurate ICP refinement. The observability of orientation is also proofed in its extended version~\cite{yin20193d}. Similarly, Chen \emph{et~al.}~\cite{chen2020iros} use their OverlapNet~\cite{chen2021overlapnet} to extract features of submaps in a global map and propose a new observation model for MCL by comparing the similarity between the current feature and the stored features to achieve global LiDAR localization. Sun \emph{et~al.}~\cite{sun2020localising} and Akai \emph{et~al.}~\cite{akai2020hybrid}  propose to fuse deep pose regression and MCL to build a hybrid global localization, in which deep pose regression could provide a 3-DoF or 6-DoF from an end-to-end neural network. The methods above~\cite{yin20193d,chen2021overlapnet,sun2020localising,akai2020hybrid} typically discrete the pose and map space for fast convergence of MCL in large-scale environments. A deep learning-aided samplable observation model was proposed in~\cite{chen2021deep}, named DSOM. Given a 2D laser scan and a global occupancy map, DSOM can provide a probability distribution for MCL on the global map, thus making particle sampling focus on high-likelihood regions. DSOM was tested in indoor environments and the generalization to large-scale environments still remains a problem.

The advancements caused by deep learning methods also affect the back-end state estimator of the MCL system. Jonschkowski \emph{et~al.}~\cite{jonschkowski2018differentiable} propose a differentiable particle filter (DPF) for robot pose tracking and global localization. The whole DPF pipeline includes differentiable motion and measurement models, and a belief update model for particles, making the DPF trainable in an end-to-end manner. In Differentiable SLAM-net proposed by Karkus \textit{et al.}~\cite{karkus2021differentiable}, DPF was encoded into a trainable visual SLAM for indoor localization. LiDAR-based particle filter is quite mature and there is no LiDAR-based DPF currently. But we consider differentiable state estimator could be a promising direction in this era of big data.

We also notice that there exist other frameworks that can achieve sequential-metric global localization. Multiple hypotheses tracking (MHT)~\cite{thrun2002probabilistic} is a possible solution to the global localization problem. An improved MHT framework is proposed in~\cite{gao2019novel}, and authors design a new structural unit encoding scheme to weight hypotheses. Hendrikx \textit{et al.}~\cite{hendrikx2022local} propose to build a hypotheses tree for indoor global localization. A global feature map is required for this method and explicit data associations are used to check the hypotheses. Wang \emph{et~al.}~\cite{wang2019glfp} provide a factor graph-based global localization from a floor plan map (GLFP). GLFP integrates odometry information and landmark matching into a factor graph when the robot travels. Compared to the filtering family (MCL and MHT), GLFP handles a batch of information for global pose estimation, which is similar with SeqSLAM in Section~\ref{sec:seqMatch}. The landmark matching actually provides global position information for factor graph optimization. In the works of Wilbers \textit{et al.}~\cite{wilbers2019approximating}, researchers employ graph-based sliding window approaches to fuse outdoor landmark matching and odometry information. Merfels and Stachniss \textit{et al.}~\cite{merfels2016pose} fuse global poses from GNSS and odometry information to achieve self-localization for autonomous driving. Lastly, in this subsection, the evaluation typically contains metric pose estimation on the map, e.g., using Root Mean Square Error (RMSE), which differs from approaches in Section~\ref{sec:seqMatch}.

\section{LiDAR-aided Cross-Robot Localization}
\label{sec:apply}

The review in Section~\ref{sec:single} and Section~\ref{sec:sequential} mainly focuses on single robot-based global LiDAR localization. Global localization can also be deployed into multi-robot systems for cross-robot localization, which is a new trend in the robotics community. More concretely, one robot performs mapping and another robot globally estimates its pose on this map, and vice versa.

In practice, the multi-robot system is a broad topic that involves many subproblems that are not the main concerns of this paper, such as communication bandwidth and computation efficiency. As for system architecture, we mainly focus on \textit{distributed} multi-robot systems, which is different \textit{centralized} map servers~\cite{bernreiter2022collaborative,cramariuc2022maplab}. We also note that customized scan matching is proposed for point cloud map fusion and collaborative robots~\cite{yue2022aerial}. These localization methods are based on offline map appearance, while this section mainly focuses on incremental keyframe-based cross-robot localization.

Over the last two decades, there has been a growing demand for autonomous exploration and mapping of various environments, ranging from outdoor cluttered and underground environments to complex cave networks. Due to this, multi-robot SLAM, a critical solution for navigation in GNSS-denied areas where prior maps are unavailable, is receiving more attention. The recent DARPA Subterranean (SubT) Challenge, a three-year global competition that ended in 2021, aimed to demonstrate and advance the state-of-the-art in mapping, localization, and exploration of complex underground settings and has been particularly important in improving multi-robot SLAM. The multi-robot SLAM architectures adopted by the six SubT teams are summarized in the survey by Ebadi \textit{et al}.~\cite{ebadi2022present}. Although many loop closure methods were proposed then, most of the teams detected loop closure candidates simply by calculating the distance between the current keyframe and another keyframe in the factor graph. This LCD strategy is the same as DARE-SLAM~\cite{ebadi2021dare} and LAMP~\cite{chang2022lamp, denniston2022loop}. The simple but effective LCD used in these methods mainly relies on the setting that all robots start to move in the same starting region. In this context, with a high-precision LiDAR odometry~\cite{zhang2014loam,zhao2021super} at the front end, the distance-based LCD can work well in a relatively small (\textless 5 km) area. There is no need to customize a complex place retrieval module in the robotic system~\cite{ebadi2022present}.

Despite the underground exploration, robots might not always be able to begin a task at the same location, as in large-scale search and rescue tasks. As a result, place recognition that does not rely solely on initials is necessary. In an aerial-ground collaborative manner, He \emph{et~al.}~\cite{he2020ground} extract obstacle outlines from submap point clouds and generate thumbnail images. The thumbnail images are converted into compact place descriptors by applying NetVLAD~\cite{arandjelovic2016netvlad}. DiSCo-SLAM~\cite{huang2021disco} firstly adopts LiDAR-based global descriptor, scan context~\cite{kim2018scan}, to perform place recognition in a distributed manner. The lightweight scan context descriptor makes the real-time application possible, although there are no field experiments with multi-robots in this paper. RDC-SLAM\cite{xie2021rdc} utilizes a place-recognition-only global descriptor, called DELIGHT\cite{cop2018delight}, to reduce time consumption. In the relative pose estimation part, eigenvalue-based segment descriptors are proposed to achieve feature matching. DCL-SLAM~\cite{zhong2022dcl} assesses the performance of LiDAR-Iris~\cite{LidarIris}, M2DP~\cite{he2016m2dp} and scan context~\cite{kim2018scan} and finally uses the effective and rotation-invariant LiDAR-Iris for loop closure detection. Unlike the system-oriented research mentioned above, RING++~\cite{xu2022ring++} presents a general non-learning framework to achieve roto-translation invariance with various local features while estimating the relative 3-DoF pose. The roto-translation invariant property and the robust pose estimator allow the multi-robot system to sample places along a long distance while being computationally and memory efficient. Figure~\ref{fig:cross-robot} shows the real-world experimental results using DCL SLAM~\cite{zhong2022dcl} and RING++~\cite{xu2022ring++}.

\begin{figure*}[t]
\centering
\subfigure[LiDAR map and wheeled robots team~\cite{zhong2022dcl}]{
	\includegraphics[width=8.5cm]{figure/crossrobots1.pdf}}
\subfigure[LiDAR map and legged robots team~\cite{xu2022ring++}]{
	\includegraphics[width=8.5cm]{figure/crossrobots2.pdf}}
\caption{ Qualitative results from DCL SLAM~\cite{zhong2022dcl} and RING++~\cite{xu2022ring++}. Different colors represent LiDAR maps and trajectories generated from different mobile robots: wheeled robots in DCL SLAM and legged robots in RING++.
}
\label{fig:cross-robot}
\end{figure*}

From the systems above~\cite{he2020ground,huang2021disco,xie2021rdc,zhong2022dcl,xu2022ring++}, it can be concluded that inter-robot LCD methods enable cross-robot localization in large-scale environments. However, no LiDAR LCD method can provide perfect loop closures without false positives. The false positives are outliers that make estimation systems unstable and inaccurate. More specifically, almost all cross-robot localization systems are built on graph optimization frameworks~\cite{kummerle2011g,dellaert2012factor}. These false positives provide inconsistent links between pose nodes. The optimization may not converge to a correct solution in such conditions. This problem exists not only in LiDAR-aided cross-localization but also in other SLAM-related problems with different sensors.

There exist mainly two ways to handle this problem: one is to design a robust kernel or function to filter outliers \textit{during} the graph optimization; another is to build an outlier rejection module \textit{before} the optimization or similar techniques. Both of these two kinds of methods aim at improving the robustness of graph optimization by removing inconsistent edges generated from LCD methods. For robust kernel functions, a commonly used one is the Huber function~\cite{huber1973robust} but it can not reduce the effectiveness of outlier edges in graphs~\cite{sunderhauf2012switchable}. S{\"u}nderhauf and Protzel~\cite{sunderhauf2012switchable} propose to formulate switchable constraints in the optimization. The added constraints follow different outlier rejection policies, and they can turn on or turn off loop closures. Then Agarwal \textit{et al.}~\cite{agarwal2013robust} introduce scaling factors to replace the switchable constraints. The improved version achieves a faster convergence while still keeping the robustness of graph optimization. An iterative approach RRR is proposed in~\cite{latif2013robust} and it identifies true positives via clustering consistent loop closures. Robust kernels and functions~\cite{sunderhauf2012switchable,agarwal2013robust,latif2013robust} are typically integrated into pose graph optimization frameworks~\cite{kummerle2011g,dellaert2012factor}.

Outlier rejection modules are independent of back-end estimators. RANSAC~\cite{fischler1981random} is a popular method for outlier rejection, which iteratively estimates a  model from sampled data (loop closures). RANSAC starts in a random way and it needs fine-tuned parameters to fit the model. Olson \textit{et al.}~\cite{olson2005single} propose a graph theory-based outlier rejection method, named single-cluster graph partitioning (SCGP). Note that the graph is generated from the adjacency matrix of pose nodes and not the pose graph for SLAM. SCGP estimates a pairwise consistency set as the final result via clustering in this graph. SCGP shows competitive performance with RANSAC. Similarly, the outlier rejection is formulated as a maximum set estimation problem in the work by Carlone \textit{et al.}~\cite{carlone2014selecting}. In 2018, Enqvist \textit{et al.} present a pairwise consistency maximization (PCM)~\cite{mangelson2018pairwise} for consistent mapping with loop closures.

PCM is a graph theory-guided algorithm for outlier rejection. PCM first builds a binary consistency graph by checking all loop closures of each other. The criteria of consistency check are formulated based on the transformation from odometry modules and loop closures.
After all the loop closures are checked, a consistency graph can be obtained and each edge denotes the consistency between a pair of loop closures. PCM aims at estimating the maximum pairwise internally consistent set, which is the maximum clique problem in graph theory (the same problem mentioned in TEASER~\cite{TeaserTRO2021}, see Section~\ref{sec:PRPE}). A fast clique solver by Pattabiraman \textit{et al.}~\cite{pattabiraman2015fast} is adopted in PCM~\cite{mangelson2018pairwise}. There also exist other solutions for this NP-hard problem~\cite{lusk2021clipper}. As tested in~\cite{mangelson2018pairwise}, PCM achieves better performance compared with other robust kernels or outlier rejection modules~\cite{fischler1981random,agarwal2013robust,olson2005single}. PCM has been validated in aforementioned LiDAR-aided cross-robot localization systems~\cite{huang2021disco,zhong2022dcl}, and other robot localization and mapping systems in recent years~\cite{xu2022omni,tian2022kimera}.

In summary, cross-robot localization is becoming a promising direction for future study. It involves multiple topics of robotics, such as odometry, LCD and robust estimator. The cross-robot localization topic is closely related to crowd-sourced mapping~\cite{herb2019crowd} for self-driving cars, which involves other important topics that are beyond the scope of this survey.

\section{Open Problems}
\label{sec:discussion}

We begin the discussion section with a question: which is the best global LiDAR localization method? We consider that it is decided by many key factors: environments, maps and required pose accuracy, etc. There is no single best method to handle all applications and scenarios. \textit{Users need to customize the global localization system according to what they actually need.} However, several popular methods have been validated and integrated into LiDAR-aided navigation systems. For example, particle filter family~\cite{dellaert1999monte} is widely used to handle 3-DoF re-localization for wheeled robots. For vehicle localization in urban environments, scan context family~\cite{kim2018scan} could be a good choice for loop closure detection due to its simplicity and learning-free scheme. For local pose estimation in SLAM, we kindly take MULLS~\cite{pan2021mulls} as an example. MULLS extracts feature points and uses TEASER~\cite{TeaserTRO2021} for global registration in its loop closure module.

Overall, modern global LiDAR localization techniques have enabled several important functionalities for mobile robots. However, there are still open problems and worthy topics for future study. We will discuss these problems and conclude several promising directions for global LiDAR localization.

\subsection{Evaluation Difference}

Experimental validation and evaluation are critical for research papers. We notice that related papers evaluate their methods with different metrics. We briefly categorize these metrics into two parts as follows.
\begin{itemize}
    \item Based on place retrieval. Any place recognition methods evaluate the global localization performance under machine learning metrics, like Recall@1\%~\cite{uy2018pointnetvlad}, precision-recall curves~\cite{kong2020semantic} and localization probability~\cite{dube2017segmatch,yin20193d} etc. In this context, a robot is localized successfully if the retrieved place is close to the ground truth position (\textless$d$ m). The threshold $d$ is a user-defined parameter and related to the resolution of topological keyframe-based submaps, like 25m in~\cite{uy2018pointnetvlad} and 3m in~\cite{kong2020semantic}.
    \item Based on pose estimation. Conventional LiDAR SLAM and map-based localization evaluate the performance based on rotation and translation errors. These errors are obtained by comparing the estimated global pose with the ground truth pose quantitatively. Several global localization approaches follow these metrics~\cite{kim2021scan,cattaneo2022lcdnet}.
\end{itemize}

From the metrics above, a natural question is raised: which is the primary evaluation metric for global lidar localization? Compared to other onboard sensors, LiDAR sensors provide precise and stable range measurements. More importantly, in a classical scheme of autonomous mobile robots~\cite{siegwart2011introduction}, an accurate pose state is desired from downstream planning and control modules. Hence, we argue that \textit{place retrieval is not the ultimate goal for the global LiDAR localization problem, and pose estimation metrics are more meaningful.} As presented in the previous review~\cite{toft2020long}, visual localization methods are evaluated and discussed with 6-DoF poses. Currently, there is no lidar localization are evaluated in the same pose estimation metric like~\cite{toft2020long}, and it could be a future direction for the study on global LiDAR localization. In addition to the pose accuracy, the time cost of global localization is also a critical evaluation for a real-world robot system.

\subsection{Multiple Modalities}
Modern mobile robots are equipped with multiple sensors for self-localization~\cite{jiao2022fusionportable}. In recent years, multi-modal sensing has been a hot topic in the community and has attracted much research interest. Different modalities bring direct challenges for \textit{cross-modality} global localization. But on the other hand, each sensor modality has its pros and cons, and sensor \textit{modality fusion} can potentially improve the reliability and robustness of localization. Despite the sensor modalities at the front end, recent learning techniques enable modality study to higher-level tasks, and we will also introduce \textit{high-level semantics} in the LiDAR global localization problem.

\textbf{Cross Modality.} When offline mapping and online localization use different sensor modalities, we name it cross-modality localization. Cattaneo \emph{et al.}~\cite{cattaneo2020global} propose to train 2D images and 3D point place recognition together. To achieve this, a deep neural network is built, integrating classical 2D convolution layers and 3D PointNet. Similarly, in~\cite{yin2021radar}, radar and LiDAR are mixed together for BEV-based place recognition. Overhead satellite imagery is a cheap source for outdoor localization that does not require lidar mapping beforehand. Metric global LiDAR localization on 2D satellite imagery is proposed and validated in~\cite{tang2021get}. OpenStreetMap (OSM) is also an alternative map that includes structural road and building information. In~\cite{cho2022openstreetmap}, LiDAR descriptors are matched to OSM descriptors to achieve place recognition. For metric localization, a 4-bit representation is proposed in~\cite{yan2019global} that can measure the hamming distance between laser scans and OSM. Then the distances are used to formulate the observation model of MCL. Overall, the research insight of these works~\cite{cattaneo2020global,yin2021radar,tang2021get,cho2022openstreetmap,yan2019global} is to build a shared low-dimensional representation that can connect different data modalities. Precise and global cross-modality global localization is still a challenging problem, e.g., matching a 2D visual image on a 3D LiDAR map.

\textbf{Modality Fusion.} Another direction is to build sensor fusion modules based on multiple modalities. A LiDAR-Vision segment descriptor achieves better performance for place recognition tasks than a LiDAR-only descriptor, as validated in~\cite{ratz2020oneshot}. Inspired by this, Coral~\cite{pan2021coral} designs a bi-modal place recognition by fusing colorful visual features and structural LiDAR elevation maps. AdaFusion~\cite{lai2022adafusion} uses an attention scheme to weight visual and LiDAR modalities for place recognition. In~\cite{bernreiter2021spherical}, a spherical projection enables the fusion of visual and LiDAR at the front end without losing information. From these works above~\cite{ratz2020oneshot,pan2021coral,lai2022adafusion,bernreiter2021spherical}, we can conclude that modality fusion can help improve the place recognition performance, but extra learning techniques are needed to fuse different modalities.

\textbf{High-level Semantics} As mentioned in Section~\ref{sec:PR}, raw LiDAR point clouds are textureless and in an irregular format compared to visual images. This constrains high-level robotics applications, such as scene understanding and moving object detection. Behley \emph{et al.}~\cite{behley2021ijrr} released a large semantic LiDAR dataset in 2019, named SemanticKITTI. SemanticKITTI contains point-wise annotated LiDAR scans, and multiple semantic-related benchmarks for on-road autonomous navigation. A backbone network RangeNet++~\cite{milioto2019rangenet++} and a semantic LiDAR SLAM SuMa++~\cite{chen2019suma} are also released publicly trained on semantic information provided by SemanticKITTI. The SemanticKITTI focuses on on-road robotic perception tasks, and we also note that there exists an off-road semantic LiDAR dataset, named RELLIS-3D~\cite{jiang2021rellis}. RELLIS-3D also provides a full stack of multi-modal sensor data for field robotics research. The semantic information of LiDAR benefits both place recognition and pose estimation for global localization. In~\cite{kong2020semantic,vidanapathirana2021locus,pramatarov2022boxgraph}, semantics are used to construct a semantic-spatial graph for global descriptor extraction. It is validated that using semantic information can improve place recognition performance under this graph representation. Beyond the semantic representations, semantic-aided ICP is formulated for LiDAR odometry~\cite{chen2019suma} and global point cloud alignment~\cite{li2021ssc}.

\subsection{Less Overlap}
\label{sec:lessoverlap}
Though the LiDAR scanner is powerful for environmental sensing, there exists a potential challenge when applying global LiDAR localization in practice: the overlap between two LiDAR point clouds might be very small in certain cases. For the global localization problem, the point clouds could be two scans or submaps for place retrieval, or scan-to-submap registration for pose estimation. Less overlap will make global localization techniques much more difficult. To better understand this challenge, we list three typical cases as follows.

\textbf{Occlusions by dynamics.} LiDAR scans will be partially blocked by dynamics in a high-dynamical environment, like pedestrians and vehicles around the robot. More specifically, for a spinning LiDAR sensor, the block area is decided by mainly two factors: the distance between dynamics and sensor, and the size of this dynamic. By far, dynamics removal in LiDAR scans effectively and efficiently is still quite difficult~\cite{lim2021erasor}. Compared to 360-degree rotating lidar sensors, some other range sensors can provide range data that are not easily blocked, like limited FoV solid LiDAR sensor~\cite{yuan2022std}, imaging radar~\cite{kramer2022coloradar}, and spinning radar~\cite{kim2020mulran}.

\textbf{Large translation.} For sparse keyframe-based submaps, a large translation between the retrieved keyframe and ground truth pose could result in a small overlap between the current LiDAR scan and the submaps stored in the keyframe. A powerful global point cloud registration is required to overcome this challenge.

\textbf{Viewpoint change.} Generally, for wheeled robots on roads, pose estimation is constrained in a 3-DoF space (x, y and yaw). But for flying drones in the wild, it is a complete 6-DoF pose estimation problem. When using global LiDAR localization on drones, LiDAR point clouds collected by drones might have less overlap at the same place. This is mainly due to two reasons: the 6-DoF motions of drones and the limited field-of-view (FoV) of LiDAR sensors.

\subsection{Generalization Ability}
\label{sec:generalization}

For learning-free methods, less parameter tuning is desired to ensure the generalization to new environments~\cite{vizzo2022kiss}. As for learning-based methods, generalization ability is a big challenge that has to face, especially when there is less training to support these data-driven methods. We mainly list four basic problems when deploying existing global localization methods.

\textbf{Sensor configuration.} Currently, there are dozens of LiDAR types, and each type has its unique sensor parameters. The generalization from one LiDAR sensor to another could be a problem, e.g., training on Velodyne HDL-64E scans while testing on Ouster OS1-128 scans. Another potential problem is the displacement of LiDAR sensors. If roll or pitch angle changes, laser point density and distribution will change respectively, resulting in global localization failure even using state-of-the-art methods. However, if the global localization is conducted on accumulated submaps, sensor configuration could be a minor problem.

\textbf{Unbalanced matching.} Currently, most global LiDAR localization methods are tested using relatively good data quality. In other words, the input point cloud and point cloud map have similar point density and point cloud scale. However, when aligning one LiDAR scan to one larger submap, there exist deviations between these unbalanced two data. Unbalanced point matching~\cite{lee2022learning} is still hard to solve since local features are quite different~\cite{chang2021map} in such conditions. Additionally, LiDAR sensors will be affected in challenging weather conditions, like rainy and snowy days~\cite{pitropov2021canadian}, which brings potential hazards for global LiDAR localization.

\textbf{Unseen environments.} The generalization in the unseen scenario is an old but still hard problem in the learning community. Cross-city and Cross-environments generalization remains underexposed for global LiDAR localization methods. For instance, Knights \emph{et al.}~\cite{knights2022wild} release a challenging dataset Wild-Places for LiDAR place recognition in natural environments. There is a performance drop for advanced methods~\cite{kim2018scan,xu2021transloc3d,komorowski2022improving} compared to tests in urban environments. It could be concluded that there is a domain gap between structural urban environments and unstructured natural environments. To enable continuous learning in new scenes, incremental learning~\cite{li2017learning} is a good choice that does not require retraining from scratch. Recent work InCloud~\cite{knights2022incloud} achieves incremental learning for point cloud place recognition and it overcomes catastrophic forgetting caused by learning in new domains.

\textbf{Trigger of global localization.} In a complete localization system, pose tracking takes most of the computation while global localization is only activated when it is needed. Thus, a natural question is raised: when to trigger global localization? For LCD and cross-robot localization, the trigger of global localization could be one or multiple pre-defined criteria, like similarity threshold of descriptors or an adaptive distance in~\cite{denniston2022loop}. As for re-localization applications, a robot might believe it knows where it is while it does, and it is actually the classic kidnapped robot problem in~\cite{thrun2002probabilistic}. In this context, detected localization failure could be a trigger condition for global re-localization. The LiDAR localization failure detection problem is identical to the point cloud alignment quality evaluation at the front end. Researchers propose to design multiple metrics and train classifiers to learn how to score this alignment quality~\cite{yin2019failure,adolfsson2022coral}. While at the back-end, features of state estimator can be used for failure detection~\cite{fujii2015detection}. Localization failure prediction and avoidance is also a worthwhile studied topic for long-term autonomy~\cite{nobili2018predicting}.

\section{Conclusion}
\label{sec:conclusion}

In this survey, we started with the problem formulation of global localization and list three typical situations: loop closure detection, re-localization, and cross-robot localization. Before reviewing concrete methods, we introduce basic maps for this problem. We then review single-shot approaches considering the cooperation of place recognition (place retrieval) and pose estimation (geometric transformation estimation). After that, sequential global localization and cross-robot localization are reviewed. Finally, we discuss challenging tasks and promising directions for future study.

\section*{Acknowledgment}

 We would like to thank Dr. Xiaqing Ding for her constructive suggestions.

\ifCLASSOPTIONcaptionsoff
  \newpage
\fi

\bibliographystyle{IEEEtran}

redpajama_set_name: RedPajamaArXiv