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

《无人机自主飞行航迹规划问题1.docx》由会员分享，可在线阅读，更多相关《无人机自主飞行航迹规划问题1.docx（24页珍藏版）》请在三一办公上搜索。

1、目录一、问题重述2二、符号说明2三、基本假设3四、问题分析34.1二维空间无人机航迹规划44.2三维空间无人机航迹规划5五、模型的建立与求解65. 1二维空间无人机航迹规划65. 1. 1单个雷达模型的建立65. 1. 2利用Voronoi图对雷达威胁网络的划分65. 1. 3路径代价的加权计算75. 1. 4利用Dijkstra算法进行最优路径搜索85. 1. 5利用CHC算法对初始航迹进行优化处理95. 2三维空间无人机航迹规划105. 2. 1三维数字地图的平滑115. 2. 2三维空间路径代价的定义和加权计算115. 2. 3消除不可行节点的扩展155. 2. 4将三维空间的搜索转变成

2、二维平面的搜索155. 2. 5使用A*算法进行最优航迹搜索155. 2. 6优化和调整航迹165. 3模型的仿真和可行性分析175. 3. 1二维空间无人机航迹规划模型175. 3. 2三维空间无人机航迹规划模型18六、模型优缺点206. 1二维空间无人机航迹规划模型206. 1. 1模型优点：206. 1. 2模型缺点：216. 2三维空间无人机航迹规划模型216. 2. 1模型优点：216. 2. 2模型缺点：21七、模型的推广21可以用于高速突防弹道导弹的路径规划21用于车载GPS卫星定位的汽车自动寻径21八、参考文献22一、问题重述无人机是军事领域中最具有威胁的空中突防武器之一，凭借

3、着它良好的机动特 性，无人机可以执行如情报获取，侦察监督；实施雷达干扰、迷惑欺骗对方；压制 对方防空火力（SEAD），因此世界各国争相在无人机方向进行大量的研究，我国的在 无人机方面也做出了大量的研究，其中西北工业大学在祖国的无人机方面做出了突 出贡献。无人机最主要的能力就是它的自主飞行能力，要在复杂多变的战场环境中保全自 己，完成任务，那就需要相当程度的飞行路径规划能力，无人机的航迹规划是指单 机在初始位置、终止位置和一些目标任务结点确定之后的飞行轨迹问题，其基本功能 是根据无人机的性能和飞经的地理环境、威胁环境等因素，对已知的目标规划提出满 足要求的航迹，以便在实际飞行时可以根据需要进行实

4、时局部修改。现在假定某无人机的活动范围为20kmX20km的区域，无人机起点的平面坐标为 1,2（单位：km）,攻击目标的平面坐标为19,18（单位：km），在不限制无人机起 飞降落等因素的前提下，根据电子地图和雷达威胁信息，给出无人机的最佳航迹。 需要解决的问题有：问题1:在忽略地形和无人机操作性能等因素影响的前提下，综合考虑敌方雷达 威胁，无人机航程长度等因素，在二维平面建立单机单目标的航迹规划模型。问题2：在解决问题1的前提下，把模型扩展到三维空间，并同时考虑无人机的 操作性能（主要考虑拐弯）和地形因素，即在三维空间对模型进行优化。问题3：探讨所建模型的可行性和可操作性，并进行仿真模拟。

5、二、符号说明重要符号含义J1, p第p条边的飞行长度代价Jt, p第p条边的威胁程度代价Lp第p条边的路径长度N雷达的总数量f (x)直线段函数k路径代价权值Loc (x, y, z)坐标系中第i部雷达的坐标（IV i N）Di目标到第i部雷达的斜距（1 i N）power (x, y, z)i目标收到第i部雷达的照射功率（1Vi N）P (X, y, z)i第部雷达对目标的探测概率U i N）a雷达方程参数JLi无人机在i点的时间代价（归一化）JSi无人机在i点的雷达威胁度（归一化）JHi无人机在i点的低空惩罚度（归一化）J,Ci无人机在i点的爬升/俯冲归一化代价J,Bi无人机在i点的侧转归

6、一化代价Ji无人机在i点的归一化总代价w w加权因子g (n)由起始点到节点n的实际代价值h(n)节点到目标点的代价估计值/(n)由起始点通过节点n到目标点的航迹代价估计值三、基本假设所有的雷达均是相同的；无人机的速度在飞行过程中不会发生变化；战场环境是已知的，不会发生动态改变；四、问题分析无人机航路规划是指在特定约束条件下，寻找从起始点到目标点并满足无人机性 能指标的最优或可行的航路。其本质是多约束条件下最优或可行解的求解问题。无 人机航路规划主要包括环境信息、飞行约束、航路目标以及航路规划器4部分（如图1 所示）：图1.无人机航迹规划模型按照环境模型是否实时更新，即无人机飞行环境是否确定，

7、航路规划可分为静态全 局航路规划和实时的局部航路规划。静态全局航路规划根据无人机飞行环境的确定 信息，在无人机离线状态下进行规划设计。这一过程一般在无人机起飞前完成，实 时性要求不高，因而可以采用的规划算法比较宽。实时局部航路规划通过传感器对 环境变化的反馈更新后，在相应时间内对航路进行规划设计，这种规划实时性要求 高。因主要处理的是给定数字地图下的航迹求解，故而仅考虑静态航路规划，实时 航路规划算法可以经过静态航路规划算法推广而得。4.1二维空间无人机航迹规划从题目中可以知道，无人机要根据已知的雷达坐标信息，找到一条既能最大限 度避开雷达探测，又能以最快时间到达目标点的路径。这是一个路径优化

8、问题，适 合用图搜索技术解决，要解决这个问题，应该先对雷达做一个简单的了解。众所周知，雷达作为现代战场中重要的信息获取工具，是构成无人机战场生存能 力最大的威胁之一，雷达的大致工作原理可以从经典的雷达方程中有所了解，而在 不考虑无人机起飞降落及地形因素和操作性能的前提下，无人机的路径规划只需要 考虑雷达对它的威胁程度和路径长度对无人机航程造成的影响。假设每个雷达的性能参数形同，根据雷达的工作原理，先建立单个雷达模型，从 而建立多个雷达组成的威胁网络模型，得到雷达网对无人机在各个位置的威胁程度 代价，可以对威胁程度代价和无人机路径长度代价进行加权处理，得到飞行航迹代 价，并以此作为整个空间的搜索

9、目标函数。由于基于整个二维空间的搜索过于复杂，为缩小搜索空间，可以采用Voronoi 图1 方法，Voronoi图具有较强的直观性和把复杂的空域问题转换为区域划分问题 的能力，有较好的时间特性和空间特性，在缩小问题空间方面具有很高的普适性， 所以使用基于Voronoi图的加权最优路径搜索策略，以降低搜索空间。首先利用Voronoi图对二维空间进行划分，得到然后将每条可行边对飞行航迹代 价进行积分，得到每条边的飞行航迹代价，由于使用Voronoi图得到是一个个彼此 相交的节点，这种连通图很适合用图搜索进行求解，可以采用基于无向图搜索的 Dijkstra算法找到一条当前最优路径，这里需要注意的是，

10、由于Dijkstra算法求 得的是一条一条的直线段，并不适合无人机飞行，所以有必要对得到的初始航迹进 行相应的优化处理，相应的处理算法有人工势场法、遗传算法等，而采用CHC算法 的优化线段可以取得不错的效果，利用CHC算法对初始航迹进行优化，得到最适合 无人机飞行的航迹。总的思路可用流程图（图2）表示如下：图2.二维空间的无人机航迹规划流程图4.2三维空间无人机航迹规划在三维空间中，由于引入了高度问题，使得模型进一步复杂化，不仅要考虑在 二维平面的威胁程度代价和飞行长度代价，还要将无人机的操作性能和高度因素考 虑进来，由于无人机的操作性能主要是拐弯问题，即为无人机拐弯时的最大拐角， 无人机的最

11、大爬坡/俯冲值，无人机的侧转参数，这些都是物理方面的限制，因为无 人机不能超越它的最大拐角而进行拐弯动作；而无人机的高度问题则在一定程度上反映在无人机的安全性问题上，根据雷达 模型，容易知道在雷达探测极限高度一定的情况下，无人机的飞行高度越低，则无 人机被雷达发现的概率就越小，这也就是军事上常用的低空突防，但超低空飞行也 增加了无人机坠毁的概率。可见无人机在完成任务过程中的航迹应该满足多种约束 条件，这些约束条件有的是强制条件、有的是非强制条件（但有相应的代价），它们 都给航迹的选择带来了不确定因素，增加了搜索的难度。通过分析得到，无人机的航迹选择其实就是选择一条从起始点到目标点代价最 小的路

12、线，且该路线是无人机实际可飞行完成的。代价可以是无人机的飞行时间这 样的确定代价，也可以是最大侧转角度这样的非确定代价，但是可以通过归一化等 手段将它们整合在一起。此时三维空间的航迹搜索转化为二维平面的路径求解。将二维平面栅格化，每 一个节点代表无向图中的一个顶点，相邻两点之间的路径代价就是无人机飞行所需 付出的所有归一化代价之和。问题转化为在该无向图中搜索一条从起始点到目标点的路径。因普通的路径搜索算法在地图规模比较大时效率比较低，而A*算法利用启 发式函数可以使搜索加速，所以采用A*算法搜索一条较优路径。在使用A*算法扩展 过程其实就是无人机作相应代价的操作，这样算法可以和无人机本身相对应

13、。五、模型的建立与求解5.1二维空间无人机航迹规划5.1.1单个雷达模型的建立由于雷达的威胁是战场中对无人机的主要威胁，所以对雷达的工作方式要做必要 了解，雷达的作用距离主要和雷达电磁波的能量损耗有关，根据雷达方程4：(5.1)PGA bP = t g(4 兀)2 R 4从雷达方程可以看出，无人机在飞行过程中所受到的敌雷达威胁的大小，与无人机 距雷达距离的四次方成反比，与雷达发射功率成正比。则可以建立起单个雷达的威 胁程度模型，从而搭建雷达网络威胁模型。而根据探测概率空间分布和雷达方程可 知，目标被雷达，探测到的概率为：a ,d TD 4(t)ipower = ji由上式被探测的概率可简单计算

14、为：八/ 、 1 0.5*(max_ power (x, y, z) power (x, y, z)P (x, y, z) = 1 i:iimax_ power (x, y, z) min_ power (x, y, z)ii所以在N部雷达存在的情况下，点(x,y,z)被探测的概率为：P (x, y, z) = 1 H (1 P (x, y, z)ii=1(5.2)(5.3)(5.4)在二维平面情况下，公式简化为:(5.5)P(X, y) = 1 H (1-P (x, y)ii =15.1.2利用Voronoi图对雷达威胁网络的划分定义1： Voronoi图又叫做泰森多边形或Dirichlet

15、图，它是由一组连接相邻点直线 的垂直平分线组成的连续多边形组成。在本题中，可以把每个雷达点当成一个威胁源，利用MatLab建立Voronoi图(图3)如 下所示图3.二维空间的Voronoi图这样就将无人机的飞行航迹简化到了 Vorono i图的边空间上，从而将无限空间的搜索 简化到了基于Vorono i图边的有限空间搜索，将整个二维空间的雷达威胁网络建立起 来。513路径代价的加权计算由于本题中无人机的航迹主要受到雷达威胁和航程长度的影响，则可以将雷达威 胁和航程长度转化成相应的代价数值，分别定义为威胁程度代价和飞行长度代价， 飞行长度代价在不考虑飞机速度的情况下只与飞机飞行的路径长度有关，

16、而飞行路 径又是由各条线段首尾相接组成的，所以第p条边的飞行长度代价可以简单的表示 为：l, pp(5.6)而危险程度代价是指无人机暴露在雷达下的程度，这和无人机到雷达点 的距离，还有暴露时间有关，由于航迹是由Voronoi图的边构成的，则可以 将每天边的威胁程度利用积分求的，每一条线段p的危险程度代价可定义为：(5.7)匕广 Ll U(x - X )2+( f (x)-歹)2)4 d*ii这样，一条航迹的飞行航迹代价就可以用危险程度代价和飞行长度代价加权之和来 计算，公式如下：J = kJ + (1-k) J权值k的取值范围是0,1,用来配置危险程度代价和飞行长度代价的权重关系，增 加模型的

17、灵活性。通过加权计算，将两个约束条件转化为一个目标函数，使图搜索 简单化。51.4利用Dijkstra算法进行最优路径搜索 定义2:如果对于图G的每一条边e = V ,V均有一个实数与w相对应，则称图i ,ji ji ,jG为赋权图，并称实数w为边e的权。在赋权图G中，通路p = e ,e , ,e i, ji, j1 2 k中所有边权的和称为该通路的长。从顶点V到Vj的最短通路是指所有从V.到v/勺 通路中具有最小长度的那条通路。在加权Voronoi图的基础上，使用图论中任何一种最短路径搜索算法就可以搜到无人 机的初始航迹。值得注意的是，在使用最短路径的搜索算法建立适合的数据结构时， 因为路

18、径规划不仅要适合一个方向的航迹，更重要的是适合多方向的航迹规划，所 以应该选择无向的最短路径搜索算法。在单机航迹规划实验时，选择了无向Dijkstra 搜索算法生成初始航迹。定义3: Dijkstr算法是典型最短路算法，用于计算一个节点到其他所有节点的最短 加权路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。 Dijkstra算法能得出最短路径的最优解。其算法流程图(图4)如下所示：川邻I柘:寸邪白顶点?口康=当前柠点i 啊I苗时厩:高-论4 攻的此度取F ,个-页血为当前节点耳取与当前点相郛七一I/J I-个 D.或泞山点的临时叩浣 .Er取勺和轴构半 f点位徂冠始心、为 F

19、 心 E.T初始化所仃II缶I 川馈为届大图4. Dijkstra算法流程图由于使用Voronoi图对二维空间进行的划分可能不包括起点和目标点，所以必须进 行相应处理才能进行搜索，参考有关文献，可以将起点、目标点和与它们路径代价 最接近的Voronoi图节点用直线相连，这样得到的路径也是当前最优的。5.1.5利用CHC算法对初始航迹进行优化处理定义4： CHC算法2是跨世代异物种重组大变异(Cross generation Heterogeneous recombination Cataclysmic mutation )的缩写，CHC算法是遗传算法的一种改进， 它是由Eshelman于199

20、1年提出的.CHC算法与基本遗传算法SGA不同点在于：SGA的 遗传操作比较单纯，简单地实现并行处理；而CHC算法牺牲这种单纯性，换取遗传操 作的较好效果，并强调优良个体的保留.相对于传统的遗传算法，CHC具有以下优点：(1) 健壮性.由于这一选择策略，即使当交叉操作产生较劣个体偏多时，由于原种 群大多数个体残留，不会引起个体的评价值降低.(2) 遗传多样性保持.由于大个体群操作，可以更好地保持进化过程中的遗传多样性.（3）排序方法.克服了比例适应度计算的尺度问题.将用Dijkstra算法得到的初始航迹进行如下处理：（1）选择算子根据适应度的大小按照比例选择方法来求取个体遗传到下一代的概率，方

21、法如下：1）首先选取航迹路径中的2N（N为任意正整数）个航迹点，航迹点的位置是任意 的；2）计算出每个航迹点的路径代价度fp，和总的路径代价度f ；（这里的路径代 价度包括长度代价和危险代价两个方面，在前面的路径代价度计算中已经给 出计算方法）3）计算每条航迹线段的相对路径代价度大小，即fpl f，作为被遗传到下一代 的概率；4）利用模拟赌盘操作（01之间的随机概率）来确定每条航迹线段被选中的次 数；5）对所有航迹线段按照路径代价度进行排序，选取前面N条路径代价度最小的 航迹点作为下一步进行交叉的种群，继续进行。（2）交叉算子对航迹点集中的个体进行配对，即分成N/2对个体对，然后对每一对按照一

22、定 的交叉概率进行交叉，这里采用单点交叉方法，即首先找出每对的2个航迹点中路径 代价最接近的2个点，这就是需要交叉的点，交换这2个点的编码即产生了2条新航线.（3）变异算子在进化前期不进行变异操作，当进化到一定收敛时期时才采取变异操作.可以通 过如下的方法确定变异航迹点的位置：在航线中搜索出2个不相邻的航迹点，计算这 2个航点之间的路径代价差值和它们之间的航线距离的比值，当该值小于指定的阀值 时，这2个航迹点之间的航迹点就是所有需要进行变异操作的点。在变异点的位置重 新生成一条航线。52三维空间无人机航迹规划由于所给数字地图的精度太低，不能够反映地势高低变化的走向，以及地图中 的细节，所以在进

23、行三维模型的建立和分析之前，预先对地图进行平滑，使其更能反映现实地图。5.2.1三维数字地图的平滑利用MatLab软件对原始数字地图进行三次样条插值，得到新的数字地图的三维空 间，该地图很好的反映了整个地形的走势、以及高度变化情况。插值后的地图如图5 所示。数字地图的三维显示X (km)图5.插值后的数字地图522三维空间路径代价的定义和加权计算在使用A*算法进行航迹搜索之前，首先要确定用于A*搜索的代价函数。代价函 数是所有航迹规划研究方法共同的难点，往往多个代价之间相互耦合,无法通过确切 的数学表达式加以描述。代价函数应具有以下特点:直观，对航迹代价惩罚的意义明 确;代价函数中各代价的量纲

24、要匹配;代价值计算简单，不能造成太大的计算量。在考虑了无人机整个完成任务的过程，并综合考虑问题的复杂度之后，定义航迹代如下：1. 执行任务时间（T）：无人机完成整个任务所用的时间，在不考虑无人机速度（v ） 的情况下，可以用整个航迹的长度（L）来估计。所以定义JL=L（5.9）2.3.无人机在飞行过程中的威胁度（S ）:在给定数字地图中无人机的主要威胁是敌 方雷达，可以使用上文中讨论的无人机被雷达发现概率作为威胁度的定义，但在 三维空间中雷达发现无人机的概率不仅仅向二维平面中的概率那样仅是和雷达 和无人机的距离，因为在不考虑雷达波衍射的情况下，如果无人机可能利用高山 的地势躲过雷达的探测，同样

25、无人机也可以超低空飞行躲过雷达（这里不考虑无 人机超高空情况：雷达波在高空单位空间内的功率较低空低的多，故而无人机也 可以使用高空躲避，但在当前来看无人机的飞行高度都不是很高，且雷达的可探 测高度很高，从而忽略上述情况）；综上：飞行威胁度可以简单定义如下： 无人机被第1个雷达照射的功率：0,雷达和无人机连线上存在障碍物；max（0, z - K） xj一 dx,雷达和无人机连线上不存在障碍物;（5，10）D 4（t）iipower = vi上式中K为雷达的最大探测半径。同上面推导的平面无人机被探测概率可得：P3, y, z） = 1 廿（1-P （乙 y, z）i所以简单令i=1J = P 3

26、, y,乙)(5.11)(5.12)无人机高度（H ）:无人机在飞行过程中必须要有一定的高度，如果飞得太高 就容易被敌方雷达发现；但飞得过于低无人机坠毁的概率就会增加，同时来自于 地面的威胁也会增加。在上面的威胁度计算中，已经考虑了无人机高度对雷达探 测的影响，所以这里仅仅考虑无人机的坠毁，并将它作为一个惩罚因子。J = max（0, z - h ）（5.13）其中hmin为无人机的最低安全飞行高度；min4.无人机爬坡/俯冲约束（c ）:如图6,建立坐标系作为Oxy为无人机的航迹 的坐标系，Oxyz是地面坐标系，将无人机在三维空间的运动2同时分别向水平面与铅锤面投影，Ox；轴是0x2轴在水平

27、面Oxz上的投影，9,中分别为无人机倾角 和无人机偏角；22图6.空间坐标系示意图当无人机在做爬升/俯冲机动时（图7）,无人机在第n +1时刻的铅直位置及无人 机倾角为：yyn+1=n+99L n+1nsin 9n0cos 9n0r sin A90 vny 1vAt sin 9Xr (1 cos a9 )y1= n +nr八1vn90A9nn(5.14)(A6 =99 )nn+1n图7.无人机爬升/俯冲示意图通过上述的推到计算即可得到无人在爬坡/俯冲所要满足的条件，这也同时给 出了无人机要想实现爬坡/俯冲所要付出的代价（正比于爬坡/俯冲倾角角度变 化）；所以定义：J =A9 =9 -9（5.1

28、5）无人机侧转约束（B ）:如图8是无人机的侧转示意图图8.无人机侧转示意图由图，当无人机做侧滑转弯时，无人机在乃+1时刻的水平位置及无人机偏角为:-X -X -cos中-sin 中0r sin 中XvAt cos0 cosn+1nnnHnnnnZZ+sin中cos中0Xr (1-cos A )z+-vAt cos0 sin n+1nnnHnnnn中n+1中n001JAn n0(5.16) (平=甲一平)同样利用上式可以得到无人机实现转弯所要的最小半径，从而得到无人机水平 侧转的代价，它可以正比于侧转角度变化。所以定义：J = 甲=甲一甲(5.17)以上定义了无人机完成任务中的飞行代价，但是他

29、们都是相互独立的，而且单位 也不是统一的，数值上也可能相差多个数量级，必然导致求出的总代价将会对航 迹的规划失效。在此基础上可以采用归一化的方法：分别对几个代价求解结果进 行归一化，再使用归一化之后的结果求解总代价，可以有效的控制航迹的选择。 定义J 、J 、J 、J 、J 分别为无人机在第个节点的归一化后的时间代Li Si Hi CiBi价、雷达威胁度、低空惩罚、爬升/俯冲代价、侧转代价。综合所有的约束因素，可以得出三维空间下的无人机在第n个节点时的加权路径 代价表达式为：J = w J +廿( J + J + w J + w Jf )(5.18)i 1 Li2 Si 3 Hi 4 Ci 5

30、 Bii=1其中W1 w5为加权因子，通过对以上的约束条件的加权计算，进而得到最后三维的 加权飞行航机代价Ji。A*算法计算代价值时分两部分计算.其代价函数可以表示为：f (n) = g (n) + h(n)(5.19)其中g (n)表示由起始点到节点n的实际代价值，h(n)表示节点n到目标点的代价估 计值，即为启发函数；f (n)表示由起始点通过节点n到目标点的航迹代价估计值。 很明显有g (n = /，对h(n)，可以简单定义为节点n到目标点的预计飞行时间，因 无人机的速度假设是恒定的，所以可以用节点n到目标点的距离并经过归一化后值 代替：h(n) = Dis (n, dest _ pos

31、)(5.20)综上，A*算法的代价函数已经定义完毕，这就使利用A*算法搜索最优飞行航迹成为 可能。52.3消除不可行节点的扩展在对涉及无人机的性能的代价进行定义时，譬如无人机的爬升倾角变化，因无 人机的倾角变化不能超过某一值，可以采用当倾角变化超过该值时，定义所爬升代 价为无限大。这样该方向的扩展因为代价太大，就永远不会被扩展，从而消除了扩 展到无人机不可行航迹，同时也让搜索算法简单化。5.2.4将三维空间的搜索转变成二维平面的搜索在三维空间中搜索是向立体的12个方向同时进行搜索的，通过上述航迹代价的 定义，因为无人机的每一种操作对应一个代价值，这样将战场地表栅格化之后，战 场被抽象成一个由一

32、系列顶点构成的无向图，战场中每个点对应图中的一个顶点。 相邻顶点间的边是战场中相邻点的路径，边的代价是无人机在相邻点间飞行的代价。 这样原来问题的求解转换成图中搜索一条从起始点到目标点的代价较小路径。搜索 过程中的边就是无人机进行相应边代价对应的飞行操作。据此构建出搜索成功之后 的三维路径。故而搜索被缩小到了二维平面中，搜索效率有了明显提高。5.2.5使用A*算法进行最优航迹搜索在前面加权路径计算的前提下，由于有了估计函数和启发函数，利用基于栅格 化三维空间的A*算法对节点进行搜索，A*算法是人工智能中典型的启发搜索算法, 它是利用启发信息找到以最小代价通向目标节点的最优路径。对于每个节点来说

33、， 当它利用启发式信息进行搜索时，能向与自身相邻的八个节点进行搜索，为缩小搜 索空间，不妨定义节点朝目标点方向的三个节点进行搜索，即如下图(图9)所示：图9.节点搜索方向(假定目标节点在右上方)定义5: A*算法进行搜索需要用到两个数据结构:open表和closed表，open表存 放被扩展到的节点，代价小节点放在在open表前端，closed表用于存放已经扩展过的 节点。在任意位置，节点，应该的数据结构应该存储以下信息：空间位置Loc 3,y,z)、到其余三个相邻节点的启发函数h(n)、估价函数f(n)、指向 i父节点的指针。基于栅格化三维空间的A*航迹规划算法具体步骤如下：1. 输入起始点

34、和目标点，以及数字地图数据和代价函数中各项的权值系数。2. 构造open表和closed表，并将起始点插入open表，将closed表置空。3. 若open表为空，则算法失败，退出，重新输入起始点和目标点信息；否则继续。4. 对open表中节点按飞行航迹代价J排序，并从open表中移出代价最小的节点n， 赋给当前节点变量用来扩展，并将其放入closed表中。5. 判断是否满足停机准则：如果当前节点与目标节点之间距离小于设定距离L，则 将目标节点的父节点指针指向当前节点，算法结束，从目标节点“回溯”到起 始节点，得到最优三维航迹，否则，按以下算法扩展当前节点：a) 判断该扩展节点n +1是否满足

35、高度约束条件、航向约束条件和无人机侧转约 束条件，不满足则计算下一节点，否则继续；b) 计算该扩展节点n +1的航迹代价：f(n)=h(n)+g(n)；c) 将扩展节点按航迹代价大小插入open表中：如果扩展节点既不在open表中又不在closed表中，就将其父节点指针指 向当前节点，并按航迹代价大小插入open表；如果扩展节点在open表中或者在closed表中，则调整其父节点指针指向 使其具有最小代价/的父辈节点；如果扩展节点在closed表中，并且在上一步中调整过扩展节点的父指 针，则把它再重新放入open表；6. 回到步骤3，继续执行。通过代价函数的定义，原来三维空间中的航迹搜索转变成

36、了基于二维平面中的 路径搜索，同时通过A*算法中的扩展操作可以轻易得到无人机的操作序列，这也将 有利于简化无人机的设计。526优化和调整航迹由于航迹路径是A*算法基于三次方样条插值的图形得到的，加上估价函数的较精 确选取，所以航迹路径的精度已经很高，不必要像二维空间一样进行较大的修正和优化了。5.3模型的仿真和可行性分析531二维空间无人机航迹规划模型二维空间的无人机航迹仿真模型利用雷达的工作原理，建立了单个雷达的威 胁模型和多个雷达组成的雷达网对无人及造成的威胁模型，充分考虑了雷达这一重 要工具对无人机产生的威胁，同时通过定义路径代价将无人机的航迹代价量化，使 得无人机的参数具有较强的直观性

37、，也使得计算进一步简化，在对二维空间的划分 上，使用目前国际普遍采用的Voronoi图，使模型在不失一般性的同时具有更小的 搜索空间，而选择无向Dijkstra算法搜索航迹，使得得到的飞行航迹更具可靠性。运用MatLab软件对二维空间的航迹规划进行仿真，得到初始比较粗糙的航迹如 图10所示:810X (km)数字地图的Voronoiffi起始点目标点*雷达点Voronoi三甫剖无,-线图10.二维无人机初始航迹提出用改进的CHC算法对初始路径进行进一步的优化，得到最终的二维空间无人机最 优航迹，如下图（图11）所示：图11.二维无人机最优航迹由此可以看出，在得知战场情况下运用改模型可以得到较优

38、的飞行航迹，具备较强 的可行性和通用性。5.3.2三维空间无人机航迹规划模型三维无人机航迹规划是个复杂的问题，需要考虑各种情况，三维空间无人机航 迹规划通过统一代价、再使用基于A*算法的方法求解航迹，让复杂的问题简单化， 且易于扩展。可以利用现有无人机航迹规划研究结果说明上述模型是比较全面、且 具有可解性的。全面性：现代无人机航迹静态规划研究主要考虑无人机的爬升/俯冲、侧转、雷达威胁、 离地高度等因素；上述模型中综合考虑了上述因素，而且给出了一种通用的代价计 算方法，将它们对无人机航迹规划的代价统一起来。这给基于A*算法的航迹搜索带 来了方便，使得算法本身和无人机的任务类型（时间优先、雷达威胁

39、最低）无关， 避免了更改任务类型时需要重新更改算法。可解性：A*算法是人工智能中典型的启发式搜索算法，利用启发式信息找到以最小代价通向目标节点的最优路径，较之普通搜索算法有相当高的搜索效率。能够在较快的 时间内找到一条较优航迹。且利用上述模型，原来复杂的三维空间中的搜索（每次 需要扩展18次），变为二维平面的搜索（每次只需扩展8次），搜索效率明显提高， 这也大大简短了搜索时间。利用上述模型进行简单模拟，得到如下（图12）的航迹路径：枷格化后的数字地图02468101214161820X （km）图12.利用基于栅格化三维空间A*算法求解的航迹路径图中黑色的线条是规划航迹，从图中可以看出航迹基本

40、上是处于低海拔处，这 有利于躲过雷达的探测，从而获得较小的威胁代价。对比Vonoroi图算法，明显可 以发现航迹的不同，这是因为Vonoroi图算法仅仅考虑了敌方探测的威胁，而在上 述模型中，综合考虑了多种情况，航迹线有了曲折。将上述等高线图使用三维空间显示，同时根据无人机航迹规划中的飞行方向， 构建三维坐标可以得到下图（图13）：图13.三维空间无人机航迹较优路径图地点点点字达始标数雷起目其中黑色线条为规划航迹。航迹基本上是沿着山脉的边界而走，并在有些区域 利用高山隔开雷达，这有效的避开了雷达的探测，同时也反应了算法的可行性。六、模型优缺点6.1二维空间无人机航迹规划模型6.1.1模型优点：

41、考虑了二维空间上雷达的工作原理，引进经典的雷达方程，建立单 个雷达威胁模型和多个雷达的威胁网络模型，充分体现了二维空间 雷达对无人机航迹的影响。路径代价的定义结合了雷达威胁代价和路径长度代价，并利用权值 进行综合，使得操作者可以根据无人机任务的重点对无人机的航迹 进行有机调整。将Voronoi图和Dijkstra算法结合起来使用，大大减小了搜索空间 和问题复杂度。利用改进的CHC算法对初始航迹进行优化，使得航迹更加符合无 人机的特性，具有很大程度的普适性。6.1.2模型缺点：需要的地方情况较多，缺少必要的智能性和应变能力，对动态环境 不适用。6.2三维空间无人机航迹规划模型6.21模型优点：模

42、型充分考虑了无人机在完成任务过程中的时间代价、雷达威胁度、低空惩罚、爬升/俯冲代价、侧转代价，并将它们归一化，再通 过加权计算得到航迹的代价。模型将A*算法与航迹代价独立开来，使得再保持算法不变的情况 下，通过调整代价参数实现不同性质任务的航迹规划。通过添加代价到代价集中可以提高系统在应对新战场情况下的动 态航迹规划。原来三维空间的复杂搜索过程转换成了二维平面的搜索，大大增加 了搜索的效率。6.2.2模型缺点：算法仍然需要保存大量不宜扩展点，这增加了系统开销，同时可能 会进行大量的无用扩展。七、模型的推广可以用于高速突防弹道导弹的路径规划与无人机一样，如果能够得到战场环境的相应数据，可以在三维

43、航迹模 型的基础上解决对导弹路径的规划问题，使得导弹的路径规划更容易实 现。用于车载GPS卫星定位的汽车自动寻径利用GPS卫星定位，得到汽车周围环境的交通数据情况，利用二维航迹 规划平台，得到到达目标点的最优路径，这对于未来汽车的自动驾驶和 只能寻径有非常大的意义。八、参考文献1 基于VORONOI图的无人机航迹规划赵文婷，彭俊毅2006 .82 基于CHC算法的无人机航迹规划方法张振理王英勋2007.63 无人机航路规划技术研究进展李季孙秀霞4 斯科尔尼克雷达系统导论林茂庸，等译.北京：国防工业出版社，19925 Jeffrey M. Hebert. Air Vehicle Path Pla

44、nningD. Air Force Institute of Technology,AFIT/DS/ENG/01-04.6 Michael C. Novy. Air Vehicle Optimal Trajectory for Minimization of RadarExposureD. AFIT/GAE/ENY/01M-07.7 Michael C. Novy, David R. Jacques. Air Vehicle Optimal Trajectories BetweenTwo RadarsC. Proceedings of the American Control Conference, 2002,785-790.