3D Trajectory Planning of UAV Based on DPGA

Abstract

The goal of trajectory planning is to shorten the flight distance as much as possible on the premise of ensuring the safety of UAV in flight. Therefore, the research of trajectory planning has broad prospects and great significance. As the key technology of trajectory planning, optimization algorithm has increasingly become one of the focuses of scholars at home and abroad. The dynamic programming algorithm is characterized by high computational efficiency and global optimization in trajectory planning. In 3D trajectory planning, as the spatial search space expands, the number of grid points increases faster, and time complexity of the dynamic programming algorithm is ${O}({n}^{3}) $ . It often leads to a “Curse of Dimension” phenomenon, which lowers its computational efficiency drastically. To solve this problem, this paper divides the entire planning space into stages based on Bellman’s optimality principle. A dynamic programming-genetic algorithm(DPGA) is proposed by using genetic algorithm(GA) in each stage for optimization, while using dynamic programming algorithm(DP) in global planning. The global optimization ability of the algorithm is verified through convergence analysis. Moreover, based on a series of simulation experiments, it shows that the improved algorithm proposed in this paper is more efficient than the dynamic programming algorithm and genetic algorithm alone in global optimization.

Keywords

• Trajectory planning
• dynamic programming algorithm
• genetic algorithm