成都飞机工业集团有限责任公司 彭闪 殷苑 田峰 冯张伟 姚森

航迹规划作为任务规划的核心，在任务规划中起着决定性作用。本文首先介绍了无人机航迹规划的国内外研究现状，再介绍了几种常见的航迹规划算法，最后表述了航迹规划中的一些难点与问题，并对航迹规划的发展进行了总结。

近几十年来，无人驾驶飞机在战争中已得到广泛应用，由于其机上无人操作的特点，直接减少了人员伤亡，缺少飞行员可以减轻体重，降低成本，并为新的作战范例提供机会。将使无人机能够在最少或没有人为干预的情况下执行任务，这样的军事和民用任务可能包括情报搜集、目标跟踪和救援任务[1]。

1 国内外研究现状

近年来，国内外涌现了大量关于航迹规划的算法。各式各样的算法优缺点各异，所适用的场景也不尽相同。Al等人[2]提出了一种以较低的计算复杂度提供动态路径发现的启发式算法。2003年，Nikolos等人[3]设计出一种用于无人驾驶飞行器(UAV)自主导航的离线/在线路径规划器。解决了在已知环境中使用离线规划器的无人机导航问题。Sahingoz等人[4]采用遗传算法(GA)，提出了一种多无人机系统的可飞行路径规划。2006年，Foo等人[5]提出了一种粒子群优化(PSO)算法来规划三维路径。通过使用PSO算法规划出避开障碍物和威胁区的可行路径。魏等人[6]在2016年研究了一种基于高度层引导因子的改进蚁群算法。2013年，刘等人[7]提出了一种改进后的稀疏A*算法，通过降维将三维航迹规划将至二维航迹规划，降低了计算复杂度与规划时间。2014年，王等人[8]研究了一种基于三维约束的人工势场法，用于实时航迹规划。2016年，丁等人[9]提出了一种改进后的人工势场法，该方法简单易于实现，且具有较好的适应性。

2 航迹规划算法

近年来，国内外学者研究了许多航路规划的算法，主要可分为三类：确定性算法、随机性算法、最优化算法。

2.1 确定性算法

确定性算法，大致理解是指当前节点的下一节点或下一序列是确定的。下面将介绍几种典型的确定性算法。

2.1.1 Voronoi图

Voronoi图是根据战场上的场景信息，将威胁区域的中心区域用一个圆点代替，再构建相邻威胁区之间的连线的垂直中位线，使得该垂直中位线上的每一点，与该相邻威胁点的作用距离一致，或者根据战场环境和任务需求调整权重，均衡了各区域的威胁。每一条垂直平分线共同构成了一个由若干多边形组成的网格，以此将航路规划转换成最小路径求解。如图1所示。其中灰色圈表示威胁区中心位置，多边形的任一条边为相邻威胁点的垂直中位线。

图1 Voronoi图Fig.1 Voronoi diagram

Voronoi图通常应用于划分复杂场景的区域，通过Voronoi图划分后，复杂区域被分成了很多个子区域。而多边形的每一条边则为可行路径，但可行路径不一定是最优路径，因此还需要采取其他搜索算法进行寻优，最终得出最优或次优航迹。Voronoi图的一大特征是直观，通过划分区域，可以将躲避威胁转变为求解最短路径问题，Voronoi图一般适合用在二维航路规划中。

2.1.2 A⋆算法

A*算法的主要思想是：设定合适的启发函数，选取一个当前节点，搜索其下一节点，计算其所有下一节点的代价值，并将所有下一节点的代价值进行比较，选取代价值最小的点，将其标记为扩展节点，作为潜在最优航迹节点之一，以此不断递推，直到计算到最终的目标节点。从起始点到目标点做标记的扩展点，即可构成由A*算法搜索出的最优路径。

在A*算法中，通常会设定一个OPEN表和一个CLOSE表。其中，OPEN表用来表示已经计算出代价值但还未标记为扩展节点的点集合，不包括已扩展的点。如图2所示，若当前节点为A点，则A点的下一节点有B点、C点和D点，计算出A点到B点的代价值为3，A点到C点的代价值为4，A点到D点的代价值为2，因此将B点、C点和D点放入OPEN表中，即OPEN=[B,C,D]。比较其大小，得出A点到D点的代价值最小，因此将D点放入CLOSE表，即CLOSE=[D]，同时将D点从OPEN表中删除，更新后的OPEN=[B,C]。以此类推，按A*算法计算出的CLOSE表中所存储的节点为CLOSE=[A,D,E,F,H,K]，即构成由该算法搜索出的最优航迹。

图2 路线示意图Fig.2 Schematic diagram of the route

A*算法的搜索过程用数学模型表示，代价估计值表示为：

f(n)=h(n)+g(n)

其中，f(n)表示从起始点经过节点n到目标点的代价估计函数，g(n)表示起始点到当前节点n的实际代价函数，h(n)是启发函数，也是从当前节点n到目标点的代价估计函数。通常情况下，启发函数h(n)决定了是否能找到最优路径，因此启发函数的选取尤为重要。

A*算法其实是一种扩展节点不断扩大的搜索过程，算法简单，计算量小，具有较快的规划计算速度。并且A*算法收敛程度更好，时间复杂度更小，应用范围更广，全局性好，计算效率高，内存需求少，适合解决静态的规划问题。

2.1.3 人工势场法

人工势场法采用虚拟模仿的方法，将战场上的敌方威胁区及各种禁飞区、避飞区、障碍物等视为无人机飞行的阻力，将该阻力假设成战场空间中，无人机飞行前进中的所受到的排斥力，阻碍无人机飞行。而无人机的目标终点被视为对无人机产生吸引力，于是将无人机在复杂环境下的航路规划过程看作由吸引力和排斥力组成的合力的作用过程。

人工势场法具有安全性高、算法计算简单易实现的优点，其规划时间短、速度快、实时性好。若斥力的合力大于或等于目标的吸引力，将导致无法规划出最优或次优路径，容易陷入局部最优。人工势场法一般适用于协同规划和局部静态航迹规划。

2.2 随机性算法

随机性算法，大致理解是当前节点的下一节点或下一序列通常是随机出现的，该类算法的不确定性增强。下面将介绍几种典型的随机性算法。

2.2.1 遗传算法

在航迹规划中，首先建立代价函数，再通过代价函数计算出每一节点的数值，并将其作为下一代节点选取的依据，不断进化迭代，最终规划出最优航迹。通常情况下，遗传算法的稳定性很强，能实现在全局范围内寻找最优解，时间复杂度更小，不容易陷入局部极值，找到全局最优解的概率很大。适用于三维全局航迹规划和静态航迹规划[10]。

2.2.2 蚁群算法

蚁群算法的思想是：由于蚁群在觅食的时候，会产生某种能传递信息的物质。因此蚂蚁在经过的路段中，都会存在这种物质，在找到食物的最短路径上存在的该种物质会越积越多，含量越来越高，进而使得该条路径上的蚂蚁不断增加，最终所有的蚂蚁都选择这条路径，逐渐收敛。

在航路规划中，满足约束条件下，信息素浓度相当于航迹代价，航迹代价越小的路径，会被无人机优先选择，并将代价反馈。蚁群算法具有很好的稳定性与通用性，易于并行实现，也适合和其他算法共同规划路径，其收敛程度更好，时间复杂度更小，范围更广泛，适用于离线状态下的全局航迹规划。

2.2.3 粒子群算法

粒子群优化算法基本思想为：(1)已知当前粒子的位置与速度矢量，包括大小和方向；(2)已知当前节点的历史最优速度矢量，包括历史最优速度大小与方向，即节点自身的极值；(3)已知在全部节点中的全局历史最优速度矢量，即全部节点的极值。根据这三个已知量，不断进化最后达到一个收敛的状态，直到搜索出全局最优解。以此更新后的位置点距离真实目标点有一定的偏差，通过不断进化更新，逐渐收敛于真实值。

粒子群算法具有易于实现、快速收敛的优点，可变参数少，其算法鲁性较强，原理简单，搜索能力全面。

2.3 数学规划

动态规划。动态规划算法一种求解决策过程最优的算法。它将一个问题分解成多个子问题，每一个子问题之间不是相互独立的，上一个子问题的解会影响对下一个子问题的求解，但是下一个子问题的解不会改变前面上一个子问题的解。在航迹规划中，选取恰当的代价函数，从最后一个节点往前推，找到其表示形式，直到到达起始节点。如图3所示。

图3 动态规划算法Fig.3 Dynamic programming algorithm

其中，每一条路径的数字代表该路径的代价数，到K点的代价f(K)表示为:

f(K)=min[f(D)+4,f(E)+3]

f(D)=min[f(B)+2,f(A)+4,f(C)+4]f(E)= min[f(D)+2,f(B)+1]

到每一个节点地代价为该节点的前一节点的代价加上两节点之间的代价，动态规划的思想是通过找到代价最小的节点，从目标点倒推，最终规划出一条选取代价最小的路径，并以此类推，直到规划出最优航迹或次优航迹。动态规划算法具有搜索效率高，耗费时间短的优点，并且其稳定可靠。

3 结语

在真实作战中，作战场景通常都是非常复杂的，当提前规划好的路径，在战场上遇到紧急情况时，如突然增加的障碍物，紧急出现的威胁源，例如敌方的导弹等等，如何及时规避新的障碍物以及重新规划接下来的航迹，是一个值得研究的问题。

在规划航迹时需要考虑约束条件，如飞机性能限制、任务约束等。同时也需考虑性能指标，如按照规定时间到达、飞行时间最短、任务效能最高等。而各类算法则是针对各种约束与指标形成的规划出最优航迹的方法，不同算法适用的场景不同，在实际选择规划方法时，应选择相应的算法进行航迹规划，以寻得最优航迹。