基于粒子群遗传算法的多无人机协同路径搜索*

姚 军，李思捷，罗德林，刘善国，王国耀，吴 军

（1.解放军95894 部队，北京 102211；2.厦门大学，福建 厦门 361102）

0 引言

近年来无人机（Unmanned Air Vehicles，UAV）被广泛应用于军事和民用领域。在不确定环境下侦察作战时，由于单架无人机对搜索区域信息了解有限，为了提高对搜索区域信息的感知能力和目标搜索效率，多架无人机的协同路径搜索和信息获取已经成为当前研究重点，美军已将无人机集群作战作为未来发展的重要方向。

无人机目标搜索研究一直备受科研学者的关注。文献［1-2］中提出了一种基于概率图模型的遗传算法，搜索不确定环境中的目标，但该算法未对无人机搜索路径效率进行分析。基于状态预测的滚动优化搜索决策方法，根据概率可以预测无人机要经过的路径，有效避开了禁飞区，但会出现重复搜索的路径，搜索效率较低［3-4］。文献［5］提出了一种利用合作模型的搜索算法，无人机可以在指定区域内实现协同搜索，但该算法搜索目标的数量依赖搜索区域先验信息，具有一定局限性，实用性不强。覆盖式搜索算法可对整个环境区域进行完整搜索，但考虑到无人机油耗有限，在现实状态下不太可能采用该方式进行大范围搜索［6-7］。文献［8］提出了一种对不规则凸多边形区域进行分割处理，然后分配给指定无人机进行搜索的算法，但该方法没有考虑地形和高度等环境因素对搜索的影响，同时对凹多边形也无法使用。

本文针对以上算法不足，提出了基于粒子群遗传算法的多无人机不确定区域协同路径搜索方法，其任务背景如下：在指定未知搜索范围内，已知重点区域、一般区域和禁飞区域，且在重点和一般区域随机分布一定数量的目标，研究多无人机协同路径搜索算法，实现最大可能探测未知搜索范围的信息量。方法基本流程如下：首先建立栅格化概率图模型，无人机根据目标报酬函数展开搜索任务，减少了搜索过程的随机性；其次引入协同思想并与粒子群遗传算法相结合进行航迹规划，通过加强多无人机合作，提升搜索效率和质量；最后通过仿真计算验证算法的有效性。

1 问题建模

1.1 搜索区域模型

假定任务派出n 架UAV 从指定机场出发对目标展开搜索，设定整个任务区搜索环境为X×Y，将其划分为对应大小的子单元格集合，即E={x，y|x=1，2，3，…，X，y=1，2，3，…，Y}为无人机目标搜索区域，其坐标点{x，y}表示在x 行和y 列的搜索单元格。将X×Y 栅格化为单元格集合E，即完成了栅格化环境建模，为后续无人机仿真实验提供基础环境。

为了便于后续仿真实验，算法模型作以下简化处理：1）无人机之间可以随时共享信息，不考虑通信延迟问题；2）不考虑无人机在飞行过程中的故障问题，即无人机飞行状态一直良好；3）无人机在某个子单元格执行侦察任务时，其传感器可以获取该单元格所有信息，并随时将此单元格中环境和搜索状态信息发送给其他无人机。

1.2 搜索模型初始化

在栅格图模型中假设UAV 是一个以一定速度飞行的质点，t 时刻UAVi所在单元格坐标为{xi，yi}，表示UAVi正在该单元格侦察环境信息。规定每个单元格最多存在一个目标（Q={0，1}，Q=1 表示目标存在）。由于无人机存在最小转弯半径的物理约束，在栅格图环境中规定UAVi只有8 种航向状态，即D={0，1，2，3，4，5，6，7}，具体如图1 所示。同时无人机UAVi在t 时刻的某种状态下，下一步只有3 种路径可选，即t+1 时刻的路径只能是直飞或者左右45°转弯。

图1 航向示意图

1.3 搜索概率图模型

在真实的不确定环境中往往需要对整个区域进行特征划分，主要包括重点搜索区域、一般搜索区域和禁飞区域，并对每种区域指定的环境状态进行数学建模。本文同样在栅格图模型中设置了重点搜索区域、普通区域和禁飞区域，并在对应区域的单元格中设置了目标存在概率Pxy（t）。由于缺乏目标具体信息，UAVi某时刻对单元格中目标判断存在不确定性程度，初始设置对单元格目标信息不确定度Pu=1，表示此时对该处目标信息完全不确定。当UAVi在t+1 时刻对该单元格进行侦察时，通过传感器获取目标物存在状态，此时单元格中目标信息的不确定程度会根据比例因子R 不断调整，如式（1）所示：

由于传感器存在误差，在探测过程中传感器有探测概率Ps和出错概率Pm，且Ps+Pm=1。在路径搜索过程中，会根据当前时刻传感器探测目标的状况Qt（Qt∈{0，1}，Qt=1 表示探测到目标）更新下一时刻单元格目标存在的概率。当Qt=1 时，根据式（2）更新单元格目标存在概率：

当Q=0 时采用式（3）更新单元格目标存在概率：

2 协同搜索算法设计

2.1 协同搜索及粒子群算法

协同是一种合作型关系，指群体中的个体之间在执行任务中相互协作，分享彼此的资源，以达到更好完成目标的一种合作方式。本文提出的协同搜索，其核心在于无人机在搜索过程中，实时分享传感器捕获的目标信息，包括单元格中目标存在概率和自身已经搜索过的单元格，还有为了避免与其他无人机发生碰撞，随时提供的当前单元格坐标与航向。在搜索完单元格后根据目标存在状态，更新搜索概率图和信息不确定度，并通过共享机制使其他无人机获取该单元格信息，以尽量避免重复搜索，减少不必要的油耗，提升效率。由于假设不存在通信延迟和故障等问题，在搜索过程中所有无人机共享整个栅格图信息，实现区域目标高效搜索。

粒子群算法（Particle Swarm Optimization，PSO）是由Eberhart 和Kennedy 根据鸟类觅食行为而提出的一种全局随机搜索算法。在模拟鸟类觅食过程中，假设环境未知方位存在食物，种群中的鸟类根据自身距离食物的位置进行搜索，并将距离食物最近的个体位置作为搜索的主要方向。粒子群算法基于鸟类觅食思想解决问题时，随机生成一组粒子集合，其中每一个粒子都有自己的飞行速度与方向，并作为对应问题的一个解；在每一次迭代过程中，通过适应度函数计算出粒子的适应度值，并找到当代所有粒子中适应度值最大的粒子；然后跟历史最大粒子进行对比，选择最优粒子来调整所有个体的速度和方向，不断朝着最优方向进化。PSO 算法根据式（4）和式（5）进行迭代寻优。

2.2 基于协同的粒子群遗传算法

本文以搜索概率图为基础，每个UAV 对应一个粒子群，每个粒子群中生成固定数量的个体（即粒子），采取路径滚动预测的方法，实现路径搜索。其中个体是随机生成的、长度为k 的预测搜索路径，每个路径代表无人机接下来可能要搜索的k 个单元格。为了满足最小转弯半径的物理约束条件，在搜索过程中规定无人机只能直飞和左右45 °转弯。由此粒子群算法可通过预测步长k 和飞行方向进行粒子群个体编码，在每次搜索过程中随机生成粒子群大小为N、长度为k、由{-1、0、1}（左转、直飞、右转）组成的个体，每个个体代表该无人机一个可行的搜索路径。UAVi在t 时刻位于某一单元格时，根据粒子群中最优粒子的预测路径移动一个单元格，然后在此基础上按照协同搜索的原则更新栅格图概率和无人机航向，为下一次搜索作准备。

虽然粒子群算法优点十分显著，收敛速度快、内涵并行特性、搜索效率高，可以根据个体极值和全局粒子极值指导粒子进行搜索，但也存在明显的缺点，如算法容易早熟收敛、陷入局部最优解、对不连续问题处理性能不佳。遗传算法（Genetic Algorithm，GA）凭借其极大的种群规模以及内部选择、交叉、变异的3 种机制，可以有效求解全局最优解，正好弥补粒子群算法的不足。在粒子群算法更新完个体后，采用遗传算法对个体进行选择、交叉、变异和精英保护，形成新的个体再进行粒子搜索，实现两种算法的完美融合。最后再将这两种算法和协同搜索结合，形成新的协同粒子群遗传算法（Collaborative PSO and GA，CPSOGA）用于解决无人机协同区域搜索问题，实现更优路径搜索，并提升无人机搜索信息的效率和针对性。图2 给出了UAVi在出发点A0航向为0 时生成规模为N 长度为k 的粒子群集合。

图2 粒子群集合

UAVi根据图2 的粒子群集合在栅格图中生成对应的预测路径如下页图3 所示，然后根据适应度函数计算搜索报酬，从所有路径中选择一条最合适的搜索航迹。

图3 无人机搜索路径

图4 用来说明无人机对禁飞区域的回避情况。无人机根据粒子群集合规划出预测路径的单元格节点，虽然从A0出发进入第1 个单元格m1不会影响飞机安全，但进入第2 个单元格可能会驶入禁飞区，所以不论是选择单元格集合{m1，n2，q2}还是{m1，m2，k3}的个体搜索路径都会进入禁飞区域，只有选择单元格集合{m1，n2，q1}和{m1，m2，k2}才可以确保安全，因此，面对禁飞区，要提前作好回避决策。

选取47例2017年3月—2018年3月期间本院收治的肺部孤立性肺结节患者纳入本次研究，经CT常规检查结果显示，47例患者肺部均存在孤立性结节，且无明显肺门转移现象，也不存在淋巴肿大等现象。47例患者中男31例，女16例；年龄35～75岁，平均年龄（57.24±9.09）岁；症状表现：存在明显胸部疼痛者9例，出现发热者7例，咳嗽、咳痰症状明显者10例，无明显症状表现者21例。

图4 无人机禁飞区回避示意图

2.3 适应度函数

为了保证UAVi的安全性以及协同搜索的效果，需要防止发生碰撞，并尽可能避免重复路径搜索，同时确保在规定油耗内能够完成搜索任务。在UAVi搜索路径时，如果预测的路径是之前搜索确定的路径点，则对应个体的适应度值V=0，如果不是，则按式（6）计算个体的适应度值。

其中，l_ij表示t 时刻无人机UAVi和UAVj分别预测个体路径位置{xi，yi}与{xj，yj}之间的实际距离，式（7）是其计算公式：

当l_ij＞1.414 时，表示UAVi与UAVj不会发生碰撞，采用式（6）计算个体预测路径的适应度值；当l_ij=0 时，表示UAVi与UAVj发生碰撞，个体适应度为零；当0＜l_ij≤1.414时，UAVi与UAVj可能发生碰撞，此时适应度需减去一个代价项。

式（6）中，k 表示个体的路径长度，n 表示无人机的架数，m1是权重因子，m2是代价因子。lt，t+1表示个体预测路径中相邻两个时刻UAVi的飞行预测距离，Pt表示发现目标的回报函数，其计算公式分别如式（8）和式（9）所示；Pf表示不确定度的减少报酬函数，表示随着搜索的进行，UAVi对搜索区域的信息掌握越来越多，其计算式如式（10）所示。

2.4 算法步骤

本文提出的多无人机协同路径搜索算法步骤如下：

Step 1 设定栅格图环境，初始化粒子群和遗传算法中的参数，确定粒子群大小和预测路径长度，设置无人机数量和对应的搜索起点、航向等初始状态；

Step 3 根据粒子群算法和适应度值选择全局最优粒子，并优化所有个体粒子的速度和位置；

Step 4 通过遗传算法的选择、交叉、变异等方式增强粒子群多样性，并通过精英保护方式保留Step 3 中最优个体，最后对遗传算法获得的粒子群进行适应度值计算，并以此对每个粒子代表的预测路径排序；

Step 5 对比预测路径和历史搜索路径，同时检测不同粒子群的预测路径之间是否同时相遇，剔除重复路径和危险路径，然后根据Step 4 中排序，选择最优粒子路径，并沿该路径移动一个单元格，进入下一时刻路径搜索，最后对航向和概率图进行更新；

Step 6 判断搜索是否结束，若完成搜索路径长度Tend，则输出对应UAVi的航迹，反之，跳转至Step2 继续路径搜索。

3 算法仿真

为了验证基于协同的粒子群遗传算法在多无人机区域路径搜索的效果，在MATLAB R2014a 环境中编写仿真程序。如图5 所示，设置30×30 的矩形栅格图，设定3 架无人机（图中3 个三角形）分别以航向0、4、6 从（3，1）（10，30）（30，24）位置起飞，设定2 个禁飞区和2 个重点搜索区，分别为图中黑色区域和白色方框区域，生成10 个目标（图中10个菱形）在各个搜索区域随机分布。设定每架无人机对应粒子群大小N=50，预测路径长度k=5，搜索路径长度Tend=80，传感器探测概率Ps=0.9，出错概率Pm=0.1，惯性因子ω 为3，加速因子c1和c2均为1.494 45，比例因子R 为0.5，交叉概率为0.7，变异概率为0.05。

图5 无人机路径搜索仿真环境

图6 和图7 分别为采用CPSOGA 和PSO 方法的无人机路径搜索仿真图，可以看到两幅图中，无人机都有效避开了禁飞区域，确保了搜索的安全性。在CPSOGA 算法中，设置的10 个目标均被搜索到，PSO 算法中一共31 次搜到9 个不同目标，重复率为3 倍多；在PSO 算法中出现了大量重复搜索的路径，并且只是集中在重点区域进行搜索，基本忽视了一般区域中的目标，但CPSOGA 算法不仅有效对重点区域进行搜索，而且基本没有重复无效搜索路径，同时会尝试对普通区域目标展开了搜索。

图6 CPSOGA 仿真图

图7 PSO 仿真图

为了进一步分析算法的仿真效果，对两种算法分别单独运行20 次，每一次运行对应3 架飞机共有路径点240 个，统计并分析重复路径和重点区域搜索的路径点数量，其结果如表1 所示。可以发现CPSOGA 的重复路径明显低于PSO，说明通过协同粒子群遗传算法搜索，无人机之间进行了良好的沟通，减少了重复搜索路径，提高了搜索效率，标准差更小，搜索结果更加稳定；CPSOGA 在重点区域路径少于PSO，其主要原因是无人机完成对该区域的搜索任务后会自动离开，并尝试搜索一般区域，由于离开时间取决于当时的环境，是一个不确定的状态，所以会导致其标准差比PSO 高，这也说明CPSOGA 不是一味地在重点区域搜索，算法更加先进。从仿真数据可以看出，CPSOGA 比PSO 具有更好的路径搜索效果。

表1 20 次仿真数据分析

4 结论

本文针对多无人机区域搜索问题，提出了一种新的基于粒子群遗传算法的多无人机协同路径搜索方法。为了准确描述算法，针对问题进行了建模，并采用数学语言表述，分别构建了搜索区域模型和概率图模型；为了提高路径搜索的质量和效率，将粒子群算法和遗传算法进行融合，采用适应度函数评价预测路径，形成了一种新的协同粒子群遗传算法；为了验证算法的有效性，编写程序进行了仿真实验，其结果显示，无人机的搜索航迹满足最小转弯半径约束，避开了威胁区域，实现对重点区域的强化搜索并降低了重复路径，有效提升了多无人机协同搜索效率和质量，证明了所提方法具有良好的路径搜索能力。