###
计算机系统应用:2019,28(4):25-31
本文二维码信息
码上扫一扫!
融合简化稀疏A*算法与模拟退火算法的无人机航迹规划
杨玉1,2, 金敏2, 鲁华祥2,3,4,5
(1.中国科学技术大学 微电子学院, 合肥 230026;2.中国科学院 半导体研究所, 北京 100083;3.中国科学院大学, 北京 100049;4.中国科学院 脑科学与智能技术卓越创新中心, 上海 200031;5.半导体神经网络智能感知与计算技术北京市重点实验室, 北京 100083)
UAV Path Planning Based on Fusion of Simplified Sparse A* Algorithm and Simulated Annealing Algorithm
(1.School of Microelectronics, University of Science and Technology of China, Hefei 230026, China;2.Institute of Semiconductors, Chinese Academy of Sciences, Beijing 100083, China;3.University of Chinese Academy of Sciences, Beijing 100049, China;4.Center for Excellence in Brain Science and Intelligence Technology, Chinese Academy of Sciences, Shanghai 200031, China;5.Semiconductor Neural Network Intelligent Perception and Computing Technology Beijing Key Lab, Beijing 100083, China)
摘要
图/表
参考文献
相似文献
本文已被:浏览 123次   下载 100
投稿时间:2018-10-23    修订日期:2018-11-12
中文摘要: 针对无人机航迹规划问题,提出了一种融合简化稀疏A*算法与模拟退火算法(Fusion of Simplified Sparse A* Algorithm and Simulated Annealing algorithm,简称FSSA-SA)的航迹规划方法.首先,在对威胁环境进行建模之后,将模拟退火思想与具体航迹规划问题求解相结合,给出了模拟退火算法求解航迹规划问题的具体设计与实现方法.其次,利用简化的稀疏A*算法在规划起止点之间进行一次往返搜索,并将所得结果中较优的一条航迹作为模拟退火算法的初始解,实现了两种算法的融合.然后,当退火进行至低温区时,通过对位置存在冗余的航迹节点的剔除,进一步改善了算法的求解质量.最后为了验证算法的优越性,将本文算法与稀疏A*算法、模拟退火算法进行了仿真对比试验.试验结果表明,本文提出的FSSA-SA算法相比于上述两种算法,具有较少的规划耗时;相比于稀疏A*算法,在所得航迹的综合代价相差不大的情况下,内存占用量少了两个量级;相比与模拟退火算法,在相同的退火条件下,其规划所得航迹的综合代价平均减少了35%左右.
Abstract: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.
文章编号:     中图分类号:    文献标志码:
基金项目:中科院战略性先导科技专项(A类)(XDA18040400);国家自然科学基金(61701473)
引用文本:
杨玉,金敏,鲁华祥.融合简化稀疏A*算法与模拟退火算法的无人机航迹规划.计算机系统应用,2019,28(4):25-31
YANG Yu,JIN Min,LU Hua-Xiang.UAV Path Planning Based on Fusion of Simplified Sparse A* Algorithm and Simulated Annealing Algorithm.COMPUTER SYSTEMS APPLICATIONS,2019,28(4):25-31

用微信扫一扫

用微信扫一扫