摘要：对于问题1也就是在二维平面上规划无人机最优航迹，我们首先用VORONI粗略作出可选航线，然后对每一段路径进行代价估测，问题1考虑的因素较少主要考虑了雷达威胁度和燃油两个因素。
其中雷达威胁大小的度量主要考虑飞机距离雷达的长度，距离越近其危险值也就越大，由于飞机的燃油也是有限的，过长的航行路径会导致飞机燃油耗尽。
因此在这两个因素中，我们引入加权系数，使得这危险度和航程因素影响的比重可视具体情况调节。
得出路段代价后，再用改进的Dijkstra 算法求出3条较优参考路径。
然后对这三条路径进行对比从而找出最佳路径。
问题2是在三维空间情况下规划无人机航迹，我们对选取的二维路径进行如下优化：首先，用三次样条插值法对折线路径进行平滑处理；其次，考察无人机的操作性能（主要考虑拐弯），对曲线做进一步平滑处理；然后，考虑无人机飞行高度对其安全性及操作性的影响，一方面是在威胁度计算时加入高度因素，重新进行权值计算；另一方面是对飞机飞行高度变化进行讨论，如无人机的最大仰角和过度地带飞机至少飞行的高度。
由于数字地图的复杂型，二维处理中产生的最佳路径，在三维中并不一定是最优的，我们经过计算，发现二维平面次优的航道才是三维最优的航道路径。
在问题3仿真过程中，我们使用MATLAB 7.0进行计算和最后的飞机飞行航道图形绘制，包括三次样条曲线拟合，数字地图与预处理等，使用了VC++ 6.0编写了Dijkstra 算法计算最优路径。
关键字：Voronoi图Dijkstra算法三次样条插值最小曲率半径目录一、问题的重述 (1)二、模型的假设 (1)三、模型的符号说明 (2)四、对问题的分析 (3)五、模型的建立与求解 (3)5.1 问题1模型的建立 (3)5.1.1 引入问题 (3)5.1.2约束条件 (4)5.1.3基于VORONOI图的航路代价计算 (4)5.1.3.1 VORONOI图的基本思想 (4)5.1.3.2 VORONOI图的生成原理 (4)5.1.4 Dijkstra算法 (5)5.1.4.1 Dijkstra算法的基本思想 (5)5.1.4.2 实现Dijkstra算法的步骤 (5)5.1.4.3 对Dijkstra算法的改进 (6)5.1.5 雷达威胁代价的计算 (6)5.1.6 燃油代价的计算 (7)5.1.7 航路总代价的计算 (7)5.2 问题2模型的建立 (7)5.2.1约束条件 (7)5.2.2 航路代价的计算 (8)5.2.2折线型航线平滑化 (8)5.2.3三次样条函数定义 (8)5.2.4三次样条函数原理 (9)5.2.5无人机最大转角问题 (11)5.2.6 无人机爬坡优化 (13)5.2.6.1.地形平滑 (13)5.2.6.2曲率限制法 (14)5.2.6.3最小离地间隙限制 (15)5.3 问题的求解 (16)5.3.1问题1模型的求解 (16)5.3.1.1 雷达的分布情况 (16)5.3.2问题2模型的求解 (17)六、仿真求解 (17)6.1 问题1 模型进行仿真 (18)6.1.1 VORONOI图 (18)6.1.2 VORONOI图各边的权值计算 (18)6.1.3 利用Dijkstra 算法求最优路径 (19)6.2问题2模型的仿真 (21)6.2.1 利用三次样条插值法平滑路径 (21)6.2.2 去除曲线尖角效果 (22)6.2.3 三维空间处理效果图 (24)七、模型评价与改进 (26)7.1 优点 (26)7.2 缺点和不足 (26)八、参考文献 (27)九、附录 (28)附录一 (28)附录二 (28)附录三 (29)一、问题的重述无人机的发展至今已有70多年的历史，其军事应用主要是遂行各种侦察任务。
随着无人机平台技术和机载遥感技术的不断发展，它的军事应用范围已经并将继续扩展，如通信中继、军事测绘、电子对抗、信息攻击等。
特别是精确制导武器技术的发展，又使它成为这种武器的理想平台。
众所周知自主飞行的能力是无人驾驶飞机所必须具有的。
如果要实现无人驾驶飞机的自主飞行，则要求具有相当程度的飞行航迹规划能力。
无人机的航迹规划是为了圆满完成任务而作的计划。
它往往指单机在初始位置、终止位置和一些目标任务结点确定之后的航迹规划问题，其基本功能是根据无人机的性能和飞经的地理环境、威胁环境等因素，对已知的目标规划提出满足要求的航迹，以便在实际飞行时可以根据需要进行实时局部修改。
现在我们讨论如下的情况：假定无人机的活动范围为20km×20km的区域，无人机起点的平面坐标为[1，2](单位：km)，攻击目标的平面坐标为[19，18](单位：km)，同时不考虑无人机起飞降落时的限制。
数字地图和敌方威胁情况(主要考虑雷达威胁)已在附件中给出。
数字地图可以做适当的简化，比如可以把地形近似分为三种：高地，低地以及过渡地带。
问题1：忽略地形和无人机操作性能等因素的影响，综合考虑敌方威胁，无人机航程等，基于二维平面建立单机单目标的航迹规划模型。
问题2：把模型扩展到三维空间，并同时考虑无人机的操作性能（主要考虑拐弯）和地形因素。
问题3：试讨论和分析你提出的模型的可行性，并做仿真分析。
附件一：雷达威胁的坐标方位表。
附件二：数字地图。
附件一：表1、雷达威胁的平面坐标方位表起始点坐标[1，2] 目标点坐标[19，18]威胁点1坐标[7，20] 威胁点5坐标[13，4]威胁点2坐标[11，14] 威胁点6坐标[15，18]威胁点3坐标[9，6] 威胁点7坐标[14，17]威胁点4坐标[18，2] 威胁点8坐标[20，14]二、模型的假设（1）飞行过程中不会出现故障，可以按规划的航迹飞行；（2）由于天气方面偶然性太大，为方便建模不予考虑；（3）敌方雷达每个都是相同的，对无人机的威胁程度是相同的；（4）目标位置是固定的，不需要考虑目标的移动和变动；（5）指挥官可以按照规划进行正确的决策，防止因为决策的失误而使无人机无法完成攻击目标的任务；（6）无人机在飞行的过程中得航速保持不变。
三、模型的符号说明四、对问题的分析要研究的问题是对无人机单击单目标航迹的规划，我们通过实际分析建立了合适的数学模型来规划出无人机的航迹。
在问题1中我们忽略地形因素的影响，因此这相当于我们在一个平面中考虑无人机的航迹，即建立一个基于二维平面建立单机单目标的航迹规划模型求解即可，题中也不用考虑无人机操作性能只考虑了敌方威胁，以及无人机的燃油问题也就是无人机所能飞行的最长距离等，通过图1及建立的VORONOI图（如图3）我们可以看出雷达的威胁分布的情况，我们结合Dijkstra法快速寻找了最优路径。
问题2在问题1得基础上进一步延伸，将二维平面扩展到了三维立体空间，同时需要考虑的飞行机的航迹约束条件增多了，加大了对无人机航迹规划的难度。
所以首先我们应当利用计算机软件将整个三维的地形图绘制出来，因VORONOI图单独使用不适合三维航迹的规划，又从问题中我们可以看出无人机的起始点和目标点没有改变，我们通过对雷达威胁区域先用VORONOI图表示出来，采用Dijkstra算法搜索威胁分布图，求解粗略最短路径。
在粗略最短路径的基础上，应用三次样条曲线和序列二次规划的方法求解最优路径。
五、模型的建立与求解5.1 问题1模型的建立5.1.1 引入问题在二维平面建立单机单目标的航迹规划模型，即在二维平面内找到无人机从起始位置到目标点的的最优路径。
所谓最优即无人机的损耗最小。
故需要处理如下问题：1.如何很好的避开雷达？怎么计算出雷达的威胁代价？2.如何规划出无人机的最优航迹？3.计算航程时的总代价？5.1.2约束条件1. 无人机到达终点目标的安全性能和燃油性能。
2. 无人机的航路代价主要包含其所受的威胁代价和燃油代价。
其中威胁代价中主要考虑的是雷达威胁，即不会出现敌方雷达未发现无人机而受到攻击。
5.1.3基于VORONOI 图的航路代价计算5.1.3.1 VORONOI 图的基本思想先将已知的敌方雷达威胁中心位置作为VORONOI 图的点，以威胁大小作VORONOI 图邻近区域的“距离”量度，构建出VORONOI 图，“距离”越大则所受威胁越小VORONOI 图的各条边在相应点的领域内距威胁“距离”最大，因而所受威胁相应最小，所以VORONOI 图中的弧即构成飞行器安全性最高的可飞航线，线段与线段交点即构成可飞的航迹节点，从而可以根据威胁源的强度大小和弧的长短给出各条弧的相应权值，最后利用遗传算法，从VORONOI 图中搜索出最优飞行航迹。
当无人机沿着VORONOI 图的每一条边飞行时，都将具有一定的代价，在本题中无人机的航迹规划是根据任务目标规划满足约束条件的飞行轨迹。
5.1.3.2 VORONOI 图的生成原理由图中可知给定两个点i p 和j p ，比j p 更接近i p 的点的集合恰好是由直线i j p p 的垂直平分线确定的包含i p 的半平面，同理点集中其他的点与i p 组成的线段的垂直平分线所确定的包含i p 的半平面，比其他点更接近于i p 的点的轨迹是一个凸多边形区域。
VORONOI 图中各个边到对应母点距离相等，因而我们可以将战场区域中的威胁中心作为生成VORONOI 图的母点，VORONOI 图的边就是能够最好规避对应的两个威胁的线段，所以选择构造战场的VORONOI 图可以有效地把路径搜索的空间降低到仅仅在图的边中进行搜索，极大地提高路径优化的效率。
5.1.4 Dijkstra 算法Dijkstra 算法是图论中求解最短路径的一种算法，其主要思路是用逐点增长的方法构造一棵路径树，从而得到从树根(指定点)到其他点的距离，该算法的优点是计算速度快，有利于工程实现口。
应用Dijkstra 算法进行航迹规划，就是将作战飞机的航迹规划问题转化成有向图中求解最短路径的问题，然后根据输入的敌情信息和航路数据，确定各级航路点及其代价，然后进行最优搜索，形成最优路径航路点序列，最终生成整体最优航迹。
5.1.4.1 Dijkstra 算法的基本思想在形成的赋权图中，可以将航线的代价函数值看作顶点间的距离，从而将代价函数最小的问题转化为顶点间最短路径的问题。
根据图论的知识，赋权图中的每一条边都相应的有一个代价函数值，即该边的权。
所谓最短路径问题就是在始点到顶点的路径集合中，寻找权为最小的路径，得到的路径称为始点到顶点的最短路径。
目前公认的最好的算法是由狄克斯特拉于1959年提出的。
它不仅可求出从始点到顶点的最短路径，最后所得到的实际上是从始点到各个顶点的最短路径。
先给赋权图G 的每个顶点标记一个数(称为标号)——临时标号(简称T 标号)或者固定标号(简称P 标号)。
T 标号表示从始点到这一点的最短路径长度的上界；P 标号则是从始点到这一点的最短路径长度。