Graph Gain: A Concave-Hull Based Volumetric Gain for Robotic Exploration

Zezhou Sun, Huajun Liu, Chengzhong Xu, Hui Kong

Abstract

The existing volumetric gain for robotic exploration is calculated in the 3D occupancy map, while the sampling-based exploration method is extended in the reachable (free) space. The inconsistency between them makes the existing calculation of volumetric gain inappropriate for a complete exploration of the environment. To address this issue, we propose a concave-hull based volumetric gain in a sampling-based exploration framework. The concave hull is constructed based on the viewpoints generated by Rapidly-exploring Random Tree (RRT) and the nodes that fail to expand. All space outside this concave hull is considered unknown. The volumetric gain is calculated based on the viewpoints configuration rather than using the occupancy map. With the new volumetric gain, robots can avoid inefficient or even erroneous exploration behavior caused by the inappropriateness of existing volumetric gain calculation methods. Our exploration method is evaluated against the existing state-of-the-art RRT-based method in a benchmark environment. In the evaluated environment, the average running time of our method is about 38.4% of the existing state-of-the-art method and our method is more robust.

Introduction: The "Railing Problem"

In autonomous exploration, robots rely on a metric called volumetric gain to determine the utility of visiting a new viewpoint. Traditionally, this is calculated by counting "unknown" voxels in a 3D occupancy map. However, a fundamental inconsistency exists: sensors like LiDAR can often "see" through obstacles that a robot cannot physically traverse, such as railings, shrubs, or glass partitions.

In these cases, the sensor marks the area behind the obstacle as "explored" in the occupancy map. Because the map labels it as explored, the robot's sampling-based planner—often based on Rapidly-exploring Random Trees (RRT)—perceives zero volumetric gain and moves on, even though it never actually entered that space. This leads to incomplete maps and significant "blind spots" in complex environments.

Real-world examples of penetrable obstacles like railings and shrubs that cause issues for traditional volumetric gain calculation.

Methodology: Graph-Based Volumetric Gain

The proposed Graph Gain method shifts the focus from sensor-based occupancy maps to the geometric configuration of the exploration graph itself.

1. Concave Hull Construction

The robot maintains a Rapidly-exploring Random Graph (RRG). It tracks both "successful" nodes (where the robot can move) and "expansion-failure" nodes (where it hit an obstacle or reached the edge of its local planning window). Using Delaunay triangulation, the algorithm builds a tight-fitting concave hull around these nodes, effectively representing the "frontier" of the robot's reachable territory.

Comparison between fully and insufficiently expanded RRGs showing the construction of the concave hull and frontier nodes.

2. Gain Calculation and Filtering

Instead of checking if a voxel is "unknown" in the occupancy map, the algorithm defines unknown space as any area outside this concave hull. If a voxel is outside the hull and has a clear line of sight from a candidate viewpoint, it contributes to the Graph Gain. This ensures that even if a sensor has "seen" an area, it still provides exploration incentive until the robot's graph has physically expanded into it. To ensure feasibility, the hull is filtered based on the robot's physical size.

Experimental Results

The method was evaluated in a large-scale (130m x 100m) indoor corridor simulation featuring complex layouts and penetrable obstacles. It was compared against the Dual-Stage Viewpoint Planner (DSVP), a current state-of-the-art RRT-based framework.

  • Efficiency: Graph Gain achieved a massive speedup; its average running time was only 38.4% of the DSVP method. Calculating gain by checking point-in-polygon status is significantly faster than ray-casting through dense 3D voxel grids.
  • Completeness: The proposed method successfully explored areas behind railings that the baseline method permanently omitted.
  • Robustness: The graph-based approach provided higher "contrast" between explored and unexplored areas, leading to more decisive and optimal viewpoint selection.

Conclusion

Graph Gain demonstrates that for sampling-based planners, the state of the exploration graph is a better indicator of progress than the state of the occupancy map. While the current implementation uses a 2D projection suitable for ground robots, future work involves extending this to 3D alpha shapes for aerial exploration and testing in dynamic environments with moving obstacles.

Summary updated

Abstract

The existing volumetric gain for robotic exploration is calculated in the 3D occupancy map, while the sampling-based exploration method is extended in the reachable (free) space. The inconsistency between them makes the existing calculation of volumetric gain inappropriate for a complete exploration of the environment. To address this issue, we propose a concave-hull based volumetric gain in a sampling-based exploration framework. The concave hull is constructed based on the viewpoints generated by Rapidly-exploring Random Tree (RRT) and the nodes that fail to expand. All space outside this concave hull is considered unknown. The volumetric gain is calculated based on the viewpoints configuration rather than using the occupancy map. With the new volumetric gain, robots can avoid inefficient or even erroneous exploration behavior caused by the inappropriateness of existing volumetric gain calculation methods. Our exploration method is evaluated against the existing state-of-the-art RRT-based method in a benchmark environment. In the evaluated environment, the average running time of our method is about 38.4% of the existing state-of-the-art method and our method is more robust.
BibTeX
@misc{sun2022graph,
  author = {Zezhou Sun and Huajun Liu and Chengzhong Xu and Hui Kong},
  title = {{Graph Gain: A Concave-Hull Based Volumetric Gain for Robotic Exploration}},
  year = {2022},
  eprint = {2204.10698},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2204.10698},
}
Figure