TL;DR
This paper introduces CAE-RLSM, a novel algorithm for building compact and consistent line segment maps for mobile robots in real-time. It addresses the challenge of merging redundant line segments efficiently, even after loop closures, and proposes a new, objective metric for evaluating map quality.
What Problem Does This Paper Address?
Mobile robots rely on accurate maps for navigation and planning. While grid maps are common, they can be memory-intensive for large environments. Line segment maps offer a more compact alternative. However, a key challenge is dealing with "redundant" line segments – multiple segments in the map that actually represent the same physical feature (like a long wall) but appear slightly different due to localization errors or sensor noise. Merging these redundant segments is crucial for creating a compact and consistent map. Existing methods often struggle with either real-time performance or maintaining global consistency, especially after the robot revisits a previously mapped area (loop closure). Furthermore, objectively evaluating the quality of these maps has been difficult, often relying on subjective visual inspection or metrics that can be misleading.
Methods
The core of the proposed solution is the CAE-RLSM (Consistent and Efficient Redundant Line Segment Merging) approach, which comprises two novel modules:
- One-to-Many Incremental Line Segment Merging (OTM-ILSM): This module handles the online merging of new line segments from incoming sensor data into the existing global map. Unlike previous one-to-one merging methods, OTM-ILSM allows a single new line segment to be merged with multiple existing segments in the map if they represent the same physical feature. This helps reduce redundancy more effectively during incremental updates. Crucially, it maintains a record of the correspondence between original line segments and their merged counterparts.
- Multi-Processing Global Map Adjustment (MP-GMA): This module addresses the critical issue of global consistency after loop closure. When a loop closure is detected, MP-GMA uses the recorded correspondences from OTM-ILSM to efficiently update the entire global map. Instead of re-processing everything from scratch, it leverages the stored relationships to re-merge line segments based on the corrected robot poses. This ensures that the entire map remains consistent, even with accumulated errors.
The paper also introduces a novel correlation-based metric for evaluating map quality. This metric uses globally consistent laser scans (obtained from a SLAM system) as ground truth. It rasterizes these scans into a "lookup table" and then discretizes the line segments of the generated map into pixels. By projecting these pixels onto the lookup table, it calculates a score that reflects how well the map aligns with the actual environment, taking into account sensor noise and redundancy.
Datasets
The authors evaluated their approach using a combination of public and self-recorded datasets:
- Public Datasets:
department_diigaintel_oregonseattle
- Self-Recorded Dataset:
floor_4(a hallway environment)
These datasets were collected using mobile robots equipped with SICK LMS 200 and SICK LMS 100 laser range finders. The paper also notes the use of the open-source Karto SLAM system for pose correction and lookup table generation.
Key Insights and Ideas
- One-to-Many Merging is Key for Online Efficiency: The OTM-ILSM module's ability to merge a new segment with multiple existing ones is crucial for reducing redundancy during real-time map building, a limitation of prior one-to-one approaches.
- Correspondence is King for Loop Closure: The explicit recording of correspondences between original and merged line segments is the enabler for efficient and consistent global map adjustment after loop closure, avoiding costly re-processing.
- Objective Map Quality Evaluation is Possible: The proposed correlation-based metric moves beyond subjective visual inspection or simple segment counts, providing a more principled way to assess map accuracy and consistency against real-world sensor data.
- Direction Matters: The paper emphasizes that considering line segment direction is vital to avoid incorrectly merging physically distinct features that happen to be close and overlapping.
Key Results
- Superior Map Quality: CAE-RLSM consistently achieved higher quality scores across all tested datasets compared to MS-RLSM and OTO-ILSM, as measured by the proposed correlation-based metric and an error metric. For instance, on dataset (c), CAE-RLSM achieved a quality of 97.68%, significantly outperforming OTO-ILSM (93.32%).
- Reduced Error: The proposed method also resulted in lower average errors (deviation of original to final segments), with CAE-RLSM errors generally below 10 mm.
- Real-time Performance: CAE-RLSM demonstrated excellent efficiency, with per-frame runtimes averaging around 0.08 milliseconds, making it suitable for real-time applications. This is orders of magnitude faster than offline methods like MS-RLSM.
- Efficient Global Adjustment: The MP-GMA module significantly speeds up global map adjustment after loop closure by reusing pre-computed correspondences.
Limitations and Future Work
- Endpoint Generation: The authors acknowledge that the current work doesn't deeply address the generation of endpoints for corners where multiple line segments meet. They suggest this as a potential area for future improvement.
- Resolution Dependency of Metric: The correlation-based metric is noted to be resolution-dependent, meaning its results can vary with the chosen grid cell size. While CAE-RLSM performs well across different resolutions, the metric itself requires consistent settings for fair comparison.
- Future Work: The paper suggests future work will focus on improving endpoint generation and applying the proposed approach to real-time autonomous navigation systems.
Summary updated