无人机航迹规划优化模型.docx

《无人机航迹规划优化模型.docx》由会员分享，可在线阅读，更多相关《无人机航迹规划优化模型.docx（25页珍藏版）》请在三一办公上搜索。

1、2007高教社杯全国大学生数学建模竞赛承诺书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮 件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问 题。我们知道，抄袭别人的成果是违反竞赛规则的，如果引用别人的成果或其他 公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正 文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反 竞赛规则的行为，我们将受到严肃处理。我们参赛选择的题号是（从A/B/C/D中选择一项填写）：A我们的参赛报名号为（如果赛区设置

2、报名号的话）：20004005所属学校（请填写完整的全名）：中南大学参赛队员（打印并签名）：1.2. 王雄3. 王泽指导教师或指导教师组负责人（打印并签名）：日期：2008年8月11日赛区评阅编号（由赛区组委会评阅前进行编号）：无人机自主飞行航迹规划摘要本文对无人机自主飞行航迹的二维规划和三维规划问题根据所给要求分别 建立了动态规划模型，并对模型进行了可行性分析和仿真分析，最终求得最优的 规划路线（见附录表1，表2）。首先，对于问题1，无人机自主飞行航迹的平面规划问题，我们采用传统的 图论方法，使用Voronoi图【1】对雷达威胁网络进行划分；并以雷达威胁度和 路程代价为主要考虑因素对Voro

3、noi图的每条边赋予权值，得到一个权矩阵，通 过Dijsktra算法求得出发点到目标点的最优路径。但是我们考虑到这种算法实现 较难，而且Voronoi图不可推广到三维航迹的规划问题上，因此我们通过假设条 件消除其后效性，建立了动态规划模型，并且为了增加模型精确度，将地图以 100米为单位网格化。其次，对于问题2,将问题推广到三维空间，增加了地形因素以及飞机飞行 的性能，即考虑到飞机飞行时转弯和地形影响的因素。我们使用matlab对该三 维空间进行了模拟【2】，并由平面的动态规划模型通过对每点增加高程z，对飞 机的转弯性能最小转弯角进行简化，增加地形约束条件，建立了以无人机飞行路 线广义代价为目

4、标函数的动态规划模型。再次，我们对所建立的动态规划模型做了可行性分析和仿真分析，通过对比 在广义代价方程中各个因素的权重系数的不同取值，得出不同的规划路线，最终 得出最优的规划路线，并肯定了模型的正确性。最后，我们对于此动态规划模型进行综合评价，并提出了此模型在实际条件 中应用所欠考虑的部分，并在模型的推广中对其他实际因素进行了具体的分析并 加以改进和完善。关键字Voronoi图动态规划模型广义代价代价方程仿真分析一、问题的重述1.1问题背景无人机的发展至今已有70多年的历史，其军事应用主要是遂行各种侦察任 务。随着无人机平台技术和机载遥感技术的不断发展，它的军事应用范围已经并 将继续扩展，如

5、通信中继、军事测绘、电子对抗、信息攻击等。特别是精确制导 武器技术的发展，又使它成为这种武器的理想平台。众所周知自主飞行的能力是无人驾驶飞机所必须具有的。如果要实现无人驾驶飞 机的自主飞行，则要求具有相当程度的飞行航迹规划能力。无人机的航迹规划是 为了圆满完成任务而作的计划。它往往指单机在初始位置、终止位置和一些目标 任务结点确定之后的航迹规划问题，其基本功能是根据无人机的性能和飞经的地 理环境、威胁环境等因素，对已知的目标规划提出满足要求的航迹，以便在实际飞 行时可以根据需要进行实时局部修改。现在我们讨论如下的情况：假定无人机的活动范围为20kmX20km的区域，无人机起点的平面坐标为 1,

6、2（单位：km）,攻击目标的平面坐标为19,18（单位：km）,同时不考虑无人 机起飞降落时的限制。数字地图和敌方威胁情况（主要考虑雷达威胁）已在附件中 给出。数字地图可以做适当的简化，比如可以把地形近似分为三种：高地，低地 以及过渡地带。1.2基本信息附件一：雷达威胁的坐标方位表。附件二：数字地图。1.3问题的提出问题1：忽略地形和无人机操作性能等因素的影响，综合考虑敌方威胁，无 人机航程等，基于二维平面建立单机单目标的航迹规划模型。问题2：把模型扩展到三维空间，并同时考虑无人机的操作性能（主要考虑 拐弯）和地形因素。问题3：试讨论和分析你提出的模型的可行性，并做仿真分析。二、问题的分析2.

7、1背景资料航迹规划是指在考虑环境、任务和飞机性能等一系列约束条件得前提下，为 飞机规划出一条从起点到终点的可飞路径。无人机航迹规划约束条件复杂、规划 空间广、任务多样、不确定因素繁多，尤其难于确定多人机协同执行任务的协同 规划解。目前在无人机航迹规划上已有的方法基本有如下几种：1.以分层航迹规划的 思想为基础建立的根据任务飞行环境由Voronoi图生成初始航路，根据考虑的各 个约束条件，赋予各航路相应的权值，最终从路径空间中搜索出最优的航迹；2. 基于蚁群算法的无人机航路规划方法；3.基于基因算法的航路规划方法。2.2问题分析在实际的无人机航路规划问题上其不确定性因素繁多，约束条件复杂，我们

8、这里突出题目的主要因素，即无人机执行任务时躲避雷达探测威胁和燃油代价， 忽略无人机操作的性能，无人机起飞和降落的限制等次要因素考虑航路的规划。首先我们根据所给雷达威胁的坐标方位表做出Voronoi图，采用传统的图论 算法的思路建立了模型，但是我们在求解模型的算法实现上，考虑到其在算法复 杂度相当高，以及其只适用于简单的二维图的航路规划问题，无法拓展到三维的 实际模型中应用。因此我们根据我们的需要，建立了动态规划模型对问题进行求 解。三、问题的假设1）不考虑无人机起飞降落时的限制2）不考虑风、雨等对飞机性能的影响；3）飞机的性能于飞机的飞行距离无关，即飞机在执行任务中性能不变;4）飞机燃油量和飞

9、行距离成正比；5）雷达信号强度与其距离的四次方成反比；6）飞机燃料无限，在避开威胁的情况下能到达目的地；7）不考虑无人机起飞降落时的限制a* I aijV aix ayWai四、符号说明:表示各垂直平分线的交点；:表示无人机行驶路径；:表示a上的点 ij:a横坐标；i:a纵坐标；ii :表示a点被雷达探测到的危险度；b :表示雷达点;b （b ,b ）；k kx ky:表示点“与点bk的距离;labJ.L U ）j :水平路径长度；a :飞行距离权重系数；1-a :被雷达探测到的危险代价权重系数；Di :由i点到j点的广义代价； :雷达探测强度系数五、模型的建立与求解5.1问题1忽略地形和无人

10、机操作性能等因素的影响，综合考虑敌方威胁，无人机航程 等，基于二维平面建立单机单目标的航迹规划模型。5.1.1模型1根据题目中所给出的雷达威胁点坐标方位表，我们做出Voronoi图，建立了 以形式路线的广义代价为目标函数的模型。无人机飞行路线的燃油代价正比于飞行距离即可以简单的假设飞行边这里我们简单的假设雷达探测强和其距离的4次方成反比，贝上无人机经过路线的雷达威胁代价为： ij阡 J）（V bk ）+J -如 片Ix kx y byJ Xy g ijm：雷达数；则行驶每条边的广义代价为：D =0X3）+（i_（x）.vvijijai将每条边Q的广义代价。赋予Q上得到，以行驶广义代价为权的权矩

11、 ijij阵，引出0T变量Xijfo 表示1路线未被选中Xijij 1表示1路线被选中Iij无人机航行路线的总广义代价：mind = Yx *D5. 1. 2模型2将地图以100米为单位模拟成网格图，此时表示网格中的节点。a a m Sa a -a ）出发点s到目标点f做目标向量 s,t t,x s,x t,y s,yk表示选中路线中的点；其周围相邻点q ；q = k-l,k + l,k-n-l,k-n,k-n + l,k + n-l,k + n,k + n + l这里要求飞机是朝日标点飞行，即朝前行驶则有飞行路线向量与目标向量乘T（q）=m .m o积为正：q m 口，保证飞机飞行路线的无后

12、效性。L疽jy飞行边l距离代价L为:无人机经过规划路线的雷达威胁度代价为：w =室 0 一湾，.1i = 1 k = 1aibk4i=1 k =1jObyn：所规划路线的节点数;m:雷达数；则目标函数无人机航行路线的总广义代价:min D = a lCa)+(ia)wijaii,j=1；stT(q)=m m 05.1 问题 2把模型扩展到三维空间，并同时考虑无人机的操作性能（主要考虑拐弯）和 地形因素。5.2.2模型的建立1. 模型的假设：1）不考虑风、雨、云等自然条件对无人机的影响；2）无人机的燃料充足即可以完成任务并返回出发点；3）无人机的性能在执行任务过程中是不变的，即不考虑疲劳等因素；

13、4）无人机在到达目标点上空即可执行任务，即不必降落至地面；由于模型扩展到三维空间，给出了数字地图，需要考虑到地形因素，因此建 立空间坐标系，地图上每一点增加高程坐标z；对数字地图用matlab进行模拟 如下图1：图1地形模拟图2. 无人机水平最大转角为0，竖直最大转角为甲；3.无人机飞行高度限制为0 % z o飞行边a距离代价j）为： ij L /孔）+ 4-疽 + 1则所规划路线相邻两条线q T S T k的广义代价可表示为:D = D + r l 品)+ r w + r (a - a ) s, ks, q1 qk 2 k 3 kz qzmin D s, qT (Q ) 0,Ds, S =

14、0, r +r 2+r 3=1St q,，/ + tan 00a -aq,xk,x0 z 0因此可以将飞机的每一步飞行方向确定为4个，如下图，图2所示:由于我们模型中考虑到雷达威胁度和距离代价两个必要因素，这里我们取距离代价权重系数冬=。，经过模型求解得到飞机飞行航迹坐标点具体结果参见附录表1,对航迹路线我们用matlab进行了模拟如下图，图3所示:200图3航迹路线二维模拟图其中绿色点表示无人机任务起始点和任务目标点、红圈代表雷达威胁点、蓝 色路线表示无人机规划路线。由图中可以看出所得结果我们在考虑雷达威胁度为主要因素的情况下，规划 路线是符合要求的。5.3.1三维仿真分析可行性分析：1.

15、增加了高程坐标z，和地形约束，在无人机航行路线首先确定只能在空 中搜索路线。2. 在三维空间中飞机所在点有八个正方体围成，其相邻点共有26个，考虑 到无人机行驶方向，做目标向量m =at a ，气-a ，气-a)，飞行路5 ,tt, xs, x t, ys, y t, zs, z线向量与目标向量乘积为正：t (q)=m m 0.将飞机每一步飞行方向锁定到9个，如图4所示:图4飞机飞行方向示意图3. 在我们所规划的路线条件中，无人机行驶路线中的最大转角为在200米的 路程内完成90度的转弯，我们假设无人机可以完成此最大转角。4. 我们对任务的执行做出如下假设，飞机可以在目标点上空执行任务，即飞

16、机规划路线到达目标点上空即可，无需着陆。5. 根据所建立的动态规划模型进行求解，这里我们任然突出雷达威胁度因 素，取r 1 1，得出无人机三维航迹路线坐标方位点参见附录表2。采用matlab对路线进行模拟如下图，图5所示:图5无人机航迹路线三维模拟图由图5的模拟路线我们可以看到，当我们将雷达危险度为主要考虑因素时， 动态规划模型规划出以竟可能高的飞行路线来达到广义代价最低，这种结果是符 合我们假设和要求的。通过仿真分析得出我们建立动态规划模型在二维和三维的无人机航迹路线 的规划中的正确性和优化性。六、模型的优点与不足通过仿真分析，可以看出，采用动态规划模型进行无人机航路规划明显优于 采用传统的

17、图论方法进行航路规划。首先在规划路线的实时性上，动态规划模型 是根据当时时刻的雷达威胁度，来进行路线规划，其准确度更高；而采用Voronoi 图对雷达威胁网络进行划分，忽略了很多重要的因素，其路线选定只局限于两相 邻雷达中垂线上，但对于较多雷达综合考虑其威胁度并不一定是最小，因此路线 并不一定是最优。其次在算法复杂度上，采用Dijsktra算法较为低级，对于复杂 情况其时间复杂度相当高；而采用动态规划模型，其状态转移是无后效性的，规 划路进必然最优，因此其时间复杂度很小。再次，采用简单图论方法解决无人机 航路问题，不能推广于真实的三维空间中；而动态规划模型则只是增加竖直坐标， 即可将二维动态规

18、划模型改进为三维空间的动态规划模型。在本题中给出的条件，由于地图限制，和雷达位置的限制，其考虑范围为20成x20km ；而根据所查资料现在一般雷达的侦查范围为300kmx5000km ；飞 机的最大飞行高度为10km以上。因此我们在这次问题模型的建立中无法使用真 实的数据进行分析，很多未知量都是通过简化假设来确定的，因此必修通过实际 的数据进行修改才可以达到准确性和实用性。七、模型的推广在我们建立的动态规划模型中，以雷达威胁性为主要因素，并考虑路程代价 于雷达威胁代价综合的广义代价为目标，使规划路线很好的符合了所提出的要 求。对于动态模型的推广应用我们考虑到如下几个方面：1.在考虑各项实际因素

19、，除雷达探测威胁以及燃油代价外，增加地形、高 度信息、目标范围、飞行器指令等因素我们得到如下代价方程来描述性能指标：D = Z(wT + w M + w H + w N + w P ) w w w w w1 i 234 K 5；1 2 3 4 5 均为常数；T i为威胁场对各路径点的威胁值之和；M为地形对各路径点的威胁 值之和；H为飞行器的高度信息，N k为经过目标范围的路径点编号；P飞 行器指令变化总和。2.路径规划出的是由各个航点连线组成的线路，因此并不符合无人机实际飞 行的路线，因此对其路线转弯处需要做光滑处理【3】：1)，最小离地间隙设无人机的安全离地高度为upch受法向超载限制的最大

20、爬坡度为masl如图5图5 最小离地间隙 由此，无人机的最小离地间隙：(10)Min clearnce = upch x cos(masl)2）地图的平滑处理4实际地形测绘的地形数据用于山地低空任务是，必须进行平滑处理。平滑处理的地形坡度要不大于无人机的最大爬升坡度masl，如图6图6地形坡度3. 由于现在科技飞速的进步，无人机的飞行性能和雷达的探测性能已经不能 局限于无人机飞行距离在几十千米，飞行高度在几千米的范围；雷达探测范围在 几千米的范围内。而且考虑到实际战场中的条件，在考虑到无人机飞行代价方程 中，各种代价因素应以雷达探测威胁作为最主要因素作为考虑。因此各种因素的 权重系数是决定最终

21、规划路线的决定性因素，因此在实际情况中，各项代价的权 重系数的确定尤为重要。动态规划模型可以根据不同的实际条件增加适当的约束 条件和代价，较为准确的规划出符合目标要求的最优路线。参考文献【1】彭建亮朱凡孙秀霞孙彪基于离散PSO和Voronoi图的无人机航迹规划 方法研究【2】王沫然编著的MATLAB与科学计算，电子工业出版社，北京，2008年2 月【3】唐强，张翔伦，左玲 无人机航迹规划算法的初步研究附录表一:表二：二维路线坐标点三维路线坐标点单位百米单位百米xyxyz190180190180201901791901792019017819017820190177190177201901761

22、901762019017519017520190174190174201901731901732019017219017220189171190171201881701901702018716919016920186168189168201851671881672018416618716620183165186165201821641851642018116318416320180162183162201791611821612017816018116020177159180159201761581791582017515717815720174156177156201731551761552

23、017215417515420171153174153201711521731522017015117215120169150171150201681491701492016814816914820167147169147201661461681462016514516714520165144166144201641431641421631411621401621391611381611371601361601351591341591331591321581311581301571291561281551271541261531251521241511231501221491211481201

24、471191461181451171441161431151421141411131401121391111381101371091361081351071341061331051321041311031301021291011281001661651641641631621611601591581571561551541531521511501491481471461451441431421411401391381371361351341331321311301291281271261251241432014220141201402013920138201372013620135201342

25、013320132201312013020129201282012720126201252012420123201222012120120201192011820117201162011520114201132011220111201102010920108201072010620105201042010320102201022010220123122121120119118117116115114113112111110109108107106105104103102101100999897969594939291908988878685848382818010220102201022010

26、220102201022010220102201022010220102201022010220102201022010220102201022010220102201022010220102201022010220102201022010220102201022010220102201022010220102201022010220102201022010220102201022010220102201279912698125971249612395122951219512095119961189611796116961159611497113971129711197110981099810

27、898107981069910599104991031001021001011001001009910198101971019610295102941029310292103911039010389104881048710486105851058410583106821068110680107791077810777108761087510874109731097210971110701106911068111671116611265112641126311362113611136011459114581145711456114551135411253111521105110950108491

28、074810647105461044510344102431014210041994098791022078102207710220761022075102207410220731022072102207110220701022069102206810220671022066102206510220641022063102206210220611022060102205910220581022057102205610220551022054102205310220521022051102205010220491022048101204710020469920459820449720439620

29、429520419420409320399220389120379020368920358820348720338620328520318420308320298220288120278020267920257820247720237620227520217420207320197220187120177020166920156820146720136620126520116420106320106220106120106020105920105820105720105620105520105420105320105220105120105020104920104820104720104620

30、104520399738963795369435933492339132903189308829872886278526842583248223812280217920781977187617751674157314721371127011691068106710661065106410631062106110601059105810571056105510541053104420105210432010511042201050104120104910402010481039201047103820104610371910451036181044103517104310341610421033

31、1510411032141040103113103910301210381029111037102810103610279103510268103410257103310246103210235103110224103010213102910203102810271026102510241023102210211020二维路线规划源程序：program zousyo(input,output);constbei=10; sx=1; sy=2; ex=19; ey=18;varans:real;filein,fou:text;lx,ly:array1.8of longint;tx,ty:arra

32、y1.4of longint;a,c:array-1.20*bei+1,-1.20*bei+1of real;wx,wy:array-1.20*bei+1,-1.20*bei+1of integer; procedure fileinput;vari:longint;beginassign(filein,t.txt);reset(filein);for i:=1 to 8 doreadln(filein,lxi,lyi);close(filein);end;procedure pro1;vars,f,dx,dy:real;x,y,i:longint;beginc1*bei,2*bei:=1e-

33、30;tx1: = 1; ty1:=0;tx2: = 1; ty2: = 1;tx3:=0; ty3: = 1;tx4:=1; ty4:=-1;for x:=0 to 20*bei dofor y:=0 to 20*bei dofor i:=1 to 8 dobegindx: = (lxi*bei-x);dy: = (lyi*bei-y);s:=sqrt(dx*dx+dy*dy);if s=0then s:=0.1;f:=1/s/s/s/s;ax,y:=ax,y+f;end;end;function run1(x,y:longint):real;vari:longint;s,min:real;

34、beginif cx,y0then beginrun1:=cx,y;exit;end;min:二maxint;for i:=1 to 4 doif(x-txi=0)and(x-txi=0)and(y-tyi=20*bei) then begins:=run1(x-txi,y-tyi);if sminthen beginmin:=s;wxx,y:=x-txi;wyx,y:=y-tyi;end;end;cx,y:=min+ax,y;run1:=cx,y;end;procedure outit;varx,y:longint;beginassign(fou,ans.txt);rewrite(fou);

35、x:=ex*bei;y:=ey*bei;writeln(fou,ans:0:8);repeatwriteln(fou,y);x:=wxx,y;y:=wyx,y;until (x=sx*bei)and(y=sy*bei);writeln(fou,x, ,y, ,0);close(fou);end;beginfileinput;pro1;ans:=run1(ex*bei,ey*bei);outit;end.三维路线规划源程序：program shione(input,output);constex=190; ey=180; vark,bk:longint;ans,min:real;fin:text

36、;tx,ty,tz:array1.9of longint;lx,ly:array1.8of longint;h:array-1.201,-1.201of real;a,c:arrayT.201,-1.201,T.201of real;wx,wy,wz,bx,by,bz:arrayT.201,-1.201,T.201of integer; procedure filein;vari,x,y:longint;beginmin:=maxint;assign(fin,t.txt);reset(fin);for i:=1 to 8 dobeginreadln(fin,lxi,lyi);lxi:=lxi*

37、10;lyi:=lyi*10;end;for x:=20 downto 0 dobeginfor y:=0 to 20 dobeginread(fin,hx*10,y*10);hx*10,y*10:=hx*10,y*10*10;end;end;close(fin);end;procedure pro;vardx,dy,dz,s,f,p:real;x,y,z,i:longint;begintx1: = 1; ty1:=0; tz1:=0;tx2:=0; ty2: = 1; tz2:=0;tx3: = 1; ty3: = 1; tz3:=0;tx4: = 1; ty4:=0; tz4: = 1;tx5:=0; ty5: = 1; tz5: = 1;tx6: = 1; ty6