0 引　言

近几年，随着人工智能技术的快速发展，智能船舶已成为当前全球航运领域研究的热点问题之一^[1]。船舶自主避碰技术是智能船舶的关键技术之一。

一些学者对此进行了深入研究，将各种算法与船舶避碰相结合^[2]。从算法分类来看，主要可分为智能优化算法、数理模型方法与人工智能算法^[3]。智能优化算法包括遗传算法、粒子群算法和蚁群算法等。宁军等^[4]为解决粒子群算法易陷入局部最优的问题，引入了高斯位置变异的概念，并通过模糊综合评价策略对船舶碰撞危险度进行多目标优化，实现了多船避碰。曾勇等^[5]提出将粒子群算法和遗传算法结合应用到多船避碰中，提高了算法的收敛精度和寻优速度，有效降低船舶碰撞风险。黄国良等^[6]提出一种改进的蚁群算法用于解决船舶的路径规划问题，通过设计伪随机状态转移规则并引入势场函数提高算法的迭代效率，以路径长度和安全为导向对搜索方向进行约束，提高了路径规划的质量。基于数理模型方法主要有速度障碍法（Velocity Obstacle，VO）与人工势场法（Artificial Potential Field，APF）。瞿栋等^[7]提出一种基于不确定性条件下的VO算法。该算法采用自适应阈值的最近会遇点法进行碰撞风险评估，并基于《避碰规则》建立边界缓冲区，从宏观和微观2个层面提升避碰过程的稳定性。李永正等^[8]为解决传统APF算法易陷入局部极值点问题，提出将模拟退火算法加入APF算法当中，并对船舶避碰决策的有效性进行验证。人工智能算法包括了强化学习和博弈论等，Shen等^[9]针对受限水域的船舶避碰问题，提出一种结合船舶特性、航行经验和《避碰规则》的深度强化学习模型，并通过数值模拟对3船避碰进行验证。崔浩等^[10]针对智能船与非智能船混合航行下的交互避碰问题，提出一种多智能体交互的动态博弈避碰决策方法。该方法以船舶安全和经济效益为导向，航向为博弈策略，求得船舶的最优行动序列。

综上所述，智能优化算法在解决船舶避碰时考虑因素较为全面，但大部分优化算法需要进行大量迭代，不仅耗时且计算量较大。人工智能算法虽然拓展性强，但过度依赖于数据库的优劣程度，且算法不确定性较高。而基于数理模型的方法不仅响应速度快，且在相同的输入条件下，给出的解确定，具有较大潜力。因此，本文拟采用改进的A*算法对静态障碍物进行路径规划，针对动态障碍物运动的不确定性，提出将速度障碍法与动态窗口法进行融合，实现船舶在动静态障碍物下的智能避碰。

1 基于A*算法的静态路径规划 1.1 A*算法原理

A*算法是一种启发式搜索算法，由Stanford研究院于1968年提出。其高效、快速的搜索速度以及优秀的拓展性和适应性使其在路径寻优问题中得到广泛应用。A*算法通过评价每一节点的综合函数来判断该节点是否被采纳，其一般形式为：

$ f(n) = g(n) + h(n) 。$

(1)

式中：$ f\left(n\right) $为当前节点$ n $的综合评价函数；$ g\left(n\right) $为实际代价函数，代表由起始节点到当前节点$ n $之间的代价总和；$ h\left(n\right) $为当前节点$ n $到目标节点的启发函数，其选取方式的不同对算法的性能有重要影响。常见的启发函数表达式有曼哈顿距离、欧几里得距离、切比雪夫距离以及对角线距离，它们在地图上的表达形式如图1所示。

本文采取的是欧几里得距离作为启发函数的值，其一般表达式为：

$ {D_{}} = \sqrt {{{({x_1} - {x_2})}^2} + {{({y_1} - {y_2})}^2}} 。$

(2)

式中：$ ({x}_{1},{y}_{1}) $、$ ({x}_{2},{y}_{2}) $分别为两点的横纵坐标值。A*算法是通过距离长短来判断路径是否最优，忽略了路径中转折次数过多、紧靠障碍物等情况，而这些因素对于船舶航行效率及安全有重大影响。因此，使用A*算法进行船舶路径规划时，必须考虑船舶航行的特点，解决该算法存在的不足。

1.2 A*算法的改进

为解决A*算法存在的冗余节点与转折角过多等问题，本文对栅格地图中的障碍物进行定量化描述，引入栅格障碍物占比来调节启发函数，实现算法在不同时期自适应调节搜索效率。针对搜索路径紧靠障碍物，本文通过添加障碍物安全距离，避免最优路径斜穿障碍物顶点的情况。最后通过3次折线优化对最优路径进行优化，使路径更加平滑，符合船舶航行的特点。

1）启发函数优化

A*算法的效率依赖于所选用的启发函数。如果启发函数选择不当，会导致搜索过程朝着错误的方向前进，影响算法的性能。希望算法应根据地图障碍物密度自适应调整启发函数，障碍物少时快速向目标移动，障碍物多时扩大搜索范围，以避免局部最优。启发函数也应考虑节点位置，初期当前节点与起始点距离近时应快速靠近目标。综合上述情况，本文提出的自适应启发函数表达式为：

$ h(n)=(1+\frac{l}{L})\cdot(1-\ln P)\cdot D。$

(3)

式中：$ l $为当前节点到目标节点的距离；$ L $为起始节点到目标节点的距离；$ P $为栅格障碍率，其值为起点和终点围成的矩形区域的障碍物占比；$ D $为欧几里得距离。

2）障碍物安全距离

A*算法在搜索时容易忽略算法的安全性。在栅格地图中，路径是通过连接栅格中心点形成的，可能存在父、子节点的连线斜穿障碍物顶点的情况。为保证船舶航行安全，需确保船舶与障碍物间存在一定安全距离。因此，本文引入了安全距离参数，优化子节点的选取方式。在子节点的选取上，只需判断障碍物顶点到父、子节点所在直线的垂直距离是否大于安全距离。如果大于，说明该子节点符合要求，否则，重新选取子节点。最后，所有符合要求的子节点再选取代价最小的节点作为下一次搜索的父节点。优化后的子节点选取方式如图2所示。

3）3次折线优化

上述的改进方法对于算法的搜索效率以及安全性有所提升，但是规划的路径依旧存在许多不必要的拐点，这会导致船舶在航行中频繁转向。本文采用3次折线优化方法对搜索路径进行平滑处理。

第一次折线优化：

步骤1　将规划的路径节点集合$ Rout{e}_{\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{t}} $取出进行遍历。

步骤2　判断当前节点、下个节点和下下节点是否共线。

步骤3　如果共线，则去除中间节点。否则，判断当前节点与下下节点的连线是否穿过障碍物。若障碍物栅格中心点与该直线的距离大于安全距离，则舍去中间节点，否则，把下个节点作为新的当前节点。

步骤4　重复步骤2、步骤3，一直遍历到目标节点为止，输出新的节点路径$ Rout{e}_{\mathrm{o}\mathrm{n}\mathrm{e}} $。

第二次折线优化：

步骤1　创建一个路径节点$ {Route}_{\mathrm{t}\mathrm{w}\mathrm{o}} $，并将初始节点放入其中，遍历第一次折线优化后的路径$ Rout{e}_{\mathrm{o}\mathrm{n}\mathrm{e}} $。

步骤2　将$ Rout{e}_{\mathrm{o}\mathrm{n}\mathrm{e}} $中下一节点和下下节点所连线段按照长度$ l $进行等长度均分，并将均分后的节点存储新的集合$ Rout{e}_{\mathrm{s}} $。集合$ Rout{e}_{\mathrm{s}} $中的节点可分为3种情况：第一种是2个节点连线为垂直线段，则$ Rout{e}_{\mathrm{s}} $中节点横坐标不变，纵坐标依次递增或递减$ l $。第二种是2个节点连线段为水平线段，则$ Rout{e}_{\mathrm{s}} $中节点纵坐标不变，横坐标依次递增或递减$ l $。第三种是2个节点连线段为斜线段，根据两节点的坐标求出斜线段表达式$ y=kx+b $，再通过横坐标递增或递减求出纵坐标。

步骤3　依次遍历$ Rout{e}_{\mathrm{s}} $中的等长子节点，将每个子节点与当前节点连接，判断其连线是否穿过障碍物，如果穿过，则舍弃该子节点判断下一个子节点，反之，则将该子节点存入临时节点集合$ Rout{e}_{\mathrm{t}} $并覆盖原先的临时节点。

步骤4　重复步骤3直至$ Rout{e}_{\mathrm{s}} $中的节点全部遍历完成，最后将临时节点集合$ Rout{e}_{\mathrm{t}} $中的节点存入$ {Route}_{\mathrm{t}\mathrm{w}\mathrm{o}} $中。

步骤5　重复步骤2至步骤3，直到遍历到目标节点。得到最终的节点集合$ {Route}_{\mathrm{t}\mathrm{w}\mathrm{o}} $。

第三次折线优化：将路径集合$ {Route}_{\mathrm{t}\mathrm{w}\mathrm{o}} $中的节点反向排列，并对反向排列的集合进行第二次折线优化，最终得到了3次折线优化后的节点集合$ {Route}_{\mathrm{t}\mathrm{h}\mathrm{r}\mathrm{e}\mathrm{e}} $。

4）双向A*算法

使用栅格法对航行环境建模时，地图规模对精度至关重要。较小规模可能无法准确展现真实环境，遗漏关键信息；而较大规模虽可以提高精度，但会降低算法收敛速度。为解决大规模栅格地图下使用A*算法时效率低下的问题，提出利用双向A*算法代替单向A*算法的方案。

1.3 改进后A*算法仿真实验及结果分析

改进后的A*算法主要步骤有栅格地图建模、调整启发函数，子节点选择优化及3次折线优化。改进A*算法的船舶路径规划流程如图3所示。

1）本文算法与其他算法之间的对比

本节将文献[11]-[12]算法，传统A*算法和改进后的A*算法进行对比，通过实验结果验证各种算法的效果。4种算法迭代后的路径规划结果如图4所示，相关的数据指标如表1所示。

分析可知，本文提出的改进A*算法的搜索路径，不仅不存在不安全点，算法的运行效率也是最高，且在3次折线的优化下，转折的次数也是最少的，尽管搜索出的路径并不是最短路径，但是保障了船舶航行安全。

2 改进速度障碍法的船舶避碰研究 2.1 速度障碍法原理

速度障碍法作为一种常见的避障算法，常被用于解决机器人动态避障等问题。该方法的原理是通过分析物体和障碍物之间的速度和位置关系，确定物体可安全运动的速度空间范围。速度障碍法的原理如图5所示，假设$ A $为本船，$ B $为目标船，$ {P}_{A}\mathrm{、}{P}_{B} $分别为本船和目标船的位置，$ {\mathit{V}}_{A}\mathrm{、}{\mathit{V}}_{B} $分别为本船与目标船的速度矢量。

两船会遇时，假设目标船不动，将速度用矢量相加的方式全部给到本船，则船$ A $相对于船$ B $的相对速度$ {\mathit{V}}_{BA} $的计算公式为：

$ {{\boldsymbol{V}}_{BA}} = {{\boldsymbol{V}}_A} - {{\boldsymbol{V}}_B} 。$

(4)

同时，本船与目标船的船舶领域全部叠加到目标船，形成以目标船为圆心的碰撞危险区，其半径大小由2个圆形半径相加，即为$ {R}_{O} $。假设本船在某一时刻相对目标船的速度已知，则在$ t $时刻后，本船可到达的位置点所在直线$ L $的表达式为：

$ L({P_A},{{\boldsymbol{V}}_{BA}}) = \{ {P_A} + {{\boldsymbol{V}}_{BA}}*t|t \geqslant 0\} 。$

(5)

式中：$ L({P}_{A},{\boldsymbol{V}}_{BA}) $为本船以相对速度$ {\boldsymbol{V}}_{BA} $航行$ t $时间所能到达的一系列点所在直线。只需判断直线$ L $与碰撞危险区$ {R}_{O} $是否有交点即可知本船与目标船是否存在碰撞危险。将所有可能导致本船与目标船发生碰撞的相对速度$ {\boldsymbol{V}}_{BA} $集合就得到了图5中的相对碰撞区$ RCC $。但在多船会遇中，使用$ RCC $计算较为复杂，而绝对碰撞区$ ACC $则更具优势。$ ACC $区域的表达形式为：

$ VO_B^A({{\boldsymbol{V}}_B}) = \{ {{\boldsymbol{V}}_A}|L({P_A},{{\boldsymbol{V}}_{BA}}) \cap B \ne \emptyset \} 。$

(6)

式中：$ B $为两船舶领域半径叠加形成的圆形区域；$ V{O}_{B}^{A}\left({\boldsymbol{V}}_{B}\right) $为船B对船A的速度障碍。存在多条目标船时，只需将每一艘目标船对本船的$ ACC $区域进行叠加，就得到本船的最终速度障碍区。如果用$ VO $代表本船的速度障碍，$ n $代表目标船的数目，则$ VO $的表达公式为：

$ VO = \sum\limits_{i = 1}^n {VO_i^A} ({{\boldsymbol{V}}_i})。$

(7)

2.2 四元船舶领域模型优化

将船舶领域看作一个圆形，这与实际的船舶领域不符。因此，本文采用四元船舶领域模型对速度障碍法进行优化。四元船舶领域模型由4个大小不一的椭圆构成，4个椭圆的轴长根据船舶当前状态进行自适应调整，如图6所示。

当知道船舶的速度和船长时，可根据四元船船舶的边界方程求出$ {R}_{f}、{R}_{a}、{R}_{s}、{R}_{p} $的值^[13]。本文中，将$ k=2 $的船舶领域模型引入速度障碍法中，如图7(a)所示。但由于不规则椭圆求取切线$ {l}_{1} $、$ {l}_{2} $较为困难，本文采用膨化方法对船舶领域进行处理。如图7(b)所示，将原本的偏心椭圆膨化成标准椭圆，从而将切线$ {l}_{1} $移至$ {l}_{1}' $的位置，再对两切线求解。

构建如图8所示的坐标系，通过将本船在目标船坐标系中的坐标与椭圆的标准方程联立，可求得目标船坐标系下2个切点的坐标，再通过坐标的平移与旋转，即得到本船坐标系下切点的坐标位置。

在本船坐标系下，本船坐标为$ \boldsymbol{O}{\boldsymbol{S}}_{O}=[\mathrm{0,0}{]}^{{\mathrm{T}}} $，假设在目标船坐标系，本船坐标为$ \boldsymbol{T}{\boldsymbol{S}}_{O'}=[m,n{]}^{{\mathrm{T}}} $，则$ \mathit{T}{\mathit{S}}_{O'} $的表达式为：

$ \boldsymbol{T}\boldsymbol{S}_{O'}=\boldsymbol{R}^{-1}(\boldsymbol{O}\boldsymbol{S}_O-\boldsymbol{\mathit{C}})。$

(8)

式中：$ \mathit{C} $为本船坐标系下目标船的位置坐标；$ \boldsymbol{R} $为本船与目标船坐标系的旋转矩阵，其表达式为

$ {\boldsymbol{R}} = \left[ {\begin{array}{*{20}{c}} {\cos \theta }&{\sin \theta } \\ { - \sin \theta }&{\cos \theta } \end{array}} \right] 。$

(9)

式中：$ \theta $为本船与目标船坐标系之间的旋转角，从而得到目标船坐标系下本船的位置。此时，可将椭圆的标准方程与切线方程联立，求得目标船坐标系中两切点的坐标，即为图8中$ {T}_{3}、{T}_{4} $两点坐标。

$ \left\{ {\begin{aligned} &{\frac{{x_T^2}}{{{a^2}}} + \frac{{y_T^2}}{{{b^2}}} = 1}，\\ &{\frac{{{x_T}m}}{{{a^2}}} + \frac{{{y_T}n}}{{{b^2}}} = 1}。\end{aligned}} \right. $

(10)

式中：$ a $为四元船舶领域中最大短轴距离；$ b $为最大长轴距离，其计算公式可参考文献[13]。得到$ {T}_{3}、{T}_{4} $两切点坐标后，再对式(8)进行逆运算，如式(11)所示，进而求出$ {T}_{1}、{T}_{2} $两点坐标。

$ \boldsymbol{O}\boldsymbol{S}_{T_1,T_2}=\boldsymbol{R}\cdot\boldsymbol{T}\boldsymbol{S}_{T_3,T_4}+\mathit{\boldsymbol{C}}。$

(11)

2.3 融合动态窗口法

理论上，速度障碍集合$ VO $以外的速度均被认为安全且可取。但实际中，受船舶自身影响，并非所有速度都可达。为充分考虑船舶自身特性对速度的影响，本文引入动态窗口法对速度空间进行进一步约束。

动态窗口法根据船舶自身的运动特性对未来$ \Delta t $时间后的船舶速度与航向进行约束。假设船舶可承受的速度范围为：

$ {V_i} = \left\{ {(v,\omega )|v \in \left[ {{v_{\min }},{v_{\max }}} \right],\omega \in \left[ {{\omega _{\min }},{\omega _{\max }}} \right]} \right\}。$

(12)

式中：$ {v}_{{\mathrm{min}}}、{\omega }_{{\mathrm{min}}} $为船舶的最小速度与最小角速度；$ {v}_{{\mathrm{max}}}、{\omega }_{{\mathrm{max}}} $为船舶的最大速度与最大角速度。在$ \Delta t $时间后，船舶可到达的速度与角速度空间为：

$\begin{split} V_j=&\{(v,w)\mid v \in\left[v_t-a_v\Delta t,v_t-a_v\Delta t\right],\\ &\omega\in\left[\omega_t-a_\omega\Delta t,\omega_t+a_\omega\Delta t\right]\}。\end{split}$

(13)

式中：$ {v}_{t}、{\omega }_{t} $分别为$ t $时刻的速度与角速度；$ {a}_{v}、{a}_{\omega } $分别为$ t $时刻最大加速度与最大角加速度。从而确定$ \Delta t $时刻后速度约束窗口为：

$ V = {V_i} \cap {V_j} 。$

(14)

进而确定$ \Delta t $时刻后，本船的航向$ {\theta }_{t+\Delta t} $的范围为：

$ {{\theta }_{t+\Delta t} = \left\{\theta |\theta \in \left[{\theta }_{t} + {\omega }_{t}\Delta t - \displaystyle\frac{1}{2}{\omega }_{t}\Delta{t}^{2},\,{\theta }_{t} + {\omega }_{t}\Delta t+\displaystyle\frac{1}{2}{\omega }_{t}\Delta{t}^{2}\right]\right\} 。}$

(15)

动态窗口法生成的速度窗口是由连续的速度$ V $和角度$ \theta $构成，不利于计算，因此选择通过添加合适的速度分辨率和角度分辨率对速度窗口进行离散化。离散化的速度窗口模型如图9(a)所示，将速度范围均分为$ m $份，航向均分为$ n $份，则速度窗口$ RV $被分为$ m\cdot n $对速度组合。同时，在图9(a)中舍去速度障碍集合$ VO $，即得到船舶最终可选的速度窗口集合$ RAV $，如图9(b)所示。

集合$ RAV $中的速度均满足下面关系：

$ RAV = \left\{ {V|V \in RV,V \notin VO} \right\}。$

(16)

为选出船舶最优避障路径，只需采用式(17)的评价函数对集合$ RAV $中的速度组合轨迹进行评价，从而确定船舶在下一时刻的避让角度及航速。

$ \begin{split}G(v,\omega)= & \alpha\cdot\frac{\mathrm{heading}(v,\omega)}{\displaystyle\sum\limits_{i=1}^n\mathrm{heading}(v,\omega)}+\beta\cdot\frac{\mathrm{dist}(v,\omega)}{\displaystyle\sum\limits_{i=1}^n\mathrm{dist}(v,\omega)}+ \\ & \gamma\cdot\frac{\mathrm{velocity}(v,\omega)}{\displaystyle\sum\limits_{i=1}^n\mathrm{velocity}(v,\omega)}。\end{split} $

(17)

式中：$ \mathrm{heading}(v,\omega) $为方位角评价函数，用来衡量轨迹末端航向与目标点方位角之间的差值。$ \mathrm{dist}(v,\omega) $是距离评价函数，用来衡量预测轨迹与最近障碍物之间的距离。$ \mathrm{velocity}(v,\omega) $为速度评价函数，是衡量当前轨迹的速度大小，速度越大，评价函数值也越大。由于3个评价函数单位不同，对总评价函数的影响也不同，为使计算结果更符合真实情况，对3个函数进行归一化处理。而$ \alpha $、$ \beta $、$ \gamma $分别为三者的权重，通过调整各项权重的比例，使船舶有侧重的选择航行路径。

3 改进速度障碍法的船舶动态避碰 3.1 仿真数据

本文在Matlab环境下进行仿真实验，实验过程中，目标船均以恒定速度和方向行驶。本文算法的相关参数如表2所示。

3.2 多船会遇局面仿真

可将多船会遇分解为单船会遇，再根据《避碰规则》决定本船的航行状态。多船会遇实验的仿真环境如表3所示，实验中船舶航行状态及参数变化如图10所示。

如图，本船与目标船1构成对遇局面，本船按规则右转。避让中，本船发现目标船2和船3，本着“早”、“大”、“宽”、“清”原则，本船持续右转。避开船3后，本船试图恢复初始航线，又发现与目标船4构成左舷交叉情况，本船再次右转并从船4的船尾通过。整个避让过程，本船与目标船均保持安全距离。

4 结　语

本文针对A*算法在解决船舶路径规划存在的各种不足提出改进，通过引入栅格障碍率量化环境信息、改进启发函数、增加安全距离和3次折线优化等方法提高算法效率，增加算法安全性，并通过对比实验验证改进后算法的优越性。对于多船避碰问题，将四元船舶领域模型引入速度障碍法中，优化速度障碍区的求解方式，并融合动态窗口法对速度区间进行约束，通过仿真实验验证改进算法的有效性。

本文只对本船作为让路船而它船作为直航船且保速保向航行的会遇情况进行研究，具有一定局限性。在后续的研究中，应综合它船行为导致出现紧急局面的情况。