数学建模无人机飞行航迹正文
目录
一.问题重述 ...................................... 错误!未定义书签。
二. 问题的假设与符号说明.......................................... 1
1. 合理假设................................................... 1
2. 符号说明 . ................................................................................................................... 2
三.问题的分析 . .......................................................................................................................... 2
四.模型的建立与求解 ............................................................................................................. 3
1问题一 ..................................................... 3
(一)威胁建模............................................... 3
(二)模型求解............................................... 4
(三)雷达威胁目标隶属度计算................................. 6
(四)航迹算法的规划 „„„„„„„„„„„„„„„„„„„„7
2. 问题二.................................................... 11
(一)问题求解.............................................. 11
(二)基于三维空间的A *算法进行分析 ....................... 14
3. 问题三................................................... 17 (一)模型的可行性分析............................................................................................. 18 (二)模型及算法的仿真分析„„„„„„„„„„„„„„„„„„19
(三)模型的优缺点„„„„„„„„„„„„„„„„„„„„„„错误!未定义书签。20
五 参考文献 ....................................................... 21
一、问题的重述
众所周知自主飞行的能力是无人驾驶飞机所必须具有的。如果要实现无人驾驶飞机的自主飞行, 则要求具有相当程度的飞行航迹规划能力。无人机的航迹规划是为了圆满完成任务而作的计划。它往往指单机在初始位置、终止位置和一些目标任务结点确定之后的航迹规划问题, 其基本功能是根据无人机的性能和飞经的地理环境、威胁环境等因素, 对已知的目标规划提出满足要求的航迹, 以便在实际飞行时可以根据需要进行实时局部修改。
现在我们讨论如下的情况:
假定无人机的活动范围为20km ×20km 的区域,无人机起点的平面坐标为
[1,2](单位:km), 攻击目标的平面坐标为[19,18](单位:km) ,同时不考虑无人机起飞降落时的限制。数字地图和敌方威胁情况(主要考虑雷达威胁) 已在附件中给出。数字地图可以做适当的简化,比如可以把地形近似分为三种:高地,低地以及过渡地带。
问题1:忽略地形和无人机操作性能等因素的影响,综合考虑敌方威胁,无人机航程等,基于二维平面建立单机单目标的航迹规划模型。
问题2:把模型扩展到三维空间,并同时考虑无人机的操作性能(主要考虑拐弯)和地形因素。
问题3:试讨论和分析你提出的模型的可行性,并做仿真分析。
二、问题的假设与符号说明
1、对于问题的部分合理假设说明:
(1)从雷达的探测机理可知,在理想的情况下,在飞行高度为H 的水平截面上,雷达的有效探测范围二维可以近似看作一个圆,圆的半径R 表示雷达的有效探测范围,三维时可以近似看作一个半球。(如下图1所示的雷达模型)
(2)假设在20km ×20km 的区域,雷达具有相同的功率,即具有相同的探测半径,(二维情况只考虑平面区域),三维空间考虑为20 20的栅格,雷达为点坐标。
(3)不考虑敌情信息的获取与处理及其他意外情况(比如雷达点认为是静态
等)。
(4)不考虑无人机的起飞降落情况,仅考虑飞行状态。
(5)假设整个航程飞机匀速飞行,出发,返回航线相同,为单一曲线而非闭合。
(6)飞机航程仅取决于燃料量,航程越短,燃料消耗越少。
(7)假定无人机具有相同的雷达散射截面,则其反射雷达回波的强度就与其到雷达点距离的4次方成反比。
(8)无人机的最大转角不超过50度。
2
三、问题的分析
问题一:通过敌方雷达或威胁区域构造Voronoi 图(注:该类图形的性质及在该题中的应用我队将在(四) 问题模型的建立与求解中进行详细的阐述), Voronoi 图的边界就是所有可飞的航迹, 然后给出这些边界的权值, 最后使用A *算法, 来搜索最优的航迹。其中算法中需要的代价函数用距离、危险和机动能力约束的加权和形式表示, 并且上述代价函数中元素的表达使用了模糊技术, 其大小用模糊隶属度函数来表示, 这么做可以使规划的路径、航迹上的障碍、以及所需机动的内在不确定性得到较好的反映,因为模糊技术恰是就觉问题中个因素重要程度的良好方法。通过给定搜索空间、起始节点和目标节点, 采用这种修改的A * 算法, 利用良好的启发性
搜索知识就可以找到可行的最小代价路径。
问题二:无人机在三维空间考虑,地形数据信息是航迹规划系统最主要的信息来源,存储在数字地图中。此外,一般可以将威胁处理成特殊的地形,从而将其位置和作用范围叠加到数字地图上。经过这样处理得到的数字地图不仅包含地形的信息,也考虑了威胁的信息,威胁的作用等价于抬高了当地的地形。低空飞行过程中,考虑威胁的作用,同时结合飞行器的撞地概率,通常给出一个最佳离地高度,记为h 。这样,当飞行器以高度h 离地飞行时,认为其危险最小。并且飞行航线要尽量平滑。
问题三:综合问题一和问题二,作出航行轨迹图,得到的规划路径是在Voronoi 图中的最佳路径 但是否适于无人机实际飞行需求, 需要进一步细化修正, 修正主要考虑以下几个方面:
①能否进一步缩短飞行距离;
②相邻两条线段之间的夹角如果不满足最小转弯半径的限制时的处理;
③无人机的初始航向角与规划路径的起始航向角之间差异太大时的初始阶段处理。
四、模型的建立及求解
1、问题一
模型的建立及求解
(一)威胁建模
基于Voronoi 图的规划方法主要步骤是根据已知的雷达威胁分布情况,取威胁中心点构造出威胁分布的Voronoi 图,依据雷达探测范围的威胁和燃油消耗建立航迹性能指标,然后利用搜索算法在图中搜索满足该性能指标的初始航迹,最后结合无人机的性能约束对航迹进行平滑修正,得到可行航迹,即完成整个无人机的航迹规划。
根据问题要求,首先选取某无人机的飞行区域为20 km ×20km 的高威胁空间,在该空间内分布有8个具有相同功率的雷达,根据假设它们具有相同的探测半径,采用Voronoi 图算法对该威胁区域进行有规则的分割,将状态空间内无限的搜索转化为有限的搜索。根据计算几何的知识,母点就是雷达威胁点,而Voronoi 图的边则是雷达点对的中垂线,边上的点是到平面上所有雷达最远的点即威胁最小点集合中的点。Voronoi 图用matlab 软件进行操作得到雷达威胁模拟图(见下方),其中蓝点为雷达威胁点,红点为起始点和目标点,几何距离最近的Voronoi 顶点,寻找从起始点到目标点的最优路径即完成初始航迹的规划。
根据上面介绍的算法不难得到以下Voronoi 图的特性:
①每个Voronoi 多边形内仅含一个母点;
②Voronoi 图多边形内的点到相应母点的距离最近;
③位于Voronoi 多边形上的点到其两边的母点的距离相等;
④Voronoi 图的每一个顶点恰好是图的三条边的公共交点;
⑤Voronoi 图的顶点是由原来的母点中的三个点确定的圆心。
从以上Voronoi 图的构造过程和特性可以看出,Voronoi 图中各个边到对应母点(雷达点)距离相等, 如果将战场区域中的威胁中心作为图的母点, 则显然Voronoi 图的边是能够最好规避对应的两个威胁的线段, 所以选择构造战场的Voronoi 图可以有效地把路径搜索的空间降低到仅仅在图的边中进行搜索, 极大
地提高路径优化的效率。
Voronoi 雷达威胁图
(二)模型的求解
计算Voronoi 图的每条边(路径段) 的代价包含两个部分: 威胁代价和燃料代价。即路径段的总代价是两部分代价的加权和。用公式表示为:
J i =kJ f , i +(1-k ) J t , i
其中J t , i 为路径段i 的威胁代价,J f , i 为其燃油代价, 需要着重说明的是这里k 为加权系数, 是介于0 到1 之间的数, 路径规划时可以按照任务需求在任务的安全要求和燃油要求之间进行调整。J t , i 的计算按照路径段距离威胁的距离表示, 计算公式如下:
N
J t , i =L i ∑c j (d
j =1
1/41/41/2i , j +d 1/41/6i , j +d 1/45/6i , j ) 这里N 为威胁的个数, d 反映无人机收到雷达信号的强度(4次方根是依据了前
文中的假设(7)), 为了合理描述整条线段的探测威胁, 分别选取每条线段的1/2 ,5/6 ,和1/6 点处进行与威胁之间的距离作为衡量威胁程度的指标。L i 为第i 段路径段的欧氏距离. 无人机沿着Voronoi 图边的威胁代价可认为是飞过该边的积分,为了简化计算,将每条边进行离散,如下图所示:
上图中:边各边6等分后取其中3个点(1/6,3/6,5/6)代价的平均值来代替整条边的代价。从而得到第i 条边的雷达威胁代价如下:
444J t , i =L i ∑(1/d 1/6+d +d i , j 3/6i , j 5/6i , j ) /3
j =1N
针对问题中设计的航路中遇到多个影响航路规划的因素建立多目标模糊数学模型,目标函数模糊化的形式取决于隶属函数的选择。在论域 W上的模糊集合S ,对任意x(s)∈W ,都指定一个数y(x)与之对应,意味着建立了元素x 与模糊集合S 的映射关系,如下式:
Y s :W →[0,1] , x→Y s
式中,Y s (x ) 为隶属函数,在[0,1]闭区间中取值,Y s (x ) 的大小称为隶属度,反映了元素x 对模糊集合S 的隶属程度。
鉴于以上的解释, 对由燃油代价和雷达威胁代价建立的性能指标,选用降半梯形模糊分布函数来进行优化,其具有的物理意义就是:对单个目标函数f (x ) ,存在一个最高代价值M 和一个最低代价值m ,进行归一化,得到目标代价的隶属度函数Y s (x ) ,如下式:
⎧0⎪f (x ) -m (f (x ) ≤m ) ⎪Y s (x ) =⎨(m
燃油目标隶属度计算对于燃油目标函数,Voronoi 图第i 条边的燃油代价J f , i =L i ,取Voronoi 图所有边长度的最大值和最小值作为燃油代价的肘M 和m ,据上式可得第i 条边燃油代价的隶属度Y s (x ) 。
(三)雷达威胁目标隶属度计算
对于雷达目标函数,不可从Voronoi 图所有边的威胁代价中直接选取最大值和最小值做为M 和m 。
这是因为:
(1)雷达威胁的分布密度一般是不均匀的,在雷达分布密集区域,Voronoi 边上的雷达威胁代价与雷达分布稀疏区域的有很大的差距(因为四次方的关系将距离放大或者缩小了很多) ,甚至有几个数量级的差别。这样计算出的隶属函数是不遵从统计规律的,不能合理分配各条边的雷达代价。
(2)在某些情况下,威胁代价中的最大值或者较大值对应的Voronoi 边在实际威胁场中是很危险的,因为其很可能完全覆盖在雷达探测范围内,其探测概率很可能是在90%以上,是不能选的。因此,雷达威胁代价的M 和m 应参照实际的雷达探测模型进行选择,因代价隶属度本身是模糊优化的,故只需建立简化的雷达探测模型 即可,如下式:
⎡σ⎤p ∝⎢⎥⎣R ⎦1/4
式中,P 为反射回波强度; σ为飞机的雷达散射截面;R 为飞机与雷达的距离。 依据上式,计算第i 条边雷达威胁代价的隶属度Y s (x ) , 至此, 完成了燃油和雷达威胁代价的隶属度Y s (x ) 计算。
综上所述,提出基于隶属度函数的航迹性能指标为:
J =min ∑(kY f , i +(1-k ) Y t , i )
i =1n
式中,k 为燃油代价权值,取值0~1,是为了可以直观有效地表示决策者对某目标的偏好程度。
(四)航迹算法的规划
上面我队已经将两个代价的运算,进行了详细的解释,下面我队将开始分析在
以构造好的赋权Voronoi 图上,进行航迹算法的规划。我队采用了启发式加上A *搜索算法,结合变权分析的思想,建立动态权值启发函数进行航迹规划,以满足题目中给出的对根据实际需要进行实时局部修改。
启发式搜索就是在状态空间中对每一个位置进行评估,得到最好的位置,再从这个位置进行搜索,直到发现目标。在启发式搜索中,对位置的估价是十分重要的。用于节点重要性的函数称为估价函数,在此我们设为
为: f (x ) ,并定义其一般形式
f (x ) =g (x ) +h (x )
式中f (x ) 为从起点S 经过节点x 到达目标点T 的最优路径的代价估计值;g (x )为从起点S 到节点x 已经实际付出的代价;h(x)为从节点x 到目标点T 的最优路径代价的估计值,体现问题的启发性信息,称为启发函数。
理论依据如下:
启发函数的选取
启发式搜索方法是通过使用非低约束的函数,以可接纳性为代价来换取搜索效率,启发信息越多,约束条件越多,则排除的节点就越多,估价函数越好,但同时增加了h(x)的计算量和计算时间,实时性变差。故选择启发函数进行路径规划时需兼顾效率和准确性,选取原则应是使此路径的代价与求得此路径所需要的搜索代价的某些综合性能指标为最小。
依据搜索问题的规模,我们提出动态权值的估价函数方法,并定义估价函数如下:
f (x ) =g (x ) +wh (x )
式中,w 是一个正数,分以下情形讨论:
(1)w=0,意味着搜索过程不依赖任何启发信息来保证算法的可接纳性,此时算法蜕化成相同代价搜索,适用于状态空间待扩展节点规模不大的
情形。
(2)w为某个非0固定正值时,即为常权函数非常大的w 值为过分强调启发式部分,减少节点的扩展量;而非常小的w 会突出搜索的广度优先特性,
提高算法的准确性。
(3)w为动态权值,通过对搜索初、后期赋予不同的权值来实现在搜索初期以速度优先,在搜索后期以准确度优先的目的。针对基于Voronoi 图无人机航迹规划的状态图搜索,选取当前节点N 到目标点T 的直线距离d (N , T ) 作为启发信息,为与实际代价g(x)保持数量级的平衡,同样采用模糊隶属度概念建立启发函数如下:
h (x ) =d (N , T ) /d (S , T )
式中,d (S , T ) 为起始点与目标点的直线距离。选择动态权值w 与搜索树上当前节点的深度N n 成反比,即:
w 1/N n
即在浅深度时,w 较大,搜索初期主要依赖启发式部分,然而随着深度的增加,w 逐渐变小,搜索后期会逐渐以广度优先搜索为主。
依据所建立的性能指标和启发式搜索算法,选取不同燃油权值k 和启发函数的组合,可以相应的得到不同的路径选择。其中,动态权值w ,依照前式选取,航迹规划。单威胁点时,考虑节点代价(综合威胁系数,油耗),依临近威胁点作出单威胁点模型,找到最优路径,即与圆相切的过劣弧点,如下图所示。
基于以上这些理论,综合Floyd 算法求出的最短初始路径,基本路径图为:
路径的进一步修正得到的规划路径是在Voronoi 图中的最佳路径, 但是否适于
无人机实际飞行需求, 需要进一步细化修正, 修正主要考虑以下几个方面: ①能否进一步缩短飞行距离;
②相邻两条线段之间的夹角如果不满足最小转弯半径的限制时的处理;
③无人机的初始航向角与规划路径的起始航向角之间差异太大时的初始阶段处理。
(一)距离缩短处理
从Voronoi 图的定义和特点可以知道,Voronoi 图的边尽可能地规避母点, 因而Voronoi 图中的边尽可能远地绕开威胁。但是实际情况下只要能够规避威胁, 没有必要绕着每一个威胁走折线。因此可以通过直线化来进一步缩短飞行距离。方法如下: 设初始路径的各点为(x s , y s ),(x 1, y 1),(x 2, y 2)....(x i , y i ),(x n , y n ),(x t , y t ) 。(x s , y s ) 为初始点, (x t , y t ) 为目标点。路径上的节点数为n 个。则缩短路径处理按照以下步骤进行:
令当前点为目标点, 从当前点出发依次向其之前的点连线, 当发现连线穿越了威胁时, 记录该点之前的那个点为当前点, 把此当前点与上一个当前点之间的节点删除。重新以这个当前点出发在向前连线, 直至到达初始点为止,
(二)路径中拐角的平滑处理
由于初始路径是一系列路径段的衔接, 存在相邻两线段之间的夹角, 当夹角过于尖锐时, 必然带来无人机不能实现“急转弯”, 因此要对过于尖锐的角进行平滑过渡处理。在尖锐拐角处加入一端圆弧, 进行对应的平滑过渡处理。通常这个圆弧的半径选择为无人机的最小转弯半径, 满足无人机的机动性能约束, 并且保证构成该圆弧与相连的两条线之间相切才能够平滑过渡, 用得到的两个切点代替原来的拐角点, 示意图。 初始航向角处理当无人机的初始航向角与选择的第一段路径的方向之间存在较大的差距时, 需要进行航向角方面的修正。为了满足航向角的限制, 修正后的路径一定要首先沿着与其当前位置相连的圆弧进行飞行, 然后转入第二个圆弧, 第二段圆弧与第一段圆弧光滑连接, 并接入规划的第一段路径, 第一段圆弧与无人机初始航向光滑衔接。两个圆弧的连接点是路径从无人机当前状态到达期望路径的转接点。这两个圆弧的半径应等于或大于无人机的最小转弯半径。这样可以保证路径的出发点不改变, 只需稍作调整, 改变无人机的飞行航向角即可(如图所示)
经过以上的修正处理后, 得到的路径为无人机在给定威胁分布的战场环境的可
飞行的最优路径。
2、问题二模型的建立以及求解:
模型的建立:雷达的探测机理可知,在理想的情况下,三维时可以近似看作一个半
球,圆的半径R 表示雷达的有效探测范围,大圆平面以下为雷达盲区。规避雷达可采
用二维的规避方法(航线规避),上空间高度(地形规避),无人机动作主要有转
角和爬坡两种,其它的假设与问题一相同。从而我们采用了基于Voronoi 图在三维空
间中的扩展运用。
(一)问题求解:
规划约束航迹规划时必须考虑飞行器的物理限制 ,否则飞行器不可能按规划的航迹
飞行。另外,低空飞行器的每一次飞行都是为了完成特定的飞行任务,在具体的飞
行任务中可能会有一些具体要求:
(1)最小转弯半径/最大转弯角度:它限制规划的航迹只能在小于或等于预先确定
的最大角度范围内以大于最小转弯半径进行转弯。该约束取决于具体飞行器的
性能和飞行任务要求。
(2)最大爬升/俯冲角:由飞行器自身的机动性能决定。它限制了航迹在垂直平面
内爬升和下滑的最大角度。
(3)最小航迹段长度:用于保证飞行器在能够在完成一个动作之后能顺利完成下一
个动作必须保留的最短距离。主要由最小转弯半径及最大转弯角度确定。
(4)最低飞行高度:在通过敌方防御区域时,需要在考虑碰地/撞山概率的情况下尽
可能低的高度上飞行,以减少被敌防御系统探测到并摧毁的概率。一般在保证离
地高度大于或等于某一给定高度的前提下,使飞行高度尽可能低。
在航迹满足前述各约束之后,目标函数主要考虑两个主要因素:较短的航程、
飞行高度尽可能低。
首先根据数据建立数字地图,数据如表:
建立地形高度矩阵z ;
⎛a 11 a 1n ⎫ ⎪Z = ⎪, a 为高度,m ,n 平面坐标位置。 a ⎪⎝m 1 a mn ⎭
利用MATLAB 编程解决,利用二次曲面插值算法,如下所示:
x=[0:1:20];
y=[0:1:20];
z=[0.2,0.2,0.2,0.2,0.2,0.2,0.2,0.2,0.2,0.2,0.2,0.2,0.2,0.2,0.4,0.7,0.4,0.2,0.4,0.5,0.3;
0.2,0.2,0.3,0.2,0.2,0.3,0.2,0.2,0.2,0.2,0.2,0.1,0.2,0.4,0.3,0.6,0.5,0.3,0.3,0.3,0. 2;
0.2,0.3,0.4,0.4,0.2,0.2,0.2,0.3,0.2,0.2,0.2,0.2,0.2,0.2,0.2,0.5,0.7,0.4,0.4,0.3,0. 3;
0.2,0.3,0.3,0.6,0.3,0.4,0.3,0.2,0.2,0.3,0.6,0.4,0.3,0.2,0.4,0.3,0.8,0.6,0.7,0.4,0. 4;
0.2,0.3,0.3,0.7,0.6,0.6,0.4,0.2,0.3,0.5,0.8,0.8,0.3,0.2,0.2,0.8,1.3,0.9,0.8,0.8,0. 4;
0.2,0.3,0.6,0.9,0.8,0.8,0.6,0.3,0.4,0.5,0.4,0.5,0.4,0.2,0.5,0.5,1.3,0.6,1,0.9,0.3; 0.3,0.5,0.9,1.1,1,0.7,0.7,0.4,0.6,0.4,0.4,0.3,0.5,0.5,0.3,0.9,1.2,0.8,1,0.8,0.4; 0.3,0.5,0.8,1.1,1.1,1,0.8,0.7,0.7,0.4,0.5,0.4,0.4,0.5,0.4,1.1,1.3,0.7,1,0.7,0.6; 0.4,0.5,0.4,1,1.1,1.2,1,0.9,0.7,0.5,0.6,0.3,0.6,0.4,0.6,1,1,0.6,0.9,1,0.7; 0.3,0.5,0.6,1.1,1.2,1,1,1.1,0.9,0.4,0.4,0.5,0.5,0.8,0.6,0.9,1,0.5,0.8,0.8,0.9; 0.3,0.5,0.9,1.1,1.1,1,1.2,1,0.8,0.7,0.5,0.6,0.4,0.5,0.4,1,1.3,0.9,0.9,1,0.8; 0.3,0.3,0.5,1.2,1.2,1.1,1,1.2,0.9,0.5,0.6,0.4,0.6,0.6,0.3,0.6,1.2,0.8,1,0.8,0.5;
0.2,0.3,0.4,0.9,1.1,1,1.1,1.1,0.7,0.4,0.4,0.4,0.3,0.5,0.5,0.8,1.1,0.8,1.1,0.9,0.3; 0.2,0.2,0.9,1.1,1.2,1.2,1.1,1.1,0.6,0.3,0.5,0.3,0.2,0.4,0.3,0.7,1,0.7,1.2,0.8,0.4; 0.2,0.4,1,1,1.1,1.1,1.1,1.1,0.6,0.3,0.4,0.4,0.2,0.7,0.5,0.9,0.7,0.4,0.9,0.8,0.3; 0.2,0.3,1,1,1,1.2,1,1.1,0.8,0.3,0.2,0.2,0.2,0.5,0.3,0.6,0.6,0.8,0.7,0.6,0.5; 0.2,0.2,0.9,0.7,1,1,1,0.7,0.5,0.3,0.2,0.2,0.2,0.6,0.2,0.8,0.7,0.9,0.5,0.5,0.4; 0.2,0.2,0.4,0.2,1,1.1,0.9,0.4,0.3,0.3,0.5,0.3,0.2,0.2,0.2,0.7,0.3,0.6,0.6,0.3,0.4; 0.2,0.3,0.3,0.2,0.3,1,0.4,0.5,0.3,0.3,0.3,0.3,0.2,0.2,0.2,0.6,0.5,0.4,0.4,0.2,0.2; 0.3,0.2,0.2,0.2,0.2,0.4,0.3,0.3,0.3,0.3,0.4,0.2,0.2,0.2,0.2,0.4,0.4,0.4,0.3,0.2,0. 2;
0.2,0.2,0.2,0.2,0.2,0.2,0.4,0.4,0.3,0.2,0.3,0.2,0.1,0.2,0.2,0.4,0.3,0.2,0.2,0.2,0. 2;]
x1=0:0.2:20;
y1=0:0.2:20;
[x2,y2]=meshgrid(x1,y1);
t11=interp2(x,y,z,x2,y2,'cubic');
surf(x1,y1,t11)
colormap, colorbar;meshc(x1,y1,t11)
xlabel('X/km');
ylabel('Y/km');
zlabel('Z/km');
axis([0 20 0 20 0 1.3])
hidden on
title('三维无人机飞行地形图');
从而绘制的三维地形图如下:
(二)基于三维空间的 A *算法进行分析:
这种基于A *自主搜索的在线三维路径规划方法,该方法将规划分为离线和实时两部分。离线部分工作就是建立一个飞行器的“运动模块”库,在线部分工作就是用A *算法将可实现的运动模块进行排序,形成规划航迹。以上基于A *搜索的各种三维航迹规划,大多从减少搜索空间或者减少计算机在线计算量去提高算法的效率。于是我们提出了一种基于A *搜索的飞行器三维航迹规划方法。该方法不但结合飞行器的性能对扩展邻点进行了约束,减少了搜索空间,并且通过改进启发函数,减少了扩展节点数,提高了搜索效率。在
效率地找到最优路径。A *算法中,恰当的启发函数可以高
式中,μ为距离在代价函数计算中的权系数;D 1(m ) 为从当前点m 到目标点的直线距离。该启发函数启发信息较少,对解的搜索时间比较长。本文用当前点m 到目标点的折距D fold (m ) 来代替式中的D 1(m ) ,对启发函数进行改进。由于改进后的启发函数可以获得更多的启发信息,因此可以改善算法的搜索效率。
定义:将三维空间划分为一个个长方体,任意两顶点i 和j 之间的折距D fold (i , A *算法用于飞行器航迹规划时,通常的启发函数取为: h 1(m ) =μD 1(m ) j ) 是用长方体各边长、面对角线及体对角线连接这两点,所有的连接路径中最短路径的距离。
例如:搜索空间被划分为一个个长方体,每个长方体的8个顶点(A,B ,C ,D ,E ,F ,G 和H) 的空间网格坐标随之得以确定。设长方体沿X ,Y ,Z 轴各方向上的边长分别为 R 1x ,R 1y ,R 1z 。平面x-y ,平面y-z ,平面z-x 平面上的各个面对角线分别为R 2xy ,
R 2yz ,R 2xz ;体对角线为R 3 。如图所示。
设i 点坐标为(i x , i y , i z ) ,j 点坐标为(j x , j y , j z ) 。两点沿各轴方向网络坐标差为:
n x =i x -j x
n y =i y -j y
n z =i z -j z
令
L min (i , j ) =min {n x , n y , n z }
L mid (i , j ) =mi d {n x , n y , n z }
L max (i , j ) =max {n x , n y , n z }
则折距的计算表达式为:
D fold (i , j ) =R 3L min (i , j ) +R 2L mi d -L max [L mi d (i , j ) -L min (i , j ) ]+R 1L max [L max (i , j ) -L mi d (i , j )] 式中:R 2L mi d -L max (i , j ) 为L min (i , j ) 与L max (i , j ) 对应坐标面上的面对角线;
ij (, ) 为X —Y 面上的对角线为R 2xy ,若L max (i , R 1L max (i , j ) 为L max (i , j ) 对应的坐标轴方向上的边长。如:若L mid (i , j ) 为n x ,
L max (i , j ) 为n y ,则R 2m i L x dL a m -
为n y ,则R 1L max (i , j ) j ) 为长方体沿Y 轴方向上的边长R 1y 。
特殊情况下,当网格为正方体时,边长为R 1,面对角线为R 2,体对角线为R 3,如图2所示,A 点的网格坐标为(0,0,0) ,B 点坐标为(4,2,1) ,则由式(2)可知,A 点到B 点的折距长度应为1R 3+1R 2+2R 1。即线段AC 、线段CD 与线段DB 之和。
网格A 算法中,设D (m)为计算点m 到目标点的折距,取新的启发函数为:
h 2(m ) =μD fold (m )
设应用启发函数h 1(m ) 的
算法A 1: A *算法为A 1。,对应为航迹规划器1,应用启发函数h 2(m ) 的A *算法为A 2,对应航迹规划器2。
⎧f 1(m ) =g (m ) +h 1(m ) ⎪⎨g (m ) =τP th (m ) +μD 1(m ) ⎪h (m ) =μD (m ) ⎩11
算法A 2:
⎧f 2(m ) =g (m ) +h 2(m ) ⎪⎨g (m ) =τP th (m ) +μD 1(m ) ⎪h (m ) =μD (m ) ⎩22
从两个启发函数的定义可知,h 1(m ) 的信息度高于h 2(m ) ,更加接近于h 则*(m ) 。A *得到的解必然是A 1的解,且A 1扩展点数不可能比A 2的多。由于扩展节点
的数目影响算法的运行时间,因此,算法A 2的运行时间不会多于A 1。 航迹优化
低空飞行希望有最短的航程,同时希望飞行的高度尽可能低,同时要满足飞行器的机动性能约束。上述要求和约束一般情况下是有矛盾的,把约束条件考虑到评价函数的设计中,通常的解决方法是根据要求进行加权。这里每条航迹的评价函数取为雷达或其它手段所能提供的探测距离来选取,两者之和应小于探测距离。
F 1= 在飞行器从(x1,z1 ) 飞行到(x3,z3) 的过程中,重新初始化规划起点,将(x4,z4) 作为新的当前位置再向前规划,其中z4= z3+ L;
滚动实施上述过程。这种方法边飞行边规划,是一个不断改进,循环
往复的过程,直到飞至目的地。需要注意的是,由于每次规划只知道起点,终点是未知的,所以前面讨论的航迹规划方法要做相应地改动。
首先,搜索空间的削减只能利用上式,从而搜索空间变为[a1,a2,⋯ an ]。其次,利用粒子群优化算法规划航迹时,航迹评价函数改为
F 2=F 1+
而且这个评价函数的计算涉及到的只是局部信息,起反馈校正作用,同时增加的一项用来驱使飞行器飞向终点。
最终通过matlab 程序进行本问题信息模拟从而得到最终的航路图如下:
3. 问题三 :我队所建模型的可行性分析及仿真分析
(一)模型的可行性分析:
首先,请允许我介绍我队解决无人机航迹规划问题的基本模型流程图:
图的特性是非常有必要的。现特介绍Voronoi 图的部分特性如下:
①每个Voronoi 多边形内仅含一个母点;
②Voronoi 图多边形内的点到相应母点的距离最近;
③位于Voronoi 多边形上的点到其两边的母点的距离相等;
④Voronoi 图的每一个顶点恰好是图的三条边的公共交点;
⑤Voronoi 图的顶点是由原来的母点中的三个点确定的圆心
从上面Voronoi 图的构造过程以及刚提到的特性可以看出,Voronoi 图中各个边到对应母点距离相等, 如果将战场区域中的威胁中心作为图的母点, 又根据无人机被发现的概率是与飞机到雷达距离的四次方成反比的。则有Voronoi 图的边是能够最好规避对应的两个威胁的线段, 因此把Voronoi 作为战场危险的图形分解模型是可靠的,经得起推敲的。
在既要考虑安全性,又要考虑最短路径的问题的时候,因为这两种因素之间没有某种必然的联系于是我们采取建立多目标模糊数学模型来解决这个问题。这主要是因为模糊数学是以不确定性的事物为研究对象的研究,它将确定性对象的数学与不确定性对象的数学沟通起来,使得过去精确数学、随机数学描述不足之处得到弥补。这完全符合本题发要求。因此在这块voronoi 边的威胁度上的计算模型也是合理的。
(二)模型及算法的仿真分析
由于问题一二均为单起始点问题,因此以上的航迹计算过程实际上就是仿真过程。在此就不再一一赘述。在MATLAB 7.0
下进行仿真计算得到初始航路示意图:然后运用三次样条插值对初始航路光顺优化, 得到可飞航路。如下图:
在第二问中,我们采用了一种改进的A *搜索算法进行了飞行器的三维航迹规划仿真。该方法不但航迹规划中A *算法常用的启发函数,减少了扩展节点数,缩小了搜索空间,且根据飞行器的实际性能对邻点进行了约束。经过得出的结果表明(见我队基于数字地图信息建立的等高线上的航迹图形,在下面显示),该方法可
用于实时三维航迹规划。节点扩展以广度搜索优先,即航迹逐渐靠近最优航迹,体现了算法的准确性。结果验证了采用启发式搜索进行航迹规划具有的有效性和灵活性。事实上,本方法也可在给定威胁权值W
的情况下计算其他目标点。
(三)模型的优缺点
缺点:
1. 根据voronoi 图的性质,voronoi 忽略了两个点的假设威胁不等价性:即
母点到边上的威胁不一样。此时voronoi 图边上的点就不能获得最大的安全系数。
2. 没有考虑任务的时间承受能力,而且航迹规划不一定是最好的,甚至有些
粗糙。
3. 无法考虑战场的情况变化,既不能进行动态规划。
优点:
1. 该算法效率比较高,可以比较快速的找到比较符合条件的航路
2. 可以根据要求在安全性和最短路径中进行选择,体现决策者的偏好
参考文献:
1. 赵文婷 彭俊毅 ,《基于voronoi 图的无人机航迹规划》,系统仿真学报,18卷增刊2,2006年8月
2. George F Luger.Artificial Intelligence:Structures and Strategies for Complex Problem Solving[M] Beijing:China Machine Press.2003
3. 冯慧 屈香菊,《基于多目标模糊优先方法的无人机航迹规划》,飞行力学,第25
卷第2期,2007年6月
4. 唐强 张翔伦 左玲,《无人机航迹规划算法的初步研究》,航空计算技术,第33卷第1期,2003年3月
5. 马云红 周德云,《无人机路径规划算法与仿真》,活力与指挥控制,第32卷第6期,2007年6月
6. 张雅妮 高金源,《一种基于改进
26卷第1期,2008年2月
7. 薛长虹,于凯. 大学数学实验——MATLAB 应用篇. 成都:西安交通大学出版社,2003.10 A *算法的三维航迹规划方法》,飞行力学,第