1. 模型建立

采用m架UAV搜索n个区域T＝{T_1，T_2，…T_n}。无人机具有不同的能力和属性，最初停放在同一训练基地。无人机U_i的主要特征有v_i、vs_i、h_i、theta_i，分别表示飞行速度、扫描速度、飞行高度和俯仰角。alpha_i表示宽幅传感器的水平视野，gamma_i表示传感器的安装角度，即视野与U_i纵轴之间的夹角。Ui的检测区域如图2所示。

图2 无人机检测区域

多无人机系统的任务执行效率受到最迟完成时间的无人机的限制。对任务完成时间最长的无人机补偿，即可提升整体效率从而使无人机的最大时间成本最小化，其表述如下：

满足以下约束：

1）每个区域有且只有一架UAV扫描。

2）执行搜索任务的UAV数量不大于UAV总数。

3）无人机按顺序检测目标区域。

2. 基于聚类的自适应算法

所提出的ACBA算法分为三个阶段：

1）用于评估每架无人机的飞行和扫描能力的能力评估阶段。

2）用于对区域进行聚类并将区域逐一分配给UAV的区域分配阶段。

3）顺序优化阶段，用于调整区域的访问顺序并为每个UAV生成最优路径。

（1）能力评估

能力评估阶段为UAV分配适当的优先级，并根据UAV的能力对UAV进行排序来创建UAV列表。由于无人机在执行搜索任务时的飞行和扫描能力与无人机的固有特性以及机载传感器的关键参数密切相关，因此采用能力等级作为排名函数来评估无人机的能力并为无人机分配优先级。给定U_i的优先级由R(U_i)表示，每架无人机的能力等级基于预期扫描时间成本和飞行时间成本计算。无人机列表通过将无人机按其能力等级值的升序排序而生成。值越小表示无人机能力越高。

（2）区域分配

本文采用了一种基于聚类的方法，根据距离和扫描区域计算的区域密度对区域进行分组和分布。首先，计算区域的密度，并为每个UAV选择具有当前最高密度和最长相对距离的簇中心。然后，根据最近已知的分配，将所有区域逐一添加到集群中，以平衡UAVs的时间成本。UAV的集群中心被认为是密度比邻居更高、距离其他中心更远的区域。

在本文中，给定区域T_j的密度rho_j被定义为在预定义范围内搜索所有区域的平均时间成本。截止距离delta_j表示区域T_j与密度高于它的其他区域之间的最小距离。

根据密度和距离的值来选择聚类中心。考虑一个真实场景，采用三个架UAV完全搜索18个区域，以检测中国福州市的土地利用类型，感兴趣的区域位于二维地图中，如图3(a)所示。首先，计算每个区域的密度和距离，并在图3(b)中构建决策图，为更准确和有效地选择中心，使用数量 来评估密度和距离的综合影响。在聚类中心选择过程中，gamma值较大的区域将以较高的概率被选择。图3(c)按gamma值降序排列区域。可以看出，非中心区域的γ值有平滑的移动，并且从中心区域到非中心区域有明显的跳跃。这种跳跃可以有效地指导中心的选择。

找到集群中心后，根据计算的无人机能力等级，将其依次分配给无人机。gamma值较大的区域被视为具有较高能力的UAV的集群中心。每个剩余的区域将被分配到与其最近的具有较高密度相邻区域的集群。通过这种聚类策略，每个UAV将具有一个由区域组成的独特聚类，这些区域由UAV依次扫描。图3(d)显示了图3(a)中区域的聚类结果。

图3 区域分配过程

（3）检测顺序优化

在上述阶段之后，每个UAV获得一个区域访问序列，并逐个飞往并扫描这些区域。但初始的区域访问顺序往往不够高效。为了减少执行搜索任务的时间消耗，需要顺序优化阶段来修改区域的访问顺序。采用基于共生生物搜索（SOS）的优化策略来获得每个区域的新访问顺序，以最小化总时间成本。总体流程如图4。

图4 共生生物搜索算法流程

首先生成预定义数量的生物构建初始生态系统，并且每个生物都被认为是所考虑问题的潜在解决方案。然后，根据指定的策略，依次执行互惠、共栖和寄生三个阶段，以产生新的生物。根据适应度值的大小决定是否被添加到生态系统中。

一半的初始生物体从（0，1）中随机选择实数生成，通过基于随机概率的名为交换、反转和插入的三个突变算子来生成另一半生物体。由于SOS的初始设计目标是解决连续和多约束优化问题，因此当SOS扩展到离散区域时，应采用转换方法来解决区域的顺序优化问题，本文使用最大秩值（LRV）方法将连续实数转换为表示区域序列号的整数值。如图5(a)所示，LRV按照降序对实数进行排序，并生成一个序列，以顺序访问所有区域。

图5 变换方法和突变算子

随机选择三个突变算子（即交换、反转和插入），以基于预定义的概率（如0.2、0.5、0.3）决定将执行哪个操作生成初始生物体。例如，生成范围为（0，1）的随机值p_0。如果p_0<0.2，则使用交换运算符修改给定生物体。在执行突变算子之前，随机选择给定生物体中的两个位置，交换两个位置；反转操作反转两个位置之间的局部片段；插入运算符将区域从第一个位置移动到第二个位置。图5给出了三个操作的图解。下面是共生生物搜索的主体过程。

1） 互惠阶段：给定一个生物x_i，随机选择另一个不同生物x_j，并与x_i相互作用，生成两个候选生物x_i_new和x_j_new，目的是提高生态系统的生存能力。

2） 共栖阶段：共栖阶段只有一个生物体会从个体相互作用中受益。给定一个生物体x_i，随机选择另一个不同的生物体x_j，在x_j和x_best的帮助下产生一个新的候选生物体xi_new，而x_j保持不变。

3） 寄生阶段：在给定的生物体x_i上执行三个突变操作之一（即交换、反转和插入），以生成一个新的生物体x_pv，然后从生态系统中随机选择一个不同的生物x_j作为x_pv的宿主。如果x_pv的适应度优于x_j，则x_j被x_pv替代。

当达到预定义的最大迭代次数时，顺序优化阶段停止。

1. 区域生成

区域在三个主要因素下随机产生的：区域数量n、直接决定区域总扫描面积的系统利用率u和对UAVs的扫描速度有关键影响的系统阻力系数d。表1列出了实验中采用的无人机参数。

表1 仿真实验的无人机参数

2. 任务完成时间评估

在图6中，本文的方法和五种现有方法的任务完成时间通过将区域数量从20逐渐增加到200来评估。在这些实验中，当系统利用率为0.025，系统阻力系数为0.5，即u=0.025，d=0.5时，随机生成区域。六条曲线分别是基于时空聚类的最接近策略（STCA_NA）、基于遗传算法的顺序优化策略（STCA-NA_GA）、最高有效时间比优先算法（HETRF）、具有基于遗传算法优化策略的改进HETRF算法（HETRF_GA）和基于蚁群系统（ACS）的路径规划算法（APPA）。

 图6 不同算法的平均任务完成时间

从图7中可以看出，所有六种方法的任务完成时间都随着区域的数量而逐渐增加。最可能的原因是，大量区域增加了无人机的飞行路径长度，导致执行搜索任务的额外时间成本。当区域数量保持不变时，在大多数情况下，本文方法可以实现比其他方法具有相对较小的任务完成时间值。

图7 不同系统阻力的平均任务完成时间

在图7中，通过将系统阻力系数从0.2更改为0.9，验证了六种方法的性能。生成n=180和u=0.01的区域。代表平均时间完成时间的所有六条曲线具有大致相同的趋势，从超过310分钟下降到少于160分钟。主要原因是大的系统阻力系数为无人机提供了更高的扫描速度。与图5中分析的实验结果类似，表明本文方法在任务完成时间方面具有良好的性能。

3. 算法执行时间评估

图8 不同区域数量下的执行时间

在图8中，使用对数尺度，通过将区域数从20更改为200来评估六种方法的平均时间消耗。区域参数与图5中使用的参数相同。算法的执行时间成本随着区域的数量而逐渐增加。出现这种情况的主要原因是，随着分离区域的数量增加，在整个计算过程中应考虑更多可能的区域分配和路径规划。HERTF算法在解决给定数量的区域上的路径规划问题时具有最低的执行时间。这是因为HERTF根据相对距离顺序分配区域，并忽略了区域的顺序优化过程。尽管本文的方法可以找到最佳的飞行路径，但它的时间成本实际上比其他方法更大。

4. 偏差率评估

偏差比率，定义为通过不精确方法和精确方法获得的解之间的相对差异比率，是评估方法可靠性和准确性的重要指标。本文中偏差率通过不精确算法产生的解决方案与MILP公式产生的解决的任务完成时间之间的差异比率来计算。MILP求解器的时间限制为3600秒，因为MILP公式非常耗时，即使在解决大规模规划问题时采用了十个小时，也几乎不会终止。

在图9中，通过改变系统利用率来测试方法的偏差率。这些实验中采用的区域生成参数为n=30和d=0.9。六种方法的偏差率随着系统利用率的下降而下降。由于在路径规划算法中无法优化UAV的扫描时间成本，因此更大比例的扫描时间有利于更精确的解决方案。因此，偏差率随着系统利用率的降低而降低。可以看到，当系统利用率值为0.02时，本文的方法、HETRF、HETRF_GA、APPA、STCA_NA和STCA_NA_GA的平均偏差率分别为3.96%、10.38%、8.23%、6.29%、7.34%和5.53%，这表明本文方法在给定的系统利用率下具有最小的偏差率。

图9 六种方法的偏差率评估

在图9中，通过将无人机数量从2变为10，验证了六种方法的性能。产生u=0.03和d=0.9的区域。可以看到，随着UAV增加，所有方法的偏差率都有明显的先上升后下降的趋势。这一趋势最可能的原因是，所有六种方法都不精确，只能获得次优解决方案。随着无人机数量的增加，应评估和比较路径规划问题的更多潜在解决方案，从而增加第一阶段的偏差率。同时，精确解的搜索空间随着无人机数量的增加而急剧增加，并且当设置时间限制时，MILP解算器无法找到越来越多的最优结果。因此，在第二阶段，通过不精确方法获得的解与通过MILP公式获得的解之间的差异变小，偏差率降低。当无人机数量保持不变时，本文方法的偏差率小于其他方法，表明本文方法在偏差率方面表现更好

本文专注于多个异构UAV的自动路径规划，并尝试为每个UAV获得覆盖所有感兴趣区域的适当路径。首先提出了一种新的能力等级，以评估用于搜索任务的无人机的性能。然后，受基于密度的聚类分析的启发，根据通过相对距离和扫描区域计算的密度将区域划分为组。最后，应用基于共生生物搜索的策略有效地修改聚类中每个区域的访问顺序。本工作中提出的基于自适应聚类的方法在解决多个异构无人机的自动路径规划方面具有显著优势，特别是当大量区域应被完全覆盖时。它可以有效地为每个UAV生成合理可行的路径解决方案。