中国无人机遥感应用网

无人机自主飞行航迹规划

来源：本站发布日期：2015-04-27

无人机自主飞行航迹规划问题

摘要

本文是关于无人自主飞机航迹规划的问题.

对于问题一：忽略地形和无人机操作性能等因素的影响，综合考虑敌方威胁，无人机航程等，基于二维平面建立单机单目标的航迹规划模型.首先通过Voronoi画出二维雷达威胁网络图，其次根据雷达的威胁程度与飞机经过的点与雷达间距离的关系，得到雷达的威胁程度模型，然后建立无人机沿Voronoi图每条边的雷达威胁代价关系式，利用MATLAB计算出相应的结果并对其数据进行归一化处理，最后综合雷达的威胁和飞机飞行的距离两个主要因素，建立选择飞机航迹的最终模型.在求解最优航线时，本文利用Dijkstra算法计算最短路径，得到最优航线为：从起点依次经过边19，13，14最终到达终点.

对于问题二：要求把模型扩展到三维空间，并同时考虑无人机的操作性能（主要考虑拐弯）和地形因素.首先利用MATLAB编程画出地形和雷达分布的三维图形，在飞机到达目的地的全过程中，本文考虑途中各个阻碍飞机飞行的因素和飞机自身的因素，其中包括飞机飞过的路程，飞机转弯的半径，飞机飞行的高度，飞机与雷达威胁中心的距离等主要因素，并按照相应的关系建立对应的函数表达式和规划模型.最后利用A*算法求出最优航迹.

对于问题三：要求我们讨论和分析提出的模型的可行性，并做仿真分析.

可行性分析：由于规划约束条件众多而且模糊性大，研究的各因素之间存在联系及其自身的控制和任务方式，使得航迹规划方法的研究更加复杂.所以在问题1的解决过程中，模型在一定程度上存在缺陷.但是通过这样的简化，利用Voronoi图，通过Dijsktra算法方便地解决这个问题，粗略的得到需要的结果，从这个角度来看，本文建立的模型是正确可行的.在问题2的解决过程中，在第一问的基础上拓展到三维空间，首先利用忽略地形和无人机操作性能等因素的影响，综合考虑敌方威胁，无人机点网络中寻优，得到最优路径.虽然我们没有得到最后的最优航线，但是本文建立的模型能够解决这类问题.所以，本文建立的这个模型最终是可行的.

仿真分析中，本文通过实际的假设和演算，进一步地说明了建立的模型的可行性.

关键词：Voronoi图 Dijkstra算法 A*算法

一问题重述

无人机的发展至今已有70多年的历史，其军事应用主要是遂行各种侦察任务.随着无人机平台技术和机载遥感技术的不断发展，它的军事应用范围已经并将继续扩展，如通信中继、军事测绘、电子对抗、信息攻击等.特别是精确制导武器技术的发展，又使它成为这种武器的理想平台.

众所周知自主飞行的能力是无人驾驶飞机所必须具有的.如果要实现无人驾驶飞机的自主飞行,则要求具有相当程度的飞行航迹规划能力.无人机的航迹规划是为了圆满完成任务而作的计划.它往往指单机在初始位置、终止位置和一些目标任务结点确定之后的航迹规划问题,其基本功能是根据无人机的性能和飞经的地理环境、威胁环境等因素,对已知的目标规划提出满足要求的航迹,以便在实际飞行时可以根据需要进行实时局部修改.

现在我们讨论如下的情况：

假定无人机的活动范围为20km×20km的区域，无人机起点的平面坐标为[1,2](单位：km),攻击目标的平面坐标为[19,18](单位：km)，同时不考虑无人机起飞降落时的限制.数字DT和敌方威胁情况(主要考虑雷达威胁)已在附件中给出.数字DT可以做适当的简化，比如可以把地形近似分为三种：高地，低地以及过渡地带.

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

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

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

附件一：雷达威胁的坐标方位表.

附件二：数字DT.

二模型假设

　　1）提供雷达威胁的坐标方位表和数字DT真实有效，并在短期内不会改变.

　　2）假定无人机的活动范围为20km×20km的区域.

问题一的模型假设：

　　1）忽略地形和无人机操作性能，无人机可以任意角度转弯；

　　2）不考虑气候以及飞机自身对飞行的影响；

　　3）飞机燃油量和飞行距离成正比；

　　4）飞机燃料能保证飞机在避开威胁的情况下到达目的地；

　　5）不考虑无人机起飞降落时的限制.

问题二的模型假设：

　　1）假设飞机拐弯的最大角度为；

　　2）飞机的燃料能够使得飞机到达目的地；

　　3）雷达对飞机的探测范围有限；

　　4）假设飞机能够飞过低地和过渡地带，而且不用做其它任何处理；

　　5）无人机的航迹规划系统要求得到的航迹能够有效避开敌方雷达的探测和敌方威胁的攻击.

　　6）把地形近似分为三种：高地，低地以及过渡地带.

三名词解释和符号说明

1. 名词解释

1）Voronoi图：又叫泰森多边形或Dirichlet图，它是由一组由连接两邻点直线的垂直平分线组成的连续多边形组成.N个在平面上有区别的点，按照最邻近原则划分平面；每个点与它的最近邻区域相关联.Delaunay三角形是由与相邻Voronoi多边形共享一条边的相关点连接而成的三角形.Delaunay三角形的外接圆圆心是与三角形相关的Voronoi多边形的一个顶点.Voronoi三角形是Delaunay图的偶图.

2）Dijkstra算法：Dijkstra算法是典型最短路算法，用于计算一个节点到其他所有节点的最短路径.主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止.Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低.

3）A*算法：A*算法属于一种启发式搜索.它扩展结点的次序类似于广度优先搜索，但不同的是每生成一个子结点需要计算估价函数F，以估算起始结点到该结点的代价及它到达目标结点的代价的和；每当扩展结点时，总是在所有待扩展结点中选择具有最小F值的结点作为扩展对象，以便使搜索尽量沿最有希望的方向进行.因此，A*算法只要求产生问题的全部状态空间的部分结点，就可以求解问题了，搜索效率较高.确定估价函数方法通常是：搜索到该结点的深度+距离目标最近的程度.

2．符号说明

网络图上相邻两点i和j的距离

无人机到雷达的距离

雷达j分别到第i边的三个分点的距离

雷达的威胁程度

无人机沿Voronoi图每条边的雷达威胁代价

归一化后的雷达威胁代价

第i条边总的雷达威胁代价

飞机燃油的威胁

飞机受到的综合威胁指标

表示飞机飞过的路程函数

表示飞机转弯的半径函数

表示飞机飞行的高度函数

表示飞机与雷达威胁中心的距离函数

每条边的距离

S 无人机到雷达的距离

N 雷达数目

第i点的转弯半径大于最小转弯半径

四模型分析

对于问题一：忽略地形和无人机操作性能等因素的影响，综合考虑敌方威胁，无人机航程等，基于二维平面建立单机单目标的航迹规划模型.这里可以首先通过Voronoi画出威胁网络图，然后主要综合敌方威胁代价和无人机的航程，建立一个行线综合的威胁度模型，最后通过Dijkstra算法找到威胁度最小的航行路线.

对于问题二：把模型扩展到三维空间，并同时考虑无人机的操作性能（主要考虑拐弯）和地形因素.就是在问题一的基础上,把问题转移到三维空间里,综合考虑雷达威胁因素,地形因素和飞机本身的因素,建立一个确定飞机航线的综合模型,再利用A*算法求出最优航线.

五模型的建立和求解

5.1问题一

5.1.1建立模型

对于无人飞机的航迹优化问题，这里基于Voronoi对威胁网络的划分，采用图论算法实现无人机的航迹规化.

首先，通过Voronoi画出威胁网络图，在威胁网络图中，这里把每个威胁源的中心当作一个点来处理.威胁网络图如下：

那么，本文就在这个有限的二维Voronoi威胁网络图上分析无人飞机的航迹规化问题.

对于雷达的威胁程度，由相关资料（见参考资料）知道：与飞机经过的点到雷达的距离R的四次方成反比，即：

那么，无人机沿Voronoi图每条边的雷达威胁代价就是飞机飞过该边的雷达威胁程度的积分，即：

其中，表示无人机到雷达的距离.

然后，建立选择飞机航迹的模型为：

其中，t 为飞机航迹的威胁度和距离的综合指标；

为网络图上相邻两点i和j的距离；

S 为飞机航迹的总路程；

N为雷达数目.

5.1.2求解模型

　　给每条边编号，如图所示：

对于权，这里从以下两方面考虑：

　　1）雷达的威胁程度

　　2）飞机燃油的威胁,它与飞机飞行的距离成正比

那么综合威胁可用下式表示：

1. 首先利用VB编程算出每条边的距离如下表格：

对距离做归一化处理，这里采用高优公式：

其中，为所有边的最大距离.

2. 计算雷达威胁代价

1）为了简化计算（见参考资料），我们把每条边均匀地分成6等份，取其中的三个点的威胁代价来代替整条边的威胁代价，这三个点分别是L/6,L/2,5L/6，L是第i边的长度，这样第i条边的雷达威胁代价为：

其中，表示雷达j分别到第i边的三个分点的距离

计算得到了如下结果：

为了求出最后的综合威胁，这里应该把雷达威胁和距离威胁的量纲统一，所以应对这些数据进行归一化处理，这里采用高优指标函数：

其中 .

利用VB编程处理后的数据如下表：

3. 综合威胁H

由定义的综合威胁，这里我们尽量地考虑到雷达的威胁度，所以我们对公式：

中的取为0.8，然后直接把上面得到的数据代入公式中得到了如下结果：

利用Dijkstra算法计算最短路经（见参考资料）.

设：图是无向图，它表示顶点集V，与边集E的对应关系，就是Voronoi图给出的关系图.对于每条边赋一个权值，当和有边时，为一实数，当和无边时， .算发步骤如下：

1）初始化：将起点置为P标号，，，对任何，，置为标号.即T=V-P且

2）找最小：寻找具有最小值的T标号的顶点，若为，则将的T标号该为P标号，且

3）修改：修改与相邻的顶点的T标号的值.

对任何，

4）重复2）和3）直到该为P标号为止.

当归入P而‘正好p=V时，不仅求出了从到的最短路径，而且实际上求出了从到所有各顶点的最短路径.

最后，从起点到终点找出综合威胁最小的线路为：起点 19 13

14 终点，如下图黑线所示：

本文着重于考虑雷达的威胁，所以取值为0.8.当然，这里可以根据设计者的不同要求取不同的值，因而得到的线路有可能不相同.

5.2问题二

5.2.1建立模型

首先利用MATLAB编程（程序见附录三）画出地形和雷达威胁点的三维图如下：

在已知的威胁条件下，模型扩展到三维空间，并同时考虑无人机的操作性能（主要考虑拐弯）和地形因素.建立如下的规划模型[3]：

其中，表示对应的各个的权值.各个代表的函数如下：

1）表示飞机飞过的路程函数.设飞机的起点.和经过的航迹点以及终点为：，其中行点有，那么建立如下函数：

其中，是航点到的航线距离，是到的直线距离.

2）表示飞机转弯的半径函数.函数表达式如下：

其中，表示飞机在i处的转弯半径，表示飞机的最小转弯半径.

3）表示飞机飞行的高度函数.这里我们令飞机飞行的最大高度为，那么高度函数为：

其中，为航迹点i的高度.

4）表示飞机与雷达威胁中心的距离函数.这里共有8个雷达威胁点，令它们为，那么该距离函数为：

其中，n为规划后的航线中航迹点的个数，m为航迹中经过的威胁点的个数，为飞机距离雷达威胁中心的安全距离.

5 ) 约束条件中，第一项约束为水平面内的航迹点对应高度在安全曲面z(x,y)上；第二项约束为第i点的转弯半径大于最小转弯半径；第三项约束为飞行高度的限制；第四项约束为第i个航迹点与第j个威胁中心的距离小于距威胁中心的安全距离.

5.2.2求解模型

本文采用A*算法进行航迹规划模型的求解.首先采用A*算法对三维空间内等效数字DXT进行寻优搜索，为了缩短搜索时间，搜索空间定义为起点到终点之间的空间,将搜索转化为二维网格节点的寻优问题，算法采用的评价函数采用上面给出的总的规划模型，结合A*算法的特点，对评价函数进行了改进，算法实现的思路是：当指定的起始点和终止点后，在限定的规划空间内，对下一点可能的航路点进行了评价，找到最小代价点，作为当前节点，然后继续下一点的寻找，直到到达终点为止.这样通过寻找每一步的最小代价点获得全局的最优路径点集合.

5 .3问题三

1、模型的可行性分析：

目前，无人机航迹规划技术还存在以下问题:

首先，无人机的控制由机载设备实现，任务管理在地面控制站上进行，这种控制和管理的分离，存在着由于数据链路处理和传输导致的命令滞后和延迟，所以无法实时规划航迹.

其次，无人机面临的战场环境将是异常复杂多变的，规划约束条件众多而且模糊性大，各因素之间存在联系及其自身的控制和任务方式，使得航迹规划方法的研究更加复杂.

在问题1的解决过程中，我们把雷达的威胁进行了简化，只考虑了无人机与雷达间距离的关系，但是在实际情况下，还有很多影响因素，包括雷达的功率以及地形对雷达波的影响等.所以我们的模型在一定程度上存在缺陷.但是通过这样的简化，我们可以利用Voronoi图，通过Dijsktra算法方便地解决这个问题，粗略的得到我们需要的结果，从这个角度来看，我们的模型是正确可行的.

在问题2的解决过程中，我们在第一问的基础上拓展到三维空间，首先利用MATLAB画出地形和雷达威胁的三维图，然后利用A*算法在导航点网络中寻优，得到最优路径.虽然我们没有得到最后的最优航线，但是我们建立的模型能够解决这类问题.所以，我们建立的这个模型最终是可行的.

2、仿真分析：

2.1基于Dijkstra最短路径搜索的二维平面上的航迹规划（Voronoi 最短路径（黑线））.

飞行空间由8个威胁强度相等的雷达网组成，要求规划无人机从起点飞向终点的航迹.首先进行Voronoi图对威胁网络进行划分，接着利用Dijkstra方法进行最短路径搜索，规划结果如上图所示.整个仿真过程在Matlab环境下进行.

2.2基于A*算法搜索最短路径的三维空间上的航迹规划

寻优算法:即A*算法,对以上设计出的路径，需要进行高度规划.当导航点下面有山峰等障碍物的时候)该点的高度必须严格控制（称这类导航点为高度控制点）.在路径中，起点和目标点的高度固定，也作为高度控制点，这样路径中必定含有两个或者两个以上的高度控制点，在高度规划时，根据这些高度控制点的位置和高度，对其他导航点进行插值处理.由于无人飞机飞行高度越高，距离地面上威胁点越远，威胁度指标越小，据此可制定高度规划策略.假设两个高度控制点的高度分别为h1和h2，插值的方法如下.

(1)h1 (2）h1=h2时，无人机等高飞行.

(3）h1>h2时,无人机首先按照尽量大的航迹倾角下降，下降到需要的高度时，随后等高飞行.

4）在转弯处进行光滑处理.用无人机最佳转弯半径的圆弧来代替折角，转弯时，高度保持不变.

5）任务模拟

环境中有4个雷达，假设无人机最佳侦察高度为0.4km，飞行器起飞点高度为0.2km.

仿真图如上图所示.

六模型评价

本文的优点为：

1）在处理问题一的时候，采用了Voronoi对威胁网络进行划分，使得问题从无限的空间变成了有限的二维空间，从而简化了问题.

2）采用图论算法实现无人机的航迹规化.

3）在计算问题一的最优航迹时，本文采用了Dijkstra算法计算最优路经，计算问题二时利用了A*算法，这样避免了用其它复杂方法去搜索目标航迹.

4）对于威胁分布已知的无人机航迹规划，基于VORONOI图的航迹算法是一个比较可行的航迹规划算法.