Quantitative Evaluation of Voronoi Graph Search Algorithm in UAV Path Planning

The Voronoi graph search algorithm is a classic method of UAV path planning. There have been many related mature researches in this field, but most of them are about the design and implementation of this algorithm, few studying the influence of each parameter on the performance of the whole algorithm. In this paper, the establishment of a quantitative model of UAV path planning, algorithm design, performance evaluation and optimization suggestions are discussed, and the impact of the threat proportion and the number of threats on the planning results of this algorithm is mainly studied. Furthermore, we analyze the time distribution among Voronoi graph founding time, Dijkstra planning time, and path smoothing time. The evaluation methods and optimization advice of Voronoi graph search algorithm are given, which can be adopted to other path planning algorithms as well.