基于改进人工势场法的多机改航路径规划

王兴隆, 徐肖豪, 冯江然

(中国民航大学 空中交通管理研究基地, 天津 300300)

基于改进人工势场法的多机改航路径规划

王兴隆, 徐肖豪, 冯江然

(中国民航大学 空中交通管理研究基地, 天津 300300)

恶劣天气是航空运输中造成航班延误的主要因素,实施改航策略是减少延误的一种有效方法,多航空器路径规划是改航策略的关键环节。针对恶劣天气造成大量航班延误情况,提出了采用人工势场法进行多机改航路径规划。根据航空器所受引力和斥力建立了传统人工势场模型,为解决在改航期间航空器受力出现局部最小值的问题,在航空器之间、航空器与恶劣天气之间引入不同的旋转控制力。仿真结果表明,改进的人工势场法规划的路径更短、更平滑,没有大角度转弯和反复振荡的情况,且计算效率提高了33%。

航空运输; 改航路径规划; 人工势场法; 多航空器

0 引言

导致航班延误的因素有很多,其中不利于飞行的天气,如大雾、雷暴、积冰等是造成航班延误的主要原因。根据民航局公布的资料统计,由于天气原因造成的机场或空域容量急剧下降而直接或间接导致航班延误的比例约占不正常航班的三分之一。

当出现恶劣天气时,实施改航策略是减少航班延误的一种有效途径,改航策略是航班临时选择一条不受影响的航线绕过飞行受限区域,航班改航路径规划是改航策略的一个关键问题。国外对该领域的研究已有十几年的时间,具有代表性的算法主要有:基于网格的改航路径规划法[1];基于多边形的改航路径规划法[2];基于标准进离场程序的改航路径规划法[3];基于自由飞行的改航路径规划法[4]。我国对于改航问题的研究开始于2000年,目前仍处于研究的初级阶段。我国学者从2001年开始对航班改航路径规划问题进行研究,提出了基于已有航路点的A*搜索算法[5];文献[6]提出了基于几何算法的改航路径规划方法,该方法考虑了最短航段距离、转弯角度和转弯点数量等因素对改航路径的影响;文献[7]考虑了多个限制因素,建立了基于人工势场算法的动态改航路径规划模型,实现了改航路径的快速实时规划。这些研究只考虑了单航空器(也称单机)改航路径的规划,在实际运行中,恶劣天气势必影响多个航空器的正常运行,因此,不仅要考虑航空器避让恶劣天气,也要分析航空器之间的飞行冲突。针对这一问题,本文研究了恶劣天气下的多航空器改航路径规划与优化。

1传统人工势场法的多机改航路径

规划

采用传统人工势场法建立人工势场模型时,航空器被简化为一个质点,在二维平面空间中运动[8]。航空器为了到达目标点需要不断地朝着目标点运动,目标点对航空器产生了引力。同时航空器在飞行过程中需要避开受限空域和其他航空器,受限空域和其他各航空器对航空器产生了斥力,在斥力的作用下航空器始终与受限区和其他航空器保持一定的间隔,最终完成规避运动。航空器在运动空间中任意位置X=[x,y]T处的引力势场函数为:

(1)

则吸引力是目标引力势函数的负梯度:

Fatt(X) =-grad[UA(X)]=λ(XA-X)

(2)

式中,λ为引力位置增益系数;X为航空器当前位置;XA=[xA,yA]T为目标位置矢量;‖XA-X‖为航空器与目标点间的欧氏距离。

将受限空域和其他航空器看作障碍物,其斥力势函数定义为:

Urei(X)=

(3)

相应的斥力为:

Frei(X) =-grad[Urei]

(4)

航空器在空域中所受合力为:

(5)

2改进人工势场法的多机改航路径

规划

传统人工势场法存在一些问题:航空器所受的斥力和引力在一条直线上,航空器在改航期间出现合力为零,航空器无法避开障碍物,只能在一个范围内来回振动,即陷入局部最小值点。为解决该问题,采用附加一个变化的控制力。在航空器之间避让冲突的情形中,在目标航空器周围构筑逆时针方向的旋转力代替斥力,航空器在避让危险天气的过程中通常是保持在危险天气的一定距离之外绕飞,在受限区域周围构造旋转力场和斥力场,航空器在旋转力场和斥力场共同作用形成的复合人工势场中寻找从初始位置到达目标位置的无碰撞路径。

2.1 改进人工势场法

本文对航空器的受力情况进行调整,在目标航空器周围构筑逆时针方向的旋转力代替斥力。

航空器i与j的避让过程中,航空器i所受的旋转力Frot为:

(6)

式中,krot为旋转力增益系数;rij=[(xi-xj)2+(yi-yj)2]1/2是航空器i和j之间的距离;rj为航空器j的保护区半径;ρroj为航空器j的旋转力势场半径;ρrot为航空器的旋转力场影响的最大范围。

假设恶劣天气的受限区为椭圆形,其斥力势函数定义为:

Ureo(qi,X)=

(7)

相应的斥力为:

Freo(qi,X)=

(8)

式中,kreo为受限区斥力的增益系数;XR(x0,y0)为椭圆形危险天气区域的中心;ρ(qi,X)为航空器i到椭圆的距离;rreo为椭圆圆心与航空器i的连线上,圆心到椭圆边界的长度;ρreo为受限区斥力场影响的最大距离范围。

受限区的旋转力为:

(9)

式中,ρro为受限区旋转力场半径;kro为受限区的旋转力增益系数。这样,在多航空器系统中,航空器i所受的合力为:

Frot(qi,qj)+Fro(qi,X)]

(j=1,…,m;i≠j)

(10)

以上建立了多航空器避让危险天气时的模型,需要注意的是:在计算势场力Fatt,Freo,Frot,Fro时,增益系数katt,kreo,krot,kro的值决定了势场力的大小,进而决定了航空器运动的方向。

2.2 改进人工势场法的改航路径规划步骤

步骤1:为规划选定模型参数,包括航空器数量I、航空器i的起始点Oi(x0,y0)、终点Ti(xt,yt)、受限区中心位置Obs(x0,y0)、受限区的椭圆方程参数a,b以及ρreo,ρro,ρrot,katt,kreo,krot,kro,还有移动步长l和最大运行步数J,按运动空间的信息建立人工势场模型;

步骤2:确定运行步数j(初始步数为1),将第j步航空器i的当前位置坐标Xi(xj,yj)存入二维数组Currenti(xj,yj);

步骤3:分析航空器、受限区以及目标点的相对位置,分别计算每一架航空器所受的引力Fatt,斥力Freo,旋转力Frot,Fro,并表示为分别沿x轴和y轴方向的分量;

步骤4:计算每一架航空器所受的势场力的合力F(x,y),航空器从点Xi(xj,yj)沿合力方向以固定步长l移动到下一航路点next(xj+1,yj+1),点的计算如下:

next(xj+1,yj+1)=Xi(xj,yj)+lF

(11)

步骤5:移动航空器到点next(xj+1,yj+1),置j+1点为当前点,j=j+1,xj=xj+1,yj=yj+1;

步骤6:判断航空器是否到达目标区域,如果距离目标区域的距离小于预设的阈值(通常为移动步长的整数倍),航空器到达目标区域,结束改航路径规划,输出数组Currenti从而生成完整的改航路径,任务完成;否则转步骤2继续计算,或者直到步数j大于设定的最大步数J,无法找到完整路径,说明模型参数选择不合适,需要改变参数重新规划。

3 仿真计算

算例为8架航空器,四对同高度迎头飞行,航空器的初始状态为表1,航空器预计飞行航路和状态如图1所示。航空器在飞行中不仅要绕飞天气,同时还必须避让对向的航空器,且由于改航过程中需要占用侧向间隔,相邻两架航空器的飞行冲突问题也要加入考虑之中。

表1 航空器初始状态Table 1 Initial state of the aircraft

图1 航空器预计飞行航路和状态Fig.1 Estimated flight path and state of the aircraft

首先通过传统人工势场法作改航路径的规划,各参数的设置如下:势场范围ρreo=20 km,ρro=50 km,ρrea=20 km;势场力增益系数katt=15,kreo=150,krea=170,kro=15。经MATLAB计算得到的改航路径如图2所示。

传统人工势场法可以规划出符合间隔标准的改航路径,其中航空器与危险天气的间隔保持在10 km以上;航空器之间的最小间隔为7.863 km,大于最低间隔标准的6 km。但是由于多航空器复杂冲突的存在,传统人工势场法生成的改航路径非常曲折,包括多处180°以上的大转弯;航空器飞行相当长一段距离后方能到达目标地点,特别是迎头飞行的航空器遭遇之后经过长时间的振动方得解脱;改航路径在实际工作中是不可接受的。此外,整个仿真的迭代步数达到了300步以上,主要原因就是迎头遭遇的航空器在振动过程中消耗了大量步数,造成计算资源的浪费,降低了仿真计算的效率。

图2 传统人工势场法规划的改航路径 Fig.2 Rerouting path of traditional artificial potential field

采用前面提出的改进人工势场法解决上述问题。由于航空器之间用旋转力代替排斥力,所以将航空器斥力势场ρrea变为旋转力势场ρrot=20 km,航空器斥力增益系数krea变为旋转力增益系数krot=20,其他参数不变,通过仿真计算得到的改航路径如图3所示。

图3 改进人工势场法规划的改航路径Fig.3 Rerouting path planned by improved artificial potential field

改进人工势场法规划出的改航路径较传统方法规划出的路径更短,各航空器的航迹也更为平滑,没有出现大角度转弯的情况;迎头相遇的各航空器都能很好地进行避让,没有出现反复振荡的情况,航空器之间的严重冲突得以避免。航空器与危险天气的距离均大于10 km,航空器之间最小间隔为6.729 km,符合最低间隔标准。此外,采用改进人工势场法的迭代步数均小于200,说明对人工势场法的改进节约了计算时间,计算效率提高了33%,可见本文提出的改进人工势场法能够克服传统方法的一些不足之处,适用于多航空器改航的路径规划问题。

4 结束语

本文采用改进人工势场法对多航空器改航路径进行了规划,解决了传统方法中航空器受力局部最小值的问题,仿真了航空器迎头冲突的情景。结果表明,改进人工势场法规划的路径更短、更平滑,没有大角度转弯和反复振荡的情况。在此基础上,利用空管运行中的气象和空域数据验证理论方法的实用性,是下一步研究的主要内容。

[1] Dixon M,Weiner G.Automated aircraft routing through weather-impacted airspace[C]//5th International Conference on Aviation Weather Systems.Vienna,VA,1993:295-298.

[2] Sridhar B,Chatterji G B,Grabbe S,et al.Integration of traffic flow management decisions[C]//AIAA Guidance,Navigation,and Control Conference.Monterey,Cal,2002:1-9.

[3] Krozel J,Penny S,Prete J,et al.Automated route generation for avoiding deterministic weather in transition airspace[J].Journal of Guidance,Control,and Dynamics,2007,30(1):144-153.

[4] Balen C H,Bil C.Optimal re-routing of aircraft around closed airspace in free flight[C]//AIAA Modeling and Simulation Technologies Conference.Honolulu,HI,2008:1-10.

[5] 宋柯.空中交通流量管理改航策略初步研究[D].南京:南京航空航天大学,2002.

[6] 李雄,徐肖豪,朱承元,等.基于几何算法的空中交通改航路径规划研究[J].系统工程,2008,26(8):37-40.

[7] 徐肖豪,李成功,赵嶷飞,等.基于人工势场算法的改航路径规划[J].交通运输工程学报,2009,9(6):64-68.

[8] 况菲,王耀南,张辉.动态环境下基于改进人工势场的机器人实时路径规划仿真研究[J].计算机应用,2005,25(10):2415-2417.

(编辑：方春玲)

Multi-aircraftreroutingpathplanningbasedonimprovedartificialpotentialfieldalgorithm

WANG Xing-long, XU Xiao-hao, FENG Jiang-ran

(Research Base of Air Traffic Management, Civil Aviation University of China, Tianjin 300300, China)

Severe weather is the main cause for the delay of transport aircraft, rerouting strategy is an effective way to reduce delays, multi-aircraft path planning is the key point for rerouting. For many flights delay caused by severe weather, this paper presents artificial potential field method for multi-aircraft rerouting path planning. Traditional artificial potential field model is established according to the aircraft by gravity force and repulsion force, and different rotation control force between aircraft and aircraft, aircraft and severe weather is introduced to avoid local minimum value during rerouting. Simulation result shows that the path planned by improved artificial potential field method is shorter and smoother, and no large angle turning and repeated shocks, and the computational efficiency is improved by 33%.

air transportation; rerouting path planning; artificial potential field; multi-aircraft

V355

A

1002-0853(2013)04-0381-04

2013-01-15;

2013-04-01; < class="emphasis_bold">网络出版时间

时间:2013-06-06 12:25

国家自然科学基金资助(61039001，60972006)；中央高校科研基金资助(ZXH2011D010)

王兴隆(1979-)，男，黑龙江北安人，助理研究员，研究方向为空中交通管理。