随着火灾救援，海洋监测和地质勘查等活动日益频繁，军事、工业和民用领域对广域复杂环境目标搜索提出了更多的应用需求^[1-2]。例如，相比于陆地等任务环境，海域环境多样性更强，水下环境特征变化频繁，目标运动具有较强的不确定性。这些因素要求执行系统能够时刻感知周围的未知环境信息，面对不同的环境特征自主做出调整，在有限的资源分配下，合理高效地完成多目标搜索任务^[3]。近年来，随着深度学习与强化学习等领域理论和实践技术的积累及发展，多目标搜索得到了广泛的研究和应用，主要集中在机器人和机器人群体的轨迹规划方面。

在单个机器人轨迹规划研究方面，多数研究仅仅考虑离线规划。例如用环境信息获取来选择使姿态不确定性最小化的轨迹的问题^[4]，但是该优化框架计算量较大，预测的最优轨迹无法重新规划。使用强化学习进行自适应学习的方法主要支持单个机器人的静态识别任务，且并不包括动态移动对象^[5]。多机器人轨迹规划决定了信息收集和搜索任务的完成质量^[6]。例如把多目标搜索问题转换为多旅行商问题，基于自组织映射网络算法提出了多机器人协同在线主动感知方法^[7-9]。此外，使用深度神经网络(DNN)的探测器可以提高机器人团队对三维空间中移动的人或物体的追踪搜索能力^[10-12]。但是强化学习解决方案^[13-14]和深度神经网络^[12]方法需要大量的培训场景来确定策略，无法保证适应性。此外，随着代理的数量和映射的复杂性的增加，多机器人最优路径规划变得困难。

针对大规模未知动态环境的持续、时变和多源分布等特点，本文建立了一种新型的多智能体目标搜索算法框架，运用无人机集群在飞行空间构成相互协作、优势互补、效能倍增的协同体系，以提高系统在复杂非结构化环境下完成任务的能力和效率。当前的许多目标搜索研究和实际应用通常忽略观测目标的运动或假设监测目标进行简单运动，这类方法应用于海域等大规模环境时，受视距和活动范围限制，搜索性能并不理想。本文提出了一种多目标检测的多智能体分布式搜索模型，并结合该模型建立了自组织协同搜索的最优时间算法框架。机器人团队可以实现对一组机器人观测视角的并行改进，最大限度地观察感兴趣的目标区域，在时间和空间上扩大观测数量和质量。

1 问题描述

本文重点利用自组织目标搜索算法通过多智能体系统完成大规模未知环境的监视任务。监视任务要求在大范围复杂环境中迅速搜索尽量多的目标。该搜索任务要求无人机集群拥有自主的搜索能力，根据不同的环境特性做出反应和导航，克服外部环境的信息干扰，高效自主地追踪即时目标。

本文定义无人机集群序号为 $\left\{ {1,2, \cdots ,N} \right\}$ ， ${X_i}$ 为无人机i的状态序列，包括位置、传感距离、朝向等；N为无人机数目；t为模拟时刻 $t \in {{\rm N}^ + }$ ；T为环境中的目标位置集合； $\tau $ 为目标子集； ${(x,y)_\tau }$ 为目标 $\tau $ 的位置坐标， ${({x_t},{y_t})_{{X_i}}}$ 为无人机i在t时刻的动态位置坐标； ${T_{\rm{F}}}(T) \subseteq T$ 为t时刻已发现的目标集合。

磁探仪是主要反潜探测设备之一，它不受气象条件限制、可连续搜索、分类能力好、定位精度高、不受浅海等复杂环境影响。如图1所示，在未知的非结构化环境中，本文的无人机集群通过磁探测器和感知算法来了解周围的环境，最大限度地观察感兴趣的目标区域，以发现动态或静态未知目标，最大化监测区域中的目标信息。无人机群体事先不知道目标的位置和障碍物布局，利用航空磁测系统搜寻海面及水下目标。磁探仪分辨率为0.000 3 nT，探测宽度为R。探测宽度与磁噪声环境、无人机态势、目标态势、目标磁特性、磁探仪的工作参数、检测阈等因素有关，所以本文从概率的角度对磁探仪的探测宽度进行描述，根据等效平均探测宽度模型，获得磁探仪的时变探测宽度^[15]。

为了便于研究，做出以下假设：1)同一个时刻每个单元格中仅存在一个目标；2)各无人机之间通信良好，不考虑通信延迟、中断带来的影响；3)无人机平台必须能够自主运行；4)假定无人机集群固定在平稳的飞行高度，可保证磁探仪测量精度和对地分辨率。

本文旨在用一组无人机探测存在障碍物的大规模非结构化环境的动态和静态目标，通过合适的目标函数来衡量进程的质量，其中探测器的感知半径随环境和目标实时变化。本文将预期观测时间作为任务目标函数，通过最小化发现给定静态目标所需的时间，或者通过最大化一定搜索时间内发现动态目标的平均数量来优化总体质量，目标发现率不小于95%视为完成任务。

2 算法设计

本节介绍了为多机器人目标搜索系统设计的分布式仿生集群模型和协同搜索优化策略与协调方法。无人机集群分布式目标搜索模型考虑环境和目标运动特性对多智能体系统感知传感器探测性能的影响，基于启发式的仿生集群算法和传感器探测宽度模型建立；使用差分进化算法提取从环境中感知到的信息，以引导无人机通过环境。自组织目标搜索算法考虑元启发式的使用和代理之间的本地交互，以最小化完成任务时间为目标优化分布式模型的协调参数，产生一种在线的无人机集群协调模式。本文算法流程如图2所示。

2.1 无人机集群分布式目标搜索模型

对多智能体系统而言，分布式规划避免了单一的故障点，即使通信暂时中断，机器人集群也能保证正常工作。此外，多个节点并行计算拓展了机器人团队可用的计算资源。相关的计算主要在执行计算结果的机器人个体中执行，这种规划机制能大大提高多智能体的感知决策速度。在本节中，通过采用结合不同的仿生集群算法，即基于昆虫协调方式和鸟群效应的生物机制建立了无人机集群分布式模型，同时该模型考虑了环境和目标特性变化对航空磁探测的影响。昆虫群体行为通过生物制剂机制在环境中协调无人机集群的行为模式；鸟群效应基于对齐、分离和内聚的局部规则的影响。

具体来讲，无人机定期对其位置进行目标检查。在无人机的每一个执行周期里完成如下过程：1)目标检测，如果无人机的磁探仪探测宽度内存在一个未知的目标，它会在它的位置上释放大量的吸引信息素。2)目标和边界检测，如果在探测半径内有无人机或障碍物，那么无人机就会转向自由方向并离开。如果没有发现近距离物体，无人机就会释放排斥信息素，并尝试感知吸引信息素。如果在嗅觉半径内有吸引信息素，无人机就会转向其最大强度的方向。当没有信息素的时候，无人机将在分离区域检测到同伴后，放慢速度并转离同伴。如果在该分离区域内发现没有其他无人机，无人机将朝向更大区域内的其他无人机飞。如果既没有发现无人机，也没有发现信息素，更没有发现障碍物，如果可能的话，无人机会随机转向排斥信息素最小的方向并前进。无人机群体重复以上过程，直至发现的目标达到目标总数的95%。

在上述搜索过程中，本文将搜索者、搜索环境、目标等因素条件抽象为搜索模型中的搜索要素，建立静态航空磁探仪搜索概率评估解析模型。假设在不同的横向距离L条件下，磁探仪的目标检测概率为 $P(L)$ ，则探测宽度R可以描述为目标检测概率在空间的累积，其物理含义表示航空磁探仪的等效平均探测宽度，定义为

$R = \int_{ - \infty }^{ + \infty } {P(L){\rm{d}}L} $

目标在横向探测距离 ${R_{{\rm{mad}}}}$ 范围内即被探测到，目标在 ${R_{{\rm{mad}}}}$ 范围之外则未被探测到，即检测概率表示为

$p(L) = \left\{ {\begin{array}{*{20}{c}} {1,\;\;\;\;\left| L \right| \leqslant {R_{{\rm{mad}}}}} \\ {0,\;\;\;\;\left| L \right| > {R_{{\rm{mad}}}}} \end{array}} \right.$

因此在设定的环境条件下，只需计算不同横向距离L条件下的目标检测概率，便可以得到磁探仪的等效平均探测宽度，计算公式为

$R = \int_{ - {R_\infty }}^{{R_\infty }} {p(L){\rm{d}}L = 2{R_{{\rm{mad}}}}} $

其中，目标检测概率表达式为

$P{\rm{ = }}1 - P({{{x^*}} / {{\sigma ^2}}}\left| {M,\sum {{{B_i^2}/ {{\sigma ^2}}}} } \right.)$

式中：假设磁噪声是高斯噪声，均值为0，方差为 ${\sigma ^2}$ 。检测概率 $P({{{x^*}} / {{\sigma ^2}}}\left| {M,\sum {{{B_i^2} / {{\sigma ^2}}}} } \right.)$ 是M自由度的非中心卡方分布的随机变量的累积分布函数， ${B_i}$ 表示磁探仪在t时刻输出的磁探仪的磁信号，检测阈值为 ${x^*}$ 。

具体来讲，细胞 $\left( {x,y} \right)$ 的t时刻释放的信息素强度p具有以下动力学特征：

$\begin{array}{c} {p_{x,y}}(t) = \varepsilon \cdot [(1 - \delta ) \cdot {p_{x,y}}(t - 1)+ \\ \Delta {p_{x,y}}(t - 1,t) + {d_{x,y}}(t - 1,t)] \end{array}$

其中，扩散速率为 $\delta \in \left[ {0,1} \right]$ ；蒸发速率为 $\varepsilon \in \left[ {0,1} \right]$ 。

$\left( {1 - \delta } \right) \cdot {p_{x,y}}(t - 1)$ 表示扩散到邻近细胞后的剩余量； $\Delta {p_{x,y}}(t - 1,t)$ 表示时间间隔 $\left( {t - 1,t} \right]$ 内信息素的累积浓度； ${d_{x,y}}(t - 1,t)$ 是 $\left( {t - 1,t} \right]$ 时间内从周边细胞扩散来的输入信息素，计算公式为

${d_{x,y}}(t - 1,t) = \frac{\delta }{8}\mathop {\sum\limits_{i = - 1}^1 {\sum\limits_{j = - 1}^1 {} } }\limits_{(i,j) \ne (0,0)} {p_{x + i,y + j}}(t - 1)$

8个相邻细胞在每个更新周期将一部分信息素传播到细胞 $\left( {x,y} \right)$ 。

2.2 无人机集群协同搜索优化算法

2.1节将无人机群体视为鸟群，采用昆虫信息素协调方式探测存在障碍物和目标的非结构化环境。这一过程涉及无人机集群的多个参数，如表1。这些参数直接影响协同目标搜索任务的完成质量，决定了无人机群体对不同场景的适应度和搜索过程的效率。为了产生一个与场景相适应的群体，本节采用了基于自适应算子的改进差分进化算法进行仿生集群参数调整，实现无人机集群的协同优化。

基于改进差分算法的优化策略把任务完成所需的总时间作为衡量协同搜索任务质量的评价指标。该算法需要通过最小化发现给定静态目标所需的时间。因此静态仿真场景的适应度函数被定义无人机集群目标发现率超过95%的最短时间，定义为

${\rm{fitness}}({\mathit{\Omega}} ) = {\min _{t \in {{\rm N}^ + }}}\left\{ {t:\left| {{T_{\rm{F}}}(t)} \right| \geqslant 0.95 \left| T \right|} \right\}$

式中：t时刻已发现的目标集合 ${T_{\rm{F}}}(t) \subseteq T$ ，计算公式为

${T_{\rm{F}}}(t) = \left\{ {\tau \left| {\exists {D_i},\exists t' \leqslant t:{{({x_{t'}},{y_{t'}})}_{{D_i}}} = {{(x,y)}_\tau }} \right.} \right\}$

式中：t为模拟时刻；T为环境中的目标位置集合； $\tau $ 为目标子集； ${(x,y)_\tau }$ 为目标 $\tau $ 的位置坐标； ${({x_t},{y_t})_{{D_i}}}$ 为无人机i在t时刻的动态位置坐标。

在动态场景下，通过最大化一定搜索时间内发现动态目标的平均数量来优化总体质量。动态模拟场景 ${\mathit{\Omega }}$ 的适用性定义为所有帧中发现目标的平均百分比，如式(1)：

${\rm{fitness}}({\mathit{\Omega}} ) = \frac{\lambda }{{\mathit{\Phi}} }\sum_{\varphi = 1}^{\mathit{\Phi}} {\frac{{\left| {{T_F}(\varphi )} \right|}}{{\left| {T(\varphi )} \right|}}} $

(1)

式中： $\lambda $ 为每个帧过渡周期；目标动态位置为 ${(x,y)_{\tau (\varphi )}}$ ， $\varphi {\rm{ = }}0,\lambda ,2\lambda , \cdots ,t \cdot \lambda ,{\mathit{\Phi}} $ ，其中 ${\mathit{\Phi}} $ 是预设的模拟时间的最终时刻。

设k为待调整的参数个数。进化算法的解用K维向量表示。采用基于自适应算子的改进差分进化算法选择并产生一个无人机群体，每个无人机代表搜索空间的某个k维向量解，该群体的基因型代表该可行解的各个分量，它与对应的场景相适应。 $X(0)$ 为随机均匀分布产生的初始种群，代表N个初始解集合。第t代无人机种群为 $X(t)$ ， ${x_i}(t)$ 为第t代种群 $X(t)$ 的第i个基因型。本文采用改进的差分进化算法，通过自适应差分策略实现个体变异。种群变异的中间变量h计算公式为

$h(t + 1) = {x_{r_1}}(t) + F \cdot ({x_{r_2}}(t) - {x_{r_3}}(t))i \ne r_1 \ne r_2 \ne r_3$

式中， ${x_{r_1}}$ 、 ${x_{r_2}}$ 、 ${x_{r_3}}$ 为随机选择的突变成员，自适应变异算子为

$\begin{array}{l} \lambda = {{\rm{e}}^{1 - \frac{{{G_m}}}{{{G_m} + 1 - G}}}}\\ F = {F_0} \cdot {2^\lambda } \end{array}$

式中： ${F_0}$ 为变异算子； ${G_m}$ 代表最大进化代数； $G$ 代表当前进化代数。

然后通过变异的中间变量h和第t代种群 ${x_i}(t)$ 的二项式交叉创建一个试验向量 ${{x}}_i^{\rm{*}}$ ，其中交叉公式为

${{x}}_i^*(t + 1) = \left\{ {\begin{array}{*{20}{l}} {h(t + 1),\;\;\;\;\begin{array}{*{20}{l}} {} \end{array}{\rm{rand}} \leqslant CR} \\ {{{{x}}_i}(t),\;\;\;\;{\rm{{\text{其他}}}}} \end{array}} \right.$

其中，CR为交叉概率。然后，基于贪婪算法原则，根据适应度函数的值从迭代中每个个体的试验向量 ${{x}}_i^{\rm{*}}$ 和原向量 ${{{x}}_i}(t)$ 中选择出适应度更高的，以此作为下一代的最佳拟合向量对种群进行修正。当达到终止条件时，将当前种群中最优解向量作为最优群参数，得到对应最短搜索时间的解向量。

3 仿真实验与分析

为了测试第2章提出的自组织目标搜索策略的运行情况，本文搭建了基于多智能体仿真平台Netlogo和算法开发框架Matlab的二维数字环境来验证本文设计的协同目标搜索算法。实验考虑在大面积的非结构化环境里找到静态或动态目标，无人机通过机载磁探测仪器来探测目标。在仿真数字环境中，各无人机平台能够独立自主运行，同时，各无人机之间能够正常通信，不考虑通信延迟或中断等异常情况，此外，同一个时刻每个单元格中仅存在一个目标。

3.1 静态场景实验设置与分析

静态仿真场景设置为正方形区域，由不同的障碍物和随机分布的42个目标构成。为了测试算法性能，本文开展了基于传统差分进化算法的协同策略和基于仿生集群与改进差分算法的自组织目标搜索策略的多组实验，并统计了不同规模无人机集群的测试性能。

非结构化静态环境仿真场景模型如图3，其中绿色为无人机，灰色为障碍物；红色为目标位置。

图4~5统计了无人机数目分别为6、12、22、32、42、52、62的情况下的实验结果。实验结果表明，就完成目标发现任务所需的最短时间这一指标，采用改进差分进化算法的协同搜索方案较传统进化算法方案需要的时间更短，具有更高的搜索效率。此外，随着无人机群体数量的增加，目标搜索速度不断提高，任务完成时间迅速衰减。

由图6~7可知，本文采用的自组织目标搜索策略实现静态环境的目标发现任务时，在无人机规模相同的情况下，较传统差分进化算法方案拥有更小的环境覆盖率。无人机数量大于32之后，无人机集群完成任务时的环境覆盖率随着集群规模的增加而减小，这意味着无人机群体在环境感知和目标探测的过程中不断朝感兴趣的区域搜索，在未知环境中的探索效率不断提高。

3.2 动态场景实验设置与分析

对于大规模的动态场景，本文的协同目标搜索策略通过将动态环境视为不同帧，每隔一个固定周期目标变换一次，求解使所有帧中的目标的平均百分比最大的群体最优参数。仿真海域动态场景模型如图8所示。其中，场景每隔240 s更新一次，绿色箭头为无人机，红色点为目标集群，灰色表示海域内的岛屿、礁石等障碍物。图8中t分别为240、480、720、960 s的场景模型，每一帧目标总数不断增加，且随机扩散。图8中的目标总数分别为140、240、340、340。实验结果表明，动态模拟场景的适合度定义为在所有帧中发现的目标的平均百分比。

图9为目标发现率随时间变化曲线，由仿真结果可知，利用本文的多目标搜索算法能够高效地实现大规模动态环境下的快速目标搜索任务。图10为不同目标规模时任务完成时间的折线图，由仿真结果可以看出，随着节点数目的增加，时间成本的增加幅度越来越缓慢，该结果验证了该自组织目标搜索算法在大规模集群系统中的可行性。

4 结束语

本文提出了一种面向无人机群目标搜索的自组织目标搜索策略，该策略采用基于仿生集群算法的分布式目标搜索模型，采用自适应差分进化算法实现无人机集群的协同目标搜索优化。无人机的分布式搜索模型结合了磁探仪等效平均探测宽度模型，考虑目标检测过程中环境和目标特性变化的影响，概率性发现环境中的静态和动态目标。仿真实验证明了，该协同策略明显降低了无人机集群勘探的冗余度。随着无人机群体数量的增加，目标搜索速度不断提高，任务完成时间迅速衰减；无人机的环境覆盖率随着无人机规模的增加而减少，表明该协同目标搜索算法的优势随着代理数的增加逐渐显现出来，无人机集群在未知环境中的探索效率不断提高。此外，在未知非结构化环境中，利用本文的多智能体自组织目标搜索算法能够快速发现数目增加且无规律运动的动态目标。