Frontier Detection and Reachability Analysis for Efficient 2D Graph-SLAM Based Active Exploration

Zezhou Sun, Banghe Wu, Cheng-Zhong Xu, Sanjay E. Sarma, Jian Yang, Hui Kong

Introduction

Autonomous exploration relies on a robot's ability to identify "frontiers"—the boundaries separating explored free space from unexplored territory. In traditional filtering-based SLAM, frontier detection is relatively straightforward as only the most recent sensor data modifies the map. However, modern graph-SLAM approaches, such as Google’s Cartographer, utilize global optimization to correct trajectory drift. While more accurate, these optimizations cause frequent shifts in the poses of previously established submaps. Re-detecting frontiers across the entire global map after every optimization becomes a major computational bottleneck as the environment size increases.

The Problem of Reachability and Efficiency

Beyond computational cost, standard frontier detection often identifies points that are physically inaccessible. Gaps behind thin structures or narrow passages smaller than the robot's footprint are technically frontiers but represent "meaningless" navigation goals. Attempting to plan paths to these areas leads to wasted processing and inefficient exploration behavior.

Proposed Methodology

The authors address these challenges through a three-pronged approach integrated into the Cartographer SLAM framework.

1. Selective Frontier Re-detection (The Direct Method)

Instead of an exhaustive global search, the system monitors the "accumulative pose change" of individual submaps. Frontier re-detection is only triggered for submaps whose pose shift exceeds a predefined threshold (e.g., 5cm). This "Direct Method" allows the system to ignore minor jitters while responding dynamically to significant map corrections, such as loop closures.

2. Reachability-Based Inflation

To prevent the robot from targeting unreachable areas, the system performs map inflation before frontier detection. Submaps are inflated based on the robot's physical radius plus a safety margin. By detecting frontiers on this inflated representation, the algorithm naturally filters out narrow gaps and corners where the robot cannot safely navigate.

Reachability-based inflation: (a) raw submap frontiers, (b) frontiers filtered via map inflation to ensure reachability.

3. Connectivity-Aware Clustering and Verification

Detected frontier points are clustered using the Mean-shift algorithm. To ensure global consistency, the system performs a "stabbing query"—checking if a local frontier in one submap is covered by the free space of another overlapping submap. Only those that remain uncovered are considered global frontiers.

The process of global frontier verification: (a) local frontier detection, (b) stabbing query between overlapping submaps, and (c) final global frontier identification.

Experimental Evaluation

The proposed method was evaluated using a real-world office environment and the large-scale Deutsches Museum dataset.

Key Results

  • Efficiency: The "Direct Method" reduced computational costs to 60.7% of state-of-the-art Dense Frontier Detection (DFD) in office settings and down to 40.03% in large-scale environments.
  • Accuracy: The selective update mechanism maintained high performance, achieving over 99.4% precision and 97.75% recall compared to exhaustive methods.
  • Robustness: The system effectively handled large-scale loop closures, re-detecting frontiers only in the regions affected by the global map shift.

Conclusion

By leveraging the feedback from graph-SLAM optimizers and integrating reachability analysis directly into the detection pipeline, this approach significantly enhances the efficiency of active exploration. Future work will explore extending these optimizations to 3D environments and incorporating semantic scene understanding to further prioritize exploration targets.

Summary updated

BibTeX
@inproceedings{sun2020frontier,
  author = {Zezhou Sun and Banghe Wu and Cheng-Zhong Xu and Sanjay E. Sarma and Jian Yang and Hui Kong},
  title = {{Frontier Detection and Reachability Analysis for Efficient 2D Graph-SLAM Based Active Exploration}},
  booktitle = {IEEE/RSJ International Conference on Intelligent Robots and Systems},
  year = {2020},
  doi = {10.1109/iros45743.2020.9341735},
}
Figure