Free-Space Skeleton Extraction-Based Dynamic Voronoi-A* Path Planning Algorithm
Yunfei Li, Wan-Zhen Yang, Lin Jiang, Bo Tang, Jianyang Zhu · IEEE Sensors Journal · 2025
To address the issues of poor real-time performance, long skeleton extraction times, redundant and convoluted paths, and the inability to handle dynamic environmental changes in the existing Voronoi-based path planning algorithms, we propose a dynamic Voronoi-A${}^{\ast }$path planning algorithm based on free-space skeleton extraction. First, the grid map is optimized through preprocessing, and a binary map is obtained using morphological operations. Next, an improved free-space skeleton extraction mechanism is introduced to significantly reduce skeleton extraction time, and a skeleton re-refinement algorithm is proposed to enhance skeleton accuracy. Then, Voronoi diagrams are integrated into the A${}^{\ast }$evaluation function to address the issues related to dynamic environmental changes and path redundancy. Finally, extensive simulations and real-world experiments demonstrate that the proposed algorithm reduces global path planning time by 74.16% compared to the existing methods, effectively solving the path redundancy problem.