无人机自主航道.doc

无人机航道规划 张智， 徐文胜， 梁增玉摘要无人机的航迹规划对发挥无人机的自主飞行和执行任务中起着至关重要的作用。在分析Voronoi图的性质基础上，将整个空间根据敌人的雷达部署和地方火力部署建立成Voronoi图，然后再考虑无人机的威胁代价和燃油代价将无权的Voronoi图有权化。在得到有权的Voronoi图后，运用Dijkstra搜索算法得到无人机的初始航路。最终在利用无人机的最大飞行转角来优化初始航路，得到适合无人机飞行的航路。关键字：无人机； Voronoi图； 航路代价； Dijkstra搜索算法引言航迹/任务规划的能力是无人机所必须具有的能力，如果要实现无人机的自主飞行，那么则要求系统具有很高程度的飞行中航迹规划的能力。无人机航路规划的本质是在规划空间内, 在给定的约束条件下寻找一条从起始点到目标点最优或次优的飞行航路。对于军用无人机来说, 航路规划目的是回避敌方威胁, 满足飞行品质约束(最小转弯半径、速度的限制、油料的消耗) 条件, 圆满的完成作战任务。无人机航迹规划问题无人机的航迹规划要求得到的航迹满足以下的要求：1）最大生存性：无人机能够有效避开敌方雷达的探测和敌方威胁的攻击以及人工障碍等不利因素，以保证飞机的最大生存性。2）时间约束性：无人机能够在有限的时间内到达指定的任务目标区，即满足任务的时间性约束。 3)燃油约束性：无人机能够在限定的燃油量内完成规定的任务，即满足燃油量约束。总之，无人机的航道规划可以描述为如下需要解决的问题：根据已知起点；限制条件无人机的飞行特性，如最大转弯半径，续航能力，机动特性等；需要执行任务的目标区域；威胁分布情况；终点，来寻找一条穿越目标区域的可飞的路径，并且在某性能指标下是最优的。威胁的建模威胁建模是一个复杂的综合问题, 随着威胁的种类、特征和飞行任务的变化而变化。一般来说, 可以将各种威胁简化成具有一定作用半径的圆柱或圆锥等几何体的组合。由于无人机巡航飞行的高度一般在4000m以上【1】，因此地形因素可以不予考虑，因此可把三维的航道规划转化为二维问题。由于诸如天气等因素我们不好量化，因此也不予考虑。在战场上，雷达和敌方火力的攻击是对无人机威胁最大的，为了简化, 做如下假设: 雷达之间没有通信, 即雷达不改变探测特征。雷达用一个半径为r0 的圆来代表, 无人机进入该圆时, 就有可能被探测到, 而无人机可以在与雷达距离r1 r0 的情况下探测到雷达, 从而重新规划路径。战场环境如图1 所示,在区域内有10个雷达。图1 战场威胁图初始航路的建立1 Voronoi图的建立通过Voronoi图来建立初始航路, 省去了在整个状态空间内搜索路点, 解决了“维数灾难”的问题。Voronoi图是计算几何中重要的几何图形，被广泛应用到地形处理等多种区域划分的场合，成功地解决了找最近点、求最大空圆、最小生成树等问题。定义（Voronoi图）：任意两点p 和q 之间的欧氏距离，记为dist(p, q)，设P = p1 , p2, pn 为平面上任意n个互异的点，P 对应的Voronoi图是平面的一个子区域划分，整个平面因此被划分n个单元，它们具有如下性质：任意一点q 位于点pi 所对应的单元中，当且仅当对于任何的piP，j i ，都有 dist(q, pi) dist(q, pj)【2】。Voronoi图具有的一些重要的定理【2】：（1）点q时Vor（P）的一个顶点，当且仅当在最大空圆Cp(q)的边界上，至少有三个基点。也就是说Vor（P）的顶点是相邻三点所构成的三角形的外接圆的圆心。（2）Pi和Pj之间的平分线确定了Vor( P )的一条边,当且仅当在这条线上存在一个点q, Cp(q)的边界经过Pi 和Pj，但不经过其他点。根据上述Voronoi图的性质，Voronoi多边形的每条边上的点到相对应的两个点等距离。也就是说，Voronoi边上的点是到威胁点的最远点，无疑，无人机沿Voronoi边飞行可以获得较高的安全系数。因此无人机沿着Voronoi边飞行可以有效的避免敌方火力的攻击和躲避雷达的检测。图2为根据雷达分布情况所生成的Voronoi图。图2 Voronoi图2 加权Voronoi图-计算航路代价在Voronoi图建立好之后，已经把整个战场抽象成了一个图，但此图是无向无权图，因此没有办法对此图进行航路规划，所以还得确定每一个Voronoi边的代价也就是权，使得Voronoi图变成一个无向有权图。无人机航迹规划是根据任务目标规划满足约束条件的飞行轨迹。约束条件包括无人机完成规定任务的安全性能和燃油性能。所以，无人机的航路代价包含其所受的威胁代价和燃油代价。而我们在前面已经说明了忽略地形和气候条件的合理性，因此我们只考虑雷达和敌方攻击的威胁。2.1 威胁代价函数假定无人机具有相同的雷达反射截面, 因此无人机反射雷达回波的强度就与其到雷达的距离的四次方成反比【3】, 无人机沿着Voronoi图每条边的代价是飞过该边的积分。其中，d(t)表示无人机到雷达的距离。为了简化计算，每条边均匀地分为6 等分，取其中的三个点来代替整条边的代价，这三个点分别是L/6, L/2, 5L/6，L是第i 边的长度。这样第i条边的雷达威胁代价为：式中,N 为战场区域内所有雷达的数目。可以看出,威胁是与距离的四次方成反比, 距离较远的雷达几乎没什么影响。2.2 燃油代价的确定在一般情况下无人机在巡航段的速度是恒定的，因此无人机飞行所消耗的燃油就与飞行航路的长度成正比，因此飞过第i条边消耗的燃油可简单表示为：2.3 边的代价函数的确定在得到威胁代价函数和燃油代价函数后，我们需要把二者结合起来来求得边的代价函数。在数学当中经常运用加权模型来对多个因素进行结合，但需这几个因素必需在同一等级上，即得对这几个变量进行归一化处理。因为威胁代价函数和燃油代价函数已经归一，所以可对此直接进行加权。因此在综合考虑威胁和燃油代价之后，可以得出总体代价函数为：其中，k为安全性能与燃油性能的系数，如果无人机要获得最大的安全性且相对路径较短则k取值为0，如果只考虑路径的长短那么k取1。3 初始航道的确定在确定了每一条边的代价之后，我们已经将无权Voronoi图转变成带权Voronoi图。然后再带权Voronoi图上利用Dijkstra搜索算法【4】来搜索最优的初始航道。Dijkstra搜索算法是图论中寻找最短路径的公认的最好的方法。图3为利用Dijkstra算法找到的初始航路点，为：1-2-5-8-11。图3 初始航道的建立初始航路的优化通过以上初始航道的建立，我们已经可以大体确定了无人机的主要航路。但是此航路有无人机无法飞行的尖点，即前面确定的初始航路不是光滑的航路，每两条相邻的Voronoi边形成的尖点是无人机无法航行的。因此下一步就是在满足无人机的机动特性的基础上优化航迹，取消航迹上的尖角。通常使用的方法是三次样条插值法或B样条插值法。其实无人机是可以在直线上飞行的，只是在尖角处无人机无法飞行，因此只需在航路尖角处变为光滑的就行了，所以没有必要用三次样条插值法或B样条插值法。下面就介绍一种基于无人机最大飞行转角优化航路的方法，此方法既简单，又很实用。当无人机一直以它的最大飞行转角飞行时，飞行航迹是一个圆，而此圆是无人机飞行时可以形成的半径最小的圆，可以将此圆与尖角相切来将尖角变成一条光滑的曲线，如图4。图4 优化航道无人机在飞行时可以形成很多圆形，但用半径较大的圆来相切尖角，那么所形成的光滑曲线会越偏离初始航道，这样无人就会增加航路代价，因为初始航道是代价最小的航道。结束本文提出了一种无人机航路规划方法。该方法基于Voronoi图产生初始航路，然后利用无人机的最大飞行转角对初始航道进行了平滑。对无人机实时在线自主飞行有一定的参考意义。参考文献【1】 董世友，龙国庆，祝小平.无人机航路规划的研究 2004【2】 M de Berg, M van Kreveld, M.Overmars, O.Schwarzkopf.Computational Geometry Algorithms and Applications (SecondEdition)M.Springer-Verlag Berlin Heidelberg New York. 2000.【3】 Kevin B Judd,