结合进化算法的稀疏A*算法对动态目标的无人机航迹规划研究

刘群芳　李军华

摘 要： 针对移动目标的无人机航迹规划问题，结合文化算法改进稀疏A*算法解决静态航迹的绕径问题，然后进一步使用混合算法解决目标跟随过程中动态航迹的规划速度和最优路径的平衡选择问题，最终实现不确定环境下跟随目标和威胁躲避的动态航迹实时规划。通过采用静态和动态两级分层规划结构，使用基于稀疏A*算法与文化算法的混合算法实现了动态目标和动态威胁的无人机航迹规划。

关键词： 航迹规划； 稀疏A*算法； 文化算法； 混合进化算法； 目标跟随

中图分类号：TP301.6 文献标志码：A 文章编号：1006-8228（2016）06-17-05

Abstract： In order to solve the problem of unmanned aerial vehicle （UAV） dynamic target path planning， this paper uses the two-level hierarchical planning structure and the hybrid evolutionary algorithm of the sparse A* algorithm and the cultural algorithm （CA） to realize the dynamic UAV path real-time planning under the dynamic target， solves the dynamic path planning problem of avoiding threats and following the target， improves the planning speed and reliability of the track， strengthens the flight safety of UAV.

Key words： path planning； sparse A* algorithm； culture algorithm； hybrid evolutionary algorithm； target follow

0 引言

随着现代航空领域的科技进步和战场环境的日渐复杂，对无人机飞行难度的要求也随之提高。

航迹规划作为无人机任务规划系统（Mission Planning System）的一项关键技术，目前已有多种进化算法应用于求解航迹规划问题，主要有遗传算法（GA）[1]、蚁群算法（Ant）[2]及其混合改进形式。A*算法[3]以其较快的搜速度而突出，是一种经典的最优启发式搜索算法，但其缺点是存储数据会随着搜索区间的增大而增加，导致规划耗时过长。为加快搜索速度，Szczerba[4]、周成平[5]、穆中林[6]等人均提出了改进方法，在一定程度上提高了算法的规划速度，但得到的路径往往不是最优解，存在绕径问题[7]。

传统的无人机动态航迹规划，要求能实时规避突发威胁并安全到达指定目标点，但因受到各种因素的影响、约束条件限制和任务的改变等，目标点往往是多变的。因而针对动态目标以及动态威胁需要一种更为可行的动态规划方法，以适应实际环境和任务的需求，实现对动态目标跟随的无人机航迹规划。

文化算法（Cultural Algorithm，CA）是Reynolds[8]于1994提出的，它是一种基于种群的多进化过程的计算模型，为进化搜索机制和知识存储的结合提供了一个构架。传统生物进化算法由于受种群个体经验知识的保存和表示限制，只能提供有限的进化经验知识，而近年来兴起的文化算法打破了这种局限性，因为文化算法在宏观层面及微观层面上可以对种群进化进行指导与交流，突破了种群个体的限制，可以极大地促进种群的进化和发展，因此将文化算法应用于无人机航迹规划具有一定的研究价值和意义。

本文将稀疏A*算法与文化算法相结合，应用于动态航迹规划，并在解决稀疏A*算法的绕径问题基础上，面对远近动态威胁时以安全为第一目标，平衡重规划的规划速度和航迹质量，最终实现动态目标跟随的最优航迹规划。

1 问题建模

无人机动态目标跟随的航迹规划是指无人机根据目标的改变而实时进行的航迹重规划，规划过程中需要考虑各种约束条件以及突发威胁以及动态变化的目标点的影响，以实现无人机更高要求的动态航迹规划。

根据规划内容可分为三大部分：地图模型的建立、全局静态航迹规划、动态实时航迹规划。

第一部分将各种已知威胁源按其威胁模型等效为地形，与已知地形信息融合，建立全概率综合数字地图；第二部分是在数字地图上结合各种约束条件及任务要求规划出一条全局静态预航迹；第三部分是将预航迹作为参考航迹，若探测到有突发威胁出现或者目标点改变，则依据目标点和突发威胁的情况实时修改航迹，无人机航迹规划系统框图如图1所示。

1.1 地图环境建模

地图环境是无人机航迹规划的基础，主要由地形障碍、导弹、雷达、高炮、天气、未探测区域等内容构成。将所有环境组成部分视为威胁源处理，并按其作用方式、强度及位置叠加于数字地图中，生成包含地形信息和各种威胁信息的全概率综合数字地图，同时在等效过程中将三维地图等效映射成为二维地图。

1.2 航迹代价评估函数

在航迹规划中，航迹代价评估函数是用于指导算法寻找最优航迹的重要工具，其内容主要包括评价航迹的重要指标：航迹长度和航迹威胁代价，需要按比例协调两者的权重关系。本文根据稀疏A*算法设计航迹评价函数如下：

其中，公式⑴的第一个项为实际代价部分，li为节点i-1到节点i之间的航迹长度，fi为节点i-1到节点i之间受到的威胁值，w1、w2为相应权重系数。公式⑴最后一项为启发函数部分，d（n）表示当前节点n到目标点之间的航迹估计长度，w3为相应权重系数。

2 无人机静态航迹规划

2.1 基于稀疏A*算法静态实现航迹规划流程

基于稀疏A*算法的静态航迹规划流程如图2所示，规划的核心内容为稀疏A*算法实现部分，算法的改进也主要在该部分进行设计。

基于稀疏A*算法与混合算法的静态航迹规划流程如图3所示，规划的核心部分为：首先采用稀疏A*算法进行规划，然后使用文化算法进行修径。

3 无人机动态航迹规划

由于在实际飞行中，突发威胁的出现需要无人机重新规划航迹以快速躲避威胁，但重规划航迹需要一定的时间，在该时间段内无人机还是按原来的航迹飞行直至航迹重规划完成，因此需要提出将该时间段内无人机的飞行航迹长度作为航迹重规划的距离标准，判断是以快速规划优还是路径最优解优先。

其中，D表示安全飞行规划距离，v表示无人机的飞行速度，t表示理想算法重规划航迹所需的最大平均时间。

为方便有限条件下的实验仿真，本文以无人机的最小步长N*Lmin代替。

由于无人机的飞行航迹非常复杂，因此将目标点分两种情况：固定目标点和动态目标点，然后对这两种情况分别进行动态航迹规划。

3.1 固定目标的智能无人机动态航迹规划流程

在目标固定的情况下，基于稀疏A*算法与混合算法的混合进化算法，实现规避突发威胁的无人机动态航迹规划，其流程如图4所示，针对飞行过程中的远近突发威胁，采取最佳算法方案进行规划。

4 实验仿真结果

实验仿真平台：基于XP操作系统的计算机，主频为3.20GHz，内存为3.21GB，使用matlable 7.10.0（R2010a）软件进行编程实现仿真。假定无人机在100X100km的区域内执行任务，按1：5的比例将规划区域转换为500x500的坐标区域，出发点坐标为（21，144），目标点坐标为（446，446），最大转弯角θ=60?，Lmin=4km，M取6，则扩展节点为7个，航迹代价评价函数的权重系数w1、w2、w3分别取0.001、300、0.1，静态航迹规划仿真实验结果如图6所示。

图6（a）为基于稀疏A*算法规划出的静态预航迹，图6（b）中实线为基于稀疏A*算法与文化算法的混合进化算法规划出的静态预航迹。为方便对比，将图6（a）中的航迹以虚线加入图6（b）中，其余图形为各威胁源。

对比图6中（a）、（b）两图可知，加入文化算法后有效改善了稀疏A*算法的绕径问题，缩短了航迹长度。表1展示了两种算法的时间性能参数。

从表1可知，稀疏A*算法具有最快的计算速度，而基于稀疏A*算法与文化算法的混合进化算法规划出的航迹总威胁代价最小，且航迹长度短。

在实现静态预航迹规划的基础上，进一步实现动态航迹规划。首先在目标点固定的情况下，模拟无人机实际飞行过程遇见两种动态威胁，一种为动态威胁出现在距离无人机飞行当前点小于安全飞行规划距离的情况，另一种为动态威胁出现在距离当无人机飞行当前点大于安全飞行规划距离的情况。本文中全飞行规划距离D统一采用3?Lmin作为仿真标准。这两种情况中实现的动态航迹规划仿真结果如图7所示。

图7（a）为基于稀疏A*算法与文化算法的混合进化算法规划出的静态预航迹；图7（b）为面临突发威胁出现时距离当前飞行点小于D的情况下，基于混合进化算法进行的动态实时航迹；图7（c）为面临突发威胁出现时距离当前飞行点大于D的情况下，基于混合进化算法进行的动态实时航迹。图7中虚线航迹表示静态预航迹，实线表示实时航迹，其中图7（b）和图7（c）显示了无人机遇见突发威胁时动态航迹规划实验结果。

通过图7（b）可以观察到，在面临突发威胁距离当前飞行点小于安全飞行规划距离的情况下，无人机采用稀疏A*算法快速有效地避开了临近的突发威胁，虽然存在航迹绕径，但可以保障安全飞行。

通过图7（c）可以观察到，在面临突发威胁距离当前飞行点大于安全飞行规划距离的情况下，无人机采用稀疏A*算法结合文化算法的混合进化算法规划，既规避了突发威胁又得到了最优航迹。因此，该基于混合进化算法的动态航迹规划方法有效地实现了无人机的实时动态航迹规划，并可以协调分配飞行安全与飞行代价。

为进一步提高无人机自主飞行的智能性，继续进行仿真，模拟无人机实际飞行过程中规避两种突发威胁和跟随动态目标进行的航迹规划情况。动态航迹规划仿真结果如图8所示。

图8中，（a）和（d）图为基于混合算法规划的静态预航迹，（b）和（c）图皆为动态目标跟随时对突然威胁距离无人机当前飞行点小于D的动态航迹规划。其中（b）图为突发威胁出现前对动态目标跟随的航迹规划结果，（c）图为突发威胁出现后对动态目标跟随及规避动态威胁的航迹规划结果；图8中，（e）和（f）图皆为动态目标跟随时对突然威胁距离无人机当前飞行点大于D的动态航迹规划结果。图8中，虚线表示历史重规划航迹，实线表示实时行进航迹。

通过观察图8航迹规划结果可知，该基于混合进化算法的智能动态航迹规划方法有效地实现了对动态目标的跟随，并在跟随过程中有效地规避了不同类型的动态威胁，可以保障无人机的安全，还可以实现目标追踪和监控作用。

5 结束语

本文在解决稀疏A*算法的绕径问题的基础上，实现了动态环境下的航迹动态规划，实现了动态目标跟随和突发威胁的规避。仿真结果表明，所提出的基于稀疏A*算法与文化算法的混合算法不仅能够进一步改善稀疏A*算法的航迹，还能提高无人机在不同要求下的灵活自控性，扩大了无人机的应用空间和价值，并使其性能得到更大程度的优化。

参考文献（References）：

[1] 张延松.基于遗传算法的无人机航迹规划研究[D].中南大学

硕士学位论文，2010.

[2] Zhang chao， Zhen Ziyang， Wang DaoBo， et al.UAV path

planning Method Based on Ant Colony Optimization[C]. 2010 Chinese Control and Decision Conference，2010：3790-3792

[3] 周青，李广文.基于A*算法的无人机四维航迹规划研究[J].计

算机仿真，2014.31（4）：92-96

[4] Szczerba Robert J. Robust Algorithm for Real-Time Route

Planning[J]. IEEE Transactions on Aero-space and Electronic Systems，2000.36（3）：869-878

[5] 周成平，陈前洋，秦筱.基于稀疏A*算法的三维航迹并行规划

算法[J].华中科技大学学报（自然科学版），2005.33（5）：42-45

[6] 穆中林，鲁艺，任波等.基于改进A*算法的无人机航路规划方

法研究[J].弹箭与制导学报，2007.27（1）：297-300

[7] 占伟伟，王伟，陈能成等.一种利用改进A*算法的无人机航迹

规划[J].武汉大学学报（信息科学版），2015.40（3）：315-320

[8] 齐仲纪，刘漫丹.文化算法研究[J].计算机技术与发展，2008.5

（1）：26-30