Real-Time Path Planning for Unmanned Aerial Vehicles Based on Compensated Voronoi Diagram

This paper proposes a real-time path-planning algorithm for unmanned aerial vehicles (UAVs) operating in hostile environments, such as disaster areas and battlefields. The key idea of the algorithm is to compensate Voronoi diagram to quickly yield the paths with maximum survivability against abrupt environmental changes or pop-up threats. We suggest a compensated Voronoi diagram which considers the weighted strengths of various threats, whereas the original Voronoi diagram is constructed via Delaunay triangulation with the same strength of whole threats. Then, Dijkstra algorithm is adopted to find the path connecting the vertices to maximize survivability. This algorithm is simple to implement, requires a short computation time, and can effectively consider the strengths of various threats. Numerical simulations are performed to compare the performance of the proposed method with that of the original Voronoi diagram, the improved Voronoi diagram, and the original Voronoi diagram with optimization. Results show that the proposed path-planning method provides suboptimal solutions in survivability and works in a real-time manner.