0 引　言

无人潜航器（unmanned underwear vehicle, UUV）被认为是未来海战的力量倍增器。考虑到单个UUV存在巡航时间、载荷数量以及种类等诸多限制，往往需要多UUV协同作业。另外，由于UUV的智能化水平和处置突发情况的能力有限，尚不能完全脱离有人平台独立完成所有任务，有人/无人协同仍是未来较长一段时间内多UUV系统的主要作战模式。因此，在以有人平台作为指控中心的前提下，根据任务的复杂度、UUV数量以及任务能力等，对任务进行合理地分配，对于提高多UUV系统任务执行效率和动态环境适应性至关重要^[1-2]。

传统的多UUV任务分配方法主要包括分布式和集中式两大类^[3]。分布式方法主要采用基于市场的协商拍卖机制^[4]，多目标情况下该类算法对通信速率、容量以及可靠性要求很高，对于UUV集群很难实现。集中式任务分配可以归结为多仓库开放式多旅行商问题模型，主要存在计算复杂度高，难以综合考虑旅行商数量选择、任务执行可行性以及任务负载量等问题^[5]。为了应对传统任务分配方法暴露出的上述问题，国内外研究人员对生物群体中交互机制和反应式机制涌现出的群体行为进行深入研究，提出了改进狼群算法^[6]、改进蚁群算法^[7]、改进粒子群算法^[8]等多种基于群体智能的任务分配方法，在鲁棒性、扩展性和灵活性方面都表现出显著优势。但上述群体智能算法多基于无人集群能够稳定、实时通联构成分布式网络，适应于无人机集群，而对UUV集群受水下环境复杂性和不确定影响，以及UUV自身通信性能限制，通常难以满足算法的自适应、分布式组网要求。针对UUV技术现状，为了有效降低通信强度和暴露风险，指派掌握全局信息的有人平台与多UUV协同作战较为可行^[9]。文献[10]提出一种有人/无人协同背景下的群体智能任务分配方法，有人平台负责任务下达和任务分配流程控制，UUV与有人平台交互信息并根据掌握的局部知识做出任务分配决策。与文献[11]中方法类似，该方法可以高效解决静态全局任务分配问题，但对突发情况下的动态再分配问题没有研究。另外，文献[10]中算法的目标函数没有考虑任务执行顺序对分配结果的影响，一定程度上造成解的次优性。

本文在文献[10]算法的基础上，改进了目标函数，并提出任务重置和任务接续2种策略使其满足动态任务分配场景，提出一种动静结合的多UUV任务分配方法。本文方法基于集中式体系结构构建有人/无人系统作战系统，有人平台从全局入手组织任务分配流程，UUV基于自身性能和局部信息做出最终的分配决策，降低系统复杂性，减少UUV间由协商产生的通信开销。另外，利用阈值响应机制，保证基本的任务分配质量；引入轮盘赌随机策略，提升任务分配方案的全局最优性；设置每轮分配任务数上限，改善任务分配方案的均衡性。最后，通过仿真分析验证了算法的有效性。

1 任务分配问题描述

本文考虑有人/无人协同背景下的多UUV任务分配问题，有人平台负责任务的分发，控制任务分配流程，但并不进行具体分配的方案制定，而是由UUV根据自身载荷能力和能源水平独立决策是否执行某一任务。

1.1 基本假设

多UUV任务分配问题是一个典型的多约束、多参数的非确定性多项式（non-deterministic polynomial，NP）问题，涉及系统结构、单体UUV、任务目标和外界环境等多方面因素，考虑不同因素时的模型求解策略有较大不同。本文的基本假设如下：

1）UUV的续航时间是有限的，UUV航行和任务执行过程均会消耗时间资源，时间资源耗尽时UUV无法执行任务。

2）只要任务载荷与目标匹配且UUV具有足够的能源，UUV便可执行该目标。

3）目标位置已知且静止，对UUV不构成威胁。

4）UUV到达目标后，停留满足要求的一段时间后即完成该任务目标，以该目标位置为出发点继续执行后续目标。

5）每个任务由单个满足能力要求的UUV即可完成。

6）各UUV位于不同的基地，即初始位置不同。

7）任务载荷为非消耗性载荷，可重复使用。

8）单个UUV可搭载多种任务载荷。

1.2 符号说明

假设共 $ {N_m} $ 个待分配目标， $ {N_v} $ 个可使用的UUV， $ {n_r} $ 种任务载荷。记 $ M = \left\{ {1,2,\cdots,{N_m}} \right\} $ 为任务目标集合； $ V = \left\{ {1,2,\cdots,{N_v}} \right\} $ 为UUV集合； $ R = \left\{ {1,2,\cdots,{N_r}} \right\} $ 为任务载荷类型集合； $ T = \left\{ {1,2,\cdots,{N_t}} \right\} $ 为目标类型集合。

UUV i 用如下8元组表示：

$ {V_i} = \{ x,y,v,res,{R_i},tasksToDo,taskDoing,completedTasks \} 。$

(1)

式中： $ x和 y $ 分别为横坐标和纵坐标； $ v $ 为航速； $ res $ 为续航时间； $ {R_i} \subseteq R $ 为UUV i 搭载的任务载荷； $ tasksToDo $ 为待执行的任务列表； $ taskDoing $ 为正在执行的任务； $ completedTasks $ 为已完成的任务列表。

目标 j 用如下6元组表示：

$ {M_j} = \{ x,y,type,resc,st,responsableUUV,completed\} 。$

(2)

式中： $ x和y $ 分别为目标的横坐标和纵坐标； $ type \in T $ 为目标类型； $ resc $ 为完成该目标需要消耗的时间； $ st \in \left[ {0,1} \right] $ 表示任务归一化价值， $ st $ 越大代表完成该任务获得收益越大； $ responsableUUV \in V $ 为负责执行该任务的UUV； $ completed $ 为布尔值，取1表示该任务已完成，取0表示未完成。

各任务载荷对不同类型任务的执行效能用 $ {N_r} $ 行 $ {N_t} $ 列的矩阵 $ Q $ 表示：

$ \left\{ \begin{gathered} Q = {\left( {{q_{r,t}}} \right)_{{N_r} \times {N_t}}} ，\\ {q_{rt}} \in \left[ {0,1} \right]。\\ \end{gathered} \right. $

(3)

式中： $ {q_{r,t}} $ 为利用载荷 r 执行 t 类型任务的效能， $ {q_{r,t}} $ 取值越大说明 r 类型载荷越适合执行 t 类型任务， $ {q_{r,t}} = 0 $ 表示 r 类型载荷不能执行 t 类型任务。

由于UUV i 可搭载多种任务载荷，因此UUV i 与任务 j 的载荷匹配度记为：

$ Q\left( {i,j} \right) = \mathop {\max }\limits_{r \in {R_i}} {q_{r,typ{e_j}}}。$

(4)

式中： $ {R_i} $ 为UUV i 搭载的任务载荷集合； $ typ{e_j} $ 为任务 j 的类型；当 $ Q\left( {i,j} \right) = 0 $ 表示UUV i 不能执行任务 j 。

由于任务载荷均为非消耗性载荷，因此UUV执行任务的能源约束简化为UUV剩余续航时间满足要求，即

$ \left\{ \begin{gathered} re{s_i} - \left( {res{c_j} + {{d\left( {i,j} \right)} \mathord{\left/ {\vphantom {{d\left( {i,j} \right)} {{v_i}}}} \right. } {{v_i}}}} \right) \gt 0 ，\\ d\left( {i,j} \right) = \sqrt {{{\left( {{x_i} - {x_j}} \right)}^2} + {{\left( {{y_i} - {y_j}} \right)}^2}} 。\\ \end{gathered} \right. $

(5)

式中： $ \left( {{x_i},{y_i}} \right) $ 为UUV i 执行完任务 j 的紧前任务时的位置； $ \left( {{x_j},{y_j}} \right) $ 为任务 j 的位置；为UUV i 执行完任务 j 的紧前任务后剩余的续航时间； $ res{c_j} $ 为执行需要消耗的时间。可见计算执行任务的资源消耗时，需要综合考虑飞行途中和任务执行所消耗的时间。

1.3 目标函数

由式(4)和式(5)可知，UUV i 在进行任务选择时需要综合考虑载荷与任务匹配度、任务距离这两方面因素，则UUV i 执行任务 j 的综合效能为：

$ \begin{split} {k_{i,j}} =& \frac{{{{\max }_{g \in J}}\left\{ {d\left( {i,g} \right)} \right\} - d\left( {i,j} \right)}}{{{{\max }_{g \in J}}\left\{ {d\left( {i,g} \right)} \right\}}} \times \alpha + \\ & \left( {1 - \frac{{{{\max }_{g \in J}}\left\{ {Q\left( {i,g} \right)} \right\} - Q\left( {i,j} \right)}}{{{{\max }_{g \in J}}\left\{ {Q\left( {i,g} \right)} \right\}}}} \right) \times \left( {1 - \alpha } \right) 。\end{split} $

(6)

式中： $ J $ 为可供UUV i 选择的任务集；第1项为利用最大值进行归一化的任务距离项，此项越大消耗的飞行时间越短；第2项为利用最大值进行归一化的任务匹配度值，此项越大任务执行效能越大； $ \alpha \in \left[ {0,1} \right] $ 为权重因子，用于调节任务匹配度和任务距离对综合效能的影响程度，取值越大表示越看重任务距离项，反之亦然。

UUV i 应该优先执行距离较近、任务匹配度较高的任务，通常 $ {k_{i,j}} $ 取值越大越好。文献[10]中，对于 $ {N_m} $ 个待分配目标， $ {N_v} $ 个可使用的UUV，将任务分配结果用矩阵表示：

$ Y = {\left( {{y_{i,j}}} \right)_{{N_v} \times {N_m}}}。$

(7)

式中： $ {y_{i,j}} \in \left\{ {0,1} \right\} $ ，取1表示将任务 j 分配给UUV i 执行，反之亦然。基于此，将目标函数定义为：

$ \begin{split} & {Y'} = \mathop {\arg \max }\limits_Y \sum\limits_{i \in V} {\sum\limits_{j \in M} {{k_{i,j}} \cdot {y_{i,j}}} } ，\\ & {\rm{s.t.}} \\ & {\sum\limits_{i \in V} {{y_{i,j}} \leqslant 1} }{,\qquad \forall j \in M}，\\ & {Q\left( {i,j} \right) > 0}{,\qquad \forall y} \in Y|{y_{i,j}} = 1 。\end{split} $

(8)

基于式(7)和式(8)进行优化确定任务分配矩阵，忽略了任务执行顺序对总体效能的影响，而任务执行顺序对UUV的航行时间影响显著，为此本文对目标函数进行改进。定义决策变量 $ x_{j,l}^i $ ，其中j, l=1,2,···, $ {N_m} $ ；i =1,2,···, $ {N_v} $ ，满足

$ {x}_{j,l}^{i}=\left\{\begin{array}{ll}1,& {{\rm{UUVi}}{\text{从目标}}j{\text{航行到}}l{\text{执行任务}}，}\\ 0 ,&{{\rm{UUVi}}{\text{不从目标}}j{\text{航行到}}l{\text{执行任务}}}。\end{array}\right. $

(9)

基于式(6)给出 $ x_{j,l}^i = 1 $ 的效能为：

$ \begin{split} k_{j,l}^i =& \frac{{{{\max }_{g \in J}}\left\{ {d\left( {j,g} \right)} \right\} - d\left( {j,l} \right)}}{{{{\max }_{g \in J}}\left\{ {d\left( {j,g} \right)} \right\}}} \times \alpha + \\ & \left( {1 - \frac{{{{\max }_{g \in J}}\left\{ {Q\left( {i,g} \right)} \right\} - Q\left( {i,l} \right)}}{{{{\max }_{g \in J}}\left\{ {Q\left( {i,g} \right)} \right\}}}} \right) \times \left( {1 - \alpha } \right) ，\end{split} $

(10)

由此UUV i 基于紧前任务 j 对任务 l 进行评估，将任务执行顺序纳入考虑，定义目标函数如下：

$ \max \sum\limits_{i \in V} {\sum\limits_{j,l \in M} {k_{j,l}^i \cdot x_{j,l}^i} } ，$

(11)

s.t.

$ \sum\limits_{l = 1}^{{N_m}} {x_{j,l}^i} \begin{array}{*{20}{c}} { = {y_{i,j}},}&{\forall j \in M} \end{array},i \in V，$

(12)

$ \sum\limits_{j = 1}^{{N_m}} {x_{j,l}^i} \begin{array}{*{20}{c}} { = {y_{i,l}},}&{\forall l \in M} \end{array},i \in V ，$

(13)

$ {\sum\limits_{j = 1}^{{N_m}} {\sum\limits_{i = 1}^{{N_v}} {x_{j,l}^i} } \leqslant 1},\quad\forall l \in M ，$

(14)

$ {\sum\limits_{l = 1}^{{N_m}} {\sum\limits_{i = 1}^{{N_v}} {x_{j,l}^i} } \leqslant 1},\quad \forall j \in M，$

(15)

$ \begin{array}{*{20}{c}} {Q\left( {i,j} \right) > 0,}&{\forall } \end{array}x_{j,l}^i = 1，$

(16)

$ \begin{array}{*{20}{c}} {Q\left( {i,l} \right) > 0,}&{\forall } \end{array}x_{j,l}^i = 1 ，$

(17)

$ \sum\limits_{j = 0}^{{N_m}} {\frac{{d\left( {j,l} \right)}}{{{v_i}}}x_{j,l}^i + res{c_l} \cdot {y_{i,l}}} \begin{array}{*{20}{c}} { \leqslant re{s_i},}&{\forall i \in } \end{array}V。$

(18)

式(12)和式(13)描述了决策变量 $ x_{j,l}^i $ 与式(7)中任务分配矩阵的关系；式(14)和式(15)任务执行次数约束；式(16)和式(17)为载荷匹配约束；式(18)为UUV续航时间约束，j=0代表UUV的出发基地。

通过求解式(11)，可以确定各UUV的任务序列为：

$ {M_i} = \left\{ {m_1^i,m_2^i,\cdots ,m_{{n_i}}^i} \right\},i \in V 。$

(19)

式中， $ {n_i} $ 为UUV i需要执行的任务个数。

2 有人/无人协同下的多UUV任务分配方法

基于水下通信技术现状，为了尽可能减少通信量和通信不稳定的影响，采用如图1所示的集中式控制体系结构实现有人/无人协同。有人平台与UUV可进行双向通信，UUV之间不进行通信，有人平台掌握全局信息，下达待分配的任务集，并为UUV提供必要的航保信息，UUV基于自身能力、可用能源等局部信息做出任务选择。

基于集中式控制体系结构，模拟自然界动物种群的分工协作，提出一种多UUV任务分配方法，该方法运行过程中不断更新待访问UUV集和待分配任务集这2个关键集合，直到所有任务均被分配或没有可用的UUV为止，算法流程如图2所示。

图2中，各UUV依次进行任务选择是任务分配算法的核心，步骤1和步骤2是基于式(10)计算UUV i 对于可选任务集中各任务的执行倾向，执行倾向越大的任务，UUV i 选择该任务的可能性越大。步骤3和步骤4，设定UUV每轮可分配的任务数上限（本文设置为1），在此基础上基于轮盘赌选择出执行倾向较大的一个任务。通过设置任务上限，避免率先参与分配的UUV选择过多任务，造成各UUV任务负载的不均衡，另外也可缓解由于将任务分配给次优UUV造成的分配方案的次优性。

2.1 任务执行倾向计算

由此UUV i 执行任务 l 的倾向与UUV i 的能力以及任务 l 的自身价值两方面因素有关。假设任务 l 的紧前任务为 j，则基于式(10)计算可得UUV i 对任务 l 的执行效能 $ k_{j,l}^i $ 。另外，由式(2)可知，任务 l 的自身价值用 $ s{t_l} $ 表示。综合上述两方面，UUV i 经由任务 j 执行任务 l 的倾向为：

$ T_{j,l}^i = \frac{{{{\left( {s{t_l}} \right)}^2}}}{{{{\left( {s{t_l}} \right)}^2} + {{\left( {1 - k_{j,l}^i} \right)}^2}}} 。$

(20)

由式(20)可知， $ k_{j,l}^i $ 和 $ s{t_l} $ 越大，UUV i 选择执行任务 l 的可能性越大。

2.2 基于轮盘赌策略的任务选择

UUV i 在进行任务选择时，基于式(20)计算可选任务集中各任务的执行倾向，按照执行倾向由大到小对可选任务集进行排序，对排序后的任务集执行图3所示操作。

图3中，max_num是UUV每轮可分配的任务数上限，本文取max_num=1，从而使各UUV的资源能够得以充分利用，尽可能避免出现空闲UUV的情况时。通过设置轮盘赌策略，引入了随机性，算法在利用当前局部信息的同时，有机会拒绝当前局部最优选择，探索找到后续更优方案，在一定程度上可以提升方案的全局最优性。

2.3 算法的动态适应性

本文任务分配方法基于集中式控制体系结构提出，有人平台拥有任务分配的全局信息，可以根据各UUV反馈的任务选择和任务执行情况，合理掌控任务分配的进度，显然可以应对静态、全局任务分配问题。

对于动态应用场景，本文算法也能很好应对。因为每次完成一轮任务分配，有人平台需要对下一轮可用UUV集和可供选择的任务集进行更新。在正常情况下，剔除能源不足的UUV即可得到下一轮可用UUV集，剔除已被分配的任务即可得到下一轮可供选择的任务集。当发生突发情况时，比如某一UUV故障、新增可用UUV、新增任务等，在完成本轮任务分配后，在进行可用UUV集和可供选择的任务集更新时会将上述情况纳入考虑，完成UUV增删和任务增删等操作，将故障UUV的未完成任务视作新增任务处理。具体应对策略可分为2种：

1）接续式策略，即当新增任务时，已经分配的任务保持不变，将新增任务添加到可供选择任务集，供下一轮任务分配使用；

2）重置式策略，即当新增任务时，除UUV正在执行任务保持不变外，其余已分配待执行任务均清空，添加到可供选择任务集中，待下一轮统一进行重新分配。

3 仿真实验

为了验证本文任务分配算法的有效性，利用基于Agent建模理论的NetLogo 6.2^[12]可编程建模平台设计、实现任务分配仿真实验平台。基于该平台可以进行UUV数、任务数、场景大小、新增任务情况、UUV故障情况以及动态应对策略等参数的零活设置。

3.1 想定设计

假设共有4个可用的UUV和15个待侦察的目标，随机分布在50 n mile × 50 n mile的正方形任务海域里，任务分配前的初始态势如图4所示。图中，“箭头”代表UUV，“×”代表任务。

本文取权重调节因子 $ \alpha {\text{ = }}0.6 $ ，UUV初始位置、载荷情况、航速等信息如表1所示，目标位置、类型、收益等信息如表2所示，任务载荷对不同任务的执行效能矩阵如表3所示。

3.2 静态任务分配实验结果

在没有突发情况下，将随机种子设置为17，所得的任务分配结果如图5所示。4个UUV的任务执行序列分别为：UUV 1，0→11→2→3；UUV 2，0→6→9→15；UUV 3，0→12→14→4→13→7；UUV 4，0→10→1→8→5。0代表UUV的初始位置。

该任务分配方案中，各UUV的航行距离、任务完成时间和任务个数等信息如表4所示。

由图5和表4可知，优化所得的任务分配方案，UUV航行轨迹基本没有往复，符合节省能源的要求；另外，各UUV所承担的任务数分别为3，3，4，5，可见该方案的任务负载较为均衡，且能按照“能者多劳”的原则将更多任务分配给航速快的UUV执行，从而尽快完成所有任务。

值得注意，因采用轮盘赌策略引入了随机性，为保证实现结果可复现，将随机种子作为用户可设置的参数之一，采用不同的随机种子任务分配方案会有一定差别，图6给出了随机种子为3，35，155时的任务分配方案，可见与随机种子=17时结果明显不同。基于此，在实际使用本文算法时，用户可进行多次随机，从中选择符合预期的任务分配方案。

3.3 动态任务分配实验结果

动态任务分配实验主要考虑一个UUV突发故障和新增2个任务这2种情况，对比分析接续式和重置式2种策略应对动态场景的效果。

3.3.1 UUV突发故障

假设当仿真你时间为12000 s时，UUV 4突发故障，此时总体态势如图7所示，UUV 1已执行完任务11，UUV 2已执行完任务6，UUV 3已执行完任务12、任务14和任务4，UUV 4已执行完任务10和任务1。

由于UUV 4突发故障，其尚未执行的任务8和任务5需要重新分配，采用接续式策略和重置式策略所得的任务重分配方案如图8所示。可见2种策略均可以应对UUV故障这一突发情况，在本文场景中接续式策略所得方案任务执行时间为14.51 h，重置式策略所得方案任务执行时间为12.79 h，重置式策略所得方案较优。

3.3.2 临机增加新任务

假设当仿真你时间为20000 s时，新增2个任务，任务参数如表5所示，此时总体态势如图9所示（“△”代表新增的任务）。UUV 1已执行完任务11，UUV 2已执行完任务6和任务9，UUV 3已执行完任务12、任务14、任务4和任务13，UUV 4已执行完任务10和任务1。

对于采用接续式策略和重置式策略所得的任务重分配方案如图10所示。接续式策略将任务16分配给UUV 4最后执行。将任务17分配给UUV 2最后执行；与之不同，重置式策略将原由UUV 4执行的任务5分配给UUV 1，UUV 4在执行完任务8后即开始执行任务16。接续式策略所得方案任务执行时间为8.85 h，重置式策略所得方案任务执行时间为11.75 h，接续式策略所得方案较优。

4 结　语

本文在目标函数中显式考虑任务执行顺序的影响，提出一种集中式指挥控制架构下多UUV任务分配方法，设计了接续式和重置式2种策略，使算法能够灵活应对UUV突发故障和临机增加新任务2种动态任务分配场景场景。基于Agent仿真建模设计实现了仿真实验，结果表明本文算法给出的静态任务分配方案，能够兼顾能源节约和负载均衡，但同时需要多次运行取最优解来应对轮盘赌策略引入的随机性。在本文设计的动态场景中，重置式策略和接续式策略各有优劣，正如机器学习领域“no free lunch”定理所言，没有一种策略在所有场景下都能表现最优，因此结合场景具体分析选取最合适的策略。