狭窄空间无人机动态三维A*算法研究

Research on Improved Global and Local Dynamic 3D A* Algorithm

摘要:

针对三维飞行器在动态环境下使用三维A*算法进行局部仿真时，环境信息未知，存在冗余点和拐点，导致收敛时间长、路径节点扩展代价大、易陷入局部最优问题，提出一种基于全局与局部相结合的动态三维A*寻路算法。此算法首先改进评价函数的权值系数动态分配，减小路径冗余点和拐点，从而降低算法耗时，缩短路径长度；其次改进路径生成策略，有效提高算法效率，避免陷入局部最优，进一步缩短路径长度，从而实现飞行器在三维动态环境中的路径规划。将改进后的算法进行仿真对比，仿真结果表明，改进后的算法路径更加合理，算法耗时和路径长度更短。

Abstract:

When using the 3D A* algorithm for local simulation in a dynamic environment for a 3D device, the environmental information is unknown, there are redundant points and inflection points, which leads to convergence time, path node expansion cost, and easy to trap local optimal problems. A dynamic three-dimensional A* pathfinding algorithm based on the combination of global and local is proposed. This algorithm first improves the dynamic allocation of weight coefficients of the evaluation function, reduces the redundant points and inflection points of the path, thereby reducing the algorithm time-consuming and shortening the path; secondly improves the path formation strategy, effectively improves the efficiency of the algorithm and avoids falling into Local optimization, further shorten the path degree, and realize the path planning of the implement in a three-dimensional dynamic environment. The improved algorithm is compared with simulation. The simulation results show that the improved algorithm has a more reasonable path, and the time and path length of the algorithm are shorter.