An improved PSO-ABC path planning algorithm for UAVs based on a construction of urban airspace topology with actual GIS data

In this paper, an improved particle swarm optimization - artificial bee colony (PSO-ABC) path planning algorithm for unmanned aerial vehicle (UAV) operations based on a construction of urban airspace topology is proposed. A mechanism is introduced first to build an airspace topology by assessing the feasibility of specified urban airspace. In this mechanism, a complete urban airspace is discretized into many voxels and two indexes are incorporated which are urban airspace availability and urban ground risk. The former is quantified by analyzing the connectivity of urban voxels focusing on impacts of urban buildings and other features. The latter uses an existing risk estimation model to generate an risk map that describes ground risk distributions imposed by UAV operations. According to these two indexes, the feasibility of the airspace is evaluated by a quadrant analysis and a Pareto sorting successively to produce an airspace topology with the real urban GIS data. In this constructed airspace topology, by considering the safety levels of ground areas, performance constraints of UAVs and no-fly zones defined in the city, a global and local search strategy is proposed by fusing two heuristic algorithms, which are PSO for a global search and ABC algorithm for a local search. An improved PSO-ABC planning algorithm for UAV operations is formed using an urban airspace topology. An urban area in Changqing District, Jinan City is taken as the experimental scenario to carry out simulation analysis. The experimental results show that the performances of the proposed algorithm is the best of all with high path smoothness and fast convergence speed. The proposed method significantly improves both the stability and robustness of the path planning solution.