1、题 目 无人机自主飞行航迹规划问题摘要本文分别研究了基于二维平面和三维空间的最优航迹规划问题。对于第一问，我们在忽略地形和无人机操作性能等因素影响的基础上，将影响无人机飞行的“敌方雷达威胁”和“飞行燃油代价”两个因素进行了量化处理，建立了雷达威胁模型和燃油代价模型，并在这两个模型的基础上建立了基于二维平面的最优航迹规划模型。在求解该模型时，我们依据图论中的相关理论，将二维平面划分成了若干网格，然后使用 Dijkstra 算法来求最优航迹。对于第二问，我们在第一问的模型的基础上，同时考虑了地形因素和无人机的操作性能（主要是拐弯） ，增加了“无人机飞行高度代价”和“无人机操作性能”两个指标，并对其
2、进行了量化处理。同时，我们对雷达威胁模型进行了适当的简化，建立了一个较复杂的、基于三维空间的最优航迹规划模型。在求解该模型时，我们将三维空间划分为若干个小方块，在“无人机操作性能”作为补充约束条件的基础上，采用蚁群算法，得到了最优航迹。在建立以上两个模型的基础上，我们对每个模型的可行性分别进行了分析。由于规划的约束条件众多而且模糊性大、研究的各因素之间的相互联系及不同种类无人机的控制方式和任务情况各异，因而模型存在着一定的缺陷。我们用 MATLAB 对建立的两个模型进行了仿真，分别得到了基于二维平面的最优航迹和基于三维空间最优航迹。此外，我们分析了所建模型的优缺点，并对模型的完善进行了进一步的
3、探索。关键词：最优航迹 Dijkstra 算法 蚁群算法 MATLAB 仿真1目 录1. 问题的重述-22. 问题的分析-23. 模型假设-34. 符号说明-35. 模型的建立-35.1 问题一模型的分析、建立与求解-35.2 问题二模型的分析、建立与求解-66. 模型的可行性分析与仿真-96.1 模型的可行性分析-96.2 模型的仿真-107. 模型的评价、改进及推广-128. 参考文献-149. 附录-152一、问题的重述无人机的发展至今已有 70 多年的历史，其军事应用主要是执行各种侦察任务。随着无人机平台技术和机载遥感技术的不断发展，它的军事应用范围已经得到大大的扩展，并且这种扩展还将
4、持续下去，如通信中继、军事测绘、电子对抗、信息攻击等。特别是精确制导武器技术的发展，又使它成为搭载这种武器的理想平台。众所周知， “自主飞行”的能力是无人驾驶飞机所必须具有的。如果要实现无人驾驶飞机的自主飞行,那么就要求无人驾驶飞机具有相当程度的飞行航迹规划能力。无人机的航迹规划是指其为了圆满完成任务而作的计划。它往往指单机在初始位置、终止位置和一些目标任务结点确定之后的航迹规划问题,其基本功能是根据无人机的性能和飞经的地理环境、威胁环境等因素,对已知的目标规划提出满足要求的航迹,以便在实际飞行时可以根据需要进行实时的局部修改。现在要讨论如下的情况：假定无人机的活动范围为 20km20km 的
5、区域，无人机起点的平面坐标为1,2(单位：km), 攻击目标的平面坐标为19,18(单位：km)，同时不考虑无人机起飞和降落时的限制。数字地图和敌方威胁情况(主要考虑雷达威胁)可以从附件中查得。数字地图可以做适当的简化，比如可以把地形近似分为三种：高地，低地以及过渡地带。具体问题如下：问题 1：忽略地形和无人机操作性能等因素的影响，综合考虑敌方威胁情况、无人机航程等因素，基于二维平面建立单机单目标的航迹规划模型。问题 2：把模型扩展到三维空间，并同时考虑无人机的操作性能（主要考虑拐弯）和地形因素。问题 3：试讨论和分析上述模型的可行性，并做仿真分析。二、问题的分析对于问题一，经过分析后我们认为
6、平面是一个连续的集合，为了便于研究，我们将无人机能够活动的平面划分成有限个正方形的网格，这样就可以把无限的、连续的研究对象转化为有限的、离散的，便于计算和研究。另外，这样划分也可以保证计算结果的精度。另外，要考虑敌方的威胁（这里主要指雷达威胁） ，那么就要将雷达的“威胁程度”进行量化。在进行了量化之后，就可以考虑构建威胁模型。在上述准备工作完成之后，就要根据量化的数据进行最优航迹的求解。因为我们在本问中所建立的模型求解的是最优航迹，所以可以使用 Dijkstra 算法进行求解。问题二要求把模型扩展到三维空间，并同时考虑无人机的操作性能（主要考虑拐弯）和地形因素。经过分析我们认为，问题二是在问题
7、一的基础上,把问题拓展到三维空间里,综合考虑雷达威胁因素、地形因素和飞机本身的因素,建立一个可以确定飞机最优航迹的综合模型。因此，无人机的航迹规划问题可转化为一个带约束的优化问题。如果对规划空间进行三维网格划分，可得到若干节点,从而构成一个网格图，则优化问题的搜索空间就转化为一个离散的空间节点集,而问题的求解也可简单归结为一个求解网络图最短路径的组合优化问题,使得无人机在沿着这些节点所形成的路径上飞行时具有最小代价。对此我们采用一种基于改进蚁群算法的无人机三维航迹规划方法, 将最短路径的信息反馈到系统中作为搜索的指导信号,并改进节点选择方法,以提高应用蚁群算3法搜索无人机三维航路的效率，以保证
8、在敌方防御区域内以最小的被发现概率以及可接受的航程到达目标。对于第三问，我们可以在对相关参数进行适当赋值后，在 MATLAB 中进行仿真模拟。三、模型假设（1）假设附件中所提供雷达威胁的坐标方位表和数字地图真实有效，并在短期内不会改变。（2）假设无人机的活动范围为题目中所述的 20km20km 的区域。（3）假设所有雷达全天 24 小时都开机。（4）假设每个雷达的作用方式完全一致，且无人机具有相同的雷达反射截面。（5）假设每个雷达之间不存在信息交流，即当一个雷达发现目标时，不会通知其他雷达。（6）假设无人机在执行任务的过程中不会出现故障。（7）不考虑地形的变化对气流造成的影响。四、符号说明：雷
9、达对无人机的杀伤概率()pm：突防高度下绝对杀伤区半径inR:突防高度下非绝对杀伤区半径max：雷达对无人机的威胁代价threJ：无人机飞行时的的燃油代价ful：无人机飞行时的的高度代价higJ文中出现的其它符号在用到时另行说明。五、模型的建立5.1 问题一模型的分析、建立与求解5.1.1 问题一模型的分析首先，针对本问中的模型，我们做出如下假设：（1）忽略地形和无人机操作性能等因素的影响，而且认为无人机可以任意角度转弯。（2）不考虑气候的变化对飞行造成的影响。（3）飞行所消耗的燃油量和飞行距离成正比。4（4）不考虑无人机起飞和降落时的限制。问题一要求我们在忽略地形和无人机操作性能等因素影响的
10、条件下，综合考虑敌方威胁，无人机航程等，基于二维平面建立单机单目标的航迹规划模型。考虑到平面是一个连续的集合，为了便于计算，我们将无人机能够活动的平面划分成有限个正方形的网格，这样就可以较好地把无限的、连续的研究对象转化为有限的、离散的，便于计算和研究。另外，这样划分也可以保证计算结果的精度。经过分析我们认为，要考虑敌方的威胁（这里主要指雷达威胁） ，那么首先就要将雷达的“威胁程度”进行量化。在进行了量化之后，就可以考虑构建威胁模型。在上述准备工作完成之后，就要根据量化的数据进行最优航迹的求解。因为我们在本问中所建立的模型求解的是最优航迹，所以可以使用 Dijkstra 算法进行求解。5.1.
11、2 问题一模型的建立无人机二维航行的代价应包含其所受的威胁代价和燃油代价。我们假定每个雷达的作用方式完全一致，无人机具有相同的雷达反射截面，因此无人机反射雷达回波的强度就与其到雷达的距离的四次方成反比(1/d 4)，通常认为,在地对空威胁作用范围内,飞机离其越近,所受到的威胁就越大。以圆盘的方式建模,内侧称为绝对杀伤区,外侧称为非绝对杀伤区。杀伤概率定义为（1-1）maxini1,(), 0Rrpe优优 优绝 对 杀 伤 区绝 对 杀 伤 区区 其中 p(m)表示无人机处于点 m 时的被击毁概率， 表征突防高度下绝对杀伤区minR半径,依据情报给定; 表征突防高度下非绝对杀伤区半径,可作为威胁
12、范围估计补偿inR加入;r 表征当前位置到威胁点距离值。对于威胁重叠部分,不同的威胁体对于无人机的杀伤概率计为 , i=1,2,3,4,p(m)综合评价杀伤概率则由以下公式求取i()p12n12n12nax,(),(), ()() , 1,pmmmpp 优 威胁模型示意图如下：5为了便于研究，我们将地形图划分为若干等大的方块，我们在求最优航线时，飞机沿着方块的边线和对角线飞行，可以到达与之相邻的任何一个点。那么无人机沿每条边或对角线飞行的雷达威胁代价是飞过该边的积分： （1-3）401()tthreaJdtpm其中，r(t)表示无人机到雷达的距离，p(m)表示雷达的毁伤概率。为了简化计算，我们
13、将每条边均匀地分为 6 等分，取其中的三个点来代替整条边的代价，这三个点分别是 ， ， ，L i是第 i 边的长度，这样第 i 条边的雷达威胁代价为：/6iL/2i5/i（1-4）1/6, 1/2, 5/6,4441/, /, /,()()()Nij ij ijthreaijij ij ijPddPdJ其中 N 为威胁雷达的个数。 是第 i 条边上的 1/2 处到第 j 个雷达的距离。/2,ij另一方面，在假定无人机以恒定的速度在同一高度水平飞行的情况下，无人机的燃料消耗和航迹的几何长度成正比，比例常数为 c,可表示为（1-5）,fueliiJcL综合考虑上面两方面的代价，无人机第 i 条边的
14、总代价为：（1-6）, ,(1)ithreaifuelikkJ其中，k为安全性能与燃油性能的系数，可根据任务需求调整k 的大小，k 越接近1 表示越重视燃油消耗情况，越接近0 表示越重视危险性代价。（1-7）i1minMPathJ其中M为边的条数。5.1.3 问题一模型的求解我们采用Dijkstra算法对上述模型进行求解。Dijkstra 算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。基本思路是从出发点 VS出发，逐步地向外寻找最短航迹。执行过程中，给6每个顶点予以标号，它或者表示从 Vs 到该点的最短航迹的权，称为 P 标号（或永久性标号，即某点 Vj 一旦得到 P
15、 标号，其标号值在整个计算过程中不改变） ；或者表示从Vs 到该点的最短航迹的权的上界，称为 T 标号（也称临时性标号或试探性标号，即某点 Vj 得到 T 标号，其标号值是可以改变的） 。方法的每一步是修改 T 标号，并且把某一个具有 T 标号的点改为具有 P 标号的点，最多经过 n-1 步（n 为顶点数）就可以求出从 Vs 到各点的最短航迹。算法流程图如下：其具体步骤如下：设 为一个非负权网络， ，开始给起始点 ，标上P标(,)DVA12v,nV 1v号， （即 ） ，其余各点标上T标号， 。 S为已得P标号的1)0Pv1(0dv优 ()jTv的集合，即 ， 。S23,n第一步：设 是刚刚取
16、得P标号的点，考虑所有与 相邻的点 （指以 为始点的i ijiv弧的中点 ） ，即 ，且 的标号为T标号（具有P标号的 不考虑） ，则修改jv(,)ijvAjv j的T标号，使得： ，对于所有与 不相邻的点 ；j ijmi(),jjiTivj。()第二步：若D中没有T标号的点，则算法停止，即已求出始点到达各点的最短距离。否则： 。若有多个 最小，则任取一个，然后把点 的T标号修0in()j jvv()jTv 0jv改为P标号，转入第一步。本算法的MATLAB程序见附录1。5.2 问题二模型的分析、建立与求解75.2.1 问题二模型的分析首先，针对本问中的模型，我们做出如下假设：（1）假设飞机拐
17、弯的最大角度为 90。（2）飞机的燃料能够使得飞机到达目的地。（3）雷达对飞机的探测范围有限。（4）假设无人机能够飞过各种地形。（5）无人机的航迹规划系统要求得到的航迹能够有效避开敌方雷达的探测和敌方威胁的攻击。经过分析后我们认为，根据无人机三维航迹规划的具体特征,采用蚁群算法对无人机进行三维航迹规划，可以得到较好的结果。但是注意到在传统的蚁群算法中，在对节点的选择上存在一些尚不完善的因素。因此，综上所述我们建模的整体思想是将最短航迹的信息反馈到蚁群系统中,并且对节点的选择方法进行改进,以便在较短的时间内规划出无人机的三维航迹。5.2.2 问题二模型的建立影响无人机航迹规划的因素众多，因此无人
18、机的航迹规划问题就转化为一个带约束的优化问题。我们对规划空间进行三维网格划分，可以得到若干节点,从而构成一个网格图。那么该优化问题的搜索空间就转化为一个离散的空间节点集,因此问题的求解也就归结为“求解网络图最短路径”的组合优化问题，使得无人机在沿着由这些节点所形成的路径上飞行时具有最小代价。由于要同时考虑无人机的操作性能（主要考虑拐弯）和地形因素，我们需要在模型一建立的燃油代价和雷达威胁代价的基础上引入高度代价和无人机操作性能两个限制因素，这本模型中，燃油代价主要由飞行距离和飞行速度决定的，如果无人机在飞行中保持速度恒定,则燃油代价 与航路的路程 L 成正比，表示为：fuelJ（2-1）,1f
19、liic高度代价可以表示为：（2-2）,2higJ其中 为比例系数。为了降低模型的复杂度，我们对雷达威胁代价的表达式做适2c当的简化，不妨认为雷达威胁代价的大小与无人机与雷达的距离的四次方成反比，于是雷达威胁代价可以表示为：（2-3）431/NthreaiJcr其中 为比例系数，N为威胁点的个数。3c基于以上指标，我们对各个威胁富于一定的权重后，可以建立如下最优模型，其中 为雷达威胁代价的权重， 为燃油代价的权重，其值可根据1(0,)k2(0,)k不同的任务要求进行调整，于是：（2-4）1212min()threafuelWJk8无人机在飞行时受到许多约束条件的限制,主要有如下约束条件：（1）
20、 最小步长 :它限制了无人机在改变姿态时必须直飞的距离,对每一点必须满minS足下式（2-5）minrS（2） 最大飞行高度 和最小飞行高度 :飞得较高容易被雷达发现 ,但又要避开maxHiH山峰等地理威胁。因此,每一点(x,y,z)必须满足下式（2-6）minmaxz（3）最远航程Lmax:需要在无人机油耗完之前安全返回,限定了L的最大取值。因此,性能指标中L必须满足下式（2-7）axL（3） 最大偏航角 和最大爬升角 :它限制了无人机在水平方向和垂直方向偏转maxm的最大角度。设无人机沿着x坐标轴的正方向飞行,当前所在节点的坐标为(x1,y1,z1),下一节点的坐标为(x2,y2,z2),
21、则两个节点的坐标必须满足下式（2-8）21maxa21arctntyxz因此,整个航路规划的模型就可以表示为在满足式(2-5) :式(2-8)的条件下,求使式(2-4)最小的一系列节点的集合。5.2.3 问题二模型的求解对于本模型，我们采用蚁群算法来求解模型。设M是蚁群中蚂蚁的数量,起点为点(1,2,0.3),以目标点与起点的连线为对角线建立一个立方体,此时保证满足式(2-7),否则此次任务不可执行。然后根据地图信息和最高飞行高度将范围适当地进行扩展以满足需要。设X轴方向的长度为Length,Y轴方向的长度为 Width,Z轴方向的最高飞行高度为Hight,然后在X、Y和Z轴上分别以dx、dy
22、和dz为等分间隔 , 将整个空间划分成 ：(Length/dx)(Width/dy)(Hight/dz)个相等的小立方块,各立方块的顶点就是搜索的节点。以 表示任意节点a和其相邻节bd点b之间的直线距离,以(1iLength/dx,1jWidth/dy,1kHight/dz)i,jk表示各节点上的信息浓度。蚂蚁 在运动过程中,根据各节点上的信息素l1,2M)的浓度及与相邻节点间的距离决定转移方向, 以 表示在t时刻蚂蚁l从可行节点a(tbp转移到b的概率,其计算公式为9(2-9)(),)0,ta tbat aabSbSpothers 在上式中， 为节点b上的信息素浓度,反映了蚁群在路径选择时的
23、先验经验,其a值越大则表示前面的蚂蚁经过此点的次数越多,于是该节点被选择中的概率越大; 为ab节点a和节点b之间的能见度，计算式为（2-9）1abd和为信息素浓度 与能见度 的相对重要性的权值; 为节点a的所有相邻ab tS节点的集合。在刚开始第一只蚂蚁位于原点,在地图上满足式(2-5) 式(2-8)的相邻节点中,根:据它们的初始化的信息素的值和能见度,按照式(2-9)选择下一节点,然后再以被选中的节点为出发点再按照同样的规则选择下一节点,直到到达终点。当第一只到达终点后,按照式(2-4)来计算这条路径的性能指标,然后再按照下面介绍的调整规则对各节点的信息素浓度值进行调整,同时为了防止陷入局部
24、最优,模拟自然界的真实情况,假设留在各条路径上的信息素随时间挥发,用参数(01)表示信息素的挥发程度,经过m时刻,蚂蚁到达目标点,各路径上的信息素的浓度可根据如下公式进行调整（2-10）()(1()abababtmt式中， ，表示所有蚂蚁在本次循环中留在节点b上的信息素的浓度之和，1Mlab其中/(), 0blabQJ优优蚂 蚁 当蚂 蚁 当/(), ab优当当式中， 为本次循环的性能指标值,为式(2-4)的形式， 、 为性能指标对于()Jb Q信息素的更新的比例系数。当地图上各节点的信息素调整好后,第二只蚂蚁再出发,按照同样的规则进行路径搜索直到所有的蚂蚁到达终点。当地图上各节点的信息素调整好后,第二只蚂蚁再出发,按照同样的规则进行路径搜索直到所有的蚂蚁到达终点。基于以上的描述，采用蚁群算法对无人机在三维空间进行航路规划的步骤如下:（1）初始化信息素浓度矩阵,将危险区域和受地形限制区域中的节点置0,以示惩罚,而其他节点置1。（2）将M只蚂蚁置于出发点。（3）每只蚂蚁根据转换规则式(2-9)在满足式(2-5) 式(11)的相邻节点中寻找下:一节点,并保存起来,直到到达终点。蚁群算法的MATLAB代码参见附录二。
