Abstract:

The Voronoi diagram is a graph-based commonly used technique for creating the initial feasible path sets of an unmanned aerial vehicle (UAV), whose edges are the perpendicular bisector of the two closest threat sites. It does not take the threats’ effective range into consideration, thus certain paths may go through some of the threat zones. To overcome the drawback of the Voronoi diagram, an important structure in computation geometry, Laguerre diagram, is introduced. It is proved that the generated initial paths will fall inside the interspaces of two closest threat zones when they do not intersect. Since the construction algorithm is difficult to implement, a new approach to build the Laguerre diagram based on the Delaunay graph is developed, whose time complexity is O(nlg n). Simulation results demonstrate the validity of the Laguerre diagram for path planning, and verify that the runtime of the construction algorithm can fulfill the requirement of online planning.