  This paper presents an accurate and fast 3D global localization method,
3D-BBS, that extends the existing branch-and-bound (BnB)-based 2D scan matching
(BBS) algorithm. To reduce memory consumption, we utilize a sparse hash table
for storing hierarchical 3D voxel maps. To improve the processing cost of BBS
in 3D space, we propose an efficient roto-translational space branching.
Furthermore, we devise a batched BnB algorithm to fully leverage GPU parallel
processing. Through experiments in simulated and real environments, we
demonstrated that the 3D-BBS enabled accurate global localization with only a
3D LiDAR scan roughly aligned in the gravity direction and a 3D pre-built map.
This method required only 878 msec on average to perform global localization
and outperformed state-of-the-art global registration methods in terms of
accuracy and processing speed.
