0 引　言

无人艇是一种无人操作的舰艇，与常规舰船相比，具有机动灵活、隐蔽能力强、智能化程度高等特点^[1]。为顺利完成各项任务，无人艇需要具备一定的自主航行能力。路径规划是实现无人艇自主航行的前提条件，也是智能化的重要体现。根据无人艇对航行环境是否已知可分为全局路径规划和局部路径规划^[2]。目前，全局路径规划算法主要有Dijkstra算法^[3]、A*算法^[4]、RRT算法^[5]、蚁群算法^[6]、遗传算法^[7]和粒子群优化算法^[8]等。其中，A*算法作为经典的启发式搜索算法，凭借简单有效、易于实现、适应性能力强等优点得到了广泛关注。但学者们把A*算法应用于无人艇全局路径规划时发现，传统Ａ*算法存在搜索节点多、路径贴近障碍物、转弯频繁等缺点^[9]。因此，不少学者对A*算法深入研究并加以改进，以适用于无人艇全局路径规划问题。

为提高路径规划速度，任晔等^[10]根据障碍物系数以及当前节点与目标点的距离来实现评价函数中启发函数权重的自适应调整，并通过减少节点的扩展方向来提高路径规划效率；张浩等^[11]引入启发函数加权系数以提高路径节点搜索速度，同时考虑角度因素，优先扩展起点与终点连线附近的节点；冯辉等^[12]在考虑无人艇旋回性能的基础上，提出一种变步长稀疏A*算法，仿真结果表明该算法具有较好的寻优性能，尤其适用于复杂环境下的全局路径规划问题。为改善传统A*算法路径贴近障碍物的问题，武善平等^[9]在路径规划过程中，通过设置安全距离来迫使路径远离碍航物，提高了路径的安全性；薛双飞等^[2]引入船舶航行安全代价对评价函数进行改进，可以在保证一定安全性的前提下获得最短路径。为改善路径转弯频繁的问题，WANG等^[13]利用S-57电子海图建立了八叉树网格环境模型，提出了一种基于航行安全权重、引导量和路径曲线平滑的改进A*算法，仿真结果表明，该算法能够生成安全合理的全局路径；SONG等^[14]采用路径平滑算法对A*算法生成的路径进行三次平滑处理，结果表明，平滑后的A*算法在转弯成本和距离成本方面优于传统A*方法。

在综合分析现有研究基础上，本文提出一种改进A*算法。首先，引入人工势场法对评价函数加以改进，通过考虑障碍物斥力场的影响来提高路径的安全性；其次，通过改进节点遍历方式和双向搜索机制减少搜索节点，提高路径规划速度；最后，对生成路径进行二次优化，删除冗余节点以减少转向点数量。

1 传统A*算法

A*算法是HART和NILSSON于1968年提出的一种启发式图搜索算法，最早应用于解决各种数学问题^[4]。其基本思想是首先确定一个评价函数，然后从起点开始根据评价函数不断向目标点方向搜索，同时记录每一次搜索确定的节点，直至搜索到目标点，最后从目标点返回到起始点来获得最优路径。传统A*算法的评价函数为：

$F\left( n \right) = G\left( n \right) + H\left( n \right)。$

(1)

式中：$F\left( n \right)$为从起始点经过当前节点n到目标点的估计代价值；$G\left( n \right)$为起始点到当前节点的实际代价值；$H\left( n \right)$为启发函数，表示当前节点到目标点的估计代价值。由于$G\left( n \right)$是实际代价值，因此$H\left( n \right)$对A*算法搜索结果的好坏有很大影响。假设从当前节点到目标点的实际代价值为${H^ * }\left( n \right)$，为保证A*算法能够搜索出最优路径，应当满足$H\left( n \right) \leqslant {H^ * }\left( n \right)$。

传统A*算法虽然具有简单、易于实现的特点，但实际应用中也存在诸多问题。以采取8邻域扩展方式的A*算法为例，一是评价函数仅考虑距离上的最优解，导致路径紧贴障碍物边缘，不利于无人艇航行安全；二是路径方向只能是45°的整数倍，增加不必要的转向点，造成路径不平滑，不利于无人艇操纵；三是在扩展节点时，每次都无选择性的对8个邻域节点进行搜索，产生大量与最终路径无关的节点，路径规划效率有待提高。因此，为使A*算法更好地应用于无人艇的全局路径规划问题，有必要对其进行改进。

2 改进A*算法 2.1 评价函数改进

针对传统A*算法路径紧贴障碍物的问题，引入人工势场法对评价函数进行改进。人工势场法是KHATIB^[15]于1986年提出的一种机器人路径规划算法。其基本思想是将移动机器人感知的环境看成一个虚拟的力场，障碍物产生斥力场，对移动机器人有排斥作用，越靠近障碍物，排斥力越大；目标点产生引力场，对移动机器人有吸引作用，越靠近目标点，吸引力越大；移动机器人在斥力场和引力场的综合作用下，避开障碍物，向目标点移动。本文引入人工势场法主要为解决传统A*算法规划的路径贴近障碍物的问题，故只考虑斥力场的影响。同时为简化计算量，仅考虑距离当前节点最近障碍物的斥力场。

人工势场法的斥力场函数为：

${{U}_{rep}\left(n\right) = \left\{\begin{aligned} &\dfrac{1}{2}{K}_{rep}{\left(\dfrac{1}{\rho \left(n\text{，} {n}_{obs}\right)} - \dfrac{1}{{\rho }_{0}}\right)}^{2}{\text ，} \rho \left(n\text{，}{n}_{obs}\right)\leqslant {\rho }_{0}，\\ &0{\text ，}\rho \left(n\text{，}{n}_{obs}\right)＞{\rho }_{0}。\end{aligned}\right.}$

(2)

对斥力场函数进行负梯度求解，即可得到斥力的表达式为：

${F}_{rep}\left(n\right)=\left\{\begin{array}{l}{K}_{rep}\left(\dfrac{1}{\rho \left(n\text{，}{n}_{obs}\right)}-\dfrac{1}{{\rho }_{0}}\right)\dfrac{1}{{\rho }^{2}\left(n\text{，}{n}_{obs}\right)}{\text ，} \\ \rho \left(n\text{，}{q}_{obs}\right)\leqslant {\rho }_{0}，\\ 0{\text ，}\rho \left(n\text{，}{q}_{obs}\right)＞{\rho }_{0}。\end{array}\right.$

(3)

式中：$\rho \left(n，{n}_{obs}\right)$为当前节点到距离最近障碍物的距离；${\rho _0}$为斥力场影响范围；${K_{rep}}$为斥力势场的增益系数。

经人工势场法改进后的评价函数为：

$F\left( n \right) = G\left( n \right) + H\left( n \right) + {F_{rep}}\left( n \right)。$

(4)

2.2 遍历方式改进

传统A*算法在搜索路径时，如图1所示，以当前节点为中心向周围的8个节点进行遍历，遍历过程未考虑无人艇的操纵性能。相对于移动机器人，无人艇具有惯性大的特点，特别是在转向时，其转弯能力取决于转弯半径。根据《船舶操纵性标准》，大型船舶的最小转弯半径为船长的5倍，小型船舶的最小转弯半径为船长的3倍^[6]。在构建环境模型时，每个栅格单元尺寸被设置为无人艇艇长的3倍，无人艇由当前节点栅格中心向下一节点栅格中心航行时，最大可实现90°的转向。如图2所示，考虑无人艇的操纵性能后，处于不同航向的无人艇的转向角被限制在0°～90°之间，节点的遍历方向由8邻域缩小为5邻域，降低了路径规划过程中遍历节点数量，可提高路径规划效率。

2.3 双向搜索机制改进

传统A*算法是从起始点开始逐步向目标点搜索，搜索过程中遍历节点数量较多，路径规划效率低。为提高搜索效率，可采用双向搜索机制，即在分别从起始点和目标点开始搜索。以起始点为正向搜索的起点，目标点为正向搜索的终点时，定义2个列表Openlist1和Closedlist1。以目标点为反向搜索的起点，起始点为反向搜索的终点时，定义2个列表Openlist2和Closedlist2。从正反2个方向进行搜索时，相应的遍历节点分别存放在Openlist1、Closedlist1、Openlist2和Closedlist2中。现有的双向A*算法在路径规划时，当有任意一个方向搜索到对应终点或者Closedlist1与Closedlist2中有交集时结束搜索。这就导致即使正向搜索的当前节点可以直接到达反向搜索的当前节点，依然会逐步搜索，从而扩展不必要的节点，影响搜索效率。同时，无人艇在航行过程中，尤其是在开阔水域，航线大多为直航段。基于此，在搜索过程增加可航性检验，即正向搜索的当前节点与反向搜索的当前节点的连线不通过障碍物且与障碍物保持一定安全距离D时，可认为两点之间满足可航性，即可结束循环。双向搜索机制改进后算法的流程如图3所示。

2.4 路径二次优化

在栅格环境中，传统8邻域A*算法规划的路径方向只能是45°的整数倍，这就导致路径转折点多，不仅增加路径长度，而且不利于无人艇操纵。DANIEL等^[16]在A*算法基础上提出Theta*算法，选择父节点时通过可视性检查实现了转向角度的任意化，解决了路径转折点多的问题，但频繁的可视性检查操作使得Theta*算法存在耗时长、效率低的问题。本文参考Theta*算法的思路，以生成的路径为对象进行可视性检查优化，同时为保证路径的安全性，设定障碍物的安全距离为D，即障碍物到路径的距离不能小于D。具体的优化过程如图4所示，从起点P₁开始对所有路径点进行遍历，连接P₁和P₃节点，如果P₁和P₃节点之间的连线与障碍物的距离大于安全距离D，则继续连接P₁节点和P₄节点，并对P₁和P₄节点之间的连线与障碍物的距离是否小于安全距离D进行判断，直至P₁和P_K节点连线到障碍物的距离小于安全距离D，保留关键点P₁和P_K-1，剔除P₁和P_K-1之间的节点；从节点P_K-1继续重复上述操作直到遍历到目标点，这样优化后的路径仅包含起点、关键点和目标点，从而减少转向点数量。

3 实例仿真

为验证改进A*算法的有效性，对传统A*算法、Theta*算法和改进A*算法进行仿真对比。如图5所示，选取舟山大园山和中园山水域为航行仿真环境，对电子海图图片栅格化处理后的航行环境被分为80×80个栅格，其中白色区域为可航水域，黑色区域为不可航区域。安全距离D取2倍栅格边长，障碍物斥力场范围${\rho _0}$取5倍栅格边长，斥力势场增益系数${K_{rep}}$取60。

3.1 开阔水域路径规划结果对比

在开阔水域，起始点和目标点之间无遮挡时，采用传统A*算法、Theta*算法和改进A*算法进行路径规划，图6为路径规划结果，表1为3种算法路径规划结果关键参数对比。

结果表明，从路径安全性方面来看，由于开阔水域距离障碍物较远，障碍物的影响极小，3种算法表现相同；从路径长度方面来看，改进A*算法和Theta*算法规划的路径相重合，即起始点到目标点的连线，相对于传统A*算法，路径长度减小了7.1%；从转向点数量上来看，传统A*算法存在大量的冗余节点，路径中转向点数量高达59个，而改进A*算法通过可航性检验避免了多余节点的扩展，并结合路径二次优化删除了冗余节点，达到了与Theta*算法相同的效果，提升了路径的平滑性；从规划速度方面来看，Theta*算法耗时最长，传统A*算法次之，改进A*算法最小，改进A*算法相对传统A*算法耗时减小了99.2%，规划速度的提升主要由双向搜索机制下可航行检验操作带来的。综上所述，在开阔水域规划路径时，改进A*算法相对于传统A*算法在安全性、路径长度、路径平滑性、规划速度方面均有较大提升，且规划速度的提升最为明显。

3.2 岛礁区路径规划结果对比

在岛礁区，起始点和目标点之间有岛礁遮蔽时，采用传统A*算法、Theta*算法和改进A*算法进行路径规划，图7为路径规划结果，表2为3种算法路径规划结果关键参数对比。

结果表明，从路径安全性方面来看，传统A*算法和Theta*算法规划的路径紧贴障碍物，与障碍物的最小距离为0，而改进A*算法通过引入斥力场的影响，生成的路径与障碍物的最小距离为2.5142倍单元栅格边长，提高了路径的安全性；但由于改进A*算法在规划路径时避免贴近障碍物，导致路径长度有所增加，相对于传统A*算法路径长度增加了4.6%；从转向点数量方面来看，改进A*算法表现最好，Theta*算法次之，A*算法最差，表明路径二次优化取得了比Theta*算法更好的结果，可以显著提升路径的平滑性；从规划速度方面来看，Theta*算法的可视性检查机制带来了难以忽视的计算成本，使其耗时远远大于A*算法和改进A*算法，而改进后的A*算法相对于传统A*算法搜索速度提升了28.1%，这主要得益于遍历方式和双向搜索机制的改进。综上所述，在岛礁区规划路径时，出于安全性的考虑改进A*算法规划的路径在长度上会有所增加，但在安全性、路径平滑性、规划速度方面有明显优势。

4 结　语

针对传统A*算法的缺点，结合无人艇特性提出了一种双向搜索机制改进A*算法，主要从评价函数、节点遍历方式、双向搜索机制、路径二次优化四方面进行改进。并选取开阔水域和岛礁区2种航行场景进行仿真分析，结果表明，开阔水域场景下改进A*算法在安全性、路径长度、路径平滑性、规划速度方面均有较大提升；岛礁区场景下改进A*算法在路径长度上会有所牺牲，但在安全性、路径平滑性、规划速度方面有明显优势。本文提出的改进A*算法为无人艇全局路径规划问题研究提供了新思路，但路径规划过程未考虑风、流等环境因素的影响，也不适用于动态障碍物环境，后续应当考虑无人艇在动态环境下的局部路径规划问题。