基于Dijkstra算法改进的飞行器航迹快速规划算法  

Improved fast aircraft path planning algorithm based on Dijkstra algorithm

作　　者：郑弈 谢亚琴[1] ZHENG Yi;XIE Yaqin(Nanjing University of Information Science&Technology,Nanjing 210044,China)

机构地区：[1]南京信息工程大学,南京210044

出　　处：《电子测量技术》2022年第12期73-79,共7页Electronic Measurement Technology

基　　金：国家自然科学基金(62001238,62105159)项目资助。

摘　　要：当飞行器在航行途中遇到突发情况需要临时更改路径时,这就对航迹规划算法的效率和可靠性提出了很高的要求。针对这一问题,提出了一种加入预搜索的Dijkstra算法改进方案。该算法使用归一化熵权法建立了较为客观的航迹评价函数,简化了多目标航迹优化模型。通过加入深度为一的预搜索过程实现D算法的回溯功能,解决了经典D算法因松弛性不足,在复杂约束条件下路径搜索失败率高的问题。此外,为了进一步减少运算时间,在预搜索遍历过程中加入跳出机制。算法仿真结果表明,本文所提算法的运行时间相较于普通回溯D算法减少了46%,且在复杂约束条件下的航迹搜索成功率与航迹质量均接近智能算法,能够满足复杂条件下快速航迹规划的需求。When the aircraft needs to change the path temporarily in case of emergencies during navigation, the efficiency and reliability of the route planning algorithm are urgently required. An improved Dijkstra algorithm with pre search is proposed to solve this problem. A more objective track evaluation function is established by using the normalized entropy weight method to simplify the multi-objective track optimization model. The backtracking function of D algorithm is realized by adding the pre search process with depth of one, which solves the problem of high failure rate of path search under complex constraints due to insufficient relaxation of classical D algorithm. In addition, a break mechanism is added in the pre search traversal process to further reduce the operation time. Simulation results show that the operation time of the proposed algorithm is reduced by 46% compared with ordinary backtracking D algorithm. And the algorithm is close to intelligent algorithm in path search success rate and the accuracy of the shortest path decision under complex constraints, which can meet the requirements of fast path planning under complex conditions.

关 键 词：多目标优化 熵权法 DIJKSTRA 预搜索 回溯算法 

分 类 号：TN967.5[电子电信—信号与信息处理]