基于Voronoi图的无人机快速航迹规划研究

Fast Route Planning for UAV Based on Voronoi Diagram

Voronoi图的快速构建是快速完成基于Voronoi图的航迹规划的关键。针对Voronoi图构建效率不高的问题,提出了一种快速构建Voronoi图的方法。首先,利用改进的Bowyer-Watson算法构建Delaunay三角网。在确定待插入点的影响域时,引入bool类型的数组对已构建三角网中的三角形是否为Delaunay三角形进行标记,从而缩小三角形的遍历范围,加快Delaunay三角网的构建速度。然后用间接法得到Voronoi图。此外,对航迹规划过程中起始航迹和终止航迹的确定进行了讨论,完成了基于Voronoi图的无人机航迹规划。结果表明,采用提出的间接法能快速完成Voronoi图的构造。当母点(威胁点)为20 000个时,只需要20 s的时间。对快速完成无人机的航迹规划具有重要的意义。

The key of path planning based on Voronoi diagram is to build Voronoi diagram.Considering the problem that the algorithm of building Voronoi diagram is of low efficiency,a method of building Voronoi diagram rapidly is put foryard.Firstly,the improved Bowyer-Watson algorithm is used to construct Delaunay triangulation.In obtaining the influence domain of the insertion point,an array of bool is introduced to mark whether the triangle of triangulation was Delaunay triangle,which narrowed the scope of traversing triangle,thus accelerating the speed of building Delaunay triangulation.After the construction of Delaunay triangulation,then the indirect method is used to generate Voronoi diagram.Furthermore,the obtain of starting path is discussed and ending path and finally completed the route planning for UAV based on Voronoi diagram.The result shows that the indirect way proposed can quickly build Voronoi diagram.It only needs 20 s when the number of point is 20 000,which has great significance in rapidly completing route planning for UAV.