基于改进AStar算法的无人机航迹规划算法研究概要Word文件下载.docx
《基于改进AStar算法的无人机航迹规划算法研究概要Word文件下载.docx》由会员分享，可在线阅读，更多相关《基于改进AStar算法的无人机航迹规划算法研究概要Word文件下载.docx（16页珍藏版）》请在冰点文库上搜索。
routeplanning;
threatavoidance;
A2Staralgorithm;
routecost
收稿日期:
2007-06-12
作者简介:
李季（1980—
男,博士研究生。
E2mail:
fog1995@tom.com;
孙秀霞（1962—
女,教授,博士生导师0 引言
当前,随着无人飞行器、
无人驾驶飞机以及无人
探测器的广泛应用,如何使这些无人操纵机械能够按照预先设定好的路径,有效避开障碍和威胁,实现无人干涉下的自主飞行,成为一个引起广泛关注和亟需解决的问题。
标准航迹规划问题即是按照预先选定好的代价函数,通过一系列的算法搜索,找到一条使代价函数值最小的路径。
在航迹规划问题中,常用的规划算法包含A2Star搜索算法[1-3]、动态规
划法[4]、Dijkstra算法[5]、遗传算法[6]、粒子群算
法[7]、数学规划[8]等。
在所有这些算法中,A2Star搜索算法由于计算简单、算法易实现,并且在理论上可以保证全局最优解的收敛性,因此得到了广泛的应用。
本文针对传统A2Star算法存在难以满足直飞限制以及无人机最小转弯半径等约束的局限性,提出了一种结合飞行器简化运动学方程的改进A2Star算法,并将该算法应用于航迹规划问题中,以达到保证无人机有效规避威胁、顺利到达目标的目的要求。
第29卷第7期2008年7月兵工学报ACTAARMAMENTARII
Vol.29No.7Jul.
2008
1 A2Star算法
在目前广泛使用的各种航迹规划算法中,A2Star算法作为一种启发式的图搜索算法,能够较好的满足航迹规划问题中的各种约束条件和要求。
A2Star算法能够在有限的可选状态中确定一个最优解,并在理论上保证全局最优解的收敛性,根据文献描述,目前尚没有哪种算法的扩展点数可以比A2Star算法的扩展点数更少[9]。
启发式A2Star搜索算法的基本思想是通过设定合适的启发函数,全面评估各扩展搜索节点的代价值,通过比较各扩展节点代价值的大小,选择最有希望的点加以扩展,直到找到目标节点为止A2Star算法中,:
表和close表,
扩展的节点,用已被扩展的节点[10]。
首先从open表中找出代价值最小的节点,将其加入close表进行扩展。
对扩展后的节点进行分析,根据分析结果对open表和close表进行修改,选择合适的扩展节点加入close表[11]。
在A2Star算法中,评估各扩展搜索节点的代价值时需要用到估价函数,估价函数的一般形式为f（m=g（m+h（m.（1其中:
g（m为初始节点S0到节点m已经实际付出的代价;
h（m是从节点m到目标节点Sg的估计代价,它体现了问题的启发式信息,其形式通常根据问题的特性而定,一般将h（m称为启发函数。
代价函数f（m表示从初始节点经过节点m到达目标节点的最优路径的代价估计值,它的作用是估价open表中各节点的重要性程度,决定它们在open表中的次序。
其中g（m指出了搜索的横向趋势,它有利于搜索的完备性,但影响搜索的效率。
在确定f（m时,需要权衡各种利弊得失,使g（m和h（m各占一定的比重[11]。
为了保证A2Star算法总能找到最小代价路径,进行搜索的图必须满足如下条件:
1搜索图中的每个节点的后继节点的数目是有限的。
2搜索图中所有弧的代价都大于某个正数ε.
3对于搜索图中的所有节点n,h^（n≤h（n.也就是说,h^（n不会超出实际值h（n的估计。
一般来说,满足以上三个条件并不困难。
只要满足以上条件,A2Star算法就可以保证找到一条到达目标的最优路径。
2 改进A2Star算法及其在无人机航迹规划问题中的应用
211 A2Star算法的改进
在传统A2Star算法的节点扩展过程中,节点扩展方式采用8个相邻的节点单元或24、48个相邻的节点单元,无法很好的考虑飞行器的最小转弯半径的限制,同时,大大增加了扩展的节点数。
本文提出
。
。
根据规划,假设飞行器做某一高度的水平飞行,对飞行器运动学方程进行简化,建立飞行器在地面固联坐标系上的运动学方程:
θ
k+1
=θk+θ0Δ,（2xk+1=xk+S0cos（θk+1,（3yk+1=yk+S0sin（θk+1.（4式中:
θk代表当前飞机在水平飞行时的航迹方位角;
θk+1代表下一刻飞机在水平飞行时的航迹方位角;
θ0为飞机在航向发生改变时变化角度的最小单位;
Δ表示航向发生改变的大小;
S0为航路规划的步长。
A（xk,yk和B（xk+1,yk+1分别表示飞机当前航路点和下一航路点的坐标。
无人机节点扩展的具体示意图见图1.
图1 点扩展示意图
Fig.1 Schematicdiagramofthenodeexpansion
在实际飞行中,通常只能得到由惯导平台确定的飞机航向角,当飞机在无侧滑平飞时,可以将飞机航向角近似等同于航迹方位角。
此外,飞机的最小转弯半径的计算公式为[12]
Rmin=v2min/g2y
max
-1.（5
式中:
vmin表示无人机的最小飞行速度;
ny
为无人机的最大法向过载。
根据飞机的最小转弯半径和航987
第7
期基于改进A2Star算法的无人机航迹规划算法研究
路规划的步长,可以计算出航向发生改变时的最大
角度为
θmax=arcsin（S0/（2Rmin.
（6最大转弯角度的计算示意图如图2所示
图2 Fig.2 Theatazimuth
将最大角度
θmax分为n等分,则Δ的取值范围为（-θmax,…,（-2/nθmax,（-1/nθmax,0,（1/nθmax,（2/nθmax,…,θmax.
在节点扩展时,将规划区域中栅格的交点作为待扩展的节点,由此带来一个问题,采用飞行器运动学方程计算获得的待扩展节点并非一定严格位于栅格的交点位置上,因此需要进行一定的处理,将计算得到的节点归算到栅格的交点位置上,作为待扩展节点。
采取以下步骤可以获得扩展的子节点:
1对计算得到的节点是否位于栅格交点进行判断,若为栅格交点,直接作为待扩展节点。
2若计算得到的节点不是栅格交点,则判断其位于哪一个栅格中,并对该栅格的四个顶点进行判断,判断是否位于威胁区域中。
若位于威胁区域则取消其作为待扩展节点的资格。
3计算余下的栅格的顶点到目标的距离,选取离目标最近的顶点做待扩展节点。
212 改进算法在威胁规避技术中的应用
在改进算法的应用问题上,首先考虑一种较为简单的情况,即假定飞行器对所有经历的威胁均作简单的回避。
所有威胁均用威胁圆来描述,描述方法为将威胁信息的表达统一采用这样一种形式（x,y,R,V,其中,x、y表示威胁的中心坐标,R表示受威胁影响区域的半径,V代表通过威胁等级评估得到的威胁等级。
威胁等级的数值越大,代表该威胁对无人机可能造成的损坏程度越高,无人机在穿越该威胁影响的区域时所面临的危险越大。
要求寻
找一条参考航迹使到达目标点的路径长度最短,且
规划路径不穿越所有的威胁圆。
在采用改进A2Star算法生成所需的参考航迹时,为了保证规划航线不穿越威胁区域,必须保证当前节点与扩展节点之间的连线不穿越威胁区域。
如果该连线穿越危险区域,对扩展节点应当予以删除。
按照上述方法对规划区域内部所有威胁圆依次进行验证,可以保证沿该段航迹飞行的安全性。
下面将改进A2Star算法与原始A2Star算法进行对比仿真50×
（5,5,终点,
☆表示。
得到的规划路径如4所示。
图3 A2Star算法规划航迹示意图
Fig.3 Schematicdiagramofplannedroute
byA2Staralgorithm
图4 改进算法威胁规避示意图
Fig.4 Schematicdiagramofavoidingthreat
byimprovedalgorithm
对改进A2Star算法与原始A2Star算法在规划
结束后open表的节点数和close表的节点数以及规划路径长度进行比较,结果如表1所示,采用改进算法扩展的节点数大大减少,而路径代价（在这里指的
97兵 工 学 报
第29卷
是飞行路径的长度改变不大。
之所以会产生这样的结果,是因为改进算法采用了较大的搜索步长,因而减少了扩展节点;
较大的搜索步长可以有效地对路径优化,但是也会带来较大的转弯角度,造成路径长度的增加。
综合这些因素,路径长度代价值大致相等。
表1 A2Star算法与改进算法比较
Tab.1 TheperformancecomparisonbetweentheA2star
algorithmsoftheoriginalandtheimproved算法open表节点数
close表节点数路径代价
原始A2Star算法1425296016691改进A2Star算法
165
77
6015132
213 、,、威胁代价的综合评估,。
与仅仅对威胁进行规避的做法相比较,采用路径代价综合评估技术可以更好地适应规划区域的情况以及飞行任务的需求。
例如针对一个威胁,从威胁区域中心到威胁区域边缘的威胁大小是不同的,越接近威胁中心,威胁越大,而越接近威胁区域边缘,威胁相对来说较小。
因此,针对不同飞机对抗威胁的能力以及执行任务时的紧迫性,对一些威胁程度较小的区域进行穿越可以提高执行任务的效率。
在对路径代价进行综合评估时,路径代价的评估函数使用距离代价（Distance和威胁代价（Hazard的加权和来表示,具体表达式为
Cost=Wd・Distance+Wh・Hazard,（7其中,Wd、Wh分别为组成路径代价的权重。
假定生成的路径由一系列的节点连接而成,假定路径的起点为C1,终点为Cn,生成路径可以表示为
route=（C1,C2,C3,…,Cn.（8路径代价中的距离代价可以表示为节点之间的
连线的距离的累加,即
Distance=
∑N
i=1
d（Ci
Ci
+1,
（9
其中,d（Cn,Cn+1代表当前节点到下一节点的路径长度。
为了计算威胁的代价值,将规划路径中两个节点之间的连线进行等分,即对以规划步长为长度的线段进行等分。
若规划步长为L0,则规划航迹可视为由长度为L0的直线段首尾连接而成。
为了表示每一段航迹的威胁总量,需要对该段航迹上每一点
的威胁Mhazard进行积分。
在计算威胁代价值时,我
们将扩展的直线段按照长度ΔL=L0/N分成N等份,并计算每个点到威胁中心的距离l1,l2…lN.如果该段航迹需要考虑M个威胁,那么该段航迹的威胁总量为:
Hazard=
∑M
∫L
Mhazarddl,（10
式（10中的积分项可视为直线段上N个点的威胁
值累加,即
Mi1Nj=1
ij=M
il1+i+l・Vi.
（11
A2Star算法进行规划时,按照公式（1,需要对g（n和h（n进行确定。
在这里,g（n使用距离代价和威胁代价的加权和来表示,距离代价和威胁代价按照式（9和式（11分别进行计算。
而对于h（n,对于每一个搜索节点n,应当满足h^
（n≤h3（n,其中h3（n代表从节点n到目标节点的实际路径代价。
考虑到组成路径代价的不同因素,h（n可以表示为
h（n=hd（n+hh（n.（12这里hd（n和hh（n分别是距离和威胁的启发
式代价,将hd（n取值为当前节点到目标节点的欧几里德距离,而将hh（n取值为0,这样可以满足改进A2Star算法对搜索图的限制,保证能够搜索到一条最优路径。
考虑到规划任务的需求和执行任务时的规划环境,需要对路径代价中的权重Wd、Wh进行赋值。
举例来说,若无人机在恶劣天气投递重要设备,就需要飞行路径尽可能的远离威胁,以保证飞机的安全性。
而若要执行某项紧急任务,则需要飞行的路径长度尽可能的短,以便减少飞行时间。
一个有经验的飞行员可以根据他长久以来积累的经验作这些决定;
而对于无人操纵飞行器,这就需要从有经验的飞行员那里提炼经验,
并使用一定方式表达,以便能够在航迹规划问题中得到应用。
在图5和图6中,分别给出了Wd=012,Wh=018和Wd=018,Wh=012两种情况下的规划路径仿真结果。
威胁区域特性建模和航迹规划方法仍然采用前文所述的改进A2Star算法,并结合无人机简化运动学方程对最小转弯半径进行限制。
Wd、Wh作为组成路径代价的权重,其取值的相对大小对于生成的路径的形状有较大程度的影响。
若Wd的取值相对较大,则意味着对生成路径的长度这个指标
1
97 第7期基于改进A2Star算法的无人机航迹规划算法研究
更加重视,而若Wh的取值相对较大,则意味着对威
胁规避这个指标更加重视。
由图5和图6可以看出在第一种情况下很好的规避了威胁,而在第二种情况下为了缩短路径长度,对威胁区域的边缘发生了穿越
图5
Wd,Wh=018时的规划路径
Fig.5 TheplannedrouteatWd=012,Wh=018
图6 Wd=018,Wh=012时的规划路径
Fig.6 TheplannedrouteatWd=018,Wh=012
3 结论
本文针对传统A2Star算法存在难以满足直飞限制以及飞机最小转弯半径等约束的局限性,提出
了一种结合飞行器简化运动学方程的改进A2Star算法,并将该算法应用于无人机航迹规划问题中,研究了综合考虑各路径代价影响因素情形下的航迹规划方法。
仿真结果表明,改进A2Star算法能够更为有效的解决无人机在未知危险环境中的威胁规避问题,从而为顺利完成战术任务奠定了良好的基础。
参考文献（References
[1] RobertJ.Szczerba.Robustalgorithmforreal2timerouteplanning
[C].IEEETransactionsonAerospaceandElectronicSystems,2000,36（3:
869-878.
[2] VachtsevanosG,KimW.Autonomousvehicles:
fromflightcon2
troltomissionplanningusingfuzzylogictechniques[C].The13thInternationalDigitalSignalProcessingConf.,1997:
977-981.[3] 夏洁,高金源.满足战场需求的实时飞行路径规划[J].北京航
空航天大学学报,2004,30（2:
95-99.
XIAJie,GAOJin2yuan.Real2timeflightpathplanningforcom2batmission[J].JournalofBeijingUniversityofAeronauticsandAstronautics,2004,30（2:
95-99.（inChinese
[4] 周坦胜,李斌,何万宇.真[J].,2004（12-2720.
ZHOU2,,Linearprogrammingal2referenceflightpath[J].of,2004,16（12:
2718-2720.（in
[5] 符小卫,高晓光.一种无人机路径规划算法研究[J].系统仿
真学报,2004,16（1:
20-34.
FUXiao2wei,GAOXiao2guang.StudyonakindofpathplanningalgorithmforUAV[J].JournalofSystemSimulation,2004,16（1:
20-34.（inChinese
[6] RathbunD,KragelundS,PongpunwattanaA,etal.Anevolu2
tionbasedpathplanningalgorithmforautonomousmotionofaUAVthroughuncertainenvironments[J].IEEETransactionsonAerospaceandElectronicSystems,2002,38（2:
1-12.[7] 唐强,王建元,朱志强.基于粒子群优化的三维突防航迹规划
仿真研究[J].系统仿真学报,2004,16（9:
2033-2036.
TANGQiang,WANGJian2yuan,ZHUZhi2qiang.Thesimula2tionstudyofPSObased3-Dvehiclerouteplanningforlowatti2tudepenetration[J].JournalofSystemSimulation,2004,16（9:
2033-2036.（inChinese
[8] GuangYang,VikramKapila,Optimalpathplanningforun2
mannedairvehicleswithKinematicandtacticalconstraints[C].Proceedingsofthe41stConferenceonDecisionandControl,2002:
1301-1306.
[9] IrisHongYangy,YiyuanJZhao.Real2timetrajectoryplanning
forautonomousaerospacevehiclesamidststaticobstacles[R].A2IAA2200223421,2002.
[10] 杜萍,杨春.飞行器航迹规划算法综述[J].飞行力学,2005,
23（2:
10-14.
DUPing,YANGChun.Introductionofairvehiclepathplan2ningalgor
升级会员 