Research on 3D layered visibility graph route network model and multi-objective path planning for UAVs in complex urban environments

Over the past decade, unmanned aerial vehicles (UAVs) have seen increased use in urban transportation, including applications such as package delivery and emergency rescue. However, the complex nature of urban environments poses significant challenges to the safe and efficient operation of UAVs. Path planning offers an effective solution for improving both flight efficiency and safety. This paper develops a novel flight path optimization method that accounts for the configuration of urban environments, as well as critical operational constraints, such as obstacle avoidance and flight altitude limitations. The urban environment is modeled as a 3D layered visibility graph network by deforming urban buildings to cuboid obstacles and representing the obstacles with discrete sampling points. To mitigate potential collision risks between UAVs, maneuvering protection zones (MPZs) are integrated into the network. The objective of this study is to simultaneously minimize path length and maximize the path confidence level, with the latter being a comprehensive assessment of safety, reliability, and public acceptance. To solve the proposed multi-category multi-objective path optimization problem, an improved ripple-spreading algorithm (RSA) is developed, which is theoretically proven to provide the exact and complete Pareto-optimal solution set. Simulation tests, performed on both artificially generated problems and the urban area of Shenzhen, China, demonstrate that the inclusion of MPZs reduces the computing time by 70% while increasing the average shortest path length by only 1%. In addition, compared to other existing algorithms, RSA demonstrates high efficiency in identifying the complete Pareto frontier in large-scale networks.