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

作者简介:

通讯作者:

中图分类号:

基金项目:

中科院战略性先导科技专项(A类)(XDA18040400);国家自然科学基金(61701473)


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

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 增强出版
  • |
  • 文章评论
    摘要:

    针对无人机航迹规划问题,提出了一种融合简化稀疏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*算法与模拟退火算法的无人机航迹规划.计算机系统应用,2019,28(4):25-31

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2018-10-23
  • 最后修改日期:2018-11-12
  • 录用日期:
  • 在线发布日期: 2019-03-29
  • 出版日期:
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京海淀区中关村南四街4号 中科院软件园区 7号楼305房间,邮政编码:100190
电话:010-62661041 传真: Email:csa (a) iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号