随着内河航道尺度的不断提升以及内河电子航道图系统的全面推广应用，航道测量的需求持续增长、要求不断提高。传统大型航道测量船搭载工作人员进行航道测量的方式效率较低，且对测量水深有一定的限制，较难满足物联网、大数据时代对航道测量的需求。因此，无人航道测量船技术应运而生。无人航道测量船是集移动测量技术、高精度定姿定位技术、测深仪流速仪集成技术、无人遥控和自动控制的外业作业技术等于一体的航道要素信息采集移动测量设备^[1-3]。无人航道测量船不仅节约了大量的人力、物力和财力，还扩大了测量的范围，保证了工作人员的安全, 促进了智能航运系统的发展^[4-5]。为使无人航道测量船的测量数据更加准确，在无人航道测量船完成避碰的基础上，有必要使规划的避碰路线更接近预设测量航线^[6]。

目前比较常用的路径规划算法主要有A*算法^[7-8]、Dijkstra算法^[9]、人工势场法^[10]、模拟退火(simulated annealing, SA)算法^[11]、遗传算法(genetic algorithm, GA)^[12]、蚁群算法(ant colony algorithm, ACA)^[13]等。针对无人船路径规划问题，刘琨等^[14]提出了一种改进的人工势场法，并应用到无人船的路径规划中，其主要改进是用指数函数代替二次函数以降低势场强度的变化幅度，并通过增加位置因子解决目标不可达的问题。陈佳^[15]将Dijkstra算法和蚁群算法相结合并应用到无人驾驶救助船路径规划中。首先通过Dijkstra算法寻找一条从起始点到终点的最短路径，然后利用改进的蚁群算法对找到的路径进行优化，使得到的路径更符合实际。卢艳爽^[16]采用A*算法与海事规则速度避障法相结合的方法为水面无人艇进行路径规划。首先通过A*算法找到全局路径点，然后通过速度避障法不断地调整无人艇的行驶路径，最后通过仿真验证了提出的方法的可行性和有效性。Zhu^[17]为了解决海上无人艇在内河复杂环境下的全局路径规划问题，提出了一种基于自适应网格处理的A*算法。该算法首先建立基于电子江图的环境模型，然后提出了使环境模型适应该算法的网格处理和自适应网格处理方法，最后通过仿真证明了改进算法的有效性。Praczyk等^[18]提出了利用遗传算法代替路径固定系统为无人船智能规划路径的方法，该方法可以在无人船和通信中心通信出现问题时为无人船实时规划路径。

上述研究都是无人船的路径规划以及对传统路径规划算法的改进，较少考虑船舶在避开障碍物之后需要回到预设航线的需求。针对该问题，本文提出了一种改进的A*算法，该算法在传统A*算法的基础上增加了一个代价值，并针对船舶的不同位置采用不同的估价函数，使得无人航道测量船在避开障碍物之后能够尽快回到预设测量航线；并通过仿真对比实验和实际数据验证了该算法的有效性和可行性。需要说明的是，考虑到实际情况下，若障碍物大小与航道测量测深线间距之比小于1/3，则本文提出的改进A*算法讨论的实际意义不大，因此，本文设定的前提条件是障碍物大小与航道测深线间距之比在1/3~2/3之间。

1 A*算法的改进 1.1 传统A*算法

A*算法是一种典型的启发式搜索算法，启发式搜索在一定程度上避免了无效的搜索路径，提高了搜索效率。广泛应用的启发式搜索算法包括深度优先、广度优先和最佳优先3种。A*算法是一种最佳优先的启发式搜索算法。

A*算法在某一节点的估价函数可以表示为：

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

(1)

式中，$f\left(n \right)$是节点n从初始点到目标点的估价函数；$g\left(n \right)$是在状态空间中从初始节点到n节点的实际代价；$h\left(n \right)$是从n节点到目标节点最佳路径的估计代价。

式（1）中，g(n)在f(n)中的比重越大，搜索越倾向于横向趋势；若$g\left(n \right) = 0$，则只希望找到目标节点而不考虑会付出的代价。$h\left(n \right)$是节点n到目标节点的最佳路径的实际代价${h^{\rm{*}}}\left(n \right)$的估算值($h\left(n \right) \ge {h^{\rm{*}}}\left(n \right)$)。$h\left(n \right)$在$f\left(n \right)$中的比重越大，越强调启发因素对搜索效率的影响，搜索越倾向于纵向趋势；$h\left(n \right)$比重越小，则越突出横向搜索的特性；当$h\left(n \right) = 0$时，则为广度优先搜索。

1.2 改进A*算法的提出

采用传统A*算法为无人航道测量船规划路径时，当船舶避开障碍物之后，由于缺乏对路径偏差的代价约束，A*算法规划的路径偏离预设测量航线的距离较远，不符合航道测量需求。为了使无人航道测量船在避开障碍物之后能够迅速回到预设测量航线，需要对A*算法的估价函数进行修改。根据式（1）可知，若需要在避开障碍物之后回到预设航线，则在避开障碍物之后，每个点的当前估价函数值需要在靠近预设航线方向达到最小，因此有必要在原始估价函数的基础上增加一个新的代价值，使无人航道测量船在靠近终点的同时也不断地靠近预设航线。

改进之后的A*算法的估价函数为：

$\begin{array}{l} \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;f\left( n \right) = \\ \left\{ {\begin{array}{*{20}{l}} {g\left( n \right) + h\left( n \right), {\rm{\;}}离开障碍物区域未回到预设航线}\\ {g\left( n \right) + h\left( n \right) + t\left( n \right), {\rm{\;}}其他情况} \end{array}} \right. \end{array}$

(2)

式中，$t\left(n \right)$是新增加的代价值。

分段函数取值与无人航道测量船是否需要回归到预设航线工作状态相对应。当无人航道测量船没有进入障碍物区域或者处于障碍物区域时，算法的估价函数$f\left(n \right)$取式（2）中的$g\left(n \right) + h\left(n \right)$，也就是原始A*算法对应的值；当无人航道测量船离开障碍物区域时，算法的估价函数$f\left(n \right)$取式（2）中的$g\left(n \right) + h\left(n \right) + t\left(n \right)$；当无人航道测量船跟踪上预设航线之后，算法的估价函数$f\left(n \right)$重新取$g\left(n \right) + h\left(n \right)$，也就是回归到原始A*算法。

1.3 改进A*算法代价值的选取

由以上分析可知，改进A*算法能否满足要求取决于代价值t(n)。无人航道测量船在离开障碍物区域之后，需要在靠近终点的同时不断靠近预设航线。因此，在无人航道测量船到达预设航线之前，t(n)的值应该和h(n)的值在一个数量级上，但是为了使无人航道测量船尽快回到预设航线上，t(n)的值对整个估价函数的影响程度应大于h(n)，即t(n)的值应该大于h(n)。当无人航道测量船逐步靠近预设航线时，t(n)值应逐渐减小。因此，t(n)的取值为：

$t\left( n \right) = \frac{{2d - l}}{d}h\left( n \right)$

(3)

式中，d是当前位置点到预设航线的垂直距离；l是栅格地图的每格的长度。式（3）示意图如图 1所示。

假设起点坐标为$\left({{x_0}, {y_0}} \right)$，终点坐标为$\left({{x_1}, {y_1}} \right)$，起点、终点连线的方程为：

$y - {y_0} = \frac{{{y_1} - {y_0}}}{{{x_1} - {x_0}}}\left( {x - {x_0}} \right)$

(4)

式（4）展开后可得：

$\frac{{{y_1} - {y_0}}}{{{x_1} - {x_0}}}x - y + {y_0} - \frac{{{y_1} - {y_0}}}{{{x_1} - {x_0}}}{x_0} = 0$

(5)

令$a = \frac{{{y_1} - {y_0}}}{{{x_1} - {x_0}}}$，$b = - 1$，$c = {y_0} - \frac{{{y_1} - {y_0}}}{{{x_1} - {x_0}}}{x_0}$，假设当前位置点的坐标为$\left({{x_n}, {y_n}} \right)$，则$d$的取值公式为：

$d = \frac{{\left| {a{x_n} + b{y_n} + c} \right|}}{{\sqrt {{a^2} + {b^2}} }}$

(6)

因此，改进后的A*算法估价函数$f\left(n \right)$可表示如下：

$f\left( n \right) = \left\{ {\begin{array}{*{20}{l}} {g\left( n \right) + \frac{{3d - l}}{d}h\left( n \right), {\rm{\;}}离开障碍物区域未回到预设航线}\\ {g\left( n \right) + h\left( n \right), {\rm{\;}}其他情况} \end{array}} \right.$

(7)

1.4 改进A*算法的实现

在路径规划过程中，需为无人航道测量船和检测到的障碍物分别设置一个安全范围。安全范围大小可根据实际情况具体设置。当无人航道测量船航行到某个节点时，如果发现其安全范围与障碍物安全范围有重叠，就可以认为无人航道测量船的当前节点安全范围内存在障碍物，否则没有。障碍物和无人船安全范围说明如图 2所示。

改进A*算法实现步骤如下：

1）判断起点安全范围内是否存在障碍物，若不存在，转步骤2），否则转步骤3）。

2）运用传统A*算法计算得到无人航道测量船的下一路径节点，判断该节点是否是终点，若是，则转到步骤5）；若不是，则判断该节点的安全范围内是否存在障碍物，若不存在，继续步骤2），否则，转步骤3）。

3）运用传统A*算法计算得到无人航道测量船下一路径节点，判断该节点是否是终点，若是，则转到步骤5）；若不是，则判断该节点的安全范围内是否存在障碍物，若存在，继续步骤3），否则，转步骤4）。

4）运用改进A*算法计算得到无人航道测量船下一路径节点，判断该节点是否是终点，若是，则转到步骤5）；若不是，则判断该节点是否处于预设航线之上，若是，转步骤2），否则继续步骤4）。

5）停止寻找路径节点，并将上述步骤找到的节点按照顺序连接，即为改进A*算法规划得到的路径。

2 改进A*算法仿真实验

为了验证改进A*算法的有效性，在仿真实验中利用MATLAB工具分别将改进A*算法与原始A*算法、原始人工势场法进行对比。

2.1 仿真地图构建

首先在MATLAB中构建一个大小为32×32的栅格地图，并设定左下角(0, 0)为原点坐标。地图中的边缘和障碍物设置为不可通行区域，其他区域设为可通行。

2.2 仿真实验过程

确定单个障碍物和多个障碍物两种情况，并分别设置两种仿真场景：场景1：起点坐标（15, 2），终点坐标（15, 31）；场景2：起点坐标（2, 2），终点坐标（31, 31）。

分别利用传统A*算法、原始人工势场法和改进A*算法得到避障规划路径。将3种方法生成的避障路径结合预设航线进行对比分析。图 3、图 4分别为单个障碍物和多个障碍物两种场景下得到的路径规划对比图。

图 3、图 4中，S₁、S₂、S₃分别代表传统A*算法、原始人工势场法和改进A*算法规划的路径曲线与预设航线构成的多边形面积。

2.3 仿真结果分析

当给定起始点与终点后，若两点之间不存在任何影响船舶航行的障碍物，那么此时预设航线应是两点之间的直线段。因此，本文规定的4种仿真情况中（单个障碍物两种仿真和多个障碍物两种仿真），预设航线即为起始点-终点的直线段。为了直观地对比算法改进前后的效果，引入参数S。S表示算法规划的路径曲线与预设航线构成的多边形的面积。求取公式为：

$S = \mathop {\mathop \sum \limits_{k = 1} }\limits^\infty {S_{o{p_k}{p_{k + 1}}}} = \frac{1}{2}\mathop {\mathop \sum \limits_{k = 1} }\limits^\infty \left( {{x_k}{y_{k + 1}} - {x_{k + 1}}{y_k}} \right)$

(8)

式中，S表示多边形的面积；k表示多边形顶点的顺序；S_△opkpk+1表示第k个三角形的面积；o表示选取的第1个顶点；${p_k}$表示第k个顶点；$\left({{x_k}, {y_k}} \right)$表示多边形第k个顶点的坐标。S值越小，说明规划的路径越靠近预设航线。

从图 3、图 4可以看到，单个障碍物和多个障碍物情况下的4种场景中，传统A*算法和原始人工势场法规划的路径在绕开障碍物之后虽然也能到达终点，但是绕开障碍物之后的路径与原始规划路径差距较大。通过引入的S₁、S₂、S₃值对比可知，相较于传统A*算法和原始人工势场法的路径，改进A*算法规划的路径在绕开障碍物之后更靠近原始预设航线。

根据仿真结果分析可知，改进后的A*算法对无人航道测量船的功能需求有比较明显的提升。

3 水池环境测量船路径规划实验 3.1 实验环境

实验水池长80 m，宽60 m，水面平静而开阔，可进行无人航道测量船平台的航行、导航及路径规划实验。

3.2 实验过程和结果分析

该平台的实验都是基于平面坐标系操作的，采用全球定位系统(Global Positioning System，GPS)定位，需要将GPS输出的经纬度坐标采用高斯-克吕格投影法实时转换成平面坐标。

实验时，首先确定无人航道测量船的起点和终点，在起点-终点的连线上设置障碍物，即放置浮球，并将测量船平台放置在起点，然后在软件控制界面点击相关按钮，路径规划子系统即可分别采用改进前后的A*算法为无人航道测量船规划路径。在船舶航行时，可以通过软件界面的地图远程实时观察算法规划的路径。通过无人航道测量船平台实验得到的A*算法改进前后的路径规划图如图 5所示。图 5中，设置水尺两条长边的中点分别为起始点，在水尺正中央放置障碍物，即中心点，虚线即为无人航道测量船的预设航线，实线为A*算法改进前后规划的实际路径，圆圈即为障碍物的安全范围。

从图 5可知，改进前后的A*算法都能为无人航道测量船规划一条避开障碍物并到达终点的安全航线，但是改进A*算法得到的规划航线比传统A*算法得到的规划航线更靠近预设航线，更符合无人航道测量船的功能需求。

3.3 地理围栏分析

地理围栏是基于移动位置服务的一种新应用，即用一个虚拟的栅栏围出一个虚拟地理边界^[19]。当进入、离开某个特定地理区域，或在该区域内活动时，设备可以自动接收通知和警告。虽然无人航道测量船测量数据的准确度是非常重要的指标，但是航行安全依然是无人航道测量船的首要前提。为了验证改进A*算法的安全性，本文采用地理围栏技术对实验数据进行分析。

要实现地理围栏功能，首先需要设置一个围栏，包括围栏的中心位置、围栏半径等参数。为了使分析更直观，将GPS得到的经纬度坐标通过高斯-克吕格投影法转换成平面坐标。如图 6所示，假设无人船的中心位置为$\left({{x_1}, {y_1}} \right)$，障碍物的中心位置为$\left({{x_2}, {y_2}} \right)$, 围栏半径为r（r大于障碍物的半径和无人航道测量船的半径之和），船体中心与障碍物中心的距离为R。当R < r时，可知无人船进入了障碍物的围栏之内，这时就会触发报警机制，提醒后台管理人员可能会有危险，并且可以通过R的增大与减小来判断无人船是接近障碍物的围栏还是远离障碍物的围栏, 从而及时地发出预警。

实验中，考虑到障碍物大小、无人航道测量船大小、控制和定位误差等因素，设定障碍物围栏半径为6 m（障碍物直径小于1 m，船长3 m）。本文所述的原点坐标为（20 246 250，3 390 620）m，因此平面坐标值均是相对于该原点坐标。在实际场景中，分别采用改进前后的A*算法进行无人航道测量船避障实验，得到的围栏分析图如图 7所示。

为了方便画图，图 7中纵坐标是实际的横坐标值，横坐标是实际的纵坐标值。从图 7可以看出，算法改进前后的航行路径均没有进入障碍物的围栏范围，即算法改进前后的航行路径都是安全的，但算法改进后的路径更靠近原始规划的航线，因此本文提出的改进A*算法可以让无人航道测量船更靠近规划航线，同样也能保证无人航道测量船的安全。

4 结语

本文针对传统A*算法规划的路径在避开障碍物之后无法快速回到预设航线上的问题，提出了在原始代价函数中增加一个代价值的改进A*算法。为了验证改进算法的有效性，对改进前后的A*算法分别进行MATLAB仿真对比实验和实测船平台对比实验。实验结果均表明，改进后的A*算法规划的路径在避开障碍物之后能够更快地回到预设航线上，比传统A*算法更加有效；通过地理围栏分析可以看到，改进后的算法在无人航道测量船更靠近原始规划航线的基础上也能保证船舶的安全。因此，改进后的A*算法能在一定程度上减小无人航道测量船由于主动避障造成的航线偏移误差，保证航道测量数据的有效性，同时也保证船舶的航行安全。

本文提出的改进A*算法只考虑了静态障碍物，并不适用于动态障碍物环境。下一步可考虑采用改进A*算法与人工势场法结合的方法来实现无人航道测量船的动态避障。