无人机(unmanned aerial vehicle, UAV)因其使用灵活、性价比高、可执行高风险任务等优势, 已广泛应用于各类军用或民用领域。相比于船舶监控等技术手段, 利用无人机实现海上各类突发事件的应急空中监控具有成本低、效率高、灵活性强等显著优点, 正逐步成为国内外学术界与海洋管理部门关注的热点。本文以海上目标搜索为应用背景, 针对多无人机协同航路优化问题展开研究。该问题是指针对海上目标所在的疑似海域, 如何规划各无人机的最优搜索航路, 从而有效地引导各无人机尽早发现目标^[1]。

如果区域搜索图信息完全未知或完全均等, 可采取几何类方法或随机法规划无人机搜索航路, 实现对任务区域的遍历覆盖。例如, 轩永波等^[2]提出了运动目标垂线搜索与运动目标斜线搜索方式, 给出多无人机的平行覆盖航路。Lin等^[3]在传统螺旋线法的基础上提出Top2与TopN算法, 即在各个子区域内同时规划螺旋线, 使得无人机航路满足终端时间约束与终端位置约束。此外, 为将几何类方法应用于多无人机搜索问题, 可采用区域分割、任务分配与单机规划相结合的思路^[4-6]。随机法引导无人机在搜索区域内随机飞行, 随着时间累积将逐渐覆盖任务区域^[7]。例如, Englot等^[8]将机器人采样配置点(即顺序搜索点)进行更新, 从各配置区域内选择具有相同覆盖效果但路径长度更短的配置点。文献[9]定义无人机以一定角度沿直线飞行, 到达边界后转弯, 当再次进入搜索区域后以新角度继续沿直线飞行。

如果区域内搜索图信息已知, 可采取基于搜索图的方法:首先将待搜索区域离散化为一系列单元如正方形或六边形栅格, 然后基于各单元实时更新的搜索图信息(如基于贝叶斯规则的目标概率图、基于环境不确定度的认知图、基于信息素交换机制的信息素图等), 定义各类任务指标(如最大化搜索累积概率、最小化搜索所需时间、最大化信息素势差等), 进而采取优化策略寻找最优航路, 引导无人机向最有希望的方向运动^[10-13]。Hu等^[10]采取了覆盖控制策略, 利用Voronoi图相关性质, 控制无人机向代价函数的梯度下降方向运动, 从而实现对目标的近似最优搜索。文献[12]提出了一种基于分布式模型预测控制(distributed model predictive control, DMPC)框架的多无人机协同搜索方法。

当已知任务区域信息时, 基于搜索图的方法利用了任务区域的搜索图信息, 可灵活处理各类复杂情况, 具有较高的搜索效率。然而, 该类方法仍存在局部最优等缺陷, 即无人机可能会长时间徘徊于局部区域而忽视其他高价值区域。因此, 本文为进一步提高搜索效率, 研究了面向多无人机协同目标搜索任务的航路优化问题。利用状态预测一致性算法实现各无人机间的信息融合, 进而采用考虑了未来收益的DMPC方法规划各无人机搜索航路。本研究提出的方法具有较高的搜索效率, 尤其适用于时间敏感目标(简称时敏目标, 其生存概率或探测价值随着时间流逝而迅速降低)的快速搜索任务, 具有重要的应用价值。

1 面向海上目标搜索任务的多无人机协同航路优化问题描述

本文将任务海域简化为标准矩形并将其离散化为$M{\rm{ = }}{M_x} \times {M_y}$个正方形栅格。针对目标搜索任务, 我们采用目标概率图来描述目标存在于海域内各位置的可能性, 它可作为无人机搜索决策的依据。假设初始先验信息已知, 每个栅格m赋予一定的初始概率值$p(\boldsymbol{x}_0^m{\rm{|}}z_0^{}) \in [0, 1]$且已进行归一化处理即满足$\sum\limits_{m = 1}^M {p(\boldsymbol{x}_0^m{\rm{|}}z_0^{})} = 1$。此外, 随着搜索进行, 需实时更新各无人机维护的目标概率图$p(\boldsymbol{x}_k^m{\rm{|}}z_{1:k}^{})$。

假设${N_{\rm{U}}}$架同构无人机执行搜索任务, 为避免机间碰撞, 各无人机在不同的高度定高飞行。无人机装有稳定的飞行控制系统, 可得到质点模型:

$\begin{gathered} {{\dot x}_i} = {v_i}\cos {\psi _i} \hfill \\ {{\dot y}_i} = {v_i}\cos {\psi _i} \hfill \\ {{\dot \psi }_i} = \frac{{{\rm{g}}\tan {\phi _i}}}{{{v_i}}} \hfill \\ \end{gathered} $

(1)

其中, $({x_i}, {y_i})$表示无人机i位置, ${v_i}$为速度(恒定), ${\psi _i}$为偏航角, ${\rm{g}}$表示重力加速度, ${\phi _i}$表示滚转角, 因此无人机i的状态量和控制输入可分别表示为${\boldsymbol{s}_i} = {[{x_i}, {y_i}, {\psi _i}]^{\rm{T}}}$和${u_i} = {\phi _i}$。其中控制输入需满足如下约束条件:

$\left| {{\phi _i}} \right| \leqslant {\phi _{\max }}$

(2)

假设无人机视觉传感器对海面的观测区域可等效为如图 1a所示的扇形区域。此外, 引入关于距离$d$的Sigmoid函数, 定义传感器对观测区域内目标$\boldsymbol{x}_k^m$的探测概率:

$p({z_k} = D|\boldsymbol{x}_k^m){\rm{ = }}\alpha \left( {{\rm{1}} - \frac{1}{{1{\rm{ + }}\exp \left( { - \beta (d - {d_{\rm{s}}})} \right)}}} \right)$

(3)

其中, ${z_k} = D$表示$k$时刻的探测事件, 则${z_k} = \bar D$为未探测事件且满足$p({z_k} = \bar D|\boldsymbol{x}_k^m){\rm{ = }}1 - p({z_k} = D|\boldsymbol{x}_k^m)$。图 1b表示位于$(30\;{\rm{m, 10}}\;{\rm{m)}}$处、视角范围为θ_s = 120°的某传感器探测概率分布($\alpha {\rm{ = }}0.98$, $\beta {\rm{ = }}0.3$, ${d_{\rm{s}}}{\rm{ = }}30\;{\rm{m}}$)。

2 基于状态预测一致性理论的融合更新

观测事件发生后, 可根据Bayes公式更新各无人机维护的目标概率图:

$p(\boldsymbol{x}_k^m\left| {z_{1:k}^{}} \right.) = \lambda p\left( {\boldsymbol{x}_{k - 1}^m\left| {z_{1:k - 1}^{}} \right.} \right)p\left( {z_k^{}\left| {\boldsymbol{x}_k^m} \right.} \right)$

(4)

其中, $\lambda $为归一化因子, 使得任务海域所有栅格的目标概率之和为1。

由于各无人机的探测历史互不相同, 其独立维护的目标概率图也不一致, 因此需进行信息融合。本文在传统一致性理论的基础上引入状态预测器, 实现目标概率图的分布式融合, 使得无人机各自维护的目标概率图能更快地趋于一致(相等)。

首先给出状态预测一致性算法的定义。假设系统内各节点状态满足一阶动态方程${\dot s_i} = {u_i}, i \in V$, 为提高收敛速度, 在常见的连续形式一致性控制算法的基础上引入状态预测器:

$\begin{gathered} {u_i} = - \sum\limits_{j = 1}^{{N_{\rm{u}}}} {{a_{ij}}({s_i} - {s_j})} + \gamma \sum\limits_{j = 1}^{{N_{\rm{u}}}} {{a_{ij}}(\dot s_i^p - \dot s_j^p)} = - \sum\limits_{j = 1}^{{N_{\rm{u}}}} {{a_{ij}}({s_i} - {s_j})} - \hfill \\ \;\;\;\;\;\;\gamma (\sum\limits_{j = 1}^{{N_{\rm{u}}}} {\sum\limits_{k = 1}^{{N_{\rm{u}}}} {{a_{ij}}{a_{ik}}({s_i} - {s_k})} } - \sum\limits_{j = 1}^{{N_{\rm{u}}}} {\sum\limits_{p = 1}^{{N_{\rm{u}}}} {{a_{ij}}{a_{jp}}({s_j} - {s_p})} } ) \hfill \\ \end{gathered} $

(5)

其中, 右式第二部分即为状态预测器。最终各节点状态可快速趋于一致(相等)^[14]。

然后将状态预测一致性算法应用于目标概率图的信息融合。构造包含上述状态量且符合一阶动态方程形式的系统方程, 假设无人机i独立维护的目标概率为$p({\bf{x}}_k^m\left| {z_{1:k}^{}} \right.)$, 不失一般性, 假设无人机间的通信权重系数均为${a_{ij}}{\rm{ = }}1/{N_{\rm{u}}}$, 可得到无人机融合结果如下:

$Q(\boldsymbol{x}_k^m\left| {z_{1:k}^{}} \right.){\rm{ = }}\\ \left( {1 - \frac{{{N_{i, k}}}}{{{N_{\rm{u}}}}} - \gamma \frac{{{N_{i, k}}^2}}{{{N_{\rm{u}}}^2}}} \right)p(\boldsymbol{x}_k^m\left| {z_{1:k}^{}} \right.) + \sum\limits_{j \in {\rm{\{ }}{V_{i, k}}{\rm{\} }}} {\left( {(\frac{1}{{{N_{\rm{u}}}}}{\rm{ + }}\gamma \frac{{{N_{i, k}}}}{{{N_{\rm{u}}}^2}})p(\boldsymbol{x}_k^m\left| {z_{1:k}^{}} \right.)} \right)} $

(6)

其中, ${\rm{\{ }}{V_{i, k}}{\rm{\} }}$表示无人机i的邻居节点集合(不包括自身), ${N_{i, k}}$为邻居节点的个数。

3 基于DMPC的无人机航路优化

考虑到海域环境是动态未知的, 各无人机需分布式决策各自的搜索行为即确定搜索点。由于全局优化无法满足实时性需求, 因此本项目采取基于边探测边决策思路的DMPC方法:各无人机基于目标函数与约束条件规划各自有限时域内的最优搜索点, 并依据决策结果执行任务, 同时进行状态更新; 上述过程采用滚动时域的方法迭代决策, 直至任务结束。

以无人机i为例, k时刻控制输入与状态量为${u_i}(k)$和${\boldsymbol{s}_i}(k)$, 未来N步时域输入为${\boldsymbol{u}_i}[k:k + N-1] = $ ${[{u_i}(k), \cdots, {u_i}(k + N-1)]^{\rm{T}}}$, 定义${J_i}\left( {{\boldsymbol{s}_i}(k), {\boldsymbol{u}_i}[k:k + N-1]} \right)$为总优化指标, 则未来最优N步输入为:

$\boldsymbol{u}_i^*[k:k + N-1]{\rm{ = arg max }}{J_i}$

(7)

本文引入局部搜索收益${J_{\rm{m}}}$、未来搜索收益${J_{\rm{f}}}$、控制输入代价${J_{\rm{u}}}$, 构成优化指标:

${\rm{ }}{J_i}{\rm{ = }}{\lambda _{\rm{m}}}{J_{\rm{m}}} + {\lambda _{\rm{f}}}{J_{\rm{f}}} + {\lambda _{\rm{u}}}{J_{\rm{u}}}$

(8)

假设各时刻无人机观测事件互相独立, k时刻前的搜索收益${D_{1:k}}$可定义为:

${D_{1:k}}{\rm{ = }}1 - \prod\limits_{t = 1}^k {{{\bar D}_t}} $

(9)

其中, ${\bar D_k}$表示k时刻目标未探测的条件概率:

${\bar D_k}{\rm{ = }}\sum\limits_{m = 1}^M {\left( {Q(\boldsymbol{x}_k^m|{z_{1:k}})(1 - p({z_k}|\boldsymbol{x}_k^m))} \right)} $

(10)

因此局部搜索收益${J_{\rm{m}}}$表示为:

${J_{\rm{m}}}{\rm{ = }}{D_{1:k + N}} - {D_{1:k}}$

(11)

由于时域长度N的选取有限, 因此本项目还将引入未来搜索收益, 即N步之后大范围区域内的预计收益。定义$\bar N$为扩充时域长度, 以$k + N$时刻的无人机位置为起点, 根据无人机性能约束条件(最小转弯半径${r_{\min }}$、最大转弯角速率${\omega _{\max }}$、最大飞行速度${v_{\max }}$等)定义未来搜索区域$S$, 如图 2所示的斜线区域, 并将无人机完全覆盖该区域获得的单次搜索收益作为未来搜索收益${J_{\rm{f}}}$:

${J_{\rm{f}}}{\rm{ = }}\sum\limits_{\forall \boldsymbol{x}_k^m \in S}^{} {\left( {Q(\boldsymbol{x}_k^m\left| {z_{1:k}^{}} \right.)p(z_k^{}\left| {\boldsymbol{x}_k^m} \right.)} \right)} $

(12)

控制输入代价${J_{\rm{u}}}$用来描述控制输入的变化情况, 通常${J_{\rm{u}}}$越小, 规划航路越平滑:

${J_{\rm{u}}}{\rm{ = }}{\lambda _{\rm{u}}}\sum\limits_{t = k}^{k + N - 1} {\left\| {u(t) - u(t - 1)} \right\|} $

(13)

然后, 求解公式(7), 获得最优控制输入。考虑到预测精度等原因, 仅执行第一步控制输入$u_i^*(k)$, 而其他时刻的控制输入可作为下时刻初始解的参考。

4 仿真结果

本文在MATLAB软件上进行仿真验证, 每组试验运行50次, 并对搜索收益等统计结果进行分析。假设任务海域大小为5 000 m×5 000 m, 并离散化为100×100个栅格, 目标分布概率图由5个随机的指数函数叠加而成, 如图 3所示。具体仿真参数如下:任务时间$T = 600{\rm{ s}}$, 仿真步长$\Delta T = 1{\rm{ s}}$, 无人机数量${N_{\rm{U}}} = 3$, 飞行速度$v{\rm{ = }}30{\rm{ m/s}}$, 最大滚转角${\phi _{\max }}$=45°, 时域长度$N = 5$, 扩充时域长度$\bar N = 30$, 传感器参数θ_s = 120°, $\alpha {\rm{ = }}0.95$, $\beta {\rm{ = }}1.0$, ${d_{\rm{s}}}{\rm{ = }}200{\rm{ m}}$。

假设3架无人机的初始位置分别为$(0, 0){\rm{m}}$, $(0, 200){\rm{m}}$, $(200, 0){\rm{m}}$, 采取本文方法的规划结果如图 4所示, 由于在局部搜索收益的基础上额外考虑了未来大范围区域内的搜索收益, 因此该方法可引导无人机覆盖大部分有价值的区域, 具有较高的搜索效率。相比于初始目标概率图, 更新后的目标概率大大降低, 也说明无人机对任务区域进行了高效搜索。

采用传统DMPC算法的规划结果如图 5所示, 由于仅以局部搜索收益为指标, 因此无人机会陷入局部区域而忽略右下角区域, 大大降低了搜索效率。此外, 图 6给出了采用本文方法、传统DMPC法、平行线法的搜索收益曲线, 本文方法具有最高的搜索收益, 传统DMPC次之, 而由于平行线法未利用目标概率图信息, 因此搜索收益最低。

5 结论

本文研究了面向海上目标搜索任务的多无人机协同航路优化问题。在对目标概率图信息进行状态预测一致性融合的基础上, 考虑局部搜索收益与未来搜索收益, 利用DMPC方法优化各无人机搜索航路。仿真结果表明, 本文提出的方法具有较高的搜索效率, 且在一定程度上避免了传统方法的局部最优缺陷。