无人机航迹规划常用算法

ＶｏＩ．３７。Ｎｏ．８　Ａｕｇ，２０１２　火力与指挥控制　Ｆｉｒｅ　Ｃｏｎｔｒｏｌ＆Ｃｏｍｍａｎｄ　Ｃｏｎｔｒｏｌ　第３７卷第８期　２０１２年８月　

文章编号：１００２一Ｏ６４０（２０１２）Ｏ８一Ｏ００５一Ｏ４　

无人机航迹规划常用算法　

王　俊，周树道，朱国涛，程　龙，罗　炜　

（解放军理工大学气象学院，南京２１１１０１）　

摘要：无人机航迹规划是实现无人机自主飞行的关键技术保障，航迹规划算法则是航迹规划的核心。首先介绍无人机　航迹规划的相关理论，其次分析归纳了当前常用的航迹规划算法，最后阐述了航迹规划所面临的挑战及其发展方向。　关键词：航迹规划，自主飞行，算法　中图分类号：Ｖ２４９．１　文献标识码：Ａ　

Ｒｅｓｅａｒｃｈ　ｏｆ　Ｃｏｍｍｏｎ　Ｒｏｕｔｅ　Ｐｌａｎｎｉｎｇ　Ａｌｇｏｒｉｔｈｍｓ　

ｆｏｒ　Ｕｎｍａｎｎｅｄ　Ａｉｒ　Ｖｅｈｉｃｌｅ　

ＷＡＮＧ　Ｊｕｎ，ＺＨＯＵ　Ｓｈｕ－ｄａｏ，ＺＨＵ　Ｇｕｏ—ｔａｏ，ＣＨＥＮＧ　Ｌｏｎｇ，ＬＵＯ　Ｗｅｉ　

（Ｉｎｓｔｉｔｕｔｅ　ｏｆ　Ｍｅｔｅｏｒｏｌｏｇｙ。ＰＬＡ　Ｕｎｉｖ．ｏｆ　Ｓｃｉ．＆　ｃ＾．，Ｎａｎｊｉｎｇ　２１１１０１，Ｃｈｉｎａ）　

Ａｂｓｔｒａｃｔ：Ｒｏｕｔｅ　ｐｌａｎｎｉｎｇ　ｆｏｒ　ＵＡＶ　ｉｓ　ｔｈｅ　ｋｅｙ　ｔｅｃｈｎｏｌｏｇｙ　ｓｕｐｐｏｒｔ　ｆｏｒ　ａｕｔｏｎｏｍｏｕｓ　ｆｌｉｇｈｔ，ａｎｄ　ｔｈｅ　ｒｏｕｔｅ　

ｐｌａｎｎｉｎｇ　ａｌｇｏｒｉｔｈｍｓ　ｉｓ　ｔｈｅ　ｃｏｒｅ　ｏｆ　ｔｈｅ　ｒｏｕｔｅ　ｐｌａｎｎｉｎｇ．Ｆｉｒｓｔｌｙ，ｔｈｅ　ｐａｔｈ　ｐｌａｎｎｉｎｇ　ｉｓ　ｉｎｔｒｏｄｕｃｅｄ．Ｔｈｅｎ，ｔｈｅ　

ｃｕｒｒｅｎｔ　ｍａｉｎｓｔｒｅａｍ　ｒｏｕｔｅ　ｐｌａｎｎｉｎｇ　ａｌｇｏｒｉｔｈｍｓ　ｉｓ　ａｎａｌｙｚｅｄ　ａｎｄ　ｓｕｍｍａｒｉｚｅｄ．Ｆｉｎａｌｌｙ，ａ　ｂｒｉｅｆ　ｄｅｓｃｒｉｐｔｉｏｎ　ｏｆ　

ｔｈｅ　ｃｈａｌｌｅｎｇｅｓ　ｔｏ　ｔｈｅ　ｐａｔｈ　ｐｌａｎｎｉｎｇ　ａｎｄ　ｔｈｅ　ｄｅｖｅｌｏｐｍｅｎｔ　ｔｒｅａｄ　ｉｓ　ｇｉｖｅｎ．　

Ｋｅｙ　ｗｏｒｄｓ：ｒｏｕｔｅ　ｐｌａｎｎｉｎｇ，ａｕｔｏｎｏｍｏｕｓ　ｆｌｉｇｈｔ，ａｌｇｏｒｉｔｈｍｓ　

引　言　

无人机航迹规划是指在综合考虑无人机到达时　

间、油耗、威胁以及飞行区域等因素的前提下，为无　

人机规划出最优或者满意的飞行航迹，以保证圆满　

地完成飞行任务，并安全返回基地［１］。在防空技术日　

益先进且防空体系日益完善的现代战争环境中，航　

迹规划是提高无人机作战效能、实施远程精确打击　

的有效手段，规划算法是航迹规划的核心，算法的优　

劣在一定程度上决定了航迹规划的成功与否。　

１　无人机航迹规划　

无人机航迹规划是指根据预设数字地图，在给　

定无人机性能指标、地理环境、作战任务等约束条件　

的前提下，规划出一条能够回避威胁区域并且实现　

最优性能的三维航迹轨迹。航迹规划综合应用ＧＰＳ　

（Ｇｌｏｂａｌ　Ｐｏｓｉｔｉｏｎ　Ｓｙｓｔｅｍ）、ＧＩＳ（Ｇｅｏｇｒａｐｈｉｃ　

收稿日期：２０１１－０６—２６　修回日期：２０１１－０８—１８　作者简介：王俊（１９８７一），男，江苏泰州人，硕士，主要　研究方向：智能信息系统。　Ｉｎｆｏｒｍａｔｉｏｎ　Ｓｙｓｔｅｍ）、ＲＳ（Ｒｅｍｏｔｅ—ｓｅｎｓｅ　Ｓｙｓｔｅｍ）技　

术［２］，其中ＧＰＳ技术为无人机提供高精度的导航；　

运用ＧＩＳ以及ＲＳ技术可以获得地形及敌情信息，　

最后按照一定的算法规划出最优的路径。无人机航　

迹规划系统通常由以下几个部分组成：气象、地形、　

敌情等数据处理模块，全局（离线）路径生成模块，在　

线路径优化处理模块，其系统框图如图１所示。　

气象威胁　

地形威胁　

敌方雷达及　火力威胁　］ｌ　Ｉ两　］　Ｉ约束条件Ｉ　Ｌ墨　堕　

霍　商　罄卜ｆ　息ｌ　—Ｔ一～　

飞行任务要求　

图１无人机航迹规划系统框图　

为了实现无人机的智能自主飞行，要求航迹规　

划系统具备以下功能：首先在元人机起飞前，能够根　

据数字地图，结合不同的威胁因素以及无人机自身　

的约束条件离线规划出一条满足任务要求的最优参　

考航迹；在无人机飞行过程中，能够根据突发的现场　

环境改变（气象因素、地形因素、未知威胁等）进行在　・６・　（总第３７—１４６４）　火力与指挥控制　２０１２年第８期　

线的航迹重规划。航迹规划的优劣直接影响着无人　

机智能飞行的性能。　

２　航迹规划常用算法　

目前国内外学者提出了许多不同的无人机航迹　

规划算法，按照规划决策一般可以分为传统经典算　

法和现代智能算法嘲，具体分类如图２所示。　

表１列出了几种传统经典算法的优缺点以及适　

用范围。　’　航迹规划算法　

传统经典算法Ｉ　ｌ现代智能算法　

表１几种传统经典算法归纳　罔　圈　圈陲　

由表１可知，传统的航迹规划算法存在着共同　

的缺点：容易陷入局部最优解、计算量大、规划时间　

长、不具备智能搜索功能等。　

目前无人机航迹规划中常用的算法主要是人工　

智能规划算法，这其中包括Ａ—Ｓｔａｒ算法、遗传算法　

人工神经网络算法、蚁群算法以及模拟退火算法等。　

而基于这些算法的改进型或者混合型将是以后人工　

智能算法的发展方向，本文主要介绍目前较为常用　

的遗传算法、人工神经网络算法以及蚁群算法。　

２．Ｉ遗传算法（ＧＡ）　

遗传算法起源于对生物系统所进行的计算机模　

拟研究，是由Ｍｉｃｈｉｇａｎ大学的Ｈｏｌｌａｎｄ教授在文献　

［４］中提出的，其基本原理是模拟基因重组与进化的　

自然过程，把待解决问题的参数编成二进制码或十　

进制码（基因），若干基因组成一个染色体，许多染色　

体进行类似于自然选择、配对交叉和变异的运算，经　

过多次重复迭代直至得到最后的优化结果［４］。　

完整的基于遗传算法的无人机航迹规划算法应　

用流程可用图３来描述。　

将遗传算法应用于无人机航迹规划主要流程可　

以分为如下几点：　

（１）编码：遗传算法在进行搜索之前首先要对　

无人机位置以及航迹可行性编码，基因的编码方式　ｌ　卜＿　Ｉ　ｉ迹可行性编码ｆ　’Ｌ苎　￡＿ｊ　

１．位串解释得到参数　２．计算目标函数　３．函数值向适应值映射　４．适应值调整　

３种基本遗传算子：　选择算子　交叉算子　变异算子　种群１　不满足条件　

牵　

婆堡Ｉ篁三Ｉ　『厂丽考　！　．　．　Ｉ　．Ｉ出最优　统计结果　种群２　ｌｊ航迹　

图３遗传算法应用流程　

有多种，经试验表明采用一种变长的实值基因编码　

方式可以取得较好的效果［５］，每一条染色体代表无　

人机的一条航迹。　（２）初始群体生成：随机产生ｘ个初始串结构　

数据，每个串结构数据代表一个个体，　个个体构　

成一个群体。初始群体表示无人机所有可能的航迹　

位置。　（３）选取适应度函数：适应度函数的选取是遗　

传算法最为关键的部分，它是进化过程的驱动力［５］。　

（４）遗传算子：群体通过选择、交叉、变异３种　

基本的遗传操作得到下一代群体，其中选择的目的　

是为了从当前群体种选出优良的个体，根据各个个　

体的适应度值，按照一定的方法从上一代群体种选　一最优控制法一　一动态规划法一　一数学规划法一

　王俊，等：无人机航迹规划常用算法　（总第３７—１４６５）　‘７・　

择出一些优良的个体遗传到下一代群体中。通过交　

叉操作可以得到新一代个体，初始阶段应选择较大　

的交叉概率保证算法的全局搜索能力，进化至一定　

程度后可以减少交叉概率以提高搜索效率。变异操　

作可以提高算法的有效性，为新个体的产生提供了　

机会，进化初始阶段应选择较小的变异概率以保护　

优良个体，进化后期可以提高变异概率以提高算法　

的局部搜索能力。　

（５）最优航迹生成：通过不断循环进化，最后生　

成具有最大适应度值的个体即为最优航迹。　

遗传算法作为一种实用、高效、并行、鲁棒性强　

的全局随机搜索方法已经越来越广泛地应用于无人　

机航迹规划中去，近些年来更是提出了许多改进的　

遗传算法，兼顾了算法的全局搜索能力和收敛速度。　

但目前遗传算法并不适用于实时航迹规划，因此遗　

传算法常与其他的智能算法一起用于航迹规划中。　

２．２人工神经网络（ＡＮＮ）算法　

人工神经网络是模拟生物神经网络进行信息处　

理的一种数学模型，由大量的处理单元（神经元）通　

过一定的拓扑结构互相连接而成［６］。神经网络具有　

高度的并行结构和并行实现能力，具有高速寻找优　

化解的能力，能够发挥计算机的高速运算能力，可以　

很快地找到最优解，神经网络在航迹规划方面得到　

了广泛的应用。神经网络　

有多种模型：感知器神经　

网络模型、线性神经网络　

模型、ＢＰ神经网络模型、　

ＲＢＦ神经网络模型、自组　

织神经网络模型以及　

Ｈｏｐｆｉｅｌｄ神经网络模型，　

其中Ｈｏｐｆｉｅｌｄ神经网络模　

型属于反馈神经网络类　圈４　Ｈｏｐｆｉｅｌｄ神经网络　结构　

型，适合处理航迹规划等非线性问题，如图４所示。　

该算法首次引入了能量函数概念，利用　

Ｈｏｐｆｉｅｌｄ模型在状态更新过程中能量函数随状态变　

化单调递减的规律，可以寻优规划出最优航迹（稳定　

平衡状态下的输出）［６］。基于Ｈｏｐｆｉｅｌｄ神经网络模　

型的无人机航迹规划的基本原理是通过构造能量函　

数，利用网络的收敛性使能量最小达到稳定状态从　

而获取最优航迹，具体可以通过以下步骤实现：　

（１）对规划空间进行离散化处理，构建与无人　

机相适应的Ｈｏｐｆｉｅｌｄ神经网络模型。　

（２）结合数字地形信息以及约束条件构造一个　

能量函数，其中连接权可以反映地形信息，若无人机　

靠近障碍物时，连接权迅速减小，这样可以实现无人　机的安全飞行。　

（３）由于所创建的Ｈｏｐｆｉｅｌｄ神经网络是并行处　

理问题，而当前计算机处理器一般是串行工作的，因　

此需要对所建立的神经网络模型进行串行模拟。　

（４）当串行模拟达到预期的要求时，在规划空　

间则会建立起单峰梯度的数值势场。　

（５）结合势场梯度数值以及无人机飞行约束条　

件在规划空间内搜索最优航迹。　

２．３蚁群算法　

蚁群算法顾名思义起源于蚂蚁搜索食物的过　

程，它通过个体之间的信息交流与相互协作来实现　

路径搜索。蚂蚁之所以能够搜索最佳路径是基于蚂　

蚁特有的分泌物——信息素［７］，通过释放信息素可　

以影响其他蚂蚁的路径，假设在初始阶段，蚂蚁选择　

不同路径的概率相同，由于路径越短，在单位时间内　

通过的蚂蚁数量也就越多，释放的信息素也就越多，　

随着信息素强度的增大，蚂蚁选择该路径的概率也　

就越高，随着时间的推移，这条路径就成为了蚂蚁从　

出发点到目的点的最佳路径。　

无人机航迹规划可以看成是在一定规划空间内　

寻找若干航迹点，使得无人机在沿着这些航迹点飞　

行的路程最短或者代价最小，这与蚁群算法原理相　

似，因此蚁群优化算法适用于航迹规划问题。蚁群优　

化算法常与Ｖｏｒｏｎｏｉ图结合起来［１　，利用Ｖｏｒｏｎｏｉ　

图可以根据已知战场威胁源分布情况下生成初始可　

选路径集，它能够有效地将地理信息、威胁源中的　点、对象和区域以集合拓扑结构表示出来［５］。　

通过以下步骤可实现基于蚁群算法的无人机航　

迹规划：　

（１）根据已知威胁源分布情况构造Ｖｏｒｏｎｏｉ　

图，给Ｖｏｒｏｎｏｉ每条边赋予一定的权值（初始信息素　

值）。　

（２）将所有人工蚂蚁置于距离起始点最近的　

Ｖｏｒｏｎｏｉ图节点位置，根据蚂蚁状态转换规则（一般　

由两点间的可见度以及两点间边的信息素值的强度　决定）选择下一节点，直至所有蚂蚁到达终点完成搜