0 引　言

伴随着人工智能技术的发展和人类对海洋探索、开发活动的逐步深入，海洋智能无人装备被逐渐应用于海洋科学、海洋工程、海事管理等领域，尤其是在一些危险、枯燥或需要长期、广泛作业的应用场景，辅助人们从事海上作业活动。随着人工智能、传感器技术的发展和环保意识的提升，无人化、智能化、绿色化将成为未来海洋装备发展的趋势^[1]，无人水面艇（Unmanned Surface Vehicle，USV）作为一种具备较高搭载能力的高费效比无人装备，成为水上搜救、执法、护卫等军民用领域的重要平台^[2]，逐步迎来高速发展时期^[3]。2023年1月，全球首艘智能型无人系统母船“珠海云”号成功交付，为我国海洋科学、海洋经济发展提供利器^[4]，将基于无人装备的海洋探索活动推向更高的阶段。

自主路径规划能力是无人艇能够安全、高效地完成自主航行与作业任务的基础能力，也是无人艇自主能力研究的一个重要方向，主要分为基于先验环境的全局规划和基于实时感知信息的局部规划。

在无人艇全局路径规划方面，国内外学者进行了深入研究，并取得了一系列的成果。饶森^[5]基于电子海图构造分层环境模型，应用激活值和遗传算法相结合完成全局路径规划；范云生等^[6]采用改进的遗传算法，对栅格图进行编码，并完成了全局规划，仿真说明该方法能够加快路径规划的收敛速度；庄佳园等^[7]提出动态网格模型，在多轮规划中逐步淘汰无效栅格，能够快速得到较高精度的全局路径；刘美芳^[8]采用四叉树分割光栅海图，并依据航行安全建立评估函数，影响A*的节点拓展，完成安全的路径规划；程杰^[9]采用正六边形网格建立环境模型，并对网格邻域进行层级拓展，采用改进的A*算法完成了全局路径规划；Song等^[10]提出了一种适用于复杂海洋环境的改进蚁群算法，能够在栅格地图中规划出平滑的全局路径。

本研究针对无人艇的全局路径规划问题，提出了一种基于矢量电子海图的广域变尺度路径规划方法，能够兼顾无人艇作业中对路径规划的快速性和高分辨率要求。首先，设计一种广域环境建模方法，基于矢量电子海图离线对指定区域构造多层不同分辨率的栅格地图，并根据一定的规则进行栅格类型标注，确保在障碍附近可通行栅格倾向于高分辨率图层，在空旷区域可通行栅格倾向于低分辨率图层；其次，采用改进的A*算法在构造的多层栅格图层间进行穿插拓展和规划，最终找到全局路径，为无人艇后续的自主航行决策提供全局航线参考。

1 广域环境建模

电子海图是一种用于船舶助航的海洋电子地图，分为矢量海图和光栅海图，能够提供海洋环境的多种先验信息，被广泛应用于航海、海上搜救、海事管理等领域。

基于矢量电子海图数据构建有利于全局规划的环境信息表达和存储形式，即广域环境建模方法，将环境信息表达为具有不同分辨率的基础图层和派生图层。基础图层直接从矢量电子海图数据生成，其分辨率在全部图层中最高；派生图层有若干层，由基础图层逐级派生而来，分辨率逐级减半。基于栅格的环境表示方法对于环境障碍轮廓的规则性要求较低，适合用于表达不规则的海洋岸线、岛屿等，因此本方案采用栅格法构建环境图层。

栅格图层中每个栅格包含如下信息：

1）所属图层号：基础图层为0号，派生图层号为其父级图层号加1。

2）所属图层的栅格坐标：以图层左下角为（0, 0）坐标，向上为X正，向右为Y正。

3）栅格的可通行性类型：分为障碍、自由、不通行等3种形式。

栅格可通行性类型（下称“栅格类型”）含义如下：

1）障碍类型：用O表示，该栅格因处于障碍区域而不可通行。

2）自由类型：用F表示，该栅格完全处于可通行区域，可自由通行。

3）不通行：用N表示，该栅格因局部处于障碍区域或人为设定为禁行区等，在路径规划时作不通行考虑。

下面对基于电子海图的广域环境基础图层和派生图层的离线构建方法进行说明。

1.1 基础图层构建

由于各图层间具有分辨率减半的特性，为保证图层的逐级派生过程不损失精度及能够降低计算复杂度，规定基础图层宽度、高度方向的栅格数应满足如下公式：

$\left\{ {\begin{array}{*{20}{c}} {{W_g} = CEIL\left(\displaystyle\frac{W}{{{2^{(M - 1)}}{R_0}}}\right){2^{(M - 1)}}} ，\\ {{H_g} = CEIL\left(\displaystyle\frac{H}{{{2^{(M - 1)}}{R_0}}}\right){2^{(M - 1)}}}。\end{array}} \right.$

(1)

式中：${R}_{0}$为基础图层的分辨率，m；$M$为划分的图层总级数，$M > 0$；$W$、$H$分别为输入的目标区域电子海图的宽度、高度，m；$CEIL$为向上取整操作；${W}_{g}$、${H}_{g}$分别为基础图层宽度、高度方向的栅格数。

由上式处理后，基础图层的表达范围可能会超出输入的目标区域范围，超出部分对应的栅格应填充为障碍，避免后续规划时进入。

符合S57标准的电子海图数据结构复杂，对陆地、岛屿、灯塔、浮标等众多类型的环境信息进行了规范描述。基于符合S57标准的电子海图数据构建基础图层流程：

步骤1　提取目标区域电子海图中不可通行的点、线、面类元素，转换到基础图层坐标系下；

步骤2　将上述不可通行元素在基础图层中覆盖填充为“障碍”类型，其余未被覆盖的栅格填充为“自由”；

步骤3　按照安全距离约束对基础图层进行“膨胀”处理，即将图层的障碍及不可通行区域膨胀加大，为路径规划保留安全余量；

步骤4　基础图层构建完成。

1.2 派生图层生成

派生图层由基础图层逐级派生而来，其宽度、高度方向的栅格数均为上级图层的一半。因此，对于图层$m$，其分辨率${R}_{m}$为：

$R_m=2^mR_0,m\in[0,M-1]。$

(2)

为便于后续的描述，关于派生图层和父级图层之间的邻接关系，定义如下概念：

1）父级4邻域：当前层栅格对应的父级图层中的2×2栅格。对于当前层栅格$(i,j)$，其父级4邻域对应于父级图层的$(2i, 2j)$、$(2i, 2j+1)$、$(2i+1, 2j+1)$、$(2i+1, 2j)$等栅格；

2）父级12邻域：当前栅格的父级4邻域的最多12个邻接栅格（不考虑处于图层界外的邻接栅格），如图1所示。

3）父级16邻域：当前栅格的父级4邻域和父级12邻域的总和；

4）子级1邻域：与当前图层的2×2栅格对应的派生层栅格，对于当前层栅格$(2i, 2j)$、$(2i, 2j+1)$、$(2i+ 1, 2j+1)$、$(2i+1, 2j)$，其子级1邻域为派生层的栅格$(i,j)$。

在图层派生过程中判定新派生出的栅格类型时，遵循如下规则：

规则1　若父级4邻域类型均为O，则当前栅格类型为O。

规则2　若父级4邻域类型不一致或全为N，则当前栅格类型为N。

图2和图3中，X表示可为O、F、N中的任意一种类型，“～”表示“非”，图示各类型栅格位置仅为示意，不做约束。

规则3　若当前栅格的父级4邻域类型均为F，则应根据其父级12邻域进行判定，若父级12邻域类型均为F，则当前栅格类型为F，否则为N（若处于图层边界，则不计界外栅格）。

图4中，X表示可为O、F、N中的任意一种类型，“～”表示“非”，图示各类型栅格位置仅为示意，不做约束。

规则4　若当前栅格类型为F，则其父级4邻域栅格类型应修改为N（在完成派生图层全部栅格类型判定后该条规则生效）。

根据以上规则，确定派生图层各栅格类型的算法。基于父级图层（father）构造派生图层（layer）初始结构（步骤1），遍历派生层的每个栅格，根据其父级邻域情况判定其栅格类型（步骤4～步骤5，基于规则1、规则2、规则3），直到完成一轮派生图层栅格类型判定（步骤2～步骤7）。最后，基于规则4，再次遍历派生层栅格，将其中F型栅格对应的父级4邻域栅格类型修改为N。

图5是采用广域环境建模方法构建多层栅格图层的示意，图中黑色框表示栅格类型为O，白色框表示栅格类型为F，灰色框表示栅格类型为N。图5(a)是基础图层，图5(b)和图5(c)分别是基于基础图层派生的一级和二级图层；图5(d)是将各图层的O和F型栅格叠加后的效果，便于直观感受搜索的过程。

2 路径规划算法实现 2.1 A*基本介绍

A*算法是一种常用的基于代价的寻找最优路径的启发式规划方法，通过保持代价函数$f\left(n\right)$最小进行寻优搜索。

$f\left( n \right) = g\left( n \right) + h\left( n \right)。$

(3)

式中：$g\left(n\right)$为从起点$s$到节点$n$的当前最优路径的实际代价；$h\left(n\right)$为从节点$P$到目标$T$的估算代价，是A*算法“启发”的核心。

由于本方案是在不同分辨率的栅格图层间穿插规划，因此采用欧式距离反映$h\left(n\right)$：

$h(n) = k\sqrt {{{\left( {{N_{x0}} - {T_{x0}}} \right)}^2} + {{\left( {{N_{y0}} - {T_{y0}}} \right)}^2}} 。$

(4)

式中：$k$为加权系数，用于调整$h\left(n\right)$在$f\left(n\right)$的权重；$({N}_{x0}，{N}_{y0})$为当前节点$N$从所属图层转换到基础图层的栅格坐标；$({T}_{x0},{T}_{y0})$为搜索目标$T$转换到基础图层的栅格坐标。

将m层栅格坐标${N}_{m}=({N}_{xm},{N}_{ym})$转换到基础图层的方法如下：

$N\mathit{_{{m}}}\to N_0=\left(2^m(N_{xm}+\frac{1}{2}),2^m(N_{ym}+\frac{1}{2})\right)\begin{array}{*{20}{c}},\end{array}m > 0。$

(5)

式中：${N}_{0}$为坐标${N}_{m}$转换到基础图层的坐标号。

2.2 跨图层节点拓展

传统的基于栅格地图的A*算法在进行邻域节点拓展时，通常为4邻域或8邻域的同分辨率拓展，这主要是受仅有一层栅格图的约束。本方案由于采用了多层栅格图表达环境，因此A*算法进行改进（变尺度A*算法，vs-A*），使其能够支持在不同分辨率的相邻图层间执行相邻节点拓展，即节点的拓展过程包括同级拓展、父级拓展和子级拓展，这是变尺度规划的核心。

如图6所示，同级拓展就是常规的8邻域拓展。

如图7所示，父级拓展就是向当前栅格（上图中心的大栅格）的父级12邻域拓展。

如图8所示，子级拓展就是将当前栅格（上图中心4个栅格之一）转换到派生图层的对应栅格，并对其执行派生层的同级拓展。

在进行同级拓展、父级拓展和子级拓展过程中，仅拓展类型为F的邻域栅格。

根据图层派生规则，若图层m的栅格$({N}_{xm},{N}_{ym})$的类型为F，则该栅格具有如下特性：

1）按派生顺序逐级穿透到基础图层，其所覆盖的所有栅格类型均为N；

2）覆盖其的所有派生图层的对应栅格类型均为N；

3）任意2个边界相接的F型栅格，其所属图层必相同或相邻。

3 仿真实验 3.1 实验方案

为了说明设计的广域变尺度路径规划方法的有效性，采用C++语言设计开发了仿真软件，并选择香港大屿山区域的电子海图数据进行仿真验证。

根据香港大屿山区域的矢量电子海图数据，采用本文广域环境建模方法离线构建了多层栅格地图，为路径规划实验提供地图输入。

图9是基于矢量电子海图数据构建生成的香港大屿山区域广域环境模型的基础图层，图中每个像素点代表一个栅格，白色为自由类型栅格，灰色为障碍类型栅格，其详细信息如表1所示。

3.2 结果分析

取规划起点坐标为（113.882505 E, 22.275469 N），终点坐标为（114.022122 E, 22.300036 N）。分别采用传统A*算法在基础图层和本方案的变尺度A*算法在2层、4层、6层图层时进行规划。

图10中黑色点折线是规划路径经过的栅格点。从图中可以看出，相对于传统A*算法，本文的变尺度A*算法规划结果的点在狭窄水域相对密集连续，在开阔水域间距明显变大，这是由于变尺度A*算法在狭窄水域或靠近障碍区域时优先从高分辨率图层规划，保证规划精度，在开阔水域优先从低分辨率图层规划，加快规划速度。该结果说明所设计的广域环境模型和变尺度规划方案可行。

表2列出了传统A*算法与本文变尺度A*算法规划的结果对比。可知，相对于传统的A*规划方案，采用本文的变尺度A*规划方案能够在规划总航程无明显增加的前提下，显著减少搜索过程拓展的节点数，提升路径规划速度。但随着生成图层数的增加，性能提升的显著性将明显下降。

综上所述，本文方法能够在已知的电子海图区域范围内，快速规划出任意可通行的两点之间的全局安全航线，并具有如下特点：

1）在障碍附近能够选择较小尺度栅格，以保持较高的规划分辨率，有利于通过狭窄水道；

2）在空旷区域能够选择较大尺度栅格，以加大规划搜索步距，提升规划速度；

3）相对于传统A*算法，本文方法能够在规划总航程减小的同时，使路径与障碍保持一定的距离。

4 结　语

本文针对海洋智能无人艇的全局路径规划问题，基于矢量电子海图信息，构建起满足规则约束的变分辨率的多图层、栅格化的广域环境模型，对传统A*算法的搜索过程进行改进，支持在相邻图层间进行搜索拓展，进而实现在不同分辨率的图层间的穿插规划，形成变尺度A*算法。通过软件仿真实验，验证了所设计的方法的可行性和有效性，具有一定的参考和实际应用价值。