面向各类智能体如移动机器人、无人机(unmanned aerial vehicle, UAV)、无人艇(unmanned surface vehicle, USV)、自主式水下航行器、传感器的覆盖问题可广泛应用于搜索营救、区域观测、信息采集等任务, 因此近年来得到了国内外学者的广泛研究^[1-2]。该类问题主要分为两大类, 即静态覆盖和动态覆盖。静态覆盖的目标是优化各智能体的静态位置分布, 合理有效地分配多智能体资源, 形成最优覆盖配置^[3-4]; 而动态覆盖是指通过智能体的不断移动与采样, 直至按指定程度覆盖区域内的所有有价值的任务点^[5-6]。本文以UAV/USV对海面任务区域的最优观测为应用背景, 针对动态覆盖问题展开了研究。

根据任务区域内是否存在信息密度, 动态覆盖问题主要有两类求解思路。一方面, 在不存在信息密度或信息密度完全相等的区域(如农田植保等), 可采取各类穷尽策略实现智能体对任务区域的全覆盖。比如, Acar等^[7]将区域建模为连接图, 然后采取图搜索策略优化覆盖路径。Choi等^[8]利用平行线法获得平行的路径, 解决了基于侧扫声纳的多自主式水下航行器最优覆盖问题, 提高了覆盖网络的观测效率。文献[9]提出一种基于最小二乘法的多水下滑翔机最优覆盖采样方法。另一方面, 当区域内信息密度分布已知且覆盖时间有限时, 上述穷尽策略的效率较低, 因此不再适用, 而启发式策略可较好地解决该类问题。例如, Lanillos等^[10]利用滚动时域控制(receding horizon control, RHC)思路规划连续空间的覆盖搜索航路, 通过预估未来时域的观测收益作为代价指标, 然后利用梯度法进行问题求解。基于环境信息密度, 文献[11]采用Voronoi图法对洋流影响下的目标海域进行最优分配, 然后设计针对欠驱动模型的多无人艇控制律, 使得覆盖网络能够从任意初始位置收敛到最优覆盖配置。对多智能体覆盖任务来说, 为避免局部最优、降低优化或控制难度, 一种有效的解决思路就是采用多边形分割、模糊C均值聚类等方法把任务区域分割为多个子区域, 从而将多智能体协同覆盖问题简化为多个单智能体的轨迹优化问题或控制问题^[12], 但现有区域分解方法较复杂或缺乏精细的定量描述。

基于上述考虑, 本文针对多无人机/无人艇对海面区域的最优动态覆盖观测问题, 从航路优化的角度进行了问题描述, 提出了基于任务区域精细分解、子区域评估分配、航路规划相结合的分层求解思路:首先, 采用高斯混合模型(Gaussian mixture model, GMM)近似表示任务区域的信息密度分布, 从而量化提取出若干个高价值子区域; 然后, 将子区域进行排序与分配, 从而将复杂的协同优化问题简化为单UAV或USV航路规划问题; 最后, 为满足时间约束, 各UAV或USV在分配的子区域内采用并行RHC算法进行航路规划。仿真结果表明, 本文提出的方法具有较高的覆盖观测收益, 可有效解决无人机/无人艇最优动态覆盖观测问题, 具有重要的应用价值。

1 最优动态覆盖观测问题建模

本文研究了面向海面区域最优观测的无人机/无人艇动态覆盖问题, 假设${N_{\rm{A}}}$架同构无人机以及${N_{\rm{s}}}$艘同构无人艇组成的覆盖网络执行观测任务, 且任务区域可简化为标准矩形并均匀离散化为$M{\rm{ = }}{M_x} \times {M_y}$个栅格。定义$p(m), \forall m = 1, 2, \cdots, M$为观测区域的信息密度函数, 本文假设该类信息已知, 此外为便于描述, 对其进行归一化处理, 即满足$\sum\limits_{m = 1}^M {p(m)} = 1$。

本文假设无人机的航行速度是无人艇的2倍, 无人机的覆盖范围是无人艇的4倍:在每个采样时刻$t(t = 1, 2, \cdots, T)$, 无人艇在栅格中心, 且恰好覆盖该栅格并探测一次, 下一时刻向左前、正前、右前方向的相邻栅格移动; 而无人机在栅格顶点处, 恰好覆盖4个栅格, 且下一时刻向左前、正前、右前方向的相间栅格移动, 如图 1所示。

定义$d_i^t(m) \in \left\{ {0, 1} \right\}$为t时刻无人机i探测栅格m的标志位, 则$l_i^t(m){\rm{ = }}\sum\limits_{{t_i} = 1}^t {d_i^{{t_i}}(m)} $为无人机i探测栅格m>的历史观测次数, $L_{\rm{A}}^t(m){\rm{ = }}\sum\limits_{i = 1}^{{N_u}} {l_i^t(m)} $为t时刻所有无人机对栅格m的历史总观测次数。同理可得所有无人艇对栅格m的历史总观测次数$L_{\rm{s}}^t(m)$。假设各无人机与无人艇的单次观测事件均是独立的, 则可定义t时刻栅格m的历史观测概率:

$ G_{}^t(m) = 1-{\left( {1-{g_{\rm{A}}}} \right)^{L_{\rm{A}}^t(m)}}{\left( {1-{g_{\rm{s}}}} \right)^{L_{\rm{s}}^t(m)}} $

(1)

其中, ${g_{\rm{A}}} \in (0, 1]$、${g_{\rm{s}}} \in (0, 1]$分别表示无人机、无人艇搭载传感器的观测概率(即观测可信度)。

结合信息密度函数$p(m)$, 我们可定义t时刻栅格m的历史观测收益:

$ P_{}^t(m) = p(m)G_{}^t(m) $

(2)

t时刻所有栅格的历史观测收益可定义为:

$ P_M^t = \sum\limits_{m = 1}^M {{P^t}(m)} $

(3)

定义任务时间为T, 分别定义${\phi _{\rm{A}}}$、${\phi _{\rm{s}}}$为${N_{\rm{A}}}$架无人机和${N_{\rm{s}}}$艘无人艇的规划航路, 根据式(3)可计算上述航路的观测收益$P_M^T({\phi _{\rm{A}}}, {\phi _{\rm{s}}})$。分别定义${\Phi _{\rm{A}}}$、${\Phi _{\rm{s}}}$为${\phi _{\rm{A}}}$、${\phi _{\rm{s}}}$的所有可行解集合, 最优动态覆盖观测任务可定义为寻找获得最大观测收益的航路${\phi _{\rm{A}}}^ * \in {\Phi _{\rm{A}}}$、${\phi _{\rm{s}}}^ * \in {\Phi _{\rm{s}}}$, 满足:

$ P_M^T({\phi _{\rm{A}}}^ *, {\phi _{\rm{s}}}^ * ) \ge P_M^T({\phi _{\rm{A}}}, {\phi _{\rm{s}}}), \forall {\phi _{\rm{A}}} \in {\Phi _{\rm{A}}}, {\phi _{\rm{s}}} \in {\Phi _{\rm{s}}} $

(4)

2 基于GMM-RHC的无人机/无人艇覆盖观测 2.1 求解框架

考虑到传统方法存在观测效率低、局部极小等问题, 本文采取基于观测区域分解、子区域排序与分配、航路规划的求解思路:首先, 基于信息密度函数等先验知识, 采取一种基于GMM的观测区域评价与特征提取方法, 将观测区域量化提取出若干个子区域即信息密度的聚类区域; 然后, 以最大化期望观测收益为指标, 将上述子区域排序、分配给各无人机与无人艇, 从而将复杂的协同规划问题简化为单无人机/无人艇规划问题; 最后, 基于观测收益函数, 各无人机或无人艇在分配的各子区域内采用并行RHC算法进行覆盖观测路径规划。采用上述策略, 将优先覆盖信息密度较大的高价值区域, 因此区域观测效率将大大提高, 且有效避免了局部极小问题。

2.2 基于GMM的观测区域特征提取

通常来说, 任务区域的信息密度越大, 观测收益越高。为了量化提取任务区域特征, 本项目拟采取GMM来近似表示该区域的信息密度函数。GMM用高斯概率密度函数(正态分布)精确地量化事物, 它通常将事物分解为若干个基于高斯概率密度函数的模型^[13-14]。

首先, 定义由$D(D \ge M)$个二维栅格的中心点位置组成的训练样本, 为真实地反应信息密度函数信息, 训练样本中每个栅格对应的个体个数与其信息密度成比例即${D_m}{\rm{ = }}p(m)D$。

假设用$K$个单高斯模型${G_k}(m)$($k = 1, \cdots, K$)表示信息密度, 每个高斯模型所占比例为${\alpha _k}$, 且满足$\sum\limits_{k = 1}^K {{\alpha _k}} {\rm{ = }}1$。因此, 各栅格的信息密度可用高斯混合模型表示为:

$ p(m){\rm{ = }}\sum\limits_{k = 1}^K {{\alpha _k}{G_k}(m)} $

(5)

其中, ${G_k}(m)$为高斯密度函数:

$ {G_k}(m){\rm{ = }}\frac{1}{{\sqrt {{{(2\pi )}^2}\left| {{\mathit{\boldsymbol{C}}_k}} \right|} }}{{\rm{e}}^{-\frac{1}{2}{{(\mathit{\boldsymbol{P}}-{\mathit{\boldsymbol{\mu }}_k})}^{\rm{T}}}\mathit{\boldsymbol{C}}_k^{-1}(\mathit{\boldsymbol{P}} - {\mathit{\boldsymbol{\mu }}_k})}} $

(6)

其中, $\mathit{\boldsymbol{P}}{\rm{ = [}}x, y{{\rm{]}}^{\rm{T}}}$表示栅格m的中心位置的二维向量。

然后, 需对GMM参数如权值${\alpha _k}$, 均值${\mathit{\boldsymbol{\mu }}_k}$, 方差矩阵${\mathit{\boldsymbol{C}}_k}$等进行估计:首先, 采用k-means聚类算法进行目标区域的初步划分; 然后, 采用最大期望法进行GMM参数的最大似然估计, 主要包括初始化、估计、最大化、收敛判定等步骤。

基于上述估计的各高斯模型参数, 即可提取出对应的三个标准差内(概率和99.7%)的椭圆形子区域, 它们代表了信息密度的高价值聚类区域。该子区域以${\mathit{\boldsymbol{\mu }}_k}$为中心, 以矩阵${\mathit{\boldsymbol{C}}_k}$的特征向量为坐标轴, 且长短轴大小分别$3{\sigma _{{x_k}}}$和$3{\sigma _{{y_k}}}$, 其中${\sigma _{{x_k}}}$和${\sigma _{{y_k}}}$分别表示C_k的特征值的平方根, 此外该子区域的总信息密度为$0.997{\alpha _k}$。

2.3 子区域分配 2.3.1 子区域评估与排序

本文主要考虑了3种分配指标, 即子区域总信息密度、子区域覆盖时间、转场时间等。假设某无人机或无人艇i被分配K_i个子区域, 第k个子区域的总信息密度为:

$ {R_k} = 0.997{\alpha _k} $

(7)

子区域覆盖时间表示无人机或无人艇完全覆盖子区域所需的理想时间:

$ {{T}_{C,k}}={\text{9 }\!\!\pi\!\!\text{ }{{\sigma }_{{{x}_{k}}}}{{\sigma }_{{{y}_{k}}}}}/{C}\; $

(8)

其中, C表示无人机或无人艇搭载的传感器覆盖范围, ${\rm{9 \mathit{ π} }}{\sigma _{{x_k}}}{\sigma _{{y_k}}}$表示子区域面积。

转场时间表示由初始点P⁰到第K个子区域中心(k=1)、或者从第k-1个子区域中心到第k个子区域(k≥2)中心所需的理想飞行或航行时间:

$ {T_{F, k}} = \left\{ {\begin{array}{*{20}{c}} {\left\| {{\mathit{\boldsymbol{P}}^0}-{\mathit{\boldsymbol{\mu }}_k}} \right\|/V, }&{k{\rm{ = }}1}\\ {\left\| {{\mathit{\boldsymbol{\mu }}_{k-1}}-{\mathit{\boldsymbol{\mu }}_k}} \right\|/V, }&{k \ge 2} \end{array}} \right. $

(9)

其中, V表示无人机或无人艇的运动速度。

因此, 无人机或无人艇i对某个子区域k的期望观测收益为:

$ EP_k^i = \frac{{{R_k}}}{{{T_{C, k}} + {T_{F, k}}}} $

(10)

根据上式对K_i个子区域进行迭代排序, 确定最优观测顺序。通常期望观测收益越大, 说明该区域的信息密度越高或理想观测时间越少, 优先级越高。

2.3.2 子区域分配

确定各子区域的最优观测顺序后, 可得无人机或无人艇i的期望观测收益:

$ E{A_i} = \sum\limits_{\bar k = 1}^{{K_i}} {EP_{\bar k}^i} $

(11)

其中, $\bar k$表示排序后的子区域序号。此外, 定义各无人机或无人艇的理想观测时间:

$ {T_i} = \sum\limits_{\bar k = 1}^{{K_i}} {({T_{C, \bar k}} + {T_{F, \bar k}})} $

(12)

则无人机或无人艇的总分配指标为:

$ EA={{\lambda }_{1}}\sum\limits_{i=1}^{{{N}_{\text{A}}}\text{+}{{N}_{\text{S}}}}{E{{A}_{i}}}\text{+}{{\lambda }_{2}}\sum\limits_{\begin{smallmatrix} i,j=1 \\ i\ne j \end{smallmatrix}}^{{{N}_{\text{A}}}\text{+}{{N}_{\text{S}}}}{\left| {{T}_{i}}-{{T}_{j}} \right|} $

(13)

其中, 第一部分表示总期望观测收益, 第二部分用来平衡各无人机或无人艇等各观测力量间的任务执行代价, ${\lambda _1}$和${\lambda _2}$为权重系数。EA越大, 区域观测效率越高, 因此最优分配策略如下:

$ A_{{\rm{allocation}}}^* = \arg \max (EA) $

(14)

2.4 基于并行RHC的单无人机/无人艇航路规划

在分配完子区域后, 各无人机或无人艇采取一种以最大化观测收益为目标的并行RHC航路规划方法, 使规划的航路满足任务时间约束。假设无人机或无人艇被分配的子区域中心位置为${\rm{\{ }}{\bar S_1}{\rm{, }} \cdots {\rm{, }}{\bar S_{{K_i}}}{\rm{\} }}$, 则基于并行RHC的航路规划步骤如下。

首先, 初始化各航路段, 包括从起始点P⁰到子区域${\bar S_1}$中心的最短航路段${\phi _0}$(时间${t_0}$)、各子区域的覆盖观测航线${\phi _j}{\rm{ = \{ }}{\bar S_j}{\rm{\} }}\left({j{\rm{ = }}1, \cdots, {K_i}} \right)$(时间${t_j}{\rm{ = }}1$)、各子区域最短转场航线${\phi _{j \to j{\rm{ + 1}}}}(j < {K_i})$(时间${t_{j \to j + 1}}$)。

然后, 如果上述各航路段时间之和小于任务时间T, 则需选择某航路段并添加一个新航点, 具体实现策略如下:采取RHC方法为每条航路段${\phi _j}$预规划一个新航点, 从中选择具有最大单次观测收益的航点$\mathit{\boldsymbol{P}}_{{j^{\rm{*}}}}^{}$, 将其加入到对应子区域(${j^ * }$)的内部航路段$\phi _{{j^{\rm{*}}}}^{}$, 并更新时间$t_{{j^{\rm{*}}}}^{}{\rm{ = }}t_{{j^{\rm{*}}}}^{}{\rm{ + }}1$; 如果${j^ * } < {K_i}$, 则更新从航点$\mathit{\boldsymbol{P}}_{{j^{\rm{*}}}}^{}$到子区域中心${\bar S_{{j^ * } + 1}}$的最短转场航线${\phi _{{j^ * } \to {j^ * }{\rm{ + 1}}}}$, 以及飞行时间。重复上述步骤, 逐渐扩展各覆盖航路段, 直至各段时间之和等于任务时间T。

最后, 将各航路段依次连接起来即${\rm{\{ }}{\phi _0}{\rm{, }}{\phi _1}{\rm{, }}{\phi _{1 \to 2}}{\rm{, }} \cdots {\rm{, }}{\phi _{\left({{K_i}-1} \right) \to {K_i}}}, {\phi _{{K_i}}}{\rm{\} }}$, 作为规划航路。

基于并行RHC的覆盖航路规划算法的示意图如图 2所示。

3 仿真结果

本文采用MATLAB软件进行仿真验证, 每组试验均运行20次, 并对观测收益等统计结果进行分析。假设任务区域为2 500 m×2 500 m, 将该区域平均离散为50个×50个栅格, 信息密度函数由随机产生的10个指数函数组成。其他仿真参数如下:仿真时间T=500s, 无人机数量${N_{\rm{A}}} = 1$, 无人艇数量${N_{\rm{s}}} = 2$, 传感器探测概率${g_{\rm{A}}}{\rm{ = }}0.95$, ${g_{\rm{S}}}{\rm{ = }}0.8$, 高斯模型个数$K = 7$, 训练样本个数$D = 10\; 000$, RHC时域长度$N = 4$, 权重系数${\lambda _1}{\rm{ = }}0.7$和${\lambda _2}{\rm{ = }}0.3$。

假设2架无人艇的初始位置为(100, 100)m, (500, 100)m, 无人机的初始位置为(300, 100)m。任务区域的先验信息密度分布如图 3a所示, 在区域右下角存在一个远离无人机或无人艇初始点和其他子区域的高价值子区域。采取GMM后的近似结果如图 3b所示, 共提取出7个椭圆形的子区域, 它们能较好地近似表示任务区域的信息密度。然后, 采取本文提出的区域评价与分配策略, 排序后的子区域{5, 1}分配给USV1, 子区域{2, 7}分配给USV2, 子区域{6, 4, 3}分配给UAV。基于上述分配结果, 采用并行RHC规划的无人艇与无人机覆盖观测航路如图 3c所示, 它们覆盖了所有高价值子区域, 并且优先监测信息密度较高的区域, 尤其是USV2直接探测右下角的子区域。此外, 由于无人机相比于无人艇具有更大的观测范围与飞行速度, 因此无人机的覆盖航路分布更广泛且更稀疏。

此外, 采取典型的RHC算法进行了仿真对比, 由于未对区域进行评价分配, 传统RHC算法规划的航路会使无人机或无人艇陷入局部区域而无法覆盖右下角区域, 观测效率大大降低, 如图 4所示。我们给出GMM-RHC、RHC、以及广泛应用的平行线法这三种方法的观测收益曲线, 如图 5所示, GMM- RHC具有最优的观测收益, RHC次优, 由于平行线法未有效利用任务区域的信息密度, 因此其观测效率最低。

4 结论

本文研究了面向动态覆盖观测任务的无人机/无人艇航路优化问题。以最大化观测收益为优化指标, 本文提出一种基于GMM区域分解、子区域分配与并行RHC航路规划相结合的分层求解思路, 从而简化问题求解难度。GMM方法可提取任务区域的特征, 为后续子区域分配提供了量化指标; 子区域分配确定了无人机或无人艇的任务子区域及其观测顺序; 并行RHC方法规划的航路可满足时间约束。仿真结果表明, 本文提出的方法具有较高的覆盖观测效率, 无人机或无人艇优先覆盖观测高价值区域, 有效避免了传统方法中的局部极小问题。