Clean Generalized Voronoi Diagram: An Efficient Algorithm for Path Planning in Robotics

In the field of robotics, effective environment representation is crucial for tasks such as navigation and path planning. The Generalized Voronoi Diagram (GVD) has emerged as a powerful tool due to its ability to maximize clearance from obstacles, promoting safer and more efficient navigation. However, existing GVD construction algorithms often suffer from redundant edges (weak edges) due to sensor noise, discretization, and grid misalignment. This paper introduces a prune pipeline to construct Clean GVD that addresses the limitation by eliminating weak edges during map generation. Our method builds upon incremental distance transform techniques and incorporates a pruning pipeline to ensure the removal of weak edges. Additionally, we propose an incremental topological graph construction method based on the Clean GVD. Experimental results demonstrate the effectiveness of our approach in producing compact and efficient GVDs, outperforming traditional pre-pruning and post-pruning methods in both computational efficiency and edge quality. The proposed clean GVD and topological graph construction techniques hold significant potential for improving autonomous exploration and navigation in robotic applications.