Analyses and Comparisons of UAV Path Planning Algorithms in Three-Dimensional City Environment

Path planning for unmanned aerial vehicle (UAV) is a crucial problem especially in complicated three-dimensional (3D) city environments. Until recently, several algorithms have been proposed to realize the UAV operations in 3D city environment, but the existing algorithms only focus on the ideal conditions, including known obstacles and deterministic UAV parameters. However, the complicated city environment leads to a lot of randomness. In this way the evaluations of different path planning algorithms in a city environment become indispensable for the UAV operations. In this paper three classic UAV path planning algorithms are selected to make the detailed analyses and comparisons, namely A∗ algorithm, random-rapidly tree algorithm (RRT), ant colony algorithm (ACO). Three scenarios are designed and applied to test the mentioned algorithms above, considering different sizes of city operation scenarios, different altitudes between starting point and destination point, and different densities of obstacles in the flying environment. The simulation results show that A∗ algorithm works well in all three scenarios. Similarly, ACO is especially suitable for large scale scenes with a great amount of height differences between starting and destination points. To some extent RRT is the worst of the three in the designed scenarios because of the characteristics of random walking when locating the optimum solutions.