Three-dimensional path planning of unmanned aerial vehicle based on an improved D* algorithm

Abstract

An improved D* algorithm was proposed to solve the problems of low efficiency and complex inflection points in three-dimensional path autonomous planning of unmanned aerial vehicle using traditional D* algorithm. Firstly, variable step size was used to expand nodes, which speeded up the algorithm's traversal of nodes in the planning stage. At the same time, the fusion formula of Chebyshev distance and Manhattan distance was used as surrogate value, the cost function was improved, the calculation amount of the algorithm was reduced, and the low efficiency of the algorithm was solved. Finally, the three-dimensional map and the obtained path were projected onto the two-dimensional plane, key nodes were selected, redundant nodes were discarded, and the generated path was optimized. The number of inflection points and complexity of the obtained path were reduced. The simulation results show that the improved D* algorithm can be effectively used in the path planning of unmanned aerial vehicle in the three-dimensional environment, and the expected effect is achieved in terms of accelerating the efficiency of the algorithm and improving the quality of the path.

Keywords

• three dimension
• path planning
• d* algorithm
• unmanned aerial vehicle
• simulation modeling