HPHS: Hierarchical Planning based on Hybrid Frontier Sampling for Unknown Environments Exploration

Shijun Long, Ying Li, Chenming Wu, Bin Xu, Wei Fan

TL;DR

This paper introduces HPHS, a novel hierarchical planning approach for autonomous robot exploration in unknown environments. By combining a fast, hybrid frontier sampling method with a subregion-based global planning strategy, HPHS significantly improves exploration efficiency and reduces backtracking compared to existing methods.

What Problem Does This Paper Address?

Autonomous robots are increasingly deployed for tasks like mapping, search and rescue, and inspection in unknown or dynamic environments. A key challenge is efficiently exploring these spaces to create a complete map while avoiding getting stuck in local optima or wasting time on redundant paths. Traditional methods often struggle with computational cost, especially in large environments, and can exhibit myopic behavior, leading to inefficient exploration. This paper aims to address these limitations by proposing a method that balances rapid local frontier detection with intelligent global path planning.

Methods

HPHS employs a three-phase hierarchical approach:

  1. Hybrid Frontier Sampling: This module quickly identifies potential frontier points (boundaries between known and unknown areas). It combines two strategies:
  2. LiDAR-based sampling: Directly uses point cloud data to identify frontiers based on geometric properties (e.g., sudden changes in distance or angular gaps between points). This is efficient and not dependent on map scale.
  3. Image processing-based sampling: Leverages edge and contour detection on local map data to find frontiers, complementing LiDAR data. This is restricted to a local radius to manage computational load.
  4. A filter module then refines these sampled points, removing invalid ones near obstacles or in already known/visited regions.
  5. Subregion Segmentation and Selection: To provide a global perspective, the environment map is divided into multiple subregions. The system then:
  6. Segments the map: Divides the environment into a grid of subregions.
  7. Filters subregions: Keeps only those subregions containing at least one valid frontier point.
  8. Arranges subregions: A novel revenue function is used to determine an optimal sequence for visiting these subregions. This function considers both global path coverage and travel distance, aiming to minimize backtracking and ensure comprehensive exploration.
  9. Frontier Selection: Once a subregion is selected for exploration, this module identifies the best frontier point within that subregion. It uses a heuristic function that considers:
  10. Traveling gain: The Euclidean distance to the frontier point.
  11. Orientation gain: The alignment between the robot's current orientation and the direction to the frontier point, encouraging smoother paths.
  12. Information gain: An evaluation of the potential new information the robot can acquire by moving to that frontier, penalizing areas with obstacles. The point with the highest combined heuristic score is chosen as the next target.

Datasets

The paper evaluates its method using four simulated environments (maze, office, indoor 1, indoor 2) built in the Gazebo simulator. Additionally, real-world experiments were conducted in two maze scenes and an indoor corridor scene. No new datasets were introduced; standard SLAM modules like Gmapping and Direct LiDAR Odometry were used.

Key Insights and Ideas

  • Hybrid Frontier Sampling is Key: Directly sampling frontiers from LiDAR and local maps, rather than relying solely on global map processing, dramatically speeds up frontier detection without being bottlenecked by map size.
  • Hierarchical Planning Prevents Myopia: Dividing the environment into subregions and planning an optimal sequence for visiting them allows the robot to adopt a global strategy, preventing it from getting stuck in local optima and ensuring more complete coverage.
  • Revenue Function for Global Path: The proposed revenue function for subregion sequencing is crucial. By balancing path coverage and travel distance, it intelligently guides the robot to explore efficiently, minimizing redundant travel.
  • Balancing Local and Global: The method effectively combines fast, reactive local frontier detection with deliberate, strategic global planning, a common challenge in exploration robotics.

Key Results

  • Improved Efficiency: HPHS significantly outperforms baseline methods (Frontier-based, TDLE, TARE) in simulation across various metrics.
  • Reduces travel path by 7.0% - 29.1% compared to TARE.
  • Reduces exploration time by 4.1% - 27.2% compared to TARE.
  • Improves overall efficiency by 10.4% - 42.7% compared to TARE.
  • Higher Exploration Completion: Achieves near-perfect exploration completion (99.5% - 100%) in all simulated environments, outperforming TARE (96.5% - 99.8%) and TDLE (97.2% - 98.4%).
  • Seamless Trajectories: Real-world experiments demonstrate smooth, non-backtracking trajectories, visiting areas sequentially and achieving effective exploration even in complex environments.

Limitations and Future Work

  • Limitations:
    • The paper notes that TDLE sometimes struggles to detect frontiers in the indoor 2 scene after 600s, indicating potential limitations in its sampling strategy.
  • While HPHS avoids backtracking, its initial exploration progress might be slower as it prioritizes global coverage over immediate information gain.
  • Future Work: The paper does not explicitly detail future work, but the success in complex environments suggests potential applications in more dynamic or challenging scenarios. Further research could explore more sophisticated information gain models or adaptive subregion segmentation strategies. The authors also mention releasing their source code, which will facilitate further research and development in this area.

Summary updated

Abstract

Rapid sampling from the environment to acquire available frontier points and timely incorporating them into subsequent planning to reduce fragmented regions are critical to improve the efficiency of autonomous exploration. We propose HPHS, a fast and effective method for the autonomous exploration of unknown environments. In this work, we efficiently sample frontier points directly from the LiDAR data and the local map around the robot, while exploiting a hierarchical planning strategy to provide the robot with a global perspective. The hierarchical planning framework divides the updated environment into multiple subregions and arranges the order of access to them by considering the overall revenue of the global path. The combination of the hybrid frontier sampling method and hierarchical planning strategy reduces the complexity of the planning problem and mitigates the issue of region remnants during the exploration process. Detailed simulation and real-world experiments demonstrate the effectiveness and efficiency of our approach in various aspects. The source code will be released to benefit the further research1.
BibTeX
@inproceedings{long2024hphs,
  author = {Shijun Long and Ying Li and Chenming Wu and Bin Xu and Wei Fan},
  title = {{HPHS: Hierarchical Planning based on Hybrid Frontier Sampling for Unknown Environments Exploration}},
  booktitle = {IEEE/RSJ International Conference on Intelligent Robots and Systems},
  year = {2024},
  url = {https://openreview.net/forum?id=gInqA4fVAP},
}
Figure