Optimal Path Planning for UAVs under Dynamic Obstacles

Deok-Soo KIM
Hanyang University, N/A, Korea

Keywords: UAV, path planning, dynamic Voronoi diagram, moving disks

Given moving obstacles such as moving radars and antiair artilleries, the optimal path planning for UAVs is critical. This study proposes a novel method to plan the optimal paths for UAVs using dynamic Voronoi diagram of moving disks which model the obstacles. The proposed algorithm efficiently computes the optimal paths of UAVs for many moving obstacles. The solution process consists of two phases: i) Constructing dynamic Voronoi diagram (DVD) and its derived structure called Beta-shape and ii) solving a combinatorial optimization problem. The first phase is to construct DVD and its Beta-shape, which are used for efficiently capturing the proximity information among moving disks. Given a Beta-shape, we can quickly find the optimal path of each UAV using the Beta-shape by solving a combinatorial optimization problem.