融合简化稀疏A*算法与模拟退火算法的无人机航迹规划

针对无人机航迹规划问题，提出了一种融合简化稀疏A^*算法与模拟退火算法（Fusion of Simplified Sparse A^* Algorithm and Simulated Annealing algorithm，简称FSSA-SA）的航迹规划方法.首先，在对威胁环境进行建模之后，将模拟退火思想与具体航迹规划问题求解相结合，给出了模拟退火算法求解航迹规划问题的具体设计与实现方法.其次，利用简化的稀疏A^*算法在规划起止点之间进行一次往返搜索，并将所得结果中较优的一条航迹作为模拟退火算法的初始解，实现了两种算法的融合.然后，当退火进行至低温区时，通过对位置存在冗余的航迹节点的剔除，进一步改善了算法的求解质量.最后为了验证算法的优越性，将本文算法与稀疏A^*算法、模拟退火算法进行了仿真对比试验.试验结果表明，本文提出的FSSA-SA算法相比于上述两种算法，具有较少的规划耗时；相比于稀疏A^*算法，在所得航迹的综合代价相差不大的情况下，内存占用量少了两个量级；相比与模拟退火算法，在相同的退火条件下，其规划所得航迹的综合代价平均减少了35%左右.

UAV Path Planning Based on Fusion of Simplified Sparse A* Algorithm and Simulated Annealing Algorithm

To solve the UAV path planning problem, a method based on Fusion of Simplified Sparse A^* algorithm and Simulated Annealing algorithm (FSSA-SA) is proposed. Firstly, after modeling the threat environment, the simulated annealing idea is combined with the solution of the specific route planning problem, and the concrete design and implementation method of the simulated annealing algorithm is given. Secondly, the simplified sparse A^* algorithm is used to search the roundtrip tracks between the start point and the end point, and the better one of the results will be used as the initial solution of the simulated annealing algorithm to realize the fusion of the two algorithms. Then, when annealing proceeds to the low temperature region, the solution quality of the algorithm is further improved by eliminating the redundant track nodes. Finally, in order to verify the superiority of the proposed algorithm, the simulation experiments are carried out with sparse A^* algorithm and simulated annealing algorithm. The experimental results show that the proposed FSSA-SA algorithm has less planning time-consuming than the two algorithms mentioned above; compared with the sparse A^* algorithm, the memory occupied by the FSSA-SA algorithm is two orders of magnitude less when the synthetic cost of the obtained track is not too different; compared with the simulated annealing algorithm, under the same annealing conditions, the integrated cost of the planned track is reduced by about 35% on average.