The Voronoi diagram generated by the current Voronoi path planning algorithm is bending redundant. Real-time performance of planning path based on Voronoi map is poor. Robots have many turning points, high time cost and low efficiency when navigating. A Voronoi diagram path planning algorithm based on skeleton key points re-planning was proposed. Firstly, robots built a two-dimensional environmental grid map with a mapping algorithm. The grid map constructed by the robot was pretreated. The noise and edges in the map was removed, and the tiny cracks on the boundary were filled. Secondly, the skeleton of the map was extracted. The key points in the skeleton were searched. Then the extracted key points were divided into end points and branch points. The connection relationship between each key point was found and the key points were reconnected according to the new connection relationship between adjacent points to generate a new and simpler skeleton. Finally, the path planned in each navigation was sampled down gradiently and smoothed. It was proved that the skeleton generated by the proposed algorithm was more concise and had less data than the current Voronoi diagram and skeleton.The robot can plan the straight path more quickly and had good real-time performance based on the optimized Voronoi map. The planned path was shorter. Robot had less turning points. And robot can quickly arrive at destination in the navigation process, and the navigation efficiency was high.