团队科研成果分享

2023.11.06-2023.11.12

01

研究背景

在水下物联网中，环境具有未知性，使用自主水下航行器(AUV)来进行全覆盖搜索已经成为不可避免的趋势。水下全覆盖搜索任务模型如图1所示，针对未知的水下环境，为AUV集群规划路径，以搜索环境中的目标。在执行全覆盖搜索任务时，最重要的方面是最大程度地提高任务区域的覆盖率并最小化AUV路径的长度以减少能耗。其次，由于水下环境的特点，如存在洋流和障碍物，AUV路径需要保持一定水平的平滑度。最后，考虑到大规模任务场景，算法的计算复杂性应尽量降低。然而，很少有方法可以满足上述要求。

图1  水下全覆盖搜索任务模型

02

关键技术

本文提出了一种基于混合算法的全覆盖搜索方法(HAFCS)，用于在未知水下环境中搜索移动目标。该方法结合了改进的Voronoi聚类策略、改进的人工蜂群(ABC)算法、改进的LOS技术和人工势场(APF)方法，以增强水下全覆盖搜索任务的效率。首先，采用改进的Voronoi聚类策略对整个水下区域进行划分，并将每个子区域分配给AUV，确保子区域的连续性和任务负载平衡度。其次，为增强AUV的搜索能力，设计了具有自适应因子的全维度人工蜂群算法(FD-ABC-AF)，用于为AUV规划全局路径来搜索目标，并进一步使用改进的选择性LOS技术(SLOS)对路径进行平滑。在AUV沿着全局路径航行时，可能会探测到障碍物，因此，使用APF方法为AUV动态规划局部路径来避开障碍物。

03

算法介绍

一、任务分配算法

本文所提出的方法适用于多AUV的全覆盖搜索，因此需要先进行任务分配。在环境建模中，本文采用立方体建模方法，即假设任务区域为长方体，将其划分为若干个相同的立方体。立方体边长根据AUV的探测距离设置，使得AUV在立方体中心时探测范围能够覆盖整个立方体，因此将所有立方体中心作为任务，采用改进的Voronoi聚类策略进行分配。

经典的Voronoi聚类策略将每个任务分配给到达其所需时间最少的AUV，但没有考虑每个AUV的搜索区域的连续性和任务负载平衡，容易造成多个AUV的搜索路径冗余、增加AUV间的碰撞风险，也可能导致分配不均的情况，延长任务时间。因此，本文改进了voronoi聚类策略，引入连续性约束和任务负载约束，可以用如下公式表示：

该策略描述为：对于一个未分配的任务k，使用上述公式计算它与所有已分配任务的目标函数值，并找出所有目标函数值中的最小值及对应的已分配任务i，然后将k分配给i的所属AUV。目标函数中的第一项为AUV分配距离较近的任务，并且能保证搜索区域的连续性，第二项能保证任务负载的平衡度。基于改进voronoi聚类策略的多AUV任务分配算法示意图如图2所示。

图2  基于改进voronoi聚类策略的多AUV任务分配算法示意图

二、路径规划算法

本文采用全局-局部路径规划方法，为了提高实用性，在全局路径规划中引入了路径平滑技术。因此，路径规划方法分为三个部分：全局路径规划、路径平滑技术和局部路径规划。

1）全局路径规划：本文对ABC做出了改进，用于全局路径规划。ABC的灵感来自于蜜蜂群体的智能觅食行为。蜂群中有三种蜜蜂：雇佣蜂、跟随蜂和侦察蜂。一个蜜源对应于优化问题的一个解，即一条可行路径，而每个蜜源的花蜜量代表相关解的质量（适应度）。最初，蜂群中只有雇佣蜂和跟随蜂，各占蜂群的一半。它们的数量都等于蜜源的数量，一个蜜源上有一只雇佣蜂和一只跟随蜂。雇佣蜂负责寻找可用的蜜源和收集信息，也就是在每轮迭代中以如下方式更新所有解：

即改变其中一个路径点。跟随蜂从雇佣蜂传递的信息中选择好的蜜源，进一步寻找食物，也就是基于概率决定是否更新解，而概率取决于解的适应度，适应度越高的解越有可能得到更新，更新方式与雇佣蜂相同。解的适应度计算方式为：

其中，目标函数值f(x_i)由三项组成，分别对应任务区域覆盖率、路径长度成本和转向成本。因此，一个解的覆盖率越大、路径越短、转向角越小，其适应度就越高。当蜜源的质量没有在预定的循环次数之前得到改善时，雇佣蜂就会放弃蜜源，然后，雇佣蜂就会成为侦察蜂，开始寻找新的蜜源，也就是随机生成一个新解。换句话说，雇佣蜂负责产生更多的解，提高解的多样性。而跟随蜂负责优化，提高解的最优性。当雇佣蜂变成侦察蜂时，具备了跳出局部最优的能力。

由于蜜源更新方式的较大随机性，ABC存在搜索范围不够全面、易陷入局部最优的缺点。因此，本文做出了相应的改进，提出了FD-ABC-AF，避免蜜源更新的幅度太大或太小。具体来说，为雇佣蜂和跟随蜂提出了两种不同的蜜源更新方式。将雇佣蜂产生新蜜源的方式改为：

即更新所有的路径点。将跟随蜂产生新蜜源的方式改为：

其中，ω_i,j是一个自适应因子，取决于当前两个蜜源之间的距离和其他蜜源之间的距离，可以描述为：

其中，D_i,j是当前两个蜜源之间的距离，μ是两两蜜源之间距离的均值，σ是两两蜜源之间距离的方差。这样改进有两个好处：1）在算法的“搜索”过程中，将一维搜索改为全维度搜索，提高了算法的搜索能力；2）在算法的“优化”过程中，引入自适应因子，根据当前蜜源的距离来确定因子的大小，减小了随机性，平衡了更新的幅度，更有利于得到最优解。

2）路径平滑技术：由于全局路径规划中对于转向角的约束是软约束，所规划的全局路径中仍然可能出现太大的转向角，因此需要路径平滑技术来对全局路径进行平滑处理。本文改进了LOS技术，用于路径平滑处理。LOS技术通过LOS检查对路径进行后处理，原理如图3(a)所示。在图3(a)中，有两条原始路径，用蓝色虚线表示。我们可以对路径中的某一个路径点做LOS检查，即判断该路径点是否可以被跳过，从而将路径修改为由它的父节点直接到达它的子节点。例如，路径点x_i,j可以被跳过，从而将路径修改为绿色路径，减少一个转向角。而路径点x_k,j显然不能被跳过，因为修改后的路径经过与障碍物相交的不可行域。

图3  LOS检查

在先前的使用LOS检查的文献中，都是尽可能多地使用LOS检查来删除路径点。这种做法虽然大大减少了转向角的数量，但可能导致不实际的转向角，如图3(b)所示。在图3(b)中，在x_i,j处做LOS检查后，修改了路径。虽然减少了一个转向角，但新路径中x_i,j+1处的转向角太大，对AUV来说明显是不实际的。

因此，本文改进了LOS检查，通过引入可接受性阈值，提出了SLOS检查。具体来说，增加一个角度偏差（AD）检查，即

这样的改进考虑了修改前路径和修改后路径的角度之差，从而平滑处理导致的过大转向角。

3）局部路径规划：AUV沿着全局路径进行全覆盖搜索任务时，可能会探测到突发的障碍物，因此需要为AUV规划局部路径以避开。本文使用人工势场法来规划局部路径，这种方法假设AUV在一种虚拟力场下运动，实时调整AUV的航行方向。人工势场包括引力场和斥力场，其中目标点对AUV产生引力，引导AUV朝向其运动；障碍物对AUV产生斥力，避免AUV与之发生碰撞。引力的方向由AUV指向目标，大小与它们之间的距离成正比；斥力的方向由障碍物指向AUV，大小与它们之间的距离成反比。AUV在每个路径点上所受的合力等于该点上所有斥力和引力之和，也称为势场力。因此，局部路径规划的目标函数为：

即令AUV的航行方向尽量靠近势场力的方向。

将AUV探测到的突发障碍物前方的第一个路径点作为局部路径的起点，后方的第一个路径点作为局部路径的目标点，如图4所示。其中，蓝色虚线是全局路径，绿色实线路径是局部路径。

图4  全局路径与局部路径的结合

04

实验结果

由于本文的主要贡献集中在任务分配算法与全局路径规划方法上，因此本文分别对所提出的任务分配算法、全局路径规划方法以及完整的HAFCS做了仿真实验，实验结果证明了所提出方法的有效性。

1. 任务分配算法的实验

在任务分配算法的实验中，为了证明所提出任务分配算法的有效性，引入了两个对比算法：1）voronoi聚类策略；2）基于自组织映射(SOM)的对偶竞争策略。三种方法的任务负载平衡度如表I所示，具体分配方案如图5所示。

表I  任务负载平衡度的对比

图5  任务分配方案的对比。(a)Voronoi聚类策略。(b)基于SOM的对偶竞争策略。(c)改进的Voronoi聚类策略

从表I中可以看出，voronoi聚类策略导致了分配不均的情况，这可能会延迟总体任务时长。由于考虑了任务负载平衡度，基于自组织映射的对偶竞争策略和本文所提出的改进的voronoi聚类策略能够为各个AUV分配数量相差不大的目标。在图5中，三个实心的三角形代表三个AUV，空心的圆代表目标，每个目标被分配给颜色相同的AUV。可以看出，基于自组织映射的对偶竞争策略导致了单个AUV的搜索区域的不连续性，即搜索区域没有紧密地相邻，这容易导致冗余的搜索，增加AUV间的碰撞风险。而voronoi聚类策略和本文所提出的改进的voronoi聚类策略能够保证搜索区域的连续性。

总体而言，本文所提出的方法以距离最近为原则，同时考虑了任务负载平衡和搜索区域的连续性，能够为AUV提供更有效的任务分配。

2. 全局路径规划方法的实验

在全局路径规划方法的实验中，引入了三个对比算法：1）基于时空聚类的算法(STCA)+LOS；2）多策略进化学习人工蜂群算法(MSEL-ABC)+SLOS；3）改进的量子粒子群优化算法(IQPSO)。四种算法所规划的路径图如图6所示，其中红色实心三角形代表AUV的起点。AUV需要在环境中进行尽可能全面的搜索，并避开海底地形和四个球形障碍物。从图6中可以看出，STCA+LOS所规划的路径覆盖率明显很低，转向角太大，存在冗余搜索。IQPSO所规划的路径虽然十分平滑，但同样存在覆盖率低、冗余搜索的问题。MSEL-ABC+SLOS所规划的路径克服了上述问题，但容易得到太接近障碍物的路径，如图6(b)中放大部分所示。所提出方法规划的路径不仅克服了上述问题，还能避免规划出太接近障碍物的路径，这在实际应用中非常重要。

图6  路径图的对比。(a)STCA+LOS。(b)MSEL-ABC+SLOS。(c)IQPSO。(d)FD-ABC-AF

三维路径图中难以辨别路径长度、覆盖率和转向角的大小，因此，在不引入路径平滑技术的情况下，对四种路径规划算法做了对比实验。所规划路径的长度、覆盖率、转向角和计算时间如表II所示。

表II  路径的对比

从表II可以看出，STCA得到了最短的路径，但它在覆盖率和平滑度方面最差。IQPSO所规划路径长度最短，但优势并不明显，且覆盖率与两种改进的ABC相差较大。两种改进的ABC在路径长度和覆盖率方面性能相近，但从转向角的占比情况可以看出，MSEL-ABC所规划路径存在较大的转向角；从计算时间可以看出，由于多策略进化数据库和反馈机制，MSEL-ABC需要更大的计算成本，这在大规模任务下会导致较差的鲁棒性。

四种路径规划算法的收敛性如图7所示。从图7中可以看出，IQPSO的收敛速度最慢，其次是STCA。MSEL-ABC和本文所提出的FD-ABC-AF的收敛性几乎相同，但MSEL-ABC所得的最优解略微高于其他三种算法，这可能是由于多策略进化数据库为人工蜜蜂的进化行为提供太多选择，使得算法难以专注于最优解的优化。

图7  收敛性的对比

3. HAFCS的实验

由于前两部分已经验证了所提出创新点的优越性，因此这个部分只验证HAFCS的有效性。本文先用3个AUV搜索一个的水下区域，其中有四个随机移动的障碍物和固定不动的海底地形，以及10个随机移动的目标。路径图如图8所示。从图8中可以看出，3个AUV搜索各自的区域，几乎没有冗余搜索。3个AUV的路径经过了所有的目标，即搜索率为100%。此外，AUV的路径并没有与障碍物和海底地形发生碰撞，并且与之相距较远，体现了所提出方法的安全性。

图8  HAFCS所规划的路径

然后，本文又在另外五种不同任务规模下运行了所提出的方法，实验结果如表III所示。其中，第二列说明AUV、目标和障碍物的数量，例如3-10-4表示有3个AUV、10个目标AUV和4个障碍物。从表III中可以看出，搜索率取决于AUV、目标和障碍物的密集程度，AUV越密集、目标越稀疏、障碍物越稀疏的情况下，搜索率越高。因为AUV需要在搜索的同时躲避障碍物，而密集的障碍物意味着目标位于障碍物附近的可能性更大，导致AUV无法发现它。转向角的大小取决于AUV和障碍物的密集程度，当AUV比较稀疏时，各AUV所分配到的搜索区域变小，为了将活动控制在自己的搜索区域内，AUV可能需要做出更多、更大的转向；当障碍物比较密集时，AUV也需要做出更多、更大的转向来避开。与障碍物的最小距离体现方法的安全性，也取决于AUV和障碍物的密集程度。当AUV和障碍物都比较稀疏时，AUV的全局路径经过障碍物的概率就比较小，碰撞风险也就更低；当AUV和障碍物比较密集时，碰撞风险更高。在计算时间方面，随着任务规模的增大，计算时间并没有太大的涨幅，体现了所提出方法的鲁棒性。

05

总结

针对未知环境中的水下全覆盖搜索任务，本文提出了HAFCS方法。该方法考虑了环境动态性、AUV的机动性、任务负载平衡、实用性和安全性等因素。它包括一个任务分配算法和一个全局-局部路径规划算法，为AUV集群提供最佳的任务分配方案，并为每个AUV规划平滑和安全的路径，以最大化找到目标的概率。多AUV任务分配算法基于改进的Voronoi聚类策略，引入了两个新的约束条件，以确保任务负载平衡度和搜索区域的连续性。全局-局部路径规划算法基于路径长度、平滑性、覆盖率和安全性等标准对所需路径进行优化、修改和调整。此外，所提出的方法表现出很强的鲁棒性，适用于在真实的大规模场景中部署。

扫描二维码关注我们