飞行管理问题的实时算法 复旦大学谭浩南朱正光刘剑 指导教师蔡志杰 编者按该文以区域内飞机调整飞行角幅度的平方和为目标函数,以自调整时刻起 0.3小时内飞机两两不发生碰撞为约束条件,建立了一个非线性规划模型,用逐步求精的直接 索和引人罚函数,化为无约束极值,用序列无约束最小化(SMT)两种方法进行求解 作者在建模和求解时从实际需要出发,精益求精,将上述两种方法相结合,得到了精度高 基本上是实时的方法与程序,还对模型与方法作出了恰当的分析与评价,文章清晰、完整 摘要本文讨论了在一定区域空间内进行飞行管理避免飞机相撞的模型,提出了直接 计算时间小于10秒,误差不超过0.01度,完全符合问题的要求, 本文接着给出四种不同情况分别用两种方法求解进行比较检验,取得很好的吻合,充分 说明了模型3的可靠性本文还对模型的误差进行分析并对模型进行推厂 关键词非线性规划,直接搜索,罚函数 问题的提出(略) 二、问题的分析 该问题是一个在一定约束条件下的最优化问题,初步分析题意后可知约束条件是非线 的,难以化归为线性规划问题由于题目涉及数据变量不是太多,可以考虑用逐步求精的 接搜索法求解由于题目要求的精度较高,而对于计算时间的要求也较高,如果求解时间 2、3分钟以上将失去任何实际意义我们将求解时间上限定为0.5分,以符合实际的要 .直接搜索法求的近似解难以同时满足两方面的要求但直接搜索法至少能在较短的时间 得到一个较好的可行解,这就为运用非线性规划的方法提供了条件,非线性规划的算法种 多,但均只适用于某些类型的问题由于缺乏适用的计算机软件包,我们自行编写了实 能算法的程序,综合程序准备时间和收敛速度两方面因素我们选择了SUMT算法SUMT 法与直接搜索法相结合,使我们能够在足够短的时间内找到问题的足够精确的解 三、模型假设及说明 1.不碰撞的标准为任意两架飞机的距离大于8km; 飞机飞行方向角调整的幅度不应超过30度; 所有飞机飞行速度均为每小时800km; 4.进人该区域的飞机在到达区域边缘时,与区域内飞机的距离应在60公里以上; 5.最多考虑6架飞机; 6.不必考虑飞机离开此区域后的状况; 7.飞机进入控制区域后完全服从地面控制台的调度,飞机未接到指令时保持飞行状态
8.计算机从记录新进入飞机数据到给各飞机发指令间隔为t1,t1小于0.5分 9.飞机接到指令后可立即转到所需角度,即不考虑转弯半径的影响 说明 1.假设3假定所有飞机速度均为800km/h,是出于对问题的简化.我们将在模型的推 广中给出飞机速度各不相同时的对策 2.假设4是必要的,否则可以给出无解的例证,如图所示,对该假设可作如下解释:飞机 在区域D外靠机上雷达自动保持与其他飞机距离大于60km,进人区域D后由地面控制台 进行统一控制,保证飞机距离大于8km 3.假设5中6架飞机的假设是足够多的.以世界最繁忙的国际航空港之一希思罗机场 邻近区域为例,因假设飞机在区域D作水平飞行,即知该区域内无机场.设在希思罗机场起 降的飞机有一半穿过该区域,希思罗机场1992年起降总架次为22.5万次(文献6),则平均 每小时有15架飞机穿过该区域面一架飞机穿过该区坡最多需198042≈0.28小时,则任 时刻该区域上空飞机架数的期望值不超过4.5架.另外,事实上不同飞机的飞行高度是不 同的,这就进一步减少了该区域同一水平面上飞机的数目.以上讨论虽然稍嫌粗略,但是足 以说明6架飞机的假设是合理的 4,假设8是因为计算机从接到数据到发出命令间存在一个时滞,该时滞固然越小越好 但受机器限制,一般不能忽略我们取0.5分为此时滞的一个上限,以使结果具有实际意义 当t<1秒时,可以认为实现的是实时控制,时滞可以忽略不计 5.虽然假设2给出的调整范围为30度,但实践证明,10度的调整范围就已足够(从后面 的模型1也可看出,即使两机相向飞行,各自所须的调整也不超过8度),因而在今后绝大多 数讨论和程序的编制中都将搜索区间定为[-10,10度 四、文中用到的符号及说明 t;时滞 (x0,y0)第架飞机的坐标 ao第i架飞机初始方位角t时间参数 a第i架飞机方位角D(a1,a)时刻ti,j两机距离 minD(a;a)i,j两机预计最短距离 C S, sina- sina 飞机速度
飞行管理问题的实时算法 87 △xx:-x ∫偏差平方和函数 2y·y-y 求精次数 x逐步求精搜索法中每次求精每层循环次数 g;(x)i,j飞机最短距离构成的不等式约束 (x)关于第i架飞机的等式约束 p(X,r)罚函数 r权因子 五、模型的建立及求解 (一)模型一(两架飞机的情形,略) (二)模型 模型二直接将两机模型运用于多机问题,因为它等价于飞机之间两两不相撞该模型讨 论区域中有6架以下飞机时的情形,利用了模型一判别相撞的函数 crash,同模型一同样采 方向角调整幅度平方和最优为调整原则,从而导出目标函数和约束条件如下 min (a;-aa)2 t.大:minD2(a,a)≥64(i,j=1,2,…6,i≠j),t>0; 或t<0 min D2(ai,a) + Ar,cic+△x +/4S+△x05+4y : Av Ci Ayi+ AtiC 证ash函数只考虑区域中的飞机相撞情况.我们可作如下修改:因为飞机飞过该区域 不超过0.28小时(即飞正方形区域对角线时间),我们可认为仅当minD<8,且0<t 28小时的时候,飞机在区域中相撞;否则不相撞在实际计算时,我们更把上限加大到 小时,实际上是使不相撞的条件更苛刻了一些,相当于对飞机飞离此区域后的情况也作 部分考虑,提高了全局控制的安全性 该模型我们采用直接搜索法讨论了一般情况下对原问题的求解,可在规定时间内得 个近似解,如果放宽时限,则可得一个符合精度要求的最优解 直接搜索法原理十分简单:构造多重循环,对所有可能解进行判断,直接得出在一定精 围内无可置疑的最优解但如不使用任何技巧进行直接搜索,必须耗费大量时间.以本 为例,若在[-10,10]度范围内进行搜索,步长0.01度,共6层循环,需计算6.4×109次 DX66上计算一次循环内函数费时2.7×105秒,此种算法显然是不可取的 为在30秒内算出一个较精确的解,我们采用了逐步求精的方法即每次用一定的步长 的循环次数进行“粗选”,在“粗选”出的解附近以减小了的步长进行“精选”,逐次推
进,直到达到指定精度 设每次求精步长减小的倍数是相同的,则每次求精循环次数也相同,设为x.我们考虑 -10,10]度区间,精度要求达到0.01度,设进行了n次求解,则 =200.01=2000 总循环次数L=n×x6=(log2000og(x/2)×x 由此式可知x减小,则L减小,但若x太小,则可能无法收敛到最优解经验表明x在8 次以上时才能达到较好的搜索效果 求立的量 n=(log200)/(log(8/2)=5,4≈5 此时共需搜索最多5×90=265万次,需费时71.55秒, 为将计算时间控制在30秒以内,我们又采取了一些优化方法,如 a.将底层循环内判别相撞的函数拆细分装在每层循环下,使在高层发现相撞后可提前 结束循环 b.每进入新一层循环把已积累偏差平方和与已得最小偏差平方和比较,若大则结東该 层循环; c.每进入新一层循环把已积累偏差平方和与已得最小偏差平方和比较,若大则结束该 层循环 这些措施大大减少了平均搜索次数,使得在多数情况下计算时间少于30秒,但程序不 能保证在30秒内结束运算,仍存在一些特异情况使计算时间接近最大耗时我们又试用偏 差绝对值和来代替平方和,发现对最优解影响有限,未能明显缩短计算时间 至此可知,用直接搜索法在现有机器条件下难以满足题设要求,要利用该解法,地面控 制台必须满足以下条件之一 1)拥有速度至少为486DX66三倍以上的电脑 2)降低精度要求至0.1度(4次求精步长为7,需时至多10.81秒)即使模型二不能直接 用于飞行管理,它仍有以下作用 1)可算出符合精度要求的最优解供检验其他模型 2)可在相当短的时间内算出具有一定精度的最优解作为其他算法的初值.当精度要求 为1度时,它算出最优解最多只需4.3秒(两次求精步长分别为76),大多情况下运算时间 为2-3秒 (三)模型三 该模型将原问题归结为一个非线性规划问题,并用SUMT算法进行了求解 模型二给出的解法虽然不能满足题设要求,却能在较短时间内给出一个较接近最优解 的可行解由此可行解出发,用适当的非线性规划算法可较快得出满足精度要求的最优解 以a(i=1,2,…,6)为变量,在模型二中我们已经将问题归结为非线性规划问题,主要 约 束条件为 )2, minD2(a,a1)≥64,(i,j=1,2,,6,i≠j), (1) 由于mnD2(a,a)的形式复杂,求导有困难,我们对(1)作一些改变,将目标函数改为
飞行管理问题的实时算法 S2.) i0 coai- cosa s nato 将变量改为C.0,S1,a(i=1,2,…,6)共12个,增加等式约束 (Ci:o cosa: 0)2+(S,io sina o)2=1 使问题(1)变为一个12个变量,21个2次约束条件的目标函数求极小值的问题 minf(X)=>(C2 i0+ S2. o) st.ga(X)=minD(C.0,C,0,S;,0,S,0)-64≥0, h2(X)=0,) (i=1,2,…,6), 工中 c6,60李 10,52,20 minD(C.0,C.0,S.0,S,0) (S1,0-5,0+5 x-((,0-(,0+C,j)·y )2 h, (X)=(C, :o+ cosa:0)2+(S,io sina:o)2-1 Himmelblau在文献[]中列举了三类12种算法,我们对这12种算法进行了比较,主要 是考虑其收敛速度的快慢,其次由于没有现成的软件包可供使用,必须自已编制有关程序 序准备时间的长短,即算法变为程序的复杂程度也必须考虑,综合上述两方面因素,我们 择了序列无约束最小化方法( Sequential Unconstrained Minimization Technique),简称 MT算法 SUMT算法的基本思想是重复地求解一系列无约束问题,它们的解在极限情况下趋于 线性规划问题的极小点算法的详细内容参见文献[1][2[3][4],现概述如下: 首先构造罚函数 P(X,,r)=f(X,)+re g;(X) r∑h3(X1), 中权因子r是一单调递减数列对每个r值求X,使p(X,4)取极小值设精度要求e, x-X-11<ε时结束运算,即为符合所需精度要求的最优解 对此具体问题,我们置 p(X,r)=f(X)+r-12hA(X)+r( Ingi(X)) n-0,n=m8101m,n= e=0.5×10-2 此问题编制程序SUMT1对题目中的数据进行运算,初始值用模型二以精度为1度时算出 量优值代入,结果如下:
初始角 偏转角△a 飞机1 飞机2 236.00 0 飞机 220.50 2.14 飞机4 159,00 0.42 飞机5 230.00 0.00 飞机6 偏差平方和 6.98 该程序运行时间为7.2秒 迄今为止,我们尚未讨论时滞对解的影响在模型三中, Planesumt的运行时间是稳定 的,约为4秒左右.用模型二的Slve求粗略最优解耗时在2~4.3秒,随最优解出现位置不 同而改变,加上裕量后我们可以在10秒以内给出最优解,故将时滞定为10秒由假设7,只 需将各架飞机的坐标按原速度方向向前移动10秒内的位移,在此基础上求解即可,这在程 序上实现起来相当简便.考虑时滞后得出的结果如下表所示 初始角ao 偏转角△a 飞机1 243.00 飞机2 飞机3 220,50 飞机4 飞机5 2.13 飞机 00 16 偏差平方和 11.3292 该模型运行结果在精度和耗时两方面都是令人满意的我们建议地面控制台采用比 486DX66快8倍以上的机器,这样就可以进行实时控制了.对题目所给例子给出的第一个最 优解,可以认为即是在实时控制的假设下给出的 六、模型的检验及误差分析 (一)模型检验 模型二用遍历所有可能解的方式得出最优解的,其解(在可能的精度内)的最优性是毋 庸置疑的,故我们可用模型二求出满足精度要求的解来检验模型三的结果 我们对3组数据分别用模型二和模型三进行求解,结果如下 (X0,Y0,a0) △a(Modd2)△a(Modl3) 飞机1 (60,100,270) 6.53 6.55 飞机2 (70,100,270) 5.46 飞机3 (80,100,270) 飞机 (40,100,270) 6.48 飞机6 (0,40,0) 4.30
飞行理问题的实时算法 第一组:为避免侧面碰撞各架飞机都需转动较大的角度,这是较为极端的情况,偏差的 平方和较大,但没有一架飞机需调整的角度在10度以上,弹同的8干 △a( Model2) Aa( Model 3) 机1(670.80,180) 飞机2(60,70,180)2.54 2.58 飞机3(60.6.80)0.36平0.40 飞机4(090.180)全的7,32若于7,3声问法 飞机5 飞机6 (0,80,0) 4,16 4.17 第二组:与第一组类似但可能发生的碰撞是正面的若计二, (X0,Yo,a0) △a(Mod42)Aa(Mode3) 飞机1 (0,70,0) 飞机3(0,60,180)1.91 0到0 飞机4 (40,130,270 0.07 飞机5 (80,5,180) 0.00 飞机6 第三组:四架飞机十字交错而过,另有两架飞机水平飞行,两个模型都给出了较令人满 意的调度 各组数据吻合程度很好,且给出的调整方案也颇为符合逻辑,与一般常识相符,这说明 模型三的算法是可靠的值得指出的是以模型二的较粗略的可行解作为模型三的输入是非 常必要的,这不但使解能快速收敛到指定精度,使计算时间符合要求,而且可以保证所求解 的全局最优性宾州大学教授 James.P. ignizio曾在其所著 Goal Programming and Extensions 中指出“非线性最优化…不具有用于求解问题的比较初等的通用方法,更令人失望的是非 线性最优化不能保证对一个一般的问题找出整体最优解,除非这个问题具有非常特殊的形 式这意味着研究人员必须经常满足于只找出局部的最优解,事实上,即使所采用的方法能 偶然找出整体最优解,往往也很难判别这个最优解是整体的还是局部的.”这就指明了求 的非线性规划问题的全局最优解目前尚无良策.如果没有模型二的输出作为模型三的输 人,要找到全局最优解至少是相当困难的,时间上当然难以满足要求 (二)误差分析 1.建模中的误差 考察模型假设,可知假设9带来一定误差,简单分析后可知,考虑转弯半径使飞行轨迹 在垂直飞行方向上产生一个偏差X x=(1-cs0)R,其中R为转弯半径,0为转角 对最小转弯半径小于10km的中小型飞机,转角小于15度时,偏差 X≤(1-cs15:)×10=0.34km 对最小转弯半径小于为40km的大型飞机,转角小于8度时,偏差 X≤(1-cos8°)×40=0.39km 一应沿氢,量
两种情况下偏差均小于相撞条件8km的5%,可以忽略不计,由于飞行管理中让一架飞 机做大于8度的转向是较少发生的事(由模型一知两架距离为60km的飞机在一条直线上 相对飞行时,也只需一架转7.66度,一架转7.67度即可避免相撞,)故该处假设可以认为是 合理的.下面给出发生极端情形时的一个对策;设一架大型飞机做30度的转弯,此时偏差X =(1-cs30°)×40=5.36km不可忽略在飞机开始转弯后(转弯过程约需1.6分钟)地面 控制站的计算机可算出一条曲率处处大于140的偏转线,以此曲线引导飞机飞回偏转线 这种局部调整法的优点在于计算简单,不对全局的调整角度方案产生影响,特别适用于这种 小概率事件 2.计算误差 模型一、二计算过程中的误差仅来源于机器的截断误差,对于最后结果没有重大影响 模型三计算中的误差来源于 a.建模过程中对目标函数进行替换时 b.用SUMT算法进行计算时 对于a我们对An从0度到10度计算了C2+C以1度基准的相对误差如下表所示 偏差(度)偏差的平方拟偏差相对拟偏差拟偏差相对误差 3.046E-43.046E-4 0 点,3个,21E-3413185310四B三取 l.218E-4 2.741E 4.872E-34.874E-3 ,因5,257.611E-37.615E-35.2E分4 6361,095E211.097E-2111.8E3草三身 加下门m,赚49回语1.491E21.493E21.3E-3a 1.946E=21,949E-25E3 我101003.03E-2306E-22.6E53非出中 车雪生具活个非 补出狂的 相对误差在0.3%以下,这些表明替换函数对最后结果没有显著影购, 对于b我们认为文献(1,(21、(31、[41中提供的算法已考虑了误差间题,在程序中实 际给出了两个误差控制是:相对精度界e1和绝对精度界ε2,当满足 全 2 时程序结束,这保证了解的误差在精度要求以内 阳中查 3,输入误差对结果影响单一结Q经面,芽 通过对输入数据给以小的扰动经大量计算可得如下定性结果:一向许直垂 s.飞机位置有小的扰动对结果影响甚微,扰动增大时影响明显.(6∞-1)= b.飞机方向角的扰动对结果影响显著,扰动大小与结果变化幅度基本是在一个数量级 上 以上结果说明为保证结果的准确性应尽量减小对飞机方向角测量的误差,同时对飞机 位置测量的误差也应控制在一定范围以内
飞行管理问题的实时算法 架飞 上 七、模型的评价及推广十的 为是 (一)模型的评价 差X 模型三是我们得到的主要结果,该模型可对区域内任意位置、方向的6架以内的飞机给 地面 出调整对策.如果飞机管理的计算机计算速度比486DX66快10倍左右,则可实现实时控 我种 制.因而具有计算时间短、精度高的特点,实用性强,较为完满地解决了原始问题.建模过程 中用到的非线性规划方法具有一般性,容易作出推广,缺点是当飞机数目增多时,非线性规 划的规模增大了,计算时间增长较快,幸好对假设的分析表明这种情况是很少发生的 (二)模型的推广(略) 响 参考文献 1.D. M. Himmelblau,实用非线性规划 2.JL.,Lims,非线性边值问题的一些解法 所示 3.D.G. Luenberger,线性与非线性规划引论 4.程极泰,最优设计的数学方法 5.邓乃场,无约束最优化计算方法 顾其行,国际航空运输管理 7. James P. Lgnizio, Goal Programming and Ext 数学的应用是多种多样的,从原理上讲,数学方法的应用范围是无边际的,即物质的所 有类型的运动都可以用数学加以研究。但是数学方法的作用与意义在不同情况下是不同的。 用单一的模式来包罗现象的所有侧面是不可能的。 A.N.柯尔莫哥洛夫 《当代数学大师》,李心灿编,航空工业出版社,1994。 中实 三并因,国由 量级 飞机
空中防撞系统的设计有 黄春峰饶红玲刘伟 最三说 ,(中国科学技术大学,合肥23002 南指导教师于清娟 编者按本文用相对运动的观点建立飞机两两不相撞的约束条件,将问题归结为一个非 线性规划问题,用惩罚函数方法化为无约束极值问题求得最优解罚函数选取合理表达清楚 关键词非线性规划,惩罚函数,最优解 文学 、符号约定 P2为第;架飞机坐标;0为第i架飞机方向角;r为P和P间距;为P与X轴的夹 角;v为飞机飞行速度 二、问题的分析与求解 空润到,其, 1.设计目标 要设计的防撞系统中,为确保飞机不相撞,应满足如下条件 (1)安全距离要求|Pa|≥8 (2)飞机偏离航向不应太远,要求|△01≤30° 根据上述条件及题目的要求,防撞系统的目标是达到总航向的改变最小、即 in(∑△01)用的 E不面营内牙一单 上述的条件和目标是我们建模的依据 2.飞机相撞的判据 根据相对运动原理P相对P的速度方向为 (u(cos0, -, ),v(sinB; -sin, )) t时刻P相对P的位置为 (ai+ vt(cos0. - B, ),bi vt(sind: -,)) 令tt=l,则有 PP12=f()=(a23+b3)+4n2“(- aisin“2+bcs,g 412sin2 9+a 0<L<Imax 由上可知,P与P若相撞仅有三种可能 1)f(0)<64,但这与初始条件不符,故无须考虑; 2)f(m)<6,a("+-)<64 且
