基于改进A*算法的滑翔飞行器轨迹规划

卢 青, 周 军, 呼卫军

(西北工业大学精确制导与控制研究所, 陕西 西安 710072)



基于改进A*算法的滑翔飞行器轨迹规划

卢 青, 周 军, 呼卫军

(西北工业大学精确制导与控制研究所, 陕西 西安 710072)

为了研究滑翔飞行器再入过程中的侧向机动问题,A*算法的相关理论被引入到轨迹规划中。飞行距离较远时,地球的曲率必须加以考虑,且再入过程中飞行器会受到各种过程约束。针对现有规划方法中在平面上进行A*算法推演的局限性,本文提出了一种基于椭球面A*算法的轨迹规划方法。通过推导将过程约束引入A*算法搜索过程中,从而规划出合理的轨迹。仿真结果表明,本文所提出的方法能够快速地对再入段的轨迹进行有效规划,具有很强的实用性。

A*算法; 滑翔飞行器; 轨迹规划; 椭球面

0 引 言

再入段是航天器利用地球大气层这一天然资源,使再入器减速下降,并消耗它具有的巨大能量。再入飞行器在再入飞行的过程中还需要同时考虑路径点和禁飞区等实际约束的突防优化问题。

随着高超声速飞行器发展的深入进行,飞行器横向的轨迹规划正在越来越多地引起国内外学者的广泛关注。2007年Jorris T R在文献[1]中首次考虑高超声速滑翔飞行器在再入过程中通过航路点和回避禁飞区的侧向轨迹优化策略。在这之后的两年Jorris T R等人又先后提出了二维[2]的以及三维[3]的满足航路点和禁飞区约束的再入飞行器轨迹规划方法。这些方法并没有对飞行过程中的约束给出明确处理,同时没有考虑多个禁飞区的情形。

在计算机技术不断发展的基础上,以A*算法为代表的启发式搜索方法越来越多地被运用到轨迹规划的过程中。文献[4]采用了线性的实时A*算法来搜寻可行的路径树。最终得到满足目标要求的最小最短路径。Richard N D则通过对标准的A*算法进行次优化修改可以在少量增加路径代价的基础上获得可行的次优轨迹,这就大大提高了轨迹规划的效率[5],A*算法的运用缩短了轨迹规划的时间,但是并没有将飞行器在飞行过程中受到的各种过程约束考虑到规划的过程中。文献[6]通过使用变步长的A*算法对飞行器飞行过程中的各种约束条件进行了考虑。这些利用A*算法进行轨迹规划过程都是以平面规划为基准,当飞行器的飞行距离较远时,显然不能继续使用平面的相关计算方式。为此,本文考虑各种过程约束条件,将飞行器可达区域的推演引入到椭球面A*算法的搜索过程中,从而完成完整的轨迹规划过程。

1 问题描述

1.1 滑翔飞行器数学模型

忽略发动机推力,得到飞行器在再入过程中半速度坐标系下较为完整的数学模型[7-8]为

(1)

式中,ωe为地球自转角速度;r为地心矢;θT为弹道倾角;σT为弹道偏角;γv为倾侧角;gr为地心矢方向上的引力加速度;f1,f2,f3,f4,f5,f6为右函数;V为速度;λ为经度;φ为纬度。Y=CLSρV2/2,X=CxSρV2/2,Z=CxSρV2tanγv/2,分别是升力、阻力、侧向力,ρ为大气密度,S为参考面积。

1.2 轨迹约束

利用再入飞行器在受到的各种约束与高度的关系得到高度-速度剖面,建立再入走廊[9]:

(2)

2 算法流程

2.1 任务与假设

再入飞行器的主要任务是在上述各种过程约束的限制下完成整个轨迹规划过程。为保证推演的严谨性作出如下假设:

假设 1 禁飞区为具有特定半径的圆域,表示为(L,B,R),L，B分别表示威胁区中心的经度、纬度,R表示威胁区的半径。

保证了算法推演的可行性,其他形状可以被近似为圆形,符合实际。

假设 2 仅考虑地心矢径方向的地球引力。

对数学模型进行了简化,方便后续推导。

假设 3 再入过程中速度变化较小。

符合再入过程的特点,可将速度表示为航程的线性函数,使后续算法推演中状态量可解。

2.2 代价函数的引入

引入代价函数[10]:

f=w1S+w2L

(3)

式中,S表示当前待扩展点到目标点大圆弧长度;L表示航迹点与威胁区最近距离。依次计算待扩展点与威胁区中心大地线长度,取最小者。

权重值取为w2=R/L,w1=1-w2,这样可以保证在不同的阶段,自动调整权重值。

由于各个代价分量的单位各不相同,这样不便于权重值的选取。因此,对上述变量进行归一化处理:

(4)

(5)

式中,m表示待扩展的节点总数。归一化处理后代价函数可以写成:

(6)

2.3 路径生成

设起点经纬度为(L0,B0),目标点经纬度为(Lf,Bf),当前节点经纬度为(L,B)。航迹点与目标点距离小于ε,搜索过程结束。

(1) 初始判断

若初始点或目标点位于任何一个威胁区内,那么搜索过程直接终止,无可行轨迹。

(2) 航迹点生成

具体航迹点生成过程如下[11-14]:

①当前节点为(L,B),L为经度,B为纬度。全方向的8个航迹点为(L+ΔL,B+ΔB),(L+ΔL,B),(L,B-ΔB),(L+ΔL,B-ΔB),(L,B+ΔB),(L-ΔL,B+ΔB),(L-ΔL,B),(L-ΔL,B-ΔB),将这8点放入OPEN表中,成为待扩展航迹点。再添加一个由当前点指向目标的大地圆弧上的参考点(L+ΔL,StdB),其中,StdB表示指向目标圆弧上点的纬度值。如图1所示,将这个点加入OPEN表中。

图1 航迹点扩展示意图Fig.1 Diagram of extended flight points

②利用9个航迹点对CLOSE表进行扩展。待扩展点位于威胁区域内时,删除该点。

③可达性判定:判定OPEN表中的6个航迹点是否位于当前点可达范围内。判断方法推导如下。

取状态向量为

x=(v,θT,σT,φ,λ,r)T

取定哈米尔顿函数为

H=λ1f1+λ2f2+λ3f3+λ4f4+λ5f5+λ6f6

(7)

λ=[λ1,λ2,λ3,λ4,λ5,λ6]为共轭向量且有

(8)

式中，∂fi/∂xj(i,j=1,2,…,6)是右函数偏导数。

飞行器纵向航程主要由攻角指令决定,横向最大航程主要由倾侧角γv决定,γv受到再入走廊的约束。需要找到倾斜角和高度之间的关系,从而将再入走廊的限制引入到横程最大弹道的计算过程中。由质心动力学方程中航迹倾角的式子,并将gr=-(fM/r2)[1+J(ae/r)2(1-5sin2φ)]代入,其中ae为地球长半轴,fM=μ为地球引力系数,J为常值,可得

(9)

将式(9)简记(用Matlab程序方便求解)为

(10)

根据式(1)的第6式可得

(11)

将式(11)代入式(9)即可得到倾斜角γvopt和矢径r之间的关系。下面对地心矢径和飞行器高度之间的关系进行求解。这里结合大地椭球的相关知识,直接给出结果[15]：

(12)

式中，re为星下点地心矩,计算式为

(13)

式中,ae为赤道半径;f为地球扁率;e为地球第一偏心率。

式(12)中φ为地心纬度,φ为地理纬度:

φ=arctan(tanφ/(1-e2))

(14)

将式(13)和式(14)代入式(12)即可得到地心矢和高度之间的关系,结合式(9)、式(11)、式(12)推导出倾斜角γvopt和高度之间的关系,由此将再入走廊的限制引入横程解算中。

对于横向最大位置弹道,飞行时间tf不作要求,状态变量终端约束除要求r(tf)=rf外,其余5个状态变量vf,θTf,σTf,φf,λf均无要求,仅要求落点的横向位移最大[7]。

(15)

从而

λ1(tf)=0,λ2(tf)=0,λ3(tf)=0,

λ4(tf)=k1,λ5(tf)=k2,λ6(tf)=v1

(16)

通过上述推导过程,只要确定当前航迹点的6个状态量,就可以用横向最大位置的推导方法并结合最大升阻比攻角推导最大纵程，从而得到飞行器在当前节点的可达区域。

当前状态量的选取方法如下:

在进行航迹规划时认为飞行器的规划速度随着飞行器的航程线性变化,则速度为

V=V0-(V0-Vf)·Sgo/(Sgo+Stogo)

(17)

式中,V0为再入初始时刻飞行器的速度;Vf为再入段结束时飞行器的速度;Sgo,Stogo分别为已飞航程、待飞航程。

飞行器在再入飞行过程当前的弹道倾角取为θ<ζ,ζ为设定的一个小角度。

航迹点的航迹偏角取为航迹点与初始点连接的圆弧方向与初始航向之间的夹角,即

σ=|Adpointn-Ad0|sign(η)

(18)

式中,Adpointn为航迹点与初始点圆弧的方向;Ad0为初始方向角;sign(η)表示当前的偏角符号由与航迹点位置相关的变量η决定。

当前航迹点的经纬度及地心矢都已知。在此基础上就可以得到可达区域,删除OPEN表中位于可达区域之外的点。同时对OPEN表中的待扩展航迹点也进行可达区域解算,若目标点位于待扩展航迹点所形成的可达区域之外，则删除OPEN表中的这个点。

对剩下的航迹点选取代价函数较小的点,将该点添加至CLOSE表中。

(3) 到达条件判断

Stogo<ε

(19)

式中,ε是一个大于一部搜索距离ΔS的常量。当获取的航迹点与目标点之间的距离小于ε时搜索过程结束。

(4)收敛性证明

航迹的收敛性是指所规划航迹对于任意初始点出发最终都能到达目标点。待飞航程表示为

Stogo=Stogolast+ξΔS

(20)

式中,ξ为符号函数；Stogolast为上一步的待飞航程。由于指向目标的航迹点的存在,能够保证ξ≤0。又因为ΔS为变化量,且ΔS<ε,所以只要经过若干步迭代之后就一定能够使航迹点满足结束条件,到达目标点。

2.4 航路光顺化

为了使规划航迹具有更强的可行性,需要对航迹进行光顺化处理,处理过程如下。

由以上规划方法形成的轨迹由一系列航迹点构成,可以表示成如下形式:

ROAD=(Point0,Point1,Point2,…,Pointn)

(21)

从这些航迹点中任意选取两个航迹点,判断连线是否经过威胁区,若不经过则把两个航迹点之间的航迹点删除。从初始节点开始依次进行，如图2所示。

图2 轨迹规划流程图Fig.2 Flowchart of trajectory planning

可进行如下判断:

上述全部规划过程可用图2表示。

图3 椭球面三角形示意图Fig.3 Diagram of elliptical triangle

3 仿真结果与分析

进行仿真研究,气动参数通过气动数据表插值获得。初始状态和目标点的状态如表1和表2所示。

表1 轨迹规划状态量

仿真过程中取4个半径为500 km的圆域建立威胁区的模型。

表2 威胁区的信息

分别采用传统的A*算法和本文中的A*算法进行比较,仿真结果如图4所示。

图4 与传统算法对比的轨迹规划示意图Fig.4 Trajectory planning diagram comparing with traditional algorithm

从图4中可以看出传统的A*算法由于缺少光顺化的过程,规划出的轨迹弯折严重,不适用于实际的飞行状况，本文的算法则能够使轨迹更加平滑。与此同时,通过记录仿真时间发现,由于本文算法中指向目标的航迹点的引入,算法可以在1 s内完成规划任务,而传统的A*算法花费的时间在2～3 s之间。

为验证算法的适应性,普通的计算机上,在起点不变的情况下取多个目标点进行仿真分析,同时记录算法的收敛时间,如表3和图5所示。

表3 目标点的信息

图5 多目标情况下的轨迹规划示意图Fig.5 Trajectory planning diagram with the situation of multiple targets

通过仿真结果可以看出算法的收敛时间一般在0.6 s左右,针对不同的目标点都能够准确快速地规划出合理的轨迹。

为进一步验证算法的可靠性,对威胁区的位置进行了调整,采用初次仿真的初始点和目标点坐标进行验证,仿真结果如图6所示。

图6 变威胁区情况下的轨迹规划示意图Fig.6 Trajectory planning diagram with the situation of variable threatened zones

从图6中可以看出本算法在威胁区改变时仍然具有较好的适应性。在上述仿真的基础上,针对本文的方法又进行了蒙特卡罗打靶的大样本仿真,轨迹规划成功率接近100%,表明本文的方法具有很强的实用性。

4 结 论

本文针对滑翔飞行器这一研究对象,对传统的A*算法进行了改进。成功地将滑翔飞行器飞行过程中的各种过程约束引入到算法的推演过程中。同时结合实际应用特点进行椭球面上相关量的推演。通过仿真分析,证明了本文算法收敛速度较快,针对不同目标,不同威胁区都具有较好的适应性。

[1] Jorris T R. Common aero vehicle automous reentry trajectory optimization satisfying waypoint and no-fly zone constrains[D]. Ohio: Air Force Instituite of Technology, 2007.

[2] Jorris T R, Cobb R G. Multiple method 2-D trajectory optimization satifying waypoints and no-fly zone contraints[J].JournalofGuidance,ControlandDynamic, 2008, 31(3):543-553.

[3] Jorris T R, Cobb R G. Three-dimensional trajectory optimization satisfying waypoint and no-fly zone contraints[J].JournalofGuidance,ControlandDynamic, 2009, 32(2):551-572.

[4] Howlett J, Goodrich M, Mclain T. Learning real-time A*path planner for sensing closely-spaced targets from an aircraft[C]∥Proc.oftheAIAAGuidance,NavigationandControlConferenceandExihibit, 2003:AIAA2003-5338.

[5] Richards N D, Sharma M, Ward D G. A hybrid A*/automaton approach to on-line path planning with obstacle avoidance[C]∥Proc.oftheAIAA1stIntelligentSystemsTechnicalConference, 2004: AIAA2004-6229.

[6] Huang X, Huang P F, Yan J, et al. Route planning for hypersonic vehicle using A*algorithm[J].ComputerSimulation, 2009, 26(9): 62-127. (黄雄, 黄攀峰, 闫杰, 等. 基于A*算法的高超声速飞行器航迹规划方法[J].计算机仿真, 2009, 26(9): 62-65，127.)

[7] Zhao H Y.Reentryguidanceanddynamicsofaircraft[M]. Changsha: National University of Defense Technology Press, 1997. (赵汉元. 飞行器再入动力学和制导[M]. 长沙: 国防科技大学出版社, 1997.)

[8] Barton J D. Fundamentals of small unmanned aircraft flight[J].JohnsHopkinsAppliedPhysicsLaboratoryTechnicalDigest, 2012,31(2): 132-149.

[9] Grant M J, Clark I G, Braun R D. Rapid entry corridor trajectory optimization for conceptual design[C]∥Proc.oftheAIAAAtmosphericFlightMechanicsConference, 2010:AIAA2010-7810.

[10] Li M, Wang D B, Sheng S Z, et al. Multiple route planning based on particle swarm optimization and weighted K-means clustering[J].SystemsEngineeringandElectronics, 2012, 34(3): 512-516. (李猛, 王道波, 盛守照, 等. 基于加权K-均值聚类与粒子群优化的多航迹规划[J].系统工程与电子技术, 2012, 34(3): 512-516.)

[11] Li X Y, Zhou D Y, Feng Q. Multiple routes planning for A*algorithm based on hierarchical planning[J].SystemsEngineeringandElectronics, 2015, 37(2): 318-322. (李枭扬, 周德云, 冯琦. 基于分级规划策略的A*算法多航迹规划[J]. 系统工程与电子技术, 2015, 37(2): 318-322.)

[12] Pehlivanoglu Y V. A new vibrational genetic algorithm enhanced with a voronoi diagram for path planning of autonomous UAV[J].AerospaceScienceandTechnology, 2012, 16(1): 47-55.

[13] Foo J L, Knutzon J, Kalivarapu V, et al. Path planning of unmanned aerial vehicles using B-splines and particle swarm optimization[J].JournalofAerospaceComputing,Information,andCommunication, 2009, 6(4): 271-290.

[14] Poli R. Analysis of the publications on the applications of particle swarm optimization[J].JournalofArtificialEvolutionandApplications, 2008, 2008(1): 1-10.

[15] Lv Z P, Qiao S B.Foundationofgeodesy[M]. Wuhan: Wuhan University Press, 2010. (吕志平, 乔书波. 大地测量学基础[M]. 武汉: 武汉大学出版社, 2010.)

卢 青(1990-), 男, 博士研究生, 主要研究方向为飞行器航迹规划及制导控制理论。

E-mail: lamaxiya1990@163.com

周 军(1966-), 男, 教授, 博士, 主要研究方向为飞行器制导控制与先进控制理论。

E-mail: zhoujun@nwpu.edu.cn

呼卫军(1979-), 男, 副教授, 博士, 主要研究方向为飞行器数字仿真技术。

E-mail: huyanwj@126.com

Trajectory planning for gliding aircraft based on improved A*algorithm

LU Qing, ZHOU Jun, HU Wei-jun

(InstituteofPrecisionGuidanceandControl,NorthwesternPolytechnicalUniversity,Xi’an710072,China)

In order to solve the lateral maneuver problem of gliding aircraft during reentry process, the theory of A*algorithm is introduced into trajectory planning. Earth curvature must be considered when flying distance is far, besides, there are varies constrains during reentry process. According to the boundedness of existing trajectory planning using A*algorithm based on plane, an A*algorithm for trajectory planning based on ellipsoid is put forward. Process constrains are also introduced into the searching procedure of A*algorithm through deduction. Finally, a reasonable trajectory can be found. The results of simulation verify that the method of this paper can find out a trajectory rapidly and efficiently, and this method has strong commodity.

A*Algorithm; gliding aircraft; trajectory planning; ellipsoid

2016-02-22;

2016-10-18;网络优先出版日期:2016-10-27。

国家自然科学基金(61473226)资助课题

TP 273

A

10.3969/j.issn.1001-506X.2016.12.12

网络优先出版地址:http://www.cnki.net/kcms/detail/11.2422.TN.20161027.1612.024.html