Abstract:To address the issues of low search efficiency, multiple path waypoints, and insufficient environmental adaptability in traditional RRT algorithms for epidemic prevention robot path planning, an improved RRT path planning algorithm based on Voronoi skeleton graphs is proposed. This algorithm constructs an offline skeleton graph from the map using a generalized Voronoi diagram and employs the empty circumcircle property of the Delaunay triangulation for local real-time updates, ensuring the skeleton graph′s timeliness in unknown environments. Based on the skeleton graph, an initial heuristic path is quickly obtained, and key path nodes are generated as sub-goals for the RRT algorithm. Elliptical constraints and an attractive field bias are introduced between sub-goal nodes to accelerate sampling and reduce planning time. Finally, an adaptive multi-segment pruning strategy based on a double-pointer technique is designed to smooth the path. Simulation results demonstrate that compared to existing improved algorithms, the proposed method reduces the average number of sampled nodes by 55.57%, shortens the average path length by 6.45%, and decreases the average planning time by 51.44% in complex scenarios, effectively reducing planning overhead and enhancing path planning efficiency.