无人机航迹算法综述VIP

为促进航迹规划技术的发展,对航迹规划常用算法进行综述。首先对航迹规划的规划思想和构成进行分析；其次将航迹规划算法分为传统经典算法和现代两大类,对其中几种常用算法进行分析总结；最后阐述现代智能算法在航迹规划应用随着航空技术日益发展,越来越多的无人机被用于替代飞行员执行一些高危险、高强度或大范围巡检、搜救任务,因此完善的任务规划系统是无人机顺利完成任务的重要保障。任务规划系统一般由航迹规划、导航、数据通信3大子系统组成,而航迹无人机航迹规划就是在综合考虑无人机到达时间、油耗、威胁因素的前提下,为无人机规划出最优或满意的飞行航迹,以保证圆满地完成飞行任务[1]。无论是在军事还是民用领域,好的航迹规划系统都是提高无人机安全性能,保证无人机出色完成任务的重要手段。笔者将在对航迹规划问题进行分析的基础上,对当前几种常用航迹规划算法进行分类总结,最后指出目前研究热点及未来发展趋势。在不考虑时间因素的情况下,无人机航迹规划应该是在三维空间中进行的,但在一些任务中,无人机保持在固定高度飞行,不需要考虑高度变化问题。因此在进行航迹规划时可以将三维空间中的物体投影到二维平面,从而将三维航迹规划问题降至二维,简化问题的复杂度。但在军事突防、电力巡线、山地救援等应用中,二维航迹规航迹规划问题是一个包含多个优化目标和多个约束的非线性规划问题[2],其核心就是建立目标函数的数学模型和有效地处理各项约束。由于涉及约束条件较多,目标函数复杂,数学模型建立困难,为降低问题复杂性,目前大多数学者都采用分层规划的思想,将航迹规划分为两步进行。首先根据已知的环境信息、任务要求等在无人机起飞前为其规划出一条满足约束条件的全局最优参考航迹。无人机在行的过程中,当出现未知或动态威胁信息时,再进行局部航迹动态优化。由于全局参考航迹规划需要考虑整体的优化,因此要在避免陷入局部最优的情况下尽量减少计算量。而局部航迹动态优化用于应对突发威胁,因此要尽量缩短规划时间以确保实时无人机航迹规划一般由以下几个部分组成：描述规划空间,选择航迹的表示形式,分析约束条件,确定代价函数,选取航迹搜索算法和航迹平滑。1)描述规划空间。其目的是建立一个便于计算机进行航迹规划所使用型,即将实际的物理空间抽象成算法能处理的抽象空间,实现相互间的映射。规划空间的表示是否合理直接影响规划的效率和结果的优劣性。一种好的规划应能满足如下要求:①规划空间能合理且尽量完善地反映飞行环境中的各种信息(地形、威胁、障碍等),以利于航迹搜索；②当飞行环境中的某些信息发生变化时能实时地进行更新,以满足实时应用的要③能满足无人机自身性能约束条件,包括最大拐弯角、最大爬升/俯冲角、最大常用的规划空间表示方法有栅格法和图形法。栅格法简单的单元,并为每个单元分配一个代价值,对应于无人机经过空间相应区域的代价,并判断这些单元之间是否存在可行路径,找到包含起始点和目标点的单元,从起始单元开始,依次向栅格中代价最小的邻域移动,最后到达目标单元[3]。航迹搜索算法中式存储,所以多数的航迹规划研究都是使用栅格法表示规划空间。图形法首先根据一定规则将规划空间表示成一个由一维线段构成的网络图,然后采用某一搜索算法在该网络图上进行搜索。使用图形法必须表示出所有可能的路径,否则就可能丢失最优法[4]、可视图法(VisibilityGraph)[5]、随机路标图法(PRM：2)航迹表示。其形式有两种：一种是基于无人机滑航迹,采用此种表示方法可以省去最后的航迹平滑环节；另一种是用航迹点表示,②将复杂的航迹规划问题分解为一组统一形式的小规模子问题,对于每个子问题,只需关心一个点的坐标,从而将考察航迹是否可行变为仅考察一个点或一条直线3)分析约束条件。航迹规划问题需要考虑的约束条件包括环境约束、任务约束和无人机自身性能约束。环境约束有威胁约束(如被敌方雷达发现概率、敌方导弹高炮击落概率、撞地概率等)、禁飞区约束、复杂气象区约束等；任务约束有任务完成时间、起始点、目标点、固定航向角、低空/超低空突防等；无人机自身性能约束有最大/最小平飞速度、最大航程、最高/最低飞行高度、水平最小转弯半径、最大爬升角/俯冲角、最大纵向曲率、最大法向过载等[7]。若是进行二维航迹规划,则不需4)确定代价函数。代价函数将算法与实际物理问题紧密联系在一起。对于无人机航迹规划,代价函数是评价航迹优劣的标准,代价值越小则表明航迹越优,反之表明航迹越差。确定代价函数需要综合考虑影响航迹性能的各项因素,对各个指标进行量化和计算。三维航迹规划的代价函数通常包含航迹长度代价、威胁代价和高度代价,其中J为航迹总代价,L为航迹长度代价,一些文献也称其为燃油代价,T为威胁代价,H为高度代价；ω1、ω2、ω3为相应的权系数,根据任务需要设置其值。二维5)选取搜索算法。根据任务需求选取合适的算法规划出满足约束条件、规避障6)航迹平滑。通过相应算法搜索出的航迹对于无人机实际飞行而言并不一定可行,例如规划出的航迹拐弯点较多,而无人机在实际飞行中由于自身机动限制不能频繁转弯,因此需要对规划出的航迹进行平滑处理,消除不必要的拐弯点以利于无人机实际飞行。常用航迹平滑方法有三次样条插值法[8]、贝塞尔曲线(BezierCurve)[9]、k-trajectory算法[10]等。无人机航迹规划的本质是路径规划,即寻找适当的策略构成连接起点到终点位置的由序列点或曲线组成的路径,因此用于航迹规划的算法实际上也就是路径规划算法。路径规划算法有很多,每种算法都有其自身的优缺点和适用范围,按照规划决策可以将算法分为传统经典算法和现代智能算法[11]两类。2.1传统经典算法近年来常用于航迹规划的传统经典算法有Dijkstra算法、人工势场法(APF：ArtificialPotentialField)和模拟退火算法(SAA:SimulatedAnnealingAlgorithm)。Dijkstra算法是图论中求解最短路径的经典算法,适用于每条边的权数为非负的情况,能得到从指定顶点到其他任意顶点的最短路径。使用Dijkstra算法进行航迹规划,构建的赋权图的顶点代表航迹点,赋权图的边代表所有可行航迹,Dijkstra算法的作用就是在这些可行航迹里找到最优航迹。Dijkstra算法实现简单,但其运算时间和所用内存与搜索空间中节点个数平方成正比,在大范围高维空间中搜索时间长,对内存要求也很高,因此多用于二维静态航迹规划[12,13]。由于航迹规划空间范围大,对于Dijkstra算法在航迹规划中的应用,如何选取有效航迹点,减少航迹点数量,缩短规划时间是问题的关键。文献[12]在Voronoi图的基础上使用Dijkstra算法寻找最优航迹,将威胁看作一个点,选取各威胁点之间连线的中垂线的交点为航迹点。这种方法能保证航迹最大化避开各个威胁,安全性高,但航迹较长。并且没有考虑无人机最大转弯角约束,航迹不一定可飞。文献[13]在可视图的基础上使用Dijkstra算法寻找最短航迹,将多边形障碍的各个顶点看作航迹点,并建立转弯角约束机制。这种方法得到的航迹短,满足无人机最大转弯角约束,但由于航迹贴近障碍物,安全性较低。此外,可视图不能表达物体运动的方向性约束的缺陷导致Dijkstra算法在搜索时可能找不到路径。虽然Dijkstra算法多用于二维航迹规划,但也有学者将其应用于三维航迹规划。文献[14]将飞行空间映射到由若干个四面体作为航迹点,所有相邻四面体内切球中心点的连线构成一个三维网络,这个三维网络就是所有可行航迹。然后用Dijkstra算法在这个三维网络上寻找最短航迹。最后用似,规划出的航迹能最大化避开威胁,安全性高,但航迹相对较长。目前使用Dijkstra基础上利用Dijkstra算法寻找最短航迹,但得到的航迹若安全性高则航迹长,若航迹短则安全性低,没有在航迹长度与安全性之间寻找到一个好的平衡。人工势场法是一种模拟电势场分布的规划方法,任务区域内的目标点产生引力场,威胁源产生斥力场,无人机在引力和斥力的共同作用下向目标点运动。传统人工(3)(4)其中Katt和Krep分别为引力和斥力增益系数,且均为正常数；ρ(X,XG)为航迹Fatt=-Uatt(X)=-Kattρ(X,XG)(5)总势场力为目标点产生的引力和各个威胁源Ftotal=Fatt+∑Frep(7)人工势场法的优点是算法简明、实时性好、规划速度快,在局部规划和实时规划领域应用广泛。缺点是当无人机离目标点比较远,Fatt≫Frep时,合力方向更趋近目标点方向,无人机可能会进入威胁区；当目标点附近有威胁源时,斥力将会非常大,而引力相对较小,无人机将很难到达目标点；在复杂环境中,容易产生局部极小值,使算法停滞或震动；在障碍物附近有抖动现象,在狭窄通道间频繁摆动；在动态环境下规划效果减弱；计算势场负梯度的方法因为没有优化变量,将航迹规划问题转换成了非优化问题,因此缺乏评价指标衡量航迹的优劣,势场的建立直接决定了航迹的质量,相同的环境下,不同的势场形式也可能得到不同的航迹。针对该问题,学者们结合无人机航迹规划的特点提出了多种改进方法。文献[15]在斥力势函数中加入无人机与目标点的距离,减小斥力,改善障碍物在目标附近时,目标不可达的问题。设置引导点为无人机提供方向随机的势场力,解决局部极小值和震荡问题。文献[16]在人工势场法搜索陷入威胁区时,构造惩罚势函数替代斥力势函数,并使用模拟退火算法取代虚拟力引导的方法搜索逃离位置,有效避免了局部极小值和抖动现象,得到的航迹能成功避开威胁,但增大了计算量,降低了人工势场法的实时性。文献[17]通过引入相对速度斥力势场和斥力增益模糊控制器实现人工势场法的动态避障,避免局部极小值。文献[18]通过增加高度调节引力势函数以增强人工势场法在三维航迹规划中对高度的控制,同时引入飞行器的动力学约束条件,使航迹更具可飞性,并改善了人工势场法的局部极小值、障碍物附近抖动、狭窄通道间频繁摆动等缺点。然而文献[15-18]中均未衡量航迹优劣的评价指标,对此文献[19]引入附加控制力作为优化变量,通过优化出适当的附加控制力,使无人机在满足各种物理约束的条件下,规划出的航迹可使代价指标最优,降低了势场建立的任意性对航迹结果的影响。但文献[19]在考虑无人机动力学模型时将无人机看作质点,与实际动力学模型有一定差异。总之,对于极小值等问题,前人提出的各种改进方法都在一定程度上弥补甚至消除了这些缺陷,但对于模拟退火算法是基于蒙特卡罗迭代求解法的一种启发式随机搜索算法固体物质的退火过程,在某一初始温度下,伴随温度控制参数按照降温函数不断下降,结合概率的突跳特性在解空间中随机寻找目标函数的全局最优解,即能概率性地跳出制,包括温度控制参数的初值t及其衰减因子Δt、每个t值时的迭代次数和终止条件。模拟退火算法的优点是算法求得的解与初始解状态无关,具有渐近收敛性,是一新解的变换方法和冷却进度表的设计。在航迹规划中,模拟退火算法的一个解代表一条航迹,目标函数则是代价函数,常用于求解二维航迹规划中的TSP问题[20],但该算法多数没有考虑无人机的机动性能约束,得到的航迹可飞性不高。模拟退火算法也可与易陷入局部最优解的算法相结合帮助其跳出局部最优找到全局最优解,如遗传模拟退火算法[21],在交叉和变异过程中使用Metropolis准则判断是否接受新解,当然,2.2现代智能算法相较于传统经典算法,现代智能算法的应用更为广泛。在航迹规划中常用的现代A*算法是一种智能启发式搜索算法,它将搜索空间表示为网格的形式,以网格的中心点或顶点作为航迹点,通过搜索邻域内代价函数值最小的航迹点,从起始点逐步搜索到目标点,最后逆向回溯当前节点的父节点生成最优航迹,其中待扩展航迹节点f(x)=g(x)+h(x)(8)其中g(x)表示从起始点到当前节点的实际代价,h(x)称为启发函数,表示从当前节点到目标点的估算代价,常用的启发函数可选用欧氏距离、曼哈顿距离、对角线距离等。启发函数是A*算法的核心,它能在搜索效率和最优解之间权衡。若h(x)小于从当前节点到目标点的实际代价,则搜索得到最优路径,但这时搜索节点增多,搜索效率降低；若h(x)一直等于从当前节点到目标点的实际代价,此时A*严格按照最优路径搜索,搜索效率最高；若h(x)大于从当前节点到目标点的实际代价,则搜索结果可索效率,当路径很长时,这种影响会更明显。总之,启发函数的选择决定了A*算法是否搜索空间增大,A*算法的计算量会呈指数增长,导致规划时间过长,一般用于静态航迹规划。在航迹规划中,如何提高A*算法的运行速度并得到最优航迹是学者们重点考虑的问题。文献[7]采用结构体式最小二叉堆和三层嵌套的二叉堆技术分别维护管理找的高效率,较大幅度提高了A*算法的规划效率。文献[22]提出使用2.5维网格模型描述三维规划空间,每个网格点包含经度、纬度和高程信息,此方法计算效率要远大于三维网格划分方式。文献[23]将三维航迹规划分解为二维规划和高度规划,使用动再由二维航迹结合高程数字地图,利用粒子沉降法赋予每个航迹点高度信息,生成三维航迹。这种方法有效地将三维空间的搜索节点删减至二维,大大减少了搜索节点数离、曼哈顿距离和对角线距离,但仍不是最优航迹。由于航迹规划问题的复杂性,虽然学者们通过各种改进方法提高了A*算法的搜索效率,但仍没有找到值恒等于从当前遗传算法的基本思想是模拟生物遗传进化过程,根据“适者生存”、“优胜劣汰”的原则,借助选择、交叉、变异等操作,使所要解决的问题从初始解一步步逼近最优解。在航迹规划中,遗传算法每条染色体(个体)代表无人机的一条航迹,基因的编码方式也就是航迹节点的编码方式,适应度函数由代价函数变化而来。遗传算法的优点是不要求优化函数具备连续、可导和单峰等条件,具有较强的鲁棒性,是一种高效、并行、全局的搜索方法,适用于三维全局航迹规划。缺点是种群失去多样性而导致早熟收敛,寻优时间长,局部搜索能力差等。针对该问题,学者们提出了不同的改进方法,如引入量子、自适应等因子,但这些改进方法仍然存在较多不足。文献[24]针对量子遗传算法初始种群的单一性,引入关于概率划分的小生境协同进化策略,并对各种群采用动态量子旋转角；采用精英选择机制,保留每一代中的最优个体,并借鉴狼群分配原则对种群进行更新。该方法提高了量子遗传算法的稳定性和寻优精度,但在收敛速度上没有改善,且没有考虑无人机自身性能约束。文献[25]使用并行遗传算法结合概率地图实现多无人机协同航迹规划,并行遗传算法很好地克服了遗传算法早熟的缺陷,但文献同样没有考虑无人机自身性能约束。文献[26]通过在遗传算法主种群上附加一个病毒种群的方法,保证可行引导段的有效积累并维持种群多样性。采用定长实值和变长实值两种编码方式分别为染色体和病毒个体编码,通过采用反转录和转导这两种病毒感染操作实现两个种群间模块的信息交换,使进化信息在种群内迅速、定向地传播,消除了寻优过程的盲目性。该方法改善了遗传算法早熟和局部收敛慢的问题,提高了收敛速度,但对于搜索精度几乎没有提高。文献[27]提出多频振动遗传算法,在遗传操作中使用两次变异操作,分别作用于整个种群和精英个体,为种群提供全局多样性和局部多样性,从而有效避免早熟,提高搜索精度,达到快速收敛的目蚁群优化算法模拟蚂蚁在寻找食物过程中发现路径的行为特性,利用信息素浓度(9)叫启发函数,它可以是距离开销,也可以是距离开销与其它开销的组合,如高度、安全度等；α、β为τab与ηab的相对重要性的权值；为节点a的所有相邻节点信息素具有挥发性,随着时间的增加其浓度会降低。信息素的更新分为局部更新和全局更新,局部信息素更新是用在蚂蚁完成一个航迹点的选择时,相应的减少该点的信息素,降低此点对后来蚂蚁的吸引程度,从而增加蚂蚁的探寻范围,减小算法陷入τab(t+1)=ξτab(t)(10)其中ξ为信息素减少因子,用于控制信息素减少的大小。全局信息素更新是经过m时刻,当蚂蚁完成寻路任务后对其经过的所有航迹点上的信息素这种方式增加这条航路上的信息素,其表达式为τab(t+m)=(1-ρ)τab(t)+ρΔτab(11)Δτab=Q/J(12)蚁群优化算法的优点是具有良好的并行性、协作性和鲁棒性,后期收敛速度快。缺点是前期搜索时间长,参数多并且解的质量受参数影响大,容易陷入局部最优解,适用于三维全局航迹规划。由于信息素的分布情况、挥发方式和蚂蚁选择前盲目性影响着解的质量和获得解的时间,学者们也通常从这几个方面,结合航迹规划的特性对蚁群算法进行改进。文献[28]将蚂蚁按数量均匀分组,并在信息素浓度更新过程中使用差分进化算法的交叉、变异、选择操作,合理分配各路径上蚂蚁留下的信息素,避免某条路径上信息素累积过多而导致陷入局部最优解,从而引导蚂蚁找到最优路径。该混合算法在保证基本蚁群算法优点的同时提高了全局收敛的速度,但得到的航迹过长。文献[29]提出一种文化蚁群算法,设计了由蚁群算法演化的群体空间和由群体空间最优解构成的信仰空间,两个空间同时演化,彼此促进。在群体空间中加入惩奖机制,对到达终点的蚂蚁走过的路径,提高其信息素浓度,反之,则降低,从而提行更新。此外,文献在启发式函数中加入了航路点的方差,计算待选节点和其前面n个点的方差,使选出的节点与前面节点的波动相对较小,从而获得更平滑的航迹。该方法的双层进化模型加快了航迹的搜索速度,但惩奖机制的评判标准单一,到达终点的蚂蚁走过的路径并不一定就好,此机制可能会降低解的质量。文献[30]首先限制信息素挥发因子的范围,防止其过大或过小影响算法的全局搜索能力,并在信息素调整规则中引入航迹评价指标,提高解的质量。然后将起始点和目标点之间的连线这一最短航迹信息反馈到系统中作为搜索的指导信号,将能见度改进为当前节点与待扩展节点的距离和待扩展节点到最短航线的垂直距离加权和的倒数,降低算法寻找航迹的盲目性,加快了搜索效率。最后在该能见度的基础上,将转移概率与一个0～1之间的随机数相乘,选择邻域中转移概率最大的节点扩展。该方法在保证基本蚁群算法优点的同时提高了解的质量,大大缩短了搜索时间。粒子群优化算法模拟鸟群飞行捕食行为,把每个粒子看作优化问题的一个可行解,并将其延伸到N维空间,每个粒子主要通过跟踪两个位置决定自己下一步的飞行,一个是粒子本身所找到的最优解Pbest,即个体最好位置；另一个是种群中所有粒子当前找到的最优解Gbest,即全局最好位置,最终群体成员逐渐移入问题空间的更好区域。所有的粒子都有一个由被优化的函数决定的适应值,每个粒子还有一个决定其飞行方向和距离的速度。粒子群算法的速度和位置vij(k+1)=ωvij(k)+c1r1(pij(k)-xij(k))+c2r2(gij(k)-xij(k))(13)xij(k+1)=xij(k)+vij(k)(14)其中下标i、j、k分别表示第i个粒子,第j维空间,第k代粒子；ω为惯性权重,描述了粒子对之前速度的“继承”；c1、c2为常数,称为学习因子,体现了粒子向全局最优粒子学习的特性；r1、r2为(0,1)之间的随机数。与其他进化算法相比,粒子群算法具有两个显著的不同特点。一是没有“优胜劣汰”的机制,所有的粒子在迭代过程中始终作为种群的成员保留；二是没有交叉、变异等进化算子,每个粒子通过追随当前搜索到的最优值寻找全局最优。粒子群算法的优点是具有较强的鲁棒性,对种群大小敏感性不高,参数少,前期收敛速度快,缺点是后期收敛速度慢,容易早熟陷入局部最优解,可用于三维全局航迹规划。在航迹规划中学者们对粒子群算法的改进也多是通过提高种群的多样性避免局部最的基础上引入繁殖机制,整个种群中粒子位置更新后不直接进入下一代,而是以一定概率将粒子放入繁殖池,种群中最优个体不参与繁殖操作,以便保护其不被破坏。该度慢的问题,该方法能得到质量更好的航迹。3.1现代智能算法的改进这将要消耗大量的时间,而实际应用往往要求航迹规划系统能快速响应,远远超出规定时间得到的航迹即便再优也不具有任何意义。因此,保证在规定时间内规划出可行且尽量接近理论最优航迹的规划方法更具有现实意义。而实现这一