海洋学报

分类	变量	数值
基本参数	区域个数（Nr）	6
AUV个数（Na）	3
AUV剩余能量（E）	{0.39, 0.89, 0.65}
AUV位置（P）	{(800,2200), (1200 200), (4600 1000)}
声呐量程（Ws）	200
合作协同进化方法参数	种群规模（Np）	100
种群个数（NP）	3
最大迭代次数（maxIte）	400
交叉概率（Pc）	0.2
变异概率（Pm）	0.2

分类

变量

数值

基本
参数

区域个数（Nr）

AUV个数（Na）

AUV剩余能量（E）

{0.39, 0.89, 0.65}

AUV位置（P）

{(800,2200), (1200 200), (4600 1000)}

声呐量程（Ws）

200

合作
协同
进化
方法
参数

种群规模（Np）

100

种群个数（NP）

最大迭代次数（maxIte）

400

交叉概率（Pc）

0.2

变异概率（Pm）

0.2

分类	变量	数值
基本参数	区域个数（Nr）	6
AUV个数（Na）	3
AUV剩余能量（E）	{0.39, 0.89, 0.65}
AUV位置（P）	{(800,2200), (1200 200), (4600 1000)}
声呐量程（Ws）	200
合作协同进化方法参数	种群规模（Np）	100
种群个数（NP）	3
最大迭代次数（maxIte）	400
交叉概率（Pc）	0.2
变异概率（Pm）	0.2

分类

变量

数值

基本
参数

区域个数（Nr）

AUV个数（Na）

AUV剩余能量（E）

{0.39, 0.89, 0.65}

AUV位置（P）

{(800,2200), (1200 200), (4600 1000)}

声呐量程（Ws）

200

合作
协同
进化
方法
参数

种群规模（Np）

100

种群个数（NP）

最大迭代次数（maxIte）

400

交叉概率（Pc）

0.2

变异概率（Pm）

0.2

	本文方法	GA	BiCC
AUV $A_1 $	2248	5540	10180
AUV $A_2 $	9738	12640	1133
AUV $A_3 $	5978	9218	5978
总长度	17964	27398	17291

本文方法

BiCC

AUV

$A_1 $

2248

5540

10180

AUV

$A_2 $

9738

12640

1133

AUV

$A_3 $

5978

9218

5978

总长度

17964

27398

17291

	本文方法	GA	BiCC
AUV $A_1 $	2248	5540	10180
AUV $A_2 $	9738	12640	1133
AUV $A_3 $	5978	9218	5978
总长度	17964	27398	17291

本文方法

BiCC

AUV

$A_1 $

2248

5540

10180

AUV

$A_2 $

9738

12640

1133

AUV

$A_3 $

5978

9218

5978

总长度

17964

27398

17291

	预期工作量	实际工作量	工作量偏差
AUV $A_1 $	0.202	0.125	0.077
AUV $A_2 $	0.461	0.542	0.081
AUV $A_3 $	0.337	0.333	0.004

预期工作量

实际工作量

工作量偏差

AUV

$A_1 $

0.202

0.125

0.077

AUV

$A_2 $

0.461

0.542

0.081

AUV

$A_3 $

0.337

0.333

0.004

	预期工作量	实际工作量	工作量偏差
AUV $A_1 $	0.202	0.125	0.077
AUV $A_2 $	0.461	0.542	0.081
AUV $A_3 $	0.337	0.333	0.004

预期工作量

实际工作量

工作量偏差

AUV

$A_1 $

0.202

0.125

0.077

AUV

$A_2 $

0.461

0.542

0.081

AUV

$A_3 $

0.337

0.333

0.004

	本文方法	GA	BiCC
平均工作量偏差	0.0540	0.0002	0.2637
平均$ {H}_{3} $	0.1360	0.4553	0.1564
	AUV $A_1 $	0.067
AUV $A_2 $	0.127
AUV $A_3 $	0.214

本文方法

BiCC

平均工作量偏差

0.0540

0.0002

0.2637

平均

$ {H}_{3} $

0.1360

0.4553

0.1564

AUV

$A_1 $

0.067

AUV

$A_2 $

0.127

AUV

$A_3 $

0.214

	本文方法	GA	BiCC
平均工作量偏差	0.0540	0.0002	0.2637
平均$ {H}_{3} $	0.1360	0.4553	0.1564
	AUV $A_1 $	0.067
AUV $A_2 $	0.127
AUV $A_3 $	0.214

本文方法

BiCC

平均工作量偏差

0.0540

0.0002

0.2637

平均

$ {H}_{3} $

0.1360

0.4553

0.1564

AUV

$A_1 $

0.067

AUV

$A_2 $

0.127

AUV

$A_3 $

0.214

基于协同进化的多AUV多区域覆盖路径规划

PDF下载

蔡畅 ¹ , 陈丹 ¹ , 蔡磊 ²^,^*

海洋学报 | 论文 2024,46(11): 115-124

收起

海洋学报 | 论文 2024, 46(11): 115-124

基于协同进化的多AUV多区域覆盖路径规划

全屏

蔡畅¹, 陈丹¹, 蔡磊²^,^*

作者信息

1.石家庄铁道大学信息科学与技术学院，河北石家庄 050043

2.西北工业大学自动化学院，陕西西安 710072

蔡畅（1993—），女，河北省辛集市人，博士，主要从事自主水下航行器、覆盖路径规划、多机器人系统方向的研究。 E-mail：caichang@stdu.edu.cn

通讯作者:

*蔡磊，博士，主要从事交通运输工程研究。 E-mail：caileilei@mail.nwpu.edu.cn

Multi-AUV multi-regional coverage path planning based on coevolution

Chang Cai¹, Dan Chen¹, Lei Cai²^,^*

Affiliations

1. School of Information and Science Technology, Shijiazhuang Tiedao University, Shijiazhuang 050043, China

2. School of Automation, Northwestern Polytechnical University, Xi’an 710072, China

出版时间: 2024-11-01 doi: 10.12284/hyxb2024132

文章导航

摘要

收起

针对多自主水下航行器（Autonomous Underwater Vehicle, AUV）水下覆盖任务过程中的突发情况，研究了多AUV的覆盖路径重规划问题，提出了一种多机器人−多区域覆盖路径规划（Multi-robot Multi-regional Coverage Path Planning, M²CPP）方法，为可用AUV重新分配未覆盖区域并规划覆盖路径。首先，通过割草机算法确定每个区域中的内部路径和候选入口位置。然后，采用协同进化方法求解最优的区域分配、区域顺序及各区域的最优入口，3个种群协同进化，共同决定所有AUV的完整路径，保证种群多样性，避免陷入局部最优。仿真结果表明，本文方法在根据初始位置和剩余能量为多AUV重规划较短路径的基础上，优化路径结构，保证多AUV工作量均衡，可以较好解决该背景下的路径重规划问题。

关键词

多机器人多区域覆盖路径规划 / 覆盖路径重规划 / 多AUV系统 / 协同进化 / 任务分配

Abstract

收起

In response to contingencies that arise during the underwater coverage missions of multiple autonomous underwater vehicles (AUVs), this study addresses the problem of coverage path replanning for multiple AUVs. A multi-robot multi-regional coverage path planning (M²CPP) method is proposed to reassign uncovered areas to available AUVs and plan their coverage paths. Initially, the lawnmower algorithm is employed to determine the internal paths and candidate entry points within each region. Subsequently, a coevolutionary approach is utilized to solve for the optimal region allocation, region sequence, and the best entry points for each region. Three populations coevolve collaboratively to determine the complete paths for all AUVs, ensuring population diversity and preventing convergence into local optima. Simulation results demonstrate that the proposed method not only replans shorter paths for multiple AUVs based on their initial positions and remaining energy but also optimizes the path structure to ensure a balanced workload among the AUVs, effectively resolving the replanning issue under such scenarios.

Key words

multi-robot multi-regional coverage path planning / coverage path replanning / multi-AUV system / coevolution / task allocation

引用本文

蔡畅, 陈丹, 蔡磊. 基于协同进化的多AUV多区域覆盖路径规划. 海洋学报, 2024 , 46 (11) : 115 -124 . DOI: 10.12284/hyxb2024132

Chang Cai, Dan Chen, Lei Cai. Multi-AUV multi-regional coverage path planning based on coevolution[J]. Haiyang Xuebao, 2024 , 46 (11) : 115 -124 . DOI: 10.12284/hyxb2024132

正文

收起

1 引言

收起

近年来，自主水下机器人（Autonomous Underwater Vehicle, AUV）逐渐发展成为水下覆盖任务的得力工具^[1–3]。为了进一步提高作业效率和系统鲁棒性，将多AUV系统引入水下覆盖任务中，通过多AUV协作来完成搜索区域的覆盖任务^[4–5]，即机器人领域中的多机器人覆盖路径规划（Multi-robot Coverage Path Planning, MCPP）问题^[6]。由于不可预知的环境变化或灾难性故障，多AUV系统的部分AUV可能会失效，此时，需要重新规划未完成的覆盖任务^[7]。在此背景下，本文重点关注多AUV水下覆盖任务中突发情况下的路径重规划问题。

目前为止，部分机器人在覆盖任务中失效问题尚缺乏系统性的研究，仅在一些覆盖路径规划方法中考虑了该特殊情景。在文献[7]中，Song等人提出了基于事件驱动的多机器人协作策略，触发机器人间的博弈，迅速重新规划任务。文献[8]提出了一种基于多机器人生成树覆盖（Multiple Spanning Tree Coverage, MSTC）的在线MCPP方法，并在其中引入了容错机制。文献[9]提出了一种基于机器人的剩余能量和当前位置的覆盖路径规划（Coverage Path Planning, CPP）方法，给出了快速重规划策略。以上几种方法都是从整体协调任务层面应对重规划问题，使多机器人系统能继续完成剩余任务，不关注AUV的确切路径。

本文从覆盖任务分配与路径规划两层面考虑MCPP任务中的路径重规划问题，以明确可用机器人的后续路径。此时的路径重规划问题可以看作是将多个未覆盖区域分配给可用AUV，并设计合理路径来完成覆盖任务。因此，本文将覆盖任务重规划问题转化为多机器人多区域覆盖路径规划（Multi-robot Multi-regional Coverage Path Planning, M²CPP）问题。

M²CPP问题是近几年由Xie等人在文献[10]中首次提出，当前解决方案相对较少。现有方法通常将M²CPP问题视为多旅行商（Multiple Traveling Salesman Problem, MTSP）和覆盖路径规划问题的结合。Xie等在考虑能量有限的约束下，提出了基于分支定界（Branch-and-Bound，BnB）的方法，通过建立二叉树来寻找最佳访问区域，并逐渐形成各自的访问顺序^[11]。进一步针对大规模M²CPP问题，Xie等又提出了一种遗传算法求解每个机器人的区域分配问题。在个体编码过程中采用基于组合的染色体表示方法，并为此设计了全新的交叉和突变算子，在适应度函数中加入了能量约束^[11]。Kim提出了一种基于多智能体深度强化学习的M²CPP方法，该方法将环境的三个通道和智能体在网格地图中的真实位置值组成图像的二进制像素信息，并送入卷积神经网络，通过设计奖励信号寻找有效的覆盖路径和多机器人的合作行为^[12]。Shao等提出了一种基于二部协同进化算法（Bipartite CooperativeCoevolution，BiCC）的M²CPP方法^[13]，将区域间路径规划和区域内路径规划两部分编码为不同种群，使其共同进化，并设计了种群初始化方法及进化算子，以提高种群个体之间的差异，避免陷入局部最优。除此之外，为应对紧急情况，提高算法效率，作者还提出了一种混合-2opt算法^[13]，可以获得接近最优的解。以上方法均适用于传统M²CPP问题，其中所有机器人的起点和终点为同一地点。然而，在水下覆盖中部分AUV失效的情况下的路径重规划问题比传统的M²CPP问题面临更多的实际限制因素和更复杂的任务目标。

分析覆盖任务中部分机器人失效发生时的情景，本文在传统M²CPP问题的基础上考虑了以下几个因素。

•声呐图像质量：声呐图像质量与载体平台的运动状态有直接关系，反映在本文中即AUV沿路径运动的过程。因此，在规划路径时应避免不平稳的运动状态，尽量使AUV在区域内保持定高定速直航^[14]。

•可用AUV剩余能量：可用AUV的剩余能量在路径重规划中至关重要，其决定了每条AUV能承担的工作量^[15]。合理的工作量分配是多机器人研究中的一个重要因素^[16–17]，有助于维持多AUV系统整体正常运作，避免能量不足造成的再次重规划。

•可用AUV当前位置：当重规划发生时，所有AUV正在执行各自的任务，其位置分布于任务区域内部。因此，路径重规划方法应考虑可用AUV的当前位置^[18]，就近分配任务，避免不必要的能量消耗^[19]。

•AUV路径结构：如图1所示，多区域覆盖路径包括两类：区域间路径和区域内路径。由于覆盖剩余区域是可用AUV的主要任务，因此，减少区域间路径可保留更多用于覆盖区域的能量。水下任务中AUV的能量是及其宝贵的，优化路径结构可以延长有效作业时间。而目前，相关文献较少涉及对于路径结构方面的优化。

基于上述分析，本文提出了一种基于割草机路径规划和协同进化（Lawn Mower and Cooperative Co-evolution, LMCC）的路径重规划方法，通过解决多区域分配、多区域访问顺序和区域内覆盖路径规划3个子问题，确定每条AUV重规划的路径。此外，通过仿真实验，本文验证了所提出方法在路径总长度和路径结构等方面的显著优势，证明了LMCC方法在多AUV系统路径规划中的有效性和优越性。

2 问题建模

收起

在水下覆盖任务中，采用多条AUV以全覆盖形式遍历整个任务区域，通过用搭载的声呐进行海底成像，最终从声呐图像中找到目标。然而，由于各种原因，例如传感器或推进器等零件故障、线路问题和电量耗尽等，水下覆盖任务需要重新开始执行。由于AUV任务的准备工作、布放、操控费时费力，因此有必要在任务过程中为可用AUV重规划路径协作覆盖剩余区域。

假设有

$ Nr $

个待覆盖区域

$ R=\left\{{R}_{r}|r=1,2,\cdots ,Nr\right\} $

分布在没有障碍物的任务区域中。所有待覆盖区域都是具有不同位置、大小和形状的凸多边形。另外，所有待覆盖区域的顶点都是已知的。这些区域将被分配给

$ Na $

条可用AUV，记作

$ A=\left\{{A}_{a}|a=1,2,\cdots ,Na\right\} $

。AUV的初始位置，即路径重规划时的位置。此外，AUV的剩余电量

$ E=\left\{{E}_{a}|0 < {E}_{a} < 1,a=1,2,\cdots ,Na\right\} $

也不同，其中

$ {E}_{a}=1 $

表示AUV满电，

$ {E}_{a}=0 $

表示电量耗尽。AUV上搭载的声呐量程为

$ Ws $

，即在AUV路径的垂直方向左右

$ Ws/2 $

范围内的目标才可能被探测到。对于分配到的新任务，AUV从其初始位置开始，依次访问分配的区域，并按照区域内路径完全覆盖每一个区域。任务执行过程中，AUV以固定的高度和速度航行，以保证声呐数据质量。

路径重规划问题被认定为多机器人多区域覆盖路径规划问题。为解决该问题，本文将该问题自顶向下分解为3个子问题：多区域分配、区域访问顺序和区域内覆盖路径。

2.1 多区域分配

对于多区域分配问题，定义了分配矩阵

$ {\boldsymbol{D}} $

，

$ {\boldsymbol{D}}\in {\mathbb{R}}^{Na\times Nr} $

，分配矩阵

$ {\boldsymbol{D}} $

中的元素

$ {d}_{a,r} $

为二进制决策变量，表示区域

$ {R}_{r} $

是否分配给AUV

$ {A}_{a} $

。分配矩阵

$ {\boldsymbol{D}} $

中的元素需满足以下约束：

(1)

$ \sum _{a=1}^{Na}{d}_{a,r}=1\quad r=1,2,\cdots ,Nr, $

(2)

$ \sum _{r=1}^{Nr}{d}_{a,r}\geqslant 1\quad a=1,2,\cdots ,Na, $

(3)

$ \sum _{a=1}^{Na}\sum _{r=1}^{Nr}{d}_{a,r}=Nr. $

约束（1）确保每个区域只分配给一条AUV，约束（2）保证每条AUV都至少分得一个区域，约束（3）表示所有区域都将分配给AUV。因此，通过确定分配矩阵

$ {\boldsymbol{D}} $

可将所有区域分配给AUV。

2.2 多区域访问顺序

分配区域完成后，需要为每一条AUV确定区域间的访问顺序。设分配给AUV

$ {A}_{a} $

的区域的集合为

$ {R}^{a}\in {\mathbb{R}}^{1\times {N}_{r}^{a}} $

，其中

$ {N}_{r}^{a} $

为分配给

$ {A}_{a} $

的区域个数。然后，引入访问顺序矩阵

$ {\boldsymbol{O}}＝\left\{{{\boldsymbol{O}}}^{a}|a=1,2,\cdots ,Na\right\} $

，

$ {{\boldsymbol{O}}}^{a} $

中的元素

$ {o}_{i} $

记录AUV

$ {A}_{a} $

的第

$ i $

个区域的索引，其中

$ i=1,2,\cdots ,{N}_{r}^{a} $

，

$ {o}_{i}= 1,2,\cdots , {N}_{r} $

。例如，

$ {\boldsymbol{O}}=\{3,5,1\} $

表示某AUV将按顺序访问

$ {R}_{3}-{R}_{5}-{R}_{1} $

。因此，每个区域对应访问顺序中的一个位置，访问顺序中每个位置上都有一个区域，所有区域都存在于访问顺序矩阵

$ {\boldsymbol{O}} $

中。

2.3 区域内覆盖路径规划

区域内的覆盖路径通过按顺序遍历分布在区域内的航路点来实现。区域

$ {R}_{r} $

中的顺序航路点表示为

$ {W}^{r}=\{{W}_{1}^{r},W_2^r, \cdots ,{W}_{{N}_{w}^{r}}^{r}\} $

，其中

$ {N}_{w}^{r} $

是区域

$ {R}_{r} $

中的航路点个数。然后，通过重新对航路点排序，以生成最佳覆盖路径。与访问顺序矩阵类似，本文为区域

$ {R}_{r} $

定义路径矩阵

$ {{\boldsymbol{T}}}^{r} $

，其中元素

$ {t}_{m}^{r} $

表示区域

$ {R}_{r} $

中第

$ m $

个航路点的索引，例如

$ {t}_{3}^{r}=5 $

表示路径点5为AUV

$ {A}_{1} $

路径中的第三个路径点。路径矩阵

$ T $

的约束与区域访问顺序矩阵

$ {\boldsymbol{O}} $

相类似，在此不再赘述。

2.4 优化目标

根据上述定义，一条AUV的路径

$ S $

可以由

$ {\boldsymbol{D}} $

、

$ {{\boldsymbol{O}}}^{a} $

、

$ {{\boldsymbol{T}}}^{r} $

确定：

(4)

$ {S}_{a}=f\left({\boldsymbol{D}},{{\boldsymbol{O}}}^{a},{{\boldsymbol{T}}}^{r}\right), $

式中

$ a $

和

$ r $

是AUV和待覆盖区域的索引值。

对于AUV

$ {A}_{a} $

的路径

$ {S}_{a} $

来说，本文考虑以下优化目标。首先，总距离最短。设

$ L(\cdot ) $

表示路径中每两个航路点之间的欧氏距离之和，则总距离为

(5)

$ \min H_1=L\left(S_a\right)\quad a=1,2,\cdots,Na. $

其次，AUV的工作量应与剩余电池容量

$ E $

相匹配。前面假设AUV以固定的高度和速度移动，则能量消耗与距离成比例。本文引入工作量偏差来度量实际工作量

$ Wr $

和预期工作量

$ We $

之间的差

(6)

$\begin{split} \mathrm{min}{H}_{2}=&| W{r}_{a}-W{e}_{a}| =\left| \frac{L\left({S}_{a}\right)}{\displaystyle\sum _{a=1}^{Na}L\left({S}_{a}\right)}-\frac{{E}_{a}}{\displaystyle\sum _{a=1}^{Na}{E}_{a}}\right| \\& a=1,2,\cdots ,Na, \end{split}$

式中用实际路径长度

$ L\left({S}_{a}\right) $

衡量实际工作量，用

$ {E}_{a} $

计算预期工作量。

最后，路径结构最优。覆盖区域作为可用AUV的主要任务，因此应为区域内路径分配尽可能多的能量，而相应区域间路径应缩短，以减少非主要任务能耗。设

$ {So}_{a} $

为AUV

$ {A}_{a} $

的区域间路径，则有

(7)

$ \mathrm{min}H_3=\frac{L\left(So_a\right)}{L\left(S_a\right)}\quad a=1,2,\cdots,Na. $

通过求解上述3个子问题可以获得多条可用路径，然后以公式（5）～（7）中描述的3个目标

$ {H}_{1} $

、

$ {H}_{2} $

和

$ {H}_{3} $

来为依据确定最优路径。

3 基于协同进化和割草机算法的多AUV多区域覆盖路径规划方法

收起

本节详细介绍了提出的基于割草机（Lawn Mower, LM）算法和协同进化方法的覆盖路径重规划方法。区域内的覆盖路径采用LM算法确定，同时还得到每个区域的备选入口位置。然后，依据本文讨论的问题及优化目标，提出了一种协同进化方法，通过设计合适的个体编码及代价函数来为每条AUV分配区域、确定访问顺序及最佳入口，流程图如图2所示。

3.1 区域内覆盖路径规划

本文采用割草机算法来确定每个区域内的路径。割草机算法，即LM算法，是一种基础的单区域覆盖路径规划方法，亦称为牛耕式或往返法^[20–21]。

本文选择割草机覆盖方法的主要考虑两方面原因：第一，LM算法生成的路径总距离短、转弯少，有助于保持AUV的平稳运动状态，此时获得的声呐图像没有转弯造成的失真、变形，提高搜到目标的概率^[22–23]。第二，可以固定一组出入区域的位置。常规多区域覆盖算法忽略出入点位置，只计算路径大概距离，而有了固定出入位置可计算整体路径的精确距离，更符合能量紧缺的AUV作业需求。

LM算法可以为覆盖区域生成一条具有固定间隔和方向的路径。图3直观展示了两条具有不同方向的LM覆盖路径。可以看出，宽度和方向是两个关键变量，可以直接确定一个区域的覆盖路径。通常，路径宽度由所搭载的传感器的范围（即本文中的声呐量程

$ Ws $

）决定。方向则是按需选择，不同方向直接影响路径的转弯次数、总距离以及出入位置。

在本文提出的方法中，为了确定方向，预先计算每个区域的最小外接矩形。然后，以最小外接矩形的长边方向和短边方向作为LM算法的可选方向（如图3）。对于水下覆盖任务来说，一般情况下，图3b中的方向是最优的，由于该方向确定的路径有较少的转弯，从而保持AUV航行稳定，亦可保证采集的声呐数据的质量。特殊情况下，若该区域长宽相差较小，则两方向产生的路径都满足最少转弯。此时，需要根据整体路径需要选择一个方向，实现路径整体优化。

一旦确定方向和宽度，便可获得一组覆盖该区域的有序的航路点及可选的入口位置。以图3为例，该区域的两方向上的可选入口为8个，即p1到p8（见图3中蓝色圆圈中的点），而相应的出口位置可根据入口、宽度和方向计算得到。显然，方向和宽度确定的情况下，不同的入口会导致不同的区域间距离L（So）。因此，另一个问题也由此衍生出来，即入口的选择。为此，后续设计了一种协同进化方法来确定区域入口、多区域分配和多区域访问顺序。

3.2 区域间路径规划

对于M²CPP这种复杂问题，解决方案可由多个部分组成，与协同进化算法中的多个子群体的概念一致，故采用协同进化算法解决区域间路径规划问题。协同进化首次由Ehrlich等提出，最近成为了计算智能研究领域的一个研究热点^[24]，其特点在于优越的搜索能力和渐进学习能力，并可以克服传统遗传算法的早熟收敛现象^[25]。本小节详细描述了所提出的协同进化方法。

在协同进化方法中，将所有AUV的路径编码成一个个体，多个个体组成种群，通过分别进化、联合评估，找到最优解的组合。图4给出了提出的协同进化方法的整体流程，其中，所有AUV的路径解被编码为3个不同种群。种群的更新是通过进化操作完成的，包括交叉、变异、交换和反转。之后，使用代价函数评估原有种群和新生成的个体，并选择最优的Np个作为下一迭代中的原始种群，其中Np表示种群大小。

LMCC方法中的协同进化部分的核心是个体编码和代价函数的设计。个体编码包括了区域的分配、访问顺序和区域入口。代价函数依据第2节中的目标设计，用于评估个体优劣。下面详细介绍编码方案、代价函数设计及用到的进化操作。

3.2.1 个体编码

LMCC方法采用实数编码来表示一个完整解，其中包括了3个共同进化的种群，即

$ {pop}_{A} $

、

$ {pop}_{B} $

和

$ {pop}_{C} $

。以将6个区域分配给3条AUV为例（即

$ Nr=6 $

，

$ Na=3 $

），此时分配矩阵

$ {\boldsymbol{D}} $

和顺序矩阵

$ {\boldsymbol{O}} $

的取值为式(8)的值时，

(8)

$ {\boldsymbol{D}}=\left[\begin{array}{ccc}0 & 1& 0\\ 0& 0& 1\\ 1& 0& 0\\ 0& 0& 1\\ 0& 1& 0\\ 0& 1& 0\end{array}\right] ,{\boldsymbol{O}}_1=\left\{3\right\},{\boldsymbol{O}}_2=\left\{6,1,5\right\},{\boldsymbol{O}}_3=\left\{4,2\right\}. $

图5给出了式(8)对应3个种群的示例个体，首先，

$ {pop}_{A} $

是一组有序的区域索引，即一组乱序的

$ \{1,\cdots ,Nr\} $

，例如图5中的3-6-1-5-2-4。然后，

$ {pop}_{B} $

给出了

$ {pop}_{A} $

的分割位置，即从1到

$ Nr-1 $

的

$ Na-1 $

个整数。以图5中的第二个个体为例，基因“1”和“4”将第一个个体分为3组，即{3}、{6,1,5}、{4,2}，将3组区域分别分配给

$ {A}_{1} $

、

$ {A}_{2} $

和

$ {A}_{3} $

。最后，根据图2，每个区域有8种可选入口，分别记为1～8，

$ {pop}_{C} $

记录从1到8的

$ Nr $

个区域的入口编号，即

$ Nr $

个

$ 1~8 $

的随机数。由此，

$ {pop}_{A} $

、

$ {pop}_{B} $

和

$ {pop}_{C} $

中的个体可联合确定所有AUV的路径。

上述3个种群联合评估进化，可大大增加个体丰富度^[26]。通过迭代进化生成新个体，对其进行评估并不断保留最优个体，可以找到最优解。

3.2.2 选择操作

选择操作是模拟自然选择过程的关键步骤，目的是从当前种群中选择性能较好的个体，以便通过交叉和变异产生下一代。LMCC方法中的选择操作选用精英选择方式，将最优个体直接复制为下一代的原始种群，最大限度保留优秀基因。

若仅选择常规的精英选择，由于编码的数字有限，可能会出现大量重复个体。为解决该问题，本文方法加入了一个步骤来保持待测群体的多样性。首先，将3个群体拼接成一个

$ Np\times （2Nr+Na-1） $

的矩阵。随后，重复行用随机生成的个体来替换，直到待测群体无重复个体为止。最后，将矩阵恢复为3个种群的格式。该步骤可以有效地加快算法的收敛速度，避免陷入局部最优。

3.2.3 进化操作

进化操作用于更新种群，即产生后代、移除高代价个体和保留低成本个体。LMCC方法用到的进化操作有交叉、变异、交换和反转4种。值得说明的是，

$ {pop}_{B} $

中元素本身有顺序，因此并不适用于交换和反转，避免扰乱

$ {pop}_{A} $

的分割结果。

在交叉操作中，取两个相邻个体作为父代

$ paren{t}_{A} $

和

$ paren{t}_{B} $

，子代保留

$ paren{t}_{B} $

中的一个随机位置后两个基因，再将

$ paren{t}_{A} $

中的其他个体依次填入子代的空缺位置（见图6a）。突变操作是交换同一个体中两个随机位置的基因（见图6b）。交换操作交换同一个体中随机位置及其下一位置的基因（见图6c）。反转操作反转同一个体中两个随机位置之间基因的顺序（见图6d）。值得注意的是，由于

$ {pop}_{B} $

本身有顺序，因此不进行交换和反转操作，只采用交叉和变异产生新个体。

在上述四种进化操作之后，将生成一组新的后代个体。根据评估结果对原始个体和后代个体进行评估和排序。前

$ Np $

个最佳个体在下一次迭代中作为原始个体继续进化，直到达到最大迭代次数

$ \max Ite $

。

3.2.4 个体评估

一组可行路径可由

$ {pop}_{A} $

、

$ {pop}_{B} $

和

$ {pop}_{C} $

中的个体确定。为了评估和精炼个体，依据第2.4节中的目标函数设计了代价函数。值得说明的是，本文使用“代价函数”而非“适应度函数”，是因为函数中所有要素都取最小值。下面推导采用的代价函数。

前面提到，最终路径

$ S $

由区域间路径

$ So $

和区域内路径

$ Si $

组成。由此可得，路径

$ S $

的总长度为

(9)

$ L\left(S\right)=L\left(So\right)+L\left(Si\right), $

式中

$ L\left(So\right) $

和

$ L\left(Si\right) $

是区域间和区域内的路径长度。由于LM算法的区域内路径长度

$ L\left(Si\right) $

更易于计算，因此公式(7)中每条AUV的区域内路径距离占总距离的比值

$ {H}_{3} $

可以写成

(10)

$ {\min}{H}_{3}=\frac{L\left({S}_{a}\right)-L\left(S{i}_{a}\right)}{L\left({S}_{a}\right)}=1-\frac{L\left(S{i}_{a}\right)}{L\left({S}_{a}\right)}\quad a=1,2,\cdots ,Na, $

则，代价函数H表示为

(11)

$ \begin{split}\mathrm{min}H=&\sum _{a=1}^{Na}{H}_{1}\times \left({H}_{2}+{H}_{3}\right) =\sum _{a=1}^{Na}L\left({S}_{a}\right)\times \\&\left(\left|\frac{L\left({S}_{a}\right)}{\displaystyle\sum _{a=1}^{Na}L\left({S}_{a}\right)}-\frac{{E}_{a}}{\displaystyle\sum _{a=1}^{Na}{E}_{a}}\right|+1-\frac{L\left(S{i}_{a}\right)}{L\left({S}_{a}\right)}\right).\end{split} $

3.2.5 复杂度分析

LMCC方法是一种混合方法，包含LM区域内覆盖和协同进化两步骤。在LM方法中，时间复杂度是确定的，与航路点的数量成正比，即

$ O(Nr\times Na) $

。而协同进化用于优化区域间分配与协同，每次迭代的代价函数计算和进化操作与种群大小成正比，其计算复杂度为

$ O(\max Ite\times Np) $

。因此整体算法的计算复杂度为

$ O\left(Nr\times Na\right)+O(\max Ite\times Np) $

。由于

$ Nr\times Na $

在数值上远小于

$ \max Ite\times Np $

，因此本文方法的时间复杂度可简化为

$ O(\max Ite\times Np) $

，因此，本文算法可以在多项式时间内完成收敛。

4 仿真实验

收起

本节以MATLAB仿真的形式验证所提出算法的性能。此外，与两种现有M²CPP方法进行了比较，从路径距离、工作量分配和区域间路径比例等多维度，对仿真结果进行了详细描述和分析。

4.1 仿真场景

在仿真中，3条AUV被用于覆盖6个随机分布的多边形区域，初始位置分别位于随机3个未覆盖区域的边界上。AUV的初始位置和6个分布区域如图7所示，图中的AUV的编号和区域编号被用于仿真中。此外，随机设置3条AUV的剩余能量为

$ E=\{0.39, 0.89, 0.65\} $

。表1列出了基本场景及协同进化方法的参数。

本节将提出的LMCC方法与两种现有启发式方法M²CPP方法进行比较，即遗传算法（图中标记为“GA”^[11]）和BiCC方法^[13]。这两种方法均适用于传统M²CPP问题。文献[11]提出的遗传算法通过分组编码方式获得区域分配，并采用快速NN-2Opt算法生成相应的路径，且亦考虑了每个区域的出入口位置及机器人的有限能量。文献[13]提出的BiCC方法也是一种协同进化方法，两个个体协同进化，用于指定区域分配和访问顺序。由于个体较复杂，BiCC专门对交叉操作进行了改进，目的是生成一组能耗最低的路线。

4.2 仿真结果和分析

本小节展示了采用本文算法及两种对比算法的仿真结果，分别从最终路径、代价函数值、总距离、工作量、区域间距离与总距离之比以及运行时间6个方面展开分析和讨论。

4.2.1 最终路径

图8给出了分别采用本文方法（图8a）、GA算法（图8b）和BiCC方法（图8c）计算得到的最终路径。不同AUV的路径及航路点用分别用蓝色、红色和黄色标识，另外，AUV的剩余能量也标记在了图中。

图8a展示了本文方法的区域分配结果和最终路径。由图可知，首先，区域内路径距离最短且无转弯，保证了最优区域内路径和生成的声呐图像质量，有助于快速搜到目标。其次，工作量分配合理，规避后续出现能量不够用的情况，图中AUV

$A_2 $

具有最多能量，被分配了更多的未覆盖区域，承担了最多工作量。另外，所有AUV选择了最近的区域和起点，且在区域间的路径较少，减少了区域间路径上能量的消耗。最后，区域间能量较短，所有AUV能够就近开始执行覆盖任务，整体区域间路径较短，全力保障覆盖区域所需的能量。

图8b给出了遗传算法生成的路径，可以看出，遗传算法可以根据AUV的能量分配覆盖任务。但是，区域间的路径明显多于本文方法的路径，即区域间路径的比例更高。这表明遗传算法规划出的路径整体消耗能量更多，且增加的能耗多用于区域间路径中，不适用于能量紧缺的水下覆盖任务。

图8c描述了采用BiCC方法生成的路径，可以看出，该方法虽然将区域分配给附近的AUV，但工作量分配不合理，后期可能出现能量不够而再次重规划的风险。以AUV

$ {A}_{2} $

为例，其拥有最多的能量，却承担了最少的工作量。

总体来看，与GA方法和BiCC方法相比，本文方法可以生成有效路径，保证声呐图像质量的同时，根据AUV能量合理分配覆盖任务，保证较短区域之间路径，全力保障覆盖区域所需的能量。

4.2.2 代价函数值

400次迭代的代价函数值变化如图9所示，可以看出本文算法在第40代时找到最优解，能够快速收敛至最优。这得益于3个种群的协同进化，既保证了种群多样性，也可避免算法陷入局部最优。此外，在代价函数值评估中，所添加的移除重复个体步骤有助于避免陷入局部最优。由于两种对比算法在启发式算法的基础上加入了其他操作，因此代价函数的收敛过程不作比较。

4.2.3 路径距离

表2对比了3种方法取得的所有AUV路径长度及总距离。与另外两种算法数据相比，本文方法得到的3条AUV的路径长度分别为2248、9738和5978，3者比例接近于能量比，由此证明了本文算法可以根据合理分配工作量。另外，本文算法的路径总长度接近BiCC方法得到的总长度，两者差距不大，相较于GA算法降低了34%。因此，本文方法在缩短路径总距离上表现较好，可以生成较短且合理的路径，进一步降低整体任务所需能量。

4.2.4 工作量

对于多机器人系统来说，合理的工作量分配至关重要，决定着后续任务是否能顺利进行。表3展示了本文方法得到的路径中，所有AUV详细的预期工作量、实际工作量和工作量偏差。从表中可以看出每条AUV的实际工作量都接近于预期工作量，两者相差不大。工作量偏差是预期工作量和实际工作量的差值，最大偏差为0.081，最小偏差为0.004。从工作量上看，本文算法能够按照能量规划合适的工作量，避免出现AUV空闲或能量不足的情况。

3种方法平均工作量偏差对比由表4给出。由表可知，BiCC方法的平均工作量偏差最大，与之前分析图7时得出的结论相符，即BiCC方法存在工作量分配不合理的问题。相比之下，遗传算法的偏差则最小，其主要原因是遗传算法未考虑区域间路径的能量，避免了工作量偏差和路径的能量结构的取舍。综合以上分析可知，本文方法具有相对较低的工作量偏差，即能依据AUV能力合理分配工作量。

4.2.5 区域间距离与总距离之比（

$ {\mathit{H}}_{3} $

）

由于覆盖任务是主要任务，为保留更多能量给覆盖任务，区域间路径应最短。为此，引入了区域间距离与总距离之比（即

$ {H}_{3} $

）这一指标，该指标越小，表示区域间路径越短，覆盖任务的能量越高。

表4中的平均

$ {H}_{3} $

给出了采用本文方法的每条AUV区域间距离和总距离的比值。经过400次迭代后，3条AUV的最终值分别为0.067、0.127和0.214，区域间路径的占比例较小，78.6%以上的能量用于覆盖区域。另外，表4还描述了本文方法、GA算法和BiCC方法的最终平均

$ {H}_{3} $

值分别为0.1360、0.4553和0.1564。与遗传算法和BiCC方法相比，本文方法中区域间距离占比最小，即区域间路径消耗能量最少，可以为区域覆盖任务保留更多的能量。

通过以上比较和分析充分证明了在保证区域内路径最优的同时，本文方法产生的路径具有较短的总距离、更合理的区域分配和较低的区域间路径能量。得到的路径可最大限度引导全体可用AUV合理完成剩余覆盖任务。

5 结论

收起

本文针对采用多条AUV的水下覆盖任务出现突发状况时的路径重新规划问题开展研究，将LM区域覆盖方法和协同进化方法相结合，提出了一种多AUV多区域覆盖路径规划方法。该方法生成的路径不仅保证区域内路径转弯少、距离短，区域间路径短，保证搜索覆盖所需能量，而且工作量分配合理，降低能量与工作量不匹配带来的风险。该方法应用简单，可高效处理具有大量机器人和区域的情况。此外，由于该方法充分考虑了AUV的状态和剩余的覆盖任务，因此可以很好地应用于多种多机器人覆盖任务的故障场景，如地板清洁任务、地形覆盖任务和海洋测绘等。下一步，将通过场地实验的方式进一步验证所提出方法的性能。

基金

收起

国家自然科学基金(62071383)

参考文献

收起

文献

收起

参考文献引证文献

排序方式：

周晶, 司玉林, 林渊, 等. 海底AUV关键技术综述[J]. 海洋学报, 2023, 45(10): 1−12.

Zhou Jing, Si Yulin, Lin Yuan, et al. A review of subsea AUV technology[J]. Haiyang Xuebao, 2023, 45(10): 1−12.

Cai Chang, Chen Jianfeng, Yan Qingli, et al. A prior information–based coverage path planner for underwater search and rescue using autonomous underwater vehicle (AUV) with side–scan sonar[J]. IET Radar, Sonar & Navigation, 2022, 16(7): 1225-1239.

黄琰, 李岩, 俞建成, 等. AUV智能化现状与发展趋势[J]. 机器人, 2020, 42(2): 215−231.

Huang Yan, Li Yan, Yu Jiancheng, et al. State-of-the-art and development trends of AUV intelligence[J]. Robot, 2020, 42(2): 215−231.

Matos A, Martins A, Dias A, et al. Multiple robot operations for maritime search and rescue in euRathlon 2015 competition[C]//Proceedings of the OCEANS 2016 - Shanghai. Shanghai: IEEE, 2016.

朱大奇, 胡震. 深海潜水器研究现状与展望[J]. 安徽师范大学学报(自然科学版), 2018, 41(3): 205−216.

Zhu Daqi, Hu Zhen. Research status and prospect of deep-sea underwater vehicle[J]. Journal of Anhui Normal University (Natural Science), 2018, 41(3): 205−216.

Ai Bo, Jia Maoxin, Xu Hanwen, et al. Coverage path planning for maritime search and rescue using reinforcement learning[J]. Ocean Engineering, 2021, 241: 110098.

Song Junnan, Gupta S. CARE: cooperative autonomy for resilience and efficiency of robot teams for complete coverage of unknown environments under robot failures[J]. Autonomous Robots, 2020, 44(3/4): 647−671.

Sun Chun, Tang Jingtao, Zhang Xinyu. FT-MSTC^*: an efficient fault tolerance algorithm for multi-robot coverage path planning[C]//Proceedings of 2021 IEEE International Conference on Real-time Computing and Robotics. Xining: IEEE, 2021.

Yazici A, Kirlik G, Parlaktuna O, et al. A dynamic path planning approach for multirobot sensor-based coverage considering energy constraints[J]. IEEE Transactions on Cybernetics, 2014, 44(3): 305−314.

Xie Junfei, Carrillo L R G, Jin Lei. An integrated traveling salesman and coverage path planning problem for unmanned aircraft systems[J]. IEEE Control Systems Letters, 2019, 3(1): 67−72.

Xie Junfei, Chen Jun. Multiregional coverage path planning for multiple energy constrained UAVs[J]. IEEE Transactions on Intelligent Transportation Systems, 2022, 23(10): 17366−17381.

Kim G. Multi-agent deep reinforcement learning for multi-regional coverage path planning[D]. Ulsan: Ulsan National Institute of Science and Technology, 2022.

Shao Xianxin, Gong Yuejiao, Zhan Zhihui, et al. Bipartite cooperative coevolution for energy-aware coverage path planning of UAVs[J]. IEEE Transactions on Artificial Intelligence, 2022, 3(1): 29−42.

金磊磊, 梁红, 杨长生. 基于卷积神经网络的水下目标声呐图像识别方法[J]. 西北工业大学学报, 2021, 39(2): 285−291.

Jin Leilei, Liang Hong, Yang Changsheng. Sonar image recognition of underwater target based on convolutional neural network[J]. Journal of Northwestern Polytechnical University, 2021, 39(2): 285−291.

Zhou Hexiong, Zeng Zheng, Lian Lian. Adaptive re-planning of AUVs for environmental sampling missions: a fuzzy decision support system based on multi-objective particle swarm optimization[J]. International Journal of Fuzzy Systems, 2018, 20(2): 650−671.

Viet H H, Dang V H, Choi S, et al. BoB: an online coverage approach for multi-robot systems[J]. Applied Intelligence, 2015, 42(2): 157−173.

Kapoutsis A C, Chatzichristofis S A, Kosmatopoulos E B. DARP: divide areas algorithm for optimal multi-robot coverage path planning[J]. Journal of Intelligent & Robotic Systems, 2017, 86(3/4): 663−680.

Connell D, Manh La H. Extended rapidly exploring random tree–based dynamic path planning and replanning for mobile robots[J]. International Journal of Advanced Robotic Systems, 2018, 15(3): 255903605.

赵荞荞, 张立川, 刘禄, 等. 水下仿生机器人集群节能关键技术综述[J]. 西北工业大学学报, 2022, 40(3): 576−583.

Zhao Qiaoqiao, Zhang Lichuan, Liu Lu, et al. Review on energy-saving key technologies of underwater bionic robot swarm[J]. Journal of Northwestern Polytechnical University, 2022, 40(3): 576−583.

Choset H. Coverage of known spaces: the boustrophedon cellular decomposition[J]. Autonomous Robots, 2000, 9(3): 247−253.

Galceran E, Carreras M. A survey on coverage path planning for robotics[J]. Robotics and Autonomous Systems, 2013, 61(12): 1258−1276.

Kapetanović N, Mišković N, Tahirović A, et al. A side-scan sonar data-driven coverage planning and tracking framework[J]. Annual Reviews in Control, 2018, 46: 268−280.

Lakshmi M D, Murugan S S. Keypoint-based mapping analysis on transformed side scan sonar images[J]. Multimedia Tools and Applications, 2020, 79(35/36): 26703−26733.

Wu Meng, Zhu Xiaomin, Ma Li, et al. Torch: strategy evolution in swarm robots using heterogeneous–homogeneous coevolution method[J]. Journal of Industrial Information Integration, 2022, 25: 100239.

Miguel Antonio L, Coello Coello C A. Coevolutionary multiobjective evolutionary algorithms: survey of the state-of-the-art[J]. IEEE Transactions on Evolutionary Computation, 2018, 22(6): 851−865.

Wang Boqun, Zhang Hailong, Nie Jun, et al. Multipopulation genetic algorithm based on GPU for solving TSP problem[J]. Mathematical Problems in Engineering, 2020, 2020: 1398595.

2024年第46卷第11期

PDF下载

189

引用本文

BibTeX

文章信息

doi: 10.12284/hyxb2024132

接收时间：2024-09-02
首发时间：2025-11-26
出版时间：2024-11-01

补充材料

相关文章

文章信息

作者

出版历史

收稿日期：2024-09-02
修回日期：2024-11-04

基金

国家自然科学基金(62071383)

作者信息

1.石家庄铁道大学信息科学与技术学院，河北石家庄 050043

2.西北工业大学自动化学院，陕西西安 710072

通讯作者:

*蔡磊，博士，主要从事交通运输工程研究。 E-mail：caileilei@mail.nwpu.edu.cn

参考文献

分享链接

https://castjournals.cast.org.cn/joweb/hyxb/CN/10.12284/hyxb2024132

分享至

全文二维码

扫描看全文

引用本文

BibTeX

本文的引用情况

2种不同金属材料的力学参数

科 Family	属数 Number of genus	种数 Number of species	占总种数比例 Percentage of total species (%)	属 Genus	种数 Number of species	占总种数比例 Percentage of total species (%)
鹅膏菌科Amanitaceae	2	11	5.26	鹅膏菌属 Amanita	10	4.78
小菇科 Mycenaceae	2	12	5.74	丝盖伞属 Inocybe	5	2.39
多孔菌科 Polyporaceae	8	14	6.70	蜡蘑属 Laccaria	5	2.39
红菇科 Russulaceae	3	23	11.00	小皮伞属 Marasmius	6	2.87
				小菇属 Mycena	11	5.26
				光柄菇属 Pluteus	5	2.39
				红菇属 Russula	17	8.13
				栓菌属 Trametes	5	2.39

关闭全屏

BibTeX
EndNote
RefWorks
TxT

分类	变量	数值
基本参数	区域个数（Nr）	6
AUV个数（Na）	3
AUV剩余能量（E）	{0.39, 0.89, 0.65}
AUV位置（P）	{(800,2200), (1200 200), (4600 1000)}
声呐量程（Ws）	200
合作协同进化方法参数	种群规模（Np）	100
种群个数（NP）	3
最大迭代次数（maxIte）	400
交叉概率（Pc）	0.2
变异概率（Pm）	0.2

分类

变量

数值

基本
参数

区域个数（Nr）

AUV个数（Na）

AUV剩余能量（E）

{0.39, 0.89, 0.65}

AUV位置（P）

{(800,2200), (1200 200), (4600 1000)}

声呐量程（Ws）

200

合作
协同
进化
方法
参数

种群规模（Np）

100

种群个数（NP）

最大迭代次数（maxIte）

400

交叉概率（Pc）

0.2

变异概率（Pm）

0.2

	本文方法	GA	BiCC
AUV $A_1 $	2248	5540	10180
AUV $A_2 $	9738	12640	1133
AUV $A_3 $	5978	9218	5978
总长度	17964	27398	17291

本文方法

BiCC

AUV

$A_1 $

2248

5540

10180

AUV

$A_2 $

9738

12640

1133

AUV

$A_3 $

5978

9218

5978

总长度

17964

27398

17291

	预期工作量	实际工作量	工作量偏差
AUV $A_1 $	0.202	0.125	0.077
AUV $A_2 $	0.461	0.542	0.081
AUV $A_3 $	0.337	0.333	0.004

预期工作量

实际工作量

工作量偏差

AUV

$A_1 $

0.202

0.125

0.077

AUV

$A_2 $

0.461

0.542

0.081

AUV

$A_3 $

0.337

0.333

0.004

	本文方法	GA	BiCC
平均工作量偏差	0.0540	0.0002	0.2637
平均$ {H}_{3} $	0.1360	0.4553	0.1564
	AUV $A_1 $	0.067
AUV $A_2 $	0.127
AUV $A_3 $	0.214

本文方法

BiCC

平均工作量偏差

0.0540

0.0002

0.2637

平均

$ {H}_{3} $

0.1360

0.4553

0.1564

AUV

$A_1 $

0.067

AUV

$A_2 $

0.127

AUV

$A_3 $

0.214