2007高教社杯全国大学生数学建模竞赛承诺书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。

我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。

我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。

如有违反竞赛规则的行为，我们将受到严肃处理。

我们参赛选择的题号是（从A/B/C/D中选择一项填写）： A 我们的参赛报名号为（如果赛区设置报名号的话）： 20004005 所属学校（请填写完整的全名）：中南大学参赛队员 (打印并签名) ：1. 张腾2. 王雄3. 王泽指导教师或指导教师组负责人 (打印并签名)：日期： 2008 年 8 月 11 日赛区评阅编号（由赛区组委会评阅前进行编号）：无人机自主飞行航迹规划摘要本文对无人机自主飞行航迹的二维规划和三维规划问题根据所给要求分别建立了动态规划模型，并对模型进行了可行性分析和仿真分析，最终求得最优的规划路线（见附录表1，表2）。

首先，对于问题1，无人机自主飞行航迹的平面规划问题，我们采用传统的图论方法，使用Voronoi图【1】对雷达威胁网络进行划分；并以雷达威胁度和路程代价为主要考虑因素对Voronoi图的每条边赋予权值，得到一个权矩阵，通过Dijsktra算法求得出发点到目标点的最优路径。

但是我们考虑到这种算法实现较难，而且Voronoi图不可推广到三维航迹的规划问题上，因此我们通过假设条件消除其后效性，建立了动态规划模型，并且为了增加模型精确度，将地图以100米为单位网格化。

其次，对于问题2，将问题推广到三维空间，增加了地形因素以及飞机飞行的性能，即考虑到飞机飞行时转弯和地形影响的因素。

我们使用matlab对该三维空间进行了模拟【2】，并由平面的动态规划模型通过对每点增加高程z，对飞机的转弯性能最小转弯角进行简化，增加地形约束条件，建立了以无人机飞行路线广义代价为目标函数的动态规划模型。

再次，我们对所建立的动态规划模型做了可行性分析和仿真分析，通过对比在广义代价方程中各个因素的权重系数的不同取值，得出不同的规划路线，最终得出最优的规划路线，并肯定了模型的正确性。

最后，我们对于此动态规划模型进行综合评价，并提出了此模型在实际条件中应用所欠考虑的部分，并在模型的推广中对其他实际因素进行了具体的分析并加以改进和完善。

关键字Voronoi图动态规划模型广义代价代价方程仿真分析一、问题的重述1.1 问题背景无人机的发展至今已有70多年的历史，其军事应用主要是遂行各种侦察任务。

随着无人机平台技术和机载遥感技术的不断发展，它的军事应用范围已经并将继续扩展，如通信中继、军事测绘、电子对抗、信息攻击等。

特别是精确制导武器技术的发展，又使它成为这种武器的理想平台。

众所周知自主飞行的能力是无人驾驶飞机所必须具有的。

如果要实现无人驾驶飞机的自主飞行,则要求具有相当程度的飞行航迹规划能力。

无人机的航迹规划是为了圆满完成任务而作的计划。

它往往指单机在初始位置、终止位置和一些目标任务结点确定之后的航迹规划问题,其基本功能是根据无人机的性能和飞经的地理环境、威胁环境等因素,对已知的目标规划提出满足要求的航迹,以便在实际飞行时可以根据需要进行实时局部修改。

现在我们讨论如下的情况：假定无人机的活动范围为20km×20km的区域，无人机起点的平面坐标为[1,2](单位：km), 攻击目标的平面坐标为[19,18](单位：km)，同时不考虑无人机起飞降落时的限制。

数字地图和敌方威胁情况(主要考虑雷达威胁)已在附件中给出。

数字地图可以做适当的简化，比如可以把地形近似分为三种：高地，低地以及过渡地带。

1.2 基本信息附件一：雷达威胁的坐标方位表。

附件二：数字地图。

1.3 问题的提出问题1：忽略地形和无人机操作性能等因素的影响，综合考虑敌方威胁，无人机航程等，基于二维平面建立单机单目标的航迹规划模型。

问题2：把模型扩展到三维空间，并同时考虑无人机的操作性能（主要考虑拐弯）和地形因素。

问题3：试讨论和分析你提出的模型的可行性，并做仿真分析。

二、问题的分析2.1 背景资料航迹规划是指在考虑环境、任务和飞机性能等一系列约束条件得前提下，为飞机规划出一条从起点到终点的可飞路径。

无人机航迹规划约束条件复杂、规划空间广、任务多样、不确定因素繁多，尤其难于确定多人机协同执行任务的协同规划解。

目前在无人机航迹规划上已有的方法基本有如下几种：1.以分层航迹规划的思想为基础建立的根据任务飞行环境由Voronoi图生成初始航路，根据考虑的各个约束条件，赋予各航路相应的权值，最终从路径空间中搜索出最优的航迹；2.基于蚁群算法的无人机航路规划方法；3.基于基因算法的航路规划方法。

2.2 问题分析在实际的无人机航路规划问题上其不确定性因素繁多，约束条件复杂，我们这里突出题目的主要因素，即无人机执行任务时躲避雷达探测威胁和燃油代价，忽略无人机操作的性能，无人机起飞和降落的限制等次要因素考虑航路的规划。

首先我们根据所给雷达威胁的坐标方位表做出Voronoi图，采用传统的图论算法的思路建立了模型，但是我们在求解模型的算法实现上，考虑到其在算法复杂度相当高，以及其只适用于简单的二维图的航路规划问题，无法拓展到三维的实际模型中应用。

因此我们根据我们的需要，建立了动态规划模型对问题进行求解。

三、问题的假设1）不考虑无人机起飞降落时的限制 2）不考虑风、雨等对飞机性能的影响；3）飞机的性能于飞机的飞行距离无关，即飞机在执行任务中性能不变； 4）飞机燃油量和飞行距离成正比；5）雷达信号强度与其距离的四次方成反比；6）飞机燃料无限，在避开威胁的情况下能到达目的地； 7）不考虑无人机起飞降落时的限制四、符号说明i a ：表示各垂直平分线的交点； ija ：表示无人机行驶路径； V :表示ija 上的点 ix a ：i a 横坐标；iya ：ia 纵坐标；aiw ：表示ia 点被雷达探测到的危险度； kb ：表示雷达点； (),kkx kyb b b ；i ka b ：表示点i a 与点kb 的距离； ()ijL a ：水平路径长度；α：飞行距离权重系数；1α-：被雷达探测到的危险代价权重系数；ijD:由i 点到j 点的广义代价；β：雷达探测强度系数五、模型的建立与求解5.1问题1忽略地形和无人机操作性能等因素的影响，综合考虑敌方威胁，无人机航程等，基于二维平面建立单机单目标的航迹规划模型。

5.1.1模型1根据题目中所给出的雷达威胁点坐标方位表，我们做出Voronoi 图，建立了以形式路线的广义代价为目标函数的模型。

无人机飞行路线的燃油代价正比于飞行距离即可以简单的假设飞行边ij a距离代价()ijLa 为：()ijLa =这里我们简单的假设雷达探测强和其距离的4次方成反比，则： 无人机经过路线ij a 的雷达威胁代价为：()()()()421122ijijmmij k k LLa a kx kx y by w V b V b V b ββ====∑∑⎰⎰⎡⎤-+-⎢⎥⎣⎦m:雷达数；则行驶每条边ij a 的广义代价为：()()1ijijaiLa wDαα=+-•将每条边ij a 的广义代价ij D 赋予ij a 上得到，以行驶广义代价为权的权矩阵，引出0-1变量ij xij ij 01ij a x a ⎧⎪=⎨⎪⎩表示路线未被选中表示路线被选中无人机航行路线的总广义代价：1min nijij i D x D ==*∑5.1.2模型2将地图以100米为单位模拟成网格图，此时i a 表示网格中的节点。

出发点sa到目标点ta 做目标向量(),,,,,,s tt xs xt ys ym a a a a =--ka表示选中路线中的点；其周围相邻点q a ；1,1,1,,1,1,,1q k k k n k n k n k n k n k n =-+----++-+++；这里要求飞机是朝目标点飞行，即朝前行驶则有飞行路线向量与目标向量乘积为正：(),,0q k s t T q m m =•>，保证飞机飞行路线的无后效性。

飞行边ij a 距离代价()ijLa 为：()ij La =无人机经过规划路线的雷达威胁度代价为：()()42111122nmn mai i k i k i kix kx iy by w a b a b a b ββ======∑∑∑∑⎡⎤-+-⎢⎥⎣⎦n ：所规划路线的节点数；m:雷达数；则目标函数无人机航行路线的总广义代价：()(),1min 1nijaii j D La wαα==+-•∑；(),,0q k s t st T q m m =•>5.1问题2把模型扩展到三维空间，并同时考虑无人机的操作性能（主要考虑拐弯）和地形因素。

5.2.2模型的建立1.模型的假设：1）不考虑风、雨、云等自然条件对无人机的影响； 2）无人机的燃料充足即可以完成任务并返回出发点；3）无人机的性能在执行任务过程中是不变的，即不考虑疲劳等因素； 4）无人机在到达目标点上空即可执行任务，即不必降落至地面；由于模型扩展到三维空间，给出了数字地图，需要考虑到地形因素，因此建立空间坐标系，地图上每一点增加高程坐标z ；对数字地图用matlab 进行模拟如下图1：图1 地形模拟图2.无人机水平最大转角为θ，竖直最大转角为ϕ；3.无人机飞行高度限制为0z h ≤≤； 出发点s a 到目标点t a 做目标向量(),,,,,,,,,s t t xs xt ys yt zs zm a a a a a a =---；ka 为路线选中点； qa为ka相邻点（共26个）；这里要求飞机是朝目标点飞行，即朝前行驶则有飞行路线向量与目标向量乘积为正：(),,0q k s t T q m m =•>飞行边ij a 距离代价()ijLa 为：()()()()222qkLqx kx qy ky qz kz a a a a a a a =++---则所规划路线相邻两条线q s k →→的广义代价可表示为：()(),,123s ks q qkkkzqzLa w a a DD r r r =+++-}{,mins qD(),123,,,,0,0,1tan tan 0s s q y k y q x k x T Q st z hD r r r a a a a ϕθ⎧>⎪=⎪⎪+=⎪<⎪-⎪<⎪⎪⎪≤≤⎩+-5.3问题3试讨论和分析你提出的模型的可行性，并做仿真分析。