Abstract
As autonomous robots transition from controlled laboratory settings to expansive, real-world environments such as city-wide delivery routes and large-scale industrial sites, traditional localization methods face significant scaling challenges. This paper introduces a robust framework for robot localization that addresses the computational and memory constraints of monolithic maps. By partitioning the environment into overlapping "Block Maps" (BMs) and employing a dynamic optimization strategy, the proposed system achieves high-precision navigation over trajectories spanning several kilometers with a 150% increase in processing speed compared to traditional global map approaches.
Introduction
The "map-scaling" problem is a primary hurdle in large-scale autonomous navigation. Standard map-based localization typically requires loading massive point-cloud data into memory, leading to skyrocketing computational costs as the search space expands. While Simultaneous Localization and Mapping (SLAM) systems offer an alternative, they are prone to significant drift over long distances. Existing sub-map methodologies often struggle with spatial continuity; when a robot transitions between map segments, the lack of local context can cause trajectory jumps or total localization failure.
To resolve these issues, this research proposes a Block-Map-Based (BM) localization system. The framework ensures spatial continuity through overlapping segments and utilizes a dual-stage approach: a greedy Branch-and-Bound search for rapid initialization and a dynamic sliding window factor graph for precise, real-time tracking.
Methodology
The system architecture is built upon three technical pillars designed to balance efficiency with accuracy.
1. Keyframe-Based Block Map Generation
Rather than arbitrarily dividing a global map into tiles, the system utilizes "keyframe stitching." This process ensures that adjacent Block Maps (BMs) share significant overlapping regions. These overlaps serve as the spatial "glue," providing the robot with sufficient local context to maintain a continuous pose estimate even as it crosses the boundary from one block to another. These BMs are organized using a KD-Tree structure to facilitate rapid retrieval based on the robot's approximate location.
2. Greedy Global Localization
To establish the robot's initial position without a prior estimate, the system employs a Branch-and-Bound Search (BBS) on a multi-resolution map pyramid. The researchers improved upon standard BBS by implementing a "greedy strategy" that prunes ineffective search branches more aggressively. This allows the system to "zoom in" from a coarse 2D guess to a precise 3D pose in under a second, significantly reducing the time required for cold-start initialization.
3. Dynamic Sliding Window Factor Graph
For continuous pose tracking, the system integrates LiDAR, IMU, and map constraints into a factor graph. The innovation lies in how the system manages its "memory" during transitions:
- Intra-Block Tracking: While moving within a single BM, the system maintains a sliding window of 20 keyframes to optimize the trajectory.
- Inter-Block Transitions: When the robot detects a transition to a new BM, the window dynamically shrinks, marginalizing out older data and retaining only 5 keyframes from the previous block. This prevents historical data from interfering with the new local map constraints, ensuring a smooth and drift-free transition.
Experimental Evaluation
The framework was rigorously tested on two major public benchmarks:
- NCLT (North Campus Long-Term): A dataset from the University of Michigan featuring 6-kilometer trajectories through complex indoor and outdoor environments.
- M2DGR: A multi-scenario dataset including challenging conditions such as elevators and low-light areas.
Key Results
- Accuracy: On the NCLT dataset, the BM method consistently outperformed state-of-the-art (SOTA) algorithms like LIO-SAM and FAST-LIO2. It demonstrated superior robustness, remaining localized in scenarios where other systems suffered from significant drift or failure.
- Computational Efficiency: By utilizing localized Block Maps instead of a monolithic Global Map, the state update latency was reduced from ~36ms to ~14ms—a 150% speedup. This efficiency allows the system to run comfortably on standard embedded hardware.
- Initialization Performance: The greedy BBS approach achieved a translational error of only 0.05m in 0.87 seconds. In comparison, standard BBS methods took nearly 10 seconds and exhibited a much higher error rate (5.0m) within the same search parameters.
Discussion and Conclusion
The success of the Block-Map-Based system highlights two critical insights: first, that spatial continuity via overlapping segments is essential for robust sub-map navigation; and second, that managing the "cost of history" through dynamic marginalization prevents computational bloat without sacrificing accuracy.
While the current framework is highly effective, it relies on static pre-built maps. Future work will focus on dynamic map updating, allowing robots to adapt to environmental changes—such as construction or moved obstacles—in real-time. Additionally, the researchers aim to refine global localization for even more repetitive or feature-poor environments, further expanding the utility of the BM framework for city-scale logistics and delivery applications.
Summary updated