0 引　言

随着各国对经略海洋的日益重视，与海洋工程相关的科学研究越来越受到关注，如何高效地勘探与开发海洋资源，抵御近海与远洋军事威胁，已经成为国际科学界与各国政府的研究重点^{[1 - 2]}。与此同时，随着先进设备及无人自主系统等技术的迭代发展，多样的水下机器人、浮标及水下平台等装备已经在全球的复杂海域中实现了大规模的应用。无人水下航行器（Unmanned Underwater Vehicle，UUV）以其显著的机动性、稳定性及可携载多功能模块等优势，能够完成海洋观测、区域搜索、底部勘探和军事拒止等多种任务，成为经略海洋的重要手段之一^[3]。与此同时，各国科研人员不断提高对海洋开发的技术标准，愈来愈复杂的科研观测任务也对UUV的性能和功能提出了更严格的要求^[4]。然而单独的水下航行器个体在续航、搭载设备能力等方面存在不足，且海洋环境复杂多变，监测范围巨大，考虑到UUV单体在执行监测任务时，存在无法满足任务完成需求或遇到突发事件而导致航行器失效的风险，而集群系统具有冗余性，不会因个体的受限而使整个任务失败^[5]。因此，对UUVs集群进行整个系统性的任务规划研究应运而生，而UUVs集群协同任务规划的首要解决问题就是任务分配^[6]。

对于任务分配，它是由前置静态条件下的任务预分配和后置动态条件下的任务再分配组成。另外，任务分配方法已经广泛应用于物流交通等领域，合理的任务分配有效地减少了交通运输成本、增加了货物运输量并极大提高了相关企业的经济效益。张瑞鹏等^[7]提出了一种考虑无人机飞行航程、任务效益及时间窗口的混合粒子群算法（Particle Swarm Optimization，PSO）去解决无人机协同任务分配问题, 实现了较好的分配效果。Gnana等^[8]利用混合 ACO处理异构分布式系统中的实时任务分配问题，并通过禁忌搜索算法进行加强搜索，算法的测试与比较也验证了混合ACO禁忌搜索算法的有效性。宋育武等^[9]提出了一种改进的GA，能够有效地完成针对异构型无人机集群以时间消耗最短为目标的并行任务分配。精确式算法面临着计算量大，求解困难等缺点，而启发式算法则能够在有限的计算次数中找到令人满意的分配方案，因而成为求解任务分配问题的首选方法。

对于UUVs集群的任务分配方法，目前研究较少。LI 等^[10]提出了一种基于改进合同法网算法的异构多UUVs任务分配策略，考虑到单个UUV的负载指标和令牌环网概念，有效地提高了异构UUVs集群任务分配的合理性。另外，还针对多UUVs在三维水下环境中的目标搜索问题，提出了一种兼顾静态和动态环境变化的任务分配方法^[11]，对可能出现的随机动态干扰情况进行了分析，如在某些随机UUV的失效条件下仍然能够完成目标搜索任务，优化效果显著。Mahmoudzadeh等^[12]考虑了动态洋流和地形变化的影响，开发了一种基于时间窗的动态任务分配框架，能够自主的将任务进行优先级分配，展现出了出色的任务分配能力。ZHAO等^[13]建立了一种适用于异构UUV集群的多潜次任务分配模型，考虑了电池约束和充电续航的工程代价、异构个体间的效能差异及任务形式的多样性，提出基于离散的PSO，实现了高效的目标寻优任务。

然而，现有研究多局限于UUVs集群在固定平台场景下的任务作业能力，难以应对海洋探索中频繁出现的突发、紧急任务需求，与实际工程应用中的复杂工况存在一定脱节。相比之下，由有人/无人平台构成的移动平台具备更完备的通信设备体系，不仅能够全程跟随UUVs集群同步开展协同作业，保障二者间高质量、低延迟的通讯连接，还能在UUV遭遇故障、能源不足等突发状况时，快速提供应援急救支持，提升作业系统的容错性与可靠性。目前各国正在研制的超大型水下潜航器（XLUUV）是最典型的无人水下平台，波音公司已向美国完成“虎鲸 ”号XLUUV的交付，未来将以子母式无人集群的形式开展科学和军事任务^[14]。此外，英国的“HERNE ”、俄罗斯“波塞冬”号等XLUUV正处于研究阶段，基于此，研究移动平台支持下UUVs集群的释放与回收一体化任务分配方法，能够针对海洋探索的工程问题，将平台可移动、能作业等优势与UUVs的能力结合起来，这对于后续UUVs的集群化、智能化的发展具有积极意义。

因此，本文提出了基于区域分割和空间缩减的UUVs集群任务分配方法。首先，提出了基于区域分割的快速初始化方法，能够有效生成高质量的任务分配初始方案，提高初始解的质量，减少收敛时间。然后，提出了基于蚁群算法的UUV集群任务分配方法，通过空间缩减策略加速优化收敛。另外，建立了移动平台与UUVs的协同工作机制，移动平台引导UUVs的任务执行顺序，并与UUV集群共同展开任务工作。最后，在仿真算例中验证了所提方法的有效性。

1 UUV集群任务分配方法

本文聚焦于UUV集群的访点任务，由于UUVs和任务点的数量较多，导致随机产生的初始解往往因为过低的质量而导致算法收敛缓慢，因此为求解大规模的离散优化问题，提出了一种基于区域分割的样本生成方法，以提高初始解的质量。此外，太多任务点导致优化迭代过程漫长，每段任务点间的路线会随任务点的增多呈几何倍数上涨，其中很多任务路线本身并不合理，可以不被计算，为了摒弃这些不合理的任务路径，提出一种空间缩减策略，以减少计算代价，加速优化收敛。

1.1 基于区域分割的快速初始化方法

区域分割机制以任务点的位置信息为指引，以固定平台作为顶点，并根据任务点到固定平台的距离进行偏角θ_i计算，获得任务点的相对位置关系，以划分整个任务区域。基于坐标中心的θ_i计算公式为：

$ {\theta }_{i}\text=\left\{\begin{aligned} &{\tan }^{-1}\left(\frac{{y}_{i}-{y}_{0}}{{x}_{i}-{x}_{0}}\right) ，{\mathrm{when}} \; {x}_{i} \gt {x}_{0} ，{y}_{i}\geqslant {y}_{0}，\\ &{\tan }^{-1}\left(\frac{{y}_{i}-{y}_{0}}{{x}_{i}-{x}_{0}}\right)+2\text{π}，{\mathrm{when}} \;{x}_{i} \gt {x}_{0}，{y}_{i} \lt {y}_{0}，\\ &{\tan }^{-1}\left(\frac{{y}_{i}-{y}_{0}}{{x}_{i}-{x}_{0}}\right)+\text{π}，{\mathrm{when}} \;{x}_{i} \lt {x}_{0} ，\forall {y}_{i}，\\ &\frac{\text{π} }{2} ，{\mathrm{when }} \;{x}_{i}={x}_{0} ，{y}_{i} \gt {y}_{0}，\\ &\frac{3\text{π} }{2} ，{\mathrm{when}} \;{x}_{i}={x}_{0} ，{y}_{i} \lt {y}_{0}。\end{aligned} \right. $

(1)

式中：（x₀, y₀）和（x_i , y_i）分别为出发点和任务点的坐标参数。θi 的判定条件根据固定平台的位置不同而有所区别，具体分为从坐标中心出发和坐标原点出发两种形式，适应于不同的任务分配需求。从区域分割方法的本质来看，该方法是通过一定标准规则实现任务点的区域分配，将总任务域分割成必要的子任务域，以供不同的UUVs进行探索。从式(1)中，区域分割以坐标中心为任务原点，通过θ_i对其周围点进行位置关系的判定，将坐标点归类在不同的任务区域划内。

基于坐标原点的θi计算式为。

$ {\theta }_{i}{\text{=tan}}^{-1}\left(\frac{{y}_{i}-{y}_{0}}{{x}_{i}-{x}_{0}}\right)。$

(2)

在从坐标原点开始切割第一象限的任务域时，θ_i的计算公式较为简单。区域分割方法通过以坐标原点为起点，向任务域划出多个互不相交的射线，将任务域划分为多个面向UUVs的子域。

区域分割方法通过判定得到的角度θ_i进行任务点的区域归类，通过多层次的扇形分割和旋转偏移机制，将任务点系统性地分配到不同的区域中，从而为后续的优化算法提供高质量且多样化的初始解。该方法首先依据预设的切割次数生成多个分割方案，每个方案都通过特定的角度偏移量来实现平面的旋转分割，这种动态偏移机制确保了任务点能够在不同的分割视角下被重新组合和分配，有效增强了区域的多样性和覆盖度。这种快速生成有效初始解的方法，使后续算法能够更快地收敛到全局或者至少是较优的局部最优解，减少计算成本。该方法的流程图如图1所示。

对于解的表达，在集群任务分配样本解的染色体编码形式中，包含任务时序和多个分隔符。分割符将不同UUV的任务点集进行区分隔离，每两个分割符间的编码顺序即为UUVs各自的任务访问时序。即如有K艘UUVs执行任务，那么对应的染色体编码上有K-1个分割符，将任务点集分为对应的K份。每次新样本的生成时，通过随机采用不同的邻域生成技术来生成新的变量，即互换、插值和转向方法，能够进一步加强解的多样性，避免样本稀疏，以减少陷入局部最优解的可能性。这种领域生成方法同样对分割符号适用，能够将包含分割符的染色体片段进行位置的随机变化。区域分割结合领域生成的方法如图2所示。

1.2 基于空间缩减的蚁群算法

ACO以积累信息素的生物学机制实现解的快速收敛，若一条路径上的信息素越多，则证明该路径结果越优秀。产生新的初始样本后，会对每个划分区域分配对应的UUV，ACO算法被运用于每个UUV在自身工作区域最短航迹的优化中。ACO算法的核心是计算任务目标点的转移概率P：

$ P=\frac{{\tau }_{ij}{}^{\alpha }\cdot {\eta }_{ij}{}^{\beta }}{\displaystyle\sum\limits_{n}{\tau }_{in}{}^{\alpha }\cdot {\eta }_{in}{}^{\beta }}。$

(3)

式中：τ_ij为p_i到p_j路径上的信息浓度；η_ij为基于任务点距离的启发信息，是对距离矩阵的逐元素除法运算；α 和 β 为提前设置的相关因子，本文设定分别为1和5。可以看到，τ_ij 越高，两点间的距离越小，转移到该点的概率就越大。信息浓度随着循环的进行，蚂蚁经过该路径的次数越多，该值就会越来越大，反之会越小。

采样完成后的任务子域的合理性得到了提升，然而在每个UUV内部的时序优化中，却不可避免地出现多个任务路径不合理计算的情况。如一个任务点到另一个任务点的路径上有多个任务点存在，算法却规划计算了这2个任务点的航迹成本并反馈给了上层优化中。为了解决这种计算浪费缺陷，本文设计了蚂蚁在寻找最优路径的过程中，只能选择距离该任务点最近的部分任务点作为下个路径点，这种动态空间缩减的机制大大提高了规划方案的质量和合理性。该机制的具体表达式为：

$ Sr={\mathrm{round}}\left(m\times {e}^{-15\times \frac{Iter}{Ite{r}_{\max }}}+3\right)。$

(4)

式中：round函数使Sr值为整数，m是访问任务点的总数量，Iter和Iter_max分别为当前和最大迭代次数。可以看到，当处于算法迭代初期时，Sr值约等于m，越到后期Sr值越小，并最终趋于设定的3。

此外，尽管ACO具有优秀的快速收敛能力，但却容易陷入局部最优中，无法获得高质量的解，因此在算法的内部循环中，对每个蚂蚁引入互换、转向和插值这3种机制。

1.3 UUV集群任务分配模型

考虑移动平台和UUV集群的总任务成本最小的任务分配优化模型为：

$ {\begin{split}\min {F}_{}&={\varepsilon }_{1}\sum\limits_{k}f_{{}_\text{UUVs}}^{k}+{\varepsilon }_{2}\frac{f_{{}_\text{UUVs}}^{\max }}{f_{{}_\text{UUVs}}^{\min }}+C(f_{{}_\text{UUVs}}^{\max })，\\ s.t.C(f_{{}_\text{UUVs}}^{\max })&=\begin{cases} 1000\cdot (f_{{}_\text{UUVs}}^{\max }-{L}_{UUVs}),f_{{}_\text{UUVs}}^{\max } \gt {L}_\text{UUVs}，\\ 0,f_{{}_\text{UUVs}}^{\max }\leqslant{L}_\text{UUVs}，\end{cases} \\ {\varepsilon }_{1}+{\varepsilon }_{2}&=1，\\ k&=1,2\ldots,K。\end{split} }$

(5)

式中：f_UUVs为各UUV的航行距离；${f_\text{UUVs}^{\max } }$为UUV集群中的最大航行距离；${f_\text{UUVs}^{\min } } $为UUV集群中的最小航行距离；ε₁是关于UUV集群航行距离和的权重系数，距离和越大，成本越高。ε₂是平衡UUVs之间任务负载的权重系数，当${f_\text{UUVs}^{\max } } $与${f_\text{UUVs}^{\min } } $的差距越大，成本越高。C(${f_\text{UUVs}^{\max } } $)为关于${f_\text{UUVs}^{\max } } $的罚函数，如果${f_\text{UUVs}^{\max } } $的值超过设定的UUV的航程限制L_UUV，那么就给予超过F上限的惩罚（乘以10³），使该解不可行。两个权重系数的和等于1。图3为本节面向区域分割与空间缩减的算法的实验算例优化流程图。

通过区域分割机制能够为UUVs集群的各个对象分配合理的初始任务点集，并通过基于任务成本的目标函数生成高质量的初始解，然后利用空间缩减机制将该解输入到下层的任务时序优化迭代循环中，能够加速整个优化流程的快速收敛，为后续得到质量满意的最优解提供可靠保证。在本文的任务场景中，移动平台作为UUVs的载体，首先航行到某以目标地点开始下放第一个UUV，该UUV开始执行已经预规划的任务路线。另外，移动平台自身也相应地开展访点作业。其次，移动平台在移动的过程中，也在恰当的时机依次释放其它UUVs执行任务并在特定地点回收外出的UUV，本文图例的尺度单位均为km。为更加直观的理解本节的任务形式。图3给出具体规划案例解释。

图4展示由移动平台和2个UUV组成的UUV集群的最终任务分配示意图。五角星代表起始点p₀，共有35个带有编号的任务点随机散布在50km×50km的坐标系中。红色虚线表示移动平台的任务航迹，蓝色虚线表示UUV₁的任务航迹，绿色虚线表示UUV₂的任务航迹。带有相应边框颜色的方框表示对应UUV的释放与回收点，如图中蓝色方框表示UUV₁从该点开始释放，按照33→31→18→28→27→35→24→17→34→21的任务顺序，并最终在另一个同色方框点实现回收。需要指出的是，释放与回收位置不仅仅在任务点处，也可能在移动平台自身的任务路线上。

2 仿真实验设计与讨论 2.1 实验设置

本文构建从中心出发和从角落出发的2种问题形式，中心坐标位于所在区域的中心，角落坐标设置为（0,0）。共构建2种算例在4种算法上进行测试，这4种算法包括Rs-ACO，Rs-SA以及基准算法ACO和SA，Rs-算法表示具有区域分割和空间缩减机制辅助的算法。表1为2种问题的参数设置。

2.2 仿真实验

4种算法的关于任务成本的优化结果数据如表2 所示。可以看到，Rs-ACO 算法在2种问题中都是最优秀的。与 ACO 相比，在问题 1 上的任务成本的降幅是最大的，达到 9.89%，而在问题 2 上的降幅为 6.10%。Rs-SA 与 SA 相比，在问题 1 上降本效果最好，为 11.90%，在问题 2 上则为 9.29%，证明了两种机制的出色辅助算法寻优的能力。此外，可以明显看到角落和中心出发对 UUV 的成本有着显著影响。在优化结果方差的比较中，ACO 算法的稳定性要比 SA 更加优秀。图6为M-100 和 C-100 问题上不同优化算法的的收敛曲线示意图。

可以直观看到，在2种机制辅助下的 Rs-ACO 与 Rs-SA 的初始解质量更高，使得该初始样本更有前途，逼近优秀的局部最优甚至全局最优解。此外，尽管设定了足够多的迭代次数，相同的底层算法 ACO 与 SA 因为大规模的离散优化问题，很快便在优化过程中陷入了局部最优解中。而且不论是 RS-ACO 与 Rs-SA 的对比，还是纯算法 ACO 与 SA 的对比曲线，都展示出 ACO 算法比 SA 更优秀的全局搜索能力，因此求解集群的任务分配问题时，ACO 算法是更优的选择。寻找适合具体问题的底层 HILBA 算法，也是改进两层优化算法的方向之一。

表3为4种优化算法在不同问题中关于任务距离的优化结果。可知，在相同 8 km×80 km 的任务域中 UUVs 各自的任务航行距离，在中心出发和角落出发的两种任务问题中，最终执行任务的 UUV 数量都是 7 艘，且每种算法中 UUV 任务距离合理，并没有超过任务航程约束的情况，这表明了罚函数惩罚机制的合理性。而没有机制辅助的算法结果表现更差，各 UUV 的任务距离几乎都超过了100，尤其是 SA 算法，在 M-100 的问题中，有 4 艘 UUV的任务距离超过了119 km，几乎要达到任务航程的约束极限，这将使得 UUV 在日常工作中面临能源耗尽风险。而在2种机制的辅助下，Rs-ACO 和 Rs-SA 的 UUV 任务距离更加合理，风险系数直线降低。图7 和图8 为2种问题的最优任务分配路线结果，其中，红色虚线代表移动平台的行进路线，其它颜色的虚线代表 UUV 集群的任务路线。

2.3 分析总结

在无协同机制辅助的情况下，4种算法的仿真结果表明，UUVs 集群的任务执行路径普遍存在多处交叉，路径规划呈现出明显的不合理性。这不仅表现为 UUV 在全局范围内存在无序移动，更体现在算法未能有效识别和利用部分任务点之间的较短路径，从而造成“近点远选”的低效决策。这种规划缺陷直接导致任务执行效率降低，同时使得任务能耗与时间成本显著增加。相比之下，区域分割与空间缩减两种机制的协同应用，为解决复杂场景下的 UUVs 集群任务分配提供了高效思路。区域分割机制通过对作业空间进行合理划分，有效限制了 UUV 的全局无序移动，在一定程度上减轻了路径交叉问题；而空间缩减策略则通过缩小算法的搜索范围，增强了其在局部区域内识别最优路径的能力，从而更好地处理了近点未被优先选择的问题。两者的结合不仅提升了路径规划的合理性与经济性，也显著增强了算法在任务均衡分配方面的表现。综合实验结果来看，区域分割与空间缩减机制展现出优秀的辅助寻优能力。此外，在处理大规模集群任务分配中的任务时序优化问题时，ACO 算法相较于 SA 算法表现出更强的适应性。因此，结合了区域分割与空间缩减机制的 Rs-ACO 算法，被验证为更适用于 UUVs 集群任务分配的解决方案。

M-100的中心坐标为（40, 40）。对每种算法进行5次计算，取结果中最优值和均值。为了便于深入对比优化结果，本小节会对最终的优化目标任务成本，以及各UUV的任务距离分别进行数据分析。图5所示为通过优化拉丁超立方方法采样的2种环境下的任务点坐标示意。

3 结　语

本文针对移动平台与多艘UUVs构成的集群协同执行访点任务这一典型场景，提出了一种基于区域分割和空间所见的UUVs集群任务分配方法。首先，通过引入区域分割方法实现了任务的初步分配，有效提升了初始解的质量，为后续优化奠定了良好基础；其次，提出了基于空间缩减策略的ACO算法，显著增强了算法在处理复杂任务分配问题时的搜索效率与求解能力。最后，仿真计算验证了RS-ACO算法的有效性。未来将考虑引入动态洋流等约束，探索UUVs集群的体系作业能力。