Efficient single-shot global localization method for indoor mobile robots using branch-and-bound

Purpose The purpose of this paper is to solve the low-efficiency problem caused by large search space in global localization and develop an efficient global localization method requiring only one 2D-LiDAR scan to match against the prior map for indoor mobile robots. Design/methodology/approach This paper solves the global localization problem efficiently using branch-and-bound (B&B). Likelihood fields model is used to compute objective function, and further dilated probabilistic grids are precomputed for upper bound. Branching strategy is to partition a node in half along both X and Y dimensions. Three search strategies, namely, depth-first search (DFS), best-first search (BFS) and cyclic-best-first search (CBFS), are implemented and compared. Moreover, some acceleration tricks are designed carefully to further improve the global localization efficiency. Findings Experimental results reveal the proposed method achieves high global localization success rate and efficiency (processing time in 0.5 s) even in face of large and ambiguous scenarios, and BFS and CBFS are more suitable for B&B-based global localization method than DFS. Originality/value The proposed method achieves efficient single-shot global localization based on B&B, which will benefit the indoor mobile robots equipped with 2D-LiDAR. The authors implement and compare three search strategies and demonstrate the more suitable ones for B&B-based global localization. Key parameters are analyzed in detail to guide the readers to determine them properly in their own scenarios.