应急搜索UAV集群协同任务规划策略

鲁旭涛 智超群 张丽娜 秦英伟 李 静 王 英

①(中北大学机电工程学院 太原 030051)

②(中北大学信息与通信工程学院 太原 030051)

③(中北大学电气与控制工程学院 太原 030051)

④(中北大学能源动力工程学院 太原 030051)

1 引言

随着无人机 (Unmanned Aerial Vehicle， UAV)技术的不断发展，多UAV协同系统也在不断进步和完善。相较于单UAV作业，多UAV协同作业容错性更高，稳定性更强，适合于复杂环境下的作业。随着多UAV数量的提升，UAV集群的概念应运而生，UAV在应急区域搜索任务或协同作战任务都有广泛的应用。

在UAV集群协同区域搜索任务中，相关学者对UAV集群的任务规划有所研究。文献[1]针对UAV集群控制复杂度高，设计一种“仿鸿雁自主协同控制方法”。通过鸿雁行为机制，开发了面向UAV平台的分布式仿生集群系统。文献[2]将蚁群算法与人工势场算法结合，避免了3维空间蚁群信息素惯性而导致局部信息忽略的问题，适用于UAV的3维航迹规划。但UAV航迹实际约束条件较多，航迹规划一般是多目标动态规划问题。文献[3]针对山火火情动态时变特性，通过优化人工蜂群算法，确定UAV山火灭火路径。但动态时变应用需要及时对灭火路径进行更新，这对UAV组网的通信模型有较高的需求。

在一些复杂区域搜索难度较高时，对于同样区域需要进行2～3次覆盖搜索。则重复性覆盖搜索过程中，需要对UAV间的空间冲突进行消解。文献[4]针对复杂地形环境的UAV路径规划问题，将“鲸鱼算法”加入“灰狼算法”进行优化，通过2维问题的高维处理，将算法目标进行权重划分，在保证算法收敛速度的同时，提高了整体算法的优解搜索能力。文献[5]针对灰狼算法收敛速度慢，易陷入局部最优的问题，通过模型离散化处理，使用“A*算法”进行头狼属性的初始化，并通过“三次B样条”方法进行平滑操作，实现UAV航迹规划。除了空间冲突消解，部分复杂应用中，所需搜索区域内也包含了重点搜索区域和一般搜索区域。

相关学者针对航迹规划算法也有相关研究。目前对于路径算法的相关研究均是以最短路径为单一目标进行寻优，或是在寻优过程中加入各类实际限制条件提升算法寻优的应用性或算法的准确性。文献[6]采用优化模拟退火算法进行路径规划；文献[7]、文献[8]和文献[9]分别对蚁群算法、A*算法和混合粒子群算法进行优化，但算法优化过程均以牺牲算法效率为代价；除了对于算法本身进行优化，同时对于多机协作路径规划国内也有一定的研究。文献[10]、文献[11]和文献[12]均在多机协同背景下进行了一种自适应规划策略；文献[13]、文献[14]和文献[15]则针对实际应用进行了系统针对性优化。

在上述相关研究过程中，多数学者一般以优化算法为目标来达到集群区域搜索的精度、UAV组网的稳定性等参数。或是降低集群控制复杂度，提高网络拓扑通信能力等。针对多数需要以效率为首要目标的快速搜索策略未有明确的研究。

因此，UAV集群区域搜索任务，应采用以搜索效率为首要目标，结合其他次要目标及约束条件进行数学模型的求解。本文以搜索效率为算法目标，以全覆盖、搜索精度等为约束条件，通过优化模糊C-均值聚类算法(Optimize Fuzzy C-Means Algorithm，O-FCMA)进行搜索区域模型的划分，同时结合优化混合粒子群算法(Optimize-Hybrid Particle Swarm Optimization， O-HPSO)在实现高精度、低误判率条件下，提升区域搜索效率。

2 算法模型建立

2.1 区域环境模型建立

对于具体搜索任务主要包括无线通信搜索、光搜索和热搜索等。其中无线通信搜索包括雷达搜索、定位系统搜索等；光搜索主要包括可见光搜索、红外光搜索等；热搜索主要是热红外搜索；本文UAV主要采用雷达搜索、可见光搜索、热红外搜索等方法，即近距离无具体坐标，仅有区域范围条件下进行搜索。

UAV集群在进行区域搜索任务过程中，区域环境模型的建立速度影响搜索效率的高低，模型建立的合适参数将影响搜索精度的水平。对于一般应急区域搜索任务，应用环境的建模往往需要一定的计算能力。本方法中搜索区域模型由控制中心进行模型建立。本文对于区域搜索区域采取蜂窝图化任务区域方法，如图1所示。

图1 区域搜索算法环境模型

蜂窝图六边形单位长度的设置取决于UAV的搜索能力。蜂窝图化任务区域能将整体目标分割，降低计算需求，并且提高计算精度。

2.2 区域全覆盖模型

对于区域搜索任务，需要UAV搜索时将完整区域全部覆盖，同时区域全覆盖模型不考虑重点搜索和回访，及对于任意区域至少被搜索过1次即可。

各个UAV共同搜索覆盖的实际面积大于或等于所需要进行覆盖搜索的区域。

全覆盖模型在计算时一般会产生连续覆盖。连续时刻UAV搜索过程中邻近区域会出现重复搜索的现象。即本文方法中全覆盖模型不考虑重点搜索及回访情况，任意需要搜索的区域，只要UAV搜索过1次其区域点即可。

2.3 最快搜索目标函数模型

最快搜索目标函数模型，即为最快实现全局搜索。区域内搜索过程中，UAV集群的最快搜索速度即最快搜索区域与搜索到目标的UAV用时的比值。同一集群内的不同UAV在各自的区域内搜索效率不同。对于不同的搜索区域，即使在两块区域面积相同的情况下， UAV搜索所要飞行的路径长度也有差别。

对于UAV集群指定区域任务规划为

即各个UAV搜索区域小于指定区域，各个UAV搜索区域总和包含指定区域。

对于单个UAV在指定区域内的最快搜索分为全局最快搜索和局部最快搜索。

局部最快搜索

局部最快搜索即在任意时刻尽可能实现当前时刻内的搜索速度最快。即需要当前搜索重复区域最低，搜索未搜索区域最大。

全局最快搜索

全局最快搜索即在最快的时间内将指定需要搜索的区域全部搜索完成。在本文中，将采用全局最快搜索方法，相较于局部最快搜索方法而言，由于区域内被搜索源具有位置不确定性，局部最快搜索方法对于不确定性可能有时快于全局方法。但也有可能比全局方法慢很多，故采用全局最快搜索方法。

2.4 搜索效率模型

设UAV搜索任务区域共划分为m个区域。搜索效率模型中，平均搜索效率，即所有UAV共同搜索的范围与时间的比。

UAV行驶一定距离的时间计算式为

2.5 协同UAV高速通信模型

在UAV集群进行协同任务搜索时，需要实现低延时同步信息共享的多UAV高速通信模型。针对本文中的UAV集群路径规划过程，采用无线自组网进行UAV间的协同通信。其通信模型结构图如图2所示。

由图2可知，针对每一个UAV将采用自组网方式进行汇聚-路由-终端结构组网的搭建。而UAV集群的高速通信，首先根据文中FCMA进行区域划分，其各个聚类中心如图3所示。

图2 UAV集群组网结构

图3 UAV区域聚类中心

各个UAV在自身所需覆盖区域内均有一个聚类中心，则通过FCMA算法进一步对已有的聚类中心进行优化，得到的结果如图4所示。其中，红色实心点即为每个UAV的区域聚类中心，而黑色节点即为所有红色实心点的聚类中心，依照黑色节点坐标所属区域，则将区域内的UAV设为通信路由节点，其余设为终端节点。进一步通过各个路由节点取聚类得到整体UAV集群的汇聚节点，其结果图如图5所示。其中，红色实心点所属区域内的UAV做终端节点，黑色实心点所属区域内的UAV做路由节点，蓝色实心点所属区域的UAV做汇聚节点。通过此种方法通信实现UAV集群的无线自组网高速通信。

图4 UAV集群路由节点寻优图

图5 UAV集群无线组网节点寻优图

3 区域搜索任务算法设计

3.1 多UAV搜索区域划分方法

区域搜索任务划分主要通过对节点集内各个节点的隶属度函数，进行指定类别的区域划分，在本次应用中，通过已知路由-终端UAV组的数量确定区域划分数量，进一步得到整体区域内合理有效的任务分配。区域任务划分流程图如图6所示。

图6 O-FCMA流程图

节点与聚类中心的关系式为

即节点所属类的最大距离小于UAV搜索的最远距离。

聚类中心收敛过程为：

不仅是《圣经》还是《佛经》还是谚语，都给红月赋予了灾难的形象。《罪与罚》中没有大量的叙述，仅用了个“红月”就将小说境界全然升华，让所有人都明白阿斯科尔尼科夫的命运，小说以最简练的情景，用几个字传达出了一个贯穿整个小说的线索——阿斯科尔尼科夫正一步步走向灾难。

(1)本文主要在原有隶属度函数基础上，加入当前节点与其最近节点的欧氏距离作为影响因素，从而使得节点的分类方法具有同类性。优化后的隶属度函数计算式为

其中，dimin表示距离当前节点最近节点的欧氏距离，σ代表加入最近距离影响因子对隶属度函数的权重。对于最近节点的筛选方法，不采用当前节点与其他全部节点计算欧氏距离的方法，而是对于区域内全部节点进行X轴、Y轴和Z轴的顺序排列，分别计算X轴、Y轴和Z轴距离当前节点最近节点的欧氏距离，最小值取为最近节点与当前节点的欧氏距离。

(2)按照当前类别重新进行当前类别内聚类中心的计算，计算式为

根据区域内各个节点的隶属度及其坐标值则可以得到最优当前区域内聚类中心节点坐标。

(3)计算当前条件下的目标函数值。目标函数值计算式如式(16)

当目标函数收敛达到一定精度时，即可判断当前聚类算法满足终止条件。

3.2 搜索区域蜂窝图路径节点规划

UAV区域搜索原理如图7，设1和2分别为UAV在固定时刻的最小单位搜索区域，则1时刻和2时刻时，UAV处于的位置即1和2的圆心。

图7 蜂窝覆盖原理图

图8 蜂窝-节点覆盖图

图中覆盖6边形的圆形即为UAV搜索范围，六边形构成的蜂窝图间即为UAV实际运动覆盖的范围。而圆形和六边形的共同中心即为UAV所需要经过的坐标点。

3.3 搜索区域路径规划策略

UAV区域搜索路径规划模型即在实现传统路径规划问题的基础上，自适应确定区域搜索过程的路径转折节点。

设整体区域内共有n个节点需要UAV应急搜索，则搜索过程的总体距离为

式中，D1表示UAV路径当前搜索节点与下一搜索点之间的距离和。

式中，Di表示当前节点是各个UAV搜索过程的路径总和。

单一UAV在搜索指定区域的时间计算式为

式中，v表示UAV行驶速度。

在完成建立对于时间间隔约束的路径规划问题的数学模型后，O-HPSO的具体寻优过程流程图如图9。

图9 O-HPSO流程图

优化预选择机制的HPSO适应度函数式为

式中主要对粒子实时更新位置与速度做出描述。通过对实际算法寻优过程中的相关常数进行控制，提高寻优结果精度。

O-HPSO中的预选择机制条件式为

式(23)为O-HPSO中的预选择机制条件，预选择机制核心条件即为子代与父代适应度值的优劣比较，同时出现子代适应度值小于父代适应度值的情况下，由于在算法过程中部分个体未能及时显示优等特性而在当下迭代过程中适应度值较差，则可以通过随机重新生成一定数量的全新粒子个体，保证整个种群内的个体类型多样性。

4 实验及分析

本文在一块500 m×400 m的不规则平面区域进行仿真实验。通过本方法将实现搜索任务区域划分，同时对于各个区域内进行UAV的路径规划，完成多UAV条件下最快的区域搜索任务。总体流程图如图10所示。

图10 本方法总体流程图

4.1 算法参数设置

总体算法中的相关参数设置如表1所示。

表1 总体方法中常数参数数值及说明

4.2 实验测试

本文实验分为有源搜索测试、无源搜索测试两部分，均在500 m×400 m范围内进行。本文在上述相关参数设置下，使用配置为Intel Core i5-4200U，16 GB运行内存的计算机上，Windows10系统环境下，利用Matlab2017b进行实验。

4.2.1 有源区域任务搜索测试

有源搜索，即在有固定目标的情况下，UAV集群寻找该搜索源位置的过程。已知被搜索源的具体位置为图7中的标记点，坐标为(98.45，222.5) m，则UAV集群按照本文所述方法，16架UAV执行区域搜索任务时，搜索路径规划图如图11所示。

由图11可得，每种方法中16架无人机最大距离差值为模拟退火算法-K聚类算法的76 m，最小差值为本文算法的48 m。有源任务采用5种算法的对比结果如图12和表2所示。

图11 有源搜索本文算法UAV集群路径图

图12 有源搜索5种算法UAV路径对比图

由表2可知，在上述有源集群UAV任务搜索的条件下，5种不同方法均满足ξ，即搜索区域划分均匀标准。同时本文算法ξ值最小，采用O-FCMA进行任务区域划分最均匀，实现UAV集群整体搜索效率最大化。

表2 有源搜索对比试验结果

4.2.2 无源区域任务搜索测试

无源搜索，即常规巡检，无固定搜索目标，UAV集群需要将所需搜索区域全部覆盖。本方法得到最终UAV集群路径规划如图13所示。共计16个UAV，5种算法所得到的各个UAV搜索行驶的路径长度如图14所示。

图13 无源搜索本文算法UAV集群路径图

图14 无源搜索5种算法UAV路径对比图

可知，在搜索目标过程中，由于不同UAV路径出现重复区域搜索，不同UAV飞行路径长度不同。但16架UAV最大距离差值为62 m，占最快搜索UAV总飞行长度的19%。搜索效率为96%。即UAV在指定区域内进行搜索任务时，搜索时间越短，相对搜索效率越高，不同UAV之间飞行差值越小。对比结果如表3。

表3 无源搜索对比试验结果

4.3 实验结果分析

由以上结果可得，本文所提方法较其他方法而言，在完成全覆盖区域条件上，搜索效率最优，且最大与最小飞行距离差最小。

5 结束语

本文通过以多UAV区域任务搜索为背景，首先将所需搜索任务区域进行蜂窝图处理，将完整区域进行单位六边形分割，然后将蜂窝图等效至UAV所必须经过的坐标点。在已知坐标点条件下，采用O-FCMA将任务区域划分给各个UAV，通过O-HPSO在UAV指定区域内规划最佳路径。较其他算法而言，在保证全覆盖条件下，无源搜索降低了16%～31%的UAV决策时间，提升了3%～7%的搜索效率；有源搜索降低了7%～21%的UAV集群决策时间，提升了7%～13%的搜索效率。