基于PSO-Markov 联合模型的无人机路径规划*

2019-02-14周新志

火力与指挥控制 2019年12期

杨航，宁芊，周新志

（1.四川大学电子信息学院，成都 610065；2.电子信息控制重点实验室，成都 610036）

0 引言

近年来无人机技术的蓬勃发展，让无人机在侦查、压制、进攻等任务方面展现出了独特的优势。而无人机的路径规划，则是无人机技术的重要组成部分。它是指平台在敌方雷达、地形、任务等约束条件下，搜索出一条从起点出发，能够完成任务并且保证自身生存的最优或者次优路径。然而因为无人机面对的战场态势非常复杂，约束众多而且考虑约束相互之间可能的影响，同时还可能面对路径中出现的突发威胁，在处理这些问题的时候就会遇到较大的困难。

针对这些问题，国内外的研究人员进行了大量的工作。文献［1］采用了一种电荷法的处理方法，使得进入突发威胁区域时根据斥力让航线远离威胁。文献［2-3］将静态规划与实时规划结合起来，遇到突发则用实时规划的一小段路径替换掉静态规划的路径。但是这些方法都无法将路径中任务完成的情况以及无人机的生存状况实时地记录和展现。粒子群算法是一种新型的元启发式算法，概念简单易懂并且容易实现。

本文采用粒子群算法来进行路径实时规划，并且加入八状态马尔科夫联合模型［4］，在飞行的过程中动态获取任务完成情况与飞机生存情况，从而评估任务与生存代价，并据此对下一步路径进行规划，最后利用Matlab 进行仿真，证明了方法的可行性。

1 马尔科夫模型

为了能够直截了当地掌握无人机在飞行过程中的具体生存概率情况，将文献［5］中提到的8 种状态的马尔科夫模型与文献［6］中的状态转移与代价的计算方式引入，并在此基础上加以修改以便配合粒子群算法搜索。

1.1 八状态生存模型

生存性模型由两个子模型组成，即跟踪模型（上）和火力模型（下），如图1 所示。两个子模型之间是连接的，因为敌人向飞机发射武器的概率与飞机处于被敌方雷达识别（Identified）状态的概率有关。两个相邻的状态可以以一定的转移强度互相转化。

1.2 跟踪子模型

跟踪子模型是一个时间连续模型，一共有4 种状态：未检测（Undetected），检测（Detected），跟踪（Tracked）与识别（Identified）。敌方雷达对飞机的探测可以看作是一个随机过程，状态之间发生怎样的转换取决于飞机是否在雷达区域内。当飞机进入雷达区域时，它将逐渐转移到检测（D）状态，继续在雷达区域飞行一段时间后，敌方便可以跟踪（T）飞机，开始为发射武器做准备。最后，飞机将处于被识别（I）为打击目标的状态。因此，当飞机停留在雷达区域内时，该过程可以向图1 中右侧的状态传输。另一方面，如果飞机离开雷达区域，敌人逐渐失去对飞机的检测，直到飞机再次处于未检测状态（U），也就是说，当飞机在雷达区域之外时，该过程仅在图1中向左侧过渡。

1.2.1 跟踪模型的转移强度

强度矩阵以单位时间为分段而发生改变：

当雷达范围过大时，如果雷达区域内每一点的转移强度相同，那么就会出现一个问题：在雷达区域内部飞机的航线会呈现出一条直线。为了在内部区域无人机也能较为精确地规划路径，假定离雷达中心越近，转移强度就越大。设定o，s分别为雷达区域外部与内部的转移强度的最大值，雷达范围内的转移强度与飞机离雷达中心的距离有关：

其中，r 为雷达区域的半径，d 为飞机到雷达中心区域的空间距离。用PT（tn）向量来描述tn时刻跟踪模型的各状态概率，可以用下面的公式递归计算：

其中，指数矩阵eΔ定义为：

在一开始，飞机必然处于未检测（U）状态，所以PT（tn）的初始值设置为（1，0，0，0）。

1.2.2 重叠区域的处理

实际情况中为了确保安全，雷达区域可能会重叠。假设每个雷达能够独立地探测和跟踪飞机，那么在一个由多个雷达覆盖的区域的强度是单个强度的总和。例如假设两个传感器的相同，这意味着：

因此，转移前预期时间是单个预期时间的一半。

1.3 火力子模型

火力模型是一个时间离散模型，4 种状态为：无伤害（Unharmed）、开火（Fire）、失误（Miss）和命中（Hit）。这个过程从无伤害状态（UH）开始，只要飞机远离所有的武器范围，它就会保持在这个状态。然而，如果敌方武器已经发射出，这个转移将被立即转移到下一个状态。开火状态（F）是一个临时状态。飞机将不会长时间停留在这个状态中，而是会进一步转移到命中（H）或失误（M）状态。一个发射后的武器最终将以pkill的概率击中飞机，所以导弹从武器到飞机的飞行时间在本模型中不予考虑。在上一次开火的结果未出来之前，敌方也不会进行新一次开火。在这一工作中，假定飞机以一定时间为间隔进行伤害情况评估。每个武器系统也只能是飞机在武器射程内时以一定时间为间隔进行发射，而更复杂的伤害情况评估模型将留给未来的工作。

1.3.1 火力模型的转移概率

火力模型中状态的转移是一个离散时间的马尔科夫模型，所以此子模型以概率来转移，而不是用强度，tk时间的转移矩阵Λ（tk）用以下公式描述：

此外，当飞机离开武器攻击范围的时候，开火（F）与失误（M）这两种状态都将转移到无伤害（UH）状态，而命中（H）状态则不会再改变。

1.3.2 pfire与pkill

武器开火的概率pfire取决于许多因素，在此将问题简化，使用以下方法计算：

pi是当前时刻跟踪模型里计算出的飞机处于被敌方雷达识别状态（Identify）的概率，TV（Threat Value）是指对敌方的威胁值，为了估计威胁值，需要评估飞机的接近性、能力和意图等因素。尽管威胁值不完全由飞机与武器的距离决定，但如果飞机离武器越近，威胁值也必然会更大。这里使用的评估方法是基于文献［7］中提出的威胁评估的贝叶斯网络，这是一种比较简单的方法。该网络的输入是飞机与武器之间的距离，这是由5 个层次描述的：

文献［8］中也提出了一些更复杂的计算威胁值的方法，如果为了避免过于复杂地计算TV，也可以指定TV=x，x 为任一确定的值。pkill则是指在导弹已经发射的情况下击中飞机的概率。由于武器的性能通常是保密的，所以在此可以采用一种简单的模型，将pkill在整个过程中设定为一个恒定值。

2 粒子群优化算法

2.1 算法主要思想

粒子群算法是一种基于群体的元启发式算法，近年来已经被实验证明了其效果，并且在各种领域得到了相当广泛的应用。与其他智能算法类似，PSO算法也是通过个体之间的竞争选择而实现最优解。

在PSO 中，整个空间的每一个个体都是求解问题的一个解。在N 维解空间里，有M 个粒子组成的初始种群Z=（z1z2… zM），第i 个粒子的位置信息用向量Xi=（xi1xi2… xiN）描述，这个粒子的运动速度信息则可以用下面的向量描述［9-11］Vi=（vi1vi2… viN）。每一个粒子在解空间迭代搜索，并且通过适应度函数的值来判断解的优劣，关于适应度函数的选取将在下一节中进行详解。在每一次搜索过程中，通过两个最优值来更新粒子的位置信息，一个是粒子自身的历史最优值B，一个是整个种群中的历史最优粒子值G。然后根据本公式来迭代更新第i 个粒子的速度与位置：

在这里要强调公式中参数的选取，不当的参数将影响算法收敛速度甚至不能收敛。其中w 为惯性权重，代表了全局搜索能力，如果w 为0，则粒子会失去记忆性将收敛于目前的最佳位置。c1代表了粒子的认知能力，如果这一部分为0，在粒子之间的作用下也可以收敛，甚至速度更快，但容易出现局部收敛的问题。c2代表粒子的社会能力，即与种群中其他粒子的交互关系，如果它为0，那么种群中的粒子将失去相互之间的联系而自行搜索，这样很难寻求到整个问题的最优解。

在粒子群算法中通常由适应度函数来描述一个粒子的好坏［12-13］，在本文中为了权衡任务完成度与飞机生存性等元素，令适应度函数由下式给出：

w 分别为各项的权重，Ctotal越小说明航路的整体代价越小，粒子也越接近最优值。接下来分别对每一项约束进行说明：

其中，F 用于求点到直线的距离，Xk是当前粒子的位置，Lreference为2.2.2 节中将要提到的预规划路径。

3）Cheight是高度约束的代价，CPH为高度惩罚代价，Hmin，Hmax分别为最低和最高飞行高度。

4）Coil是油量的代价，本文将从当前位置垂直飞向预规划航路，然后沿着预规划航路，把剩余路径的两段距离之和作为判断油量是否充足的依据，若油量不足以完成剩余航路，则施加惩罚代价CPO。

5）Ctarget为到下一个任务点的距离，若任务已经全部完成，则计算到规划终点的距离。此项可以使得路径是朝向任务点飞行，若无将会直接飞向终点。

2.2 路径规划的问题转化

2.2.1 无人机坐标的计算

要确定无人机的下一步运动轨迹，首先要确定它的飞行方向与飞行速度。而在三维空间中，用极坐标描述位置变化无疑会更加方便［14］。所以将俯仰角、偏航角与飞行速度作为粒子群算法搜索的解［15-17］，然后再将极坐标转化为笛卡尔坐标就可以绘制出规划路径，如图2 所示。若整个航路一共为n 步，则粒子的位置为：

α1为第1 步的垂直俯仰角度，β1为第1 步的水平偏航角度，υ1为第1 步飞机的飞行速度，并以此类推。

图2 运动坐标三维示意图

2.2.2 动态航路规划

在面对复杂的战场态势时，如果做静态的路径规划，面对突然出现的威胁将比较难以处理，所以本文选择动态航路规划。每次搜索F 步以防止出现路径不平滑与搜索速度缓慢的问题，然后选取其中的D 步来执行。为了保证对突发威胁的提前反应，通常D 应当不大于F 的一半。下一次规划则以本次执行的终点作为起点继续执行。

同时，为了辅助规划航路和确定任务执行的先后顺序，在规划之前提前确定一条预规划航路，由起始点与任务点按顺序连接直到终点的直线组成。

3 Matlab 仿真与分析

3.1 场景与参数的设置

表1 坐标信息表

采用matlab2016 对实验进行仿真，场景设置为700*600*500 km 的区域，起始点与任务信息如表1所示，设定飞机自带雷达探测器探测的范围为20 km，粒子群规划航路的参数如下页表2 所示。马尔科夫生存模型中跟踪子模型的转移强度由表3所示，其中表示状态i 向状态j 转移的强度，令pkill=0.2。从表3 中可以看到，在雷达区域内，如只有图1 中向右转移的转移强度不为0，向左转移的强度都为0，这是因为在此区域内，雷达跟踪的几率只会随着时间的增加而增加，不会减小；反之亦然。生存模型中各个状态的状态代价值由表4 与表5 给出。跟踪模型的各个状态的生存代价是远小于火力模型的，因为它只是代表雷达的跟踪而不会造成伤害，代价则随着状态的向后转移而增强。火力模型中各状态的生存代价比跟踪模型大，无伤害（UH）与失误（M）状态都是属于未命中，开火（F）状态有可能击中，所以代价会较大，而击中（H）状态会导致飞机击毁，所以代价极大。

表2 粒子群参数表

表3 跟踪模型转移强度表

表4 跟踪子模型各状态生存代价

表5 火力子模型各状态生存代价

3.2 仿真结果与分析

3.2.1 生存代价w2偏大

在设置生存代价权重偏大的情况下，即式（12）中的0.5＜w2＜0.7 时，生存代价在总体的目标函数中所占比重较大，所以在路径规划的时候会更多地偏向考虑飞机的生存情况，在完成任务的前提下，飞机宁愿在路径长度上耗费一定的代价，也不要进入雷达与武器区域。

图3 规划路径图

图4 跟踪模型概率图

图5 火力模型概率图

图6 综合评估图

图4 中黑色区域为雷达区域，红色区域为武器区域，黄色圆点为任务区域，红色路径则为规划的飞行航路。从图4、图5 中可以看到，飞机进入第1个雷达区域后被雷达检测跟踪识别的概率逐渐上升。到达一个任务点后飞机开始退出雷达区域，退出后被跟踪的概率下降至0；然后进入第2 个雷达区域，由于生存权重较大，所以飞机没有进入武器区域太多，从图6 中可以看到敌方武器发射与命中的概率均小于0.1。从下页图7 可以看到TV 值是在进入武器区域的一小段时间内有变化，Pidentify与图5对应，Pfire值与图6 对应，生存能力Survivalblity 是由1-Phit得来，可以看到几乎约等于1，说明飞机的生存能力得到了很好的保证。

3.2.2 生存代价w2偏小

当设置生存权重w2偏小的时候，即式（12）中的0.2＜w2＜0.4 时，仿真结果如图7～图10 所示。

从图中明显可以看到，当生存权重设置为较小值的时候，对比3.2.1 节，路径规划时明显对飞机的生存情况不太敏感，在进入第2 个武器区域时已经深入到武器内部了，同时可以看到图10 中敌方开火与击中飞机的概率大大地提高了，飞机被击毁的概率甚至达到了0.4。图11 中TV 值也在较长时间内保持高值，整个航路的生存能力在后半段明显下降，说明改变权重对路径规划的影响是非常显著的。