Free-Space Skeleton Extraction-Based Dynamic Voronoi-A^* Path Planning Algorithm

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<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">${}^{\ast }$ </tex-math></inline-formula> 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<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">${}^{\ast }$ </tex-math></inline-formula> 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.