⒉启发式搜索算法
A*算法由HART等在1968年提出，是一种基于启发函数的图搜索算法，用于寻找2个节点之间最短的路径。相对于其他启发式搜索算法，A*算法效率更高，能够保证以最小的成本返回最短路径。但其缺点是适应性差，需要消耗大量的时间和储存空间，同时算法生成的锯齿状路径对船舶的航行不利。SONG等对A*算法进行了改进，将算法的搜索范围扩大了1倍，利用3种路径优化方法解决了转折过多的问题，并且将其运用到了无人船“Springer”系统中。YANG等提出了“有限角度A*算法（FFA*）”，在扩大搜索范围的同时引入了安全距离和视线制导的规则，保证了路径的有效性和合理性。WANG等将改进的A*算法用在了六边形网格地图中，提升了算法的效率，并且将“引导值”加进了启发函数当中，解决了启发函数相同时的决策问题。CHEN等提出了A*BG算法，这种算法保留了A*VG可搜索全局最优路径的优点，并且证明该算法的速度要优于传统的A*，但试验中没有考虑近海基础设施和算法实时信息的数据，其实用性还有待验证。综上可知，学术界对A*算法的改进主要包括：⑴扩大邻接点的搜索数目，改进搜索规则；⑵启发函数的改进；⑶优化路径；⑶采用不同的环境建模方法。Dijkstra算法由DIJKSTRA在1959年提出，是一种经典的最短路径搜索算法。Dijkstra算法在搜索的过程当中执行了很多与最短路径无关的顶点计算，当情况较复杂的时候，算法的效率较低。目前学术界对Dijkstra算法的改进通常分为3种：⑴基于搜索策略的优化，如扩展搜索区域；⑵优化数据储存结构；⑶优化环境模型，如分层搜索。CHENG等对Dijkstra算法的搜索策略进行了改进，将多个角度纳入搜索范围之内，用栅格地图验证了本方法比传统Dijkstra和八方向搜索的Dijkstra得到的路径距离更短。SEKARAN等提出Dijkstra的改进算法，只计算距离最近的节点，减少了不必要的节点计算，节省时间的消耗，并且在V-REP试验平台上验证了该算法的实用性。GUO等在算法中引入了运行时间计算机制，当出现多条路径长度相等的情况时，通过运行时间计算出最优的路径。康文雄等提出了分层Dijkstra算法，该算法利用分层结构，可实现对搜索进度的保存与回溯等操作，该算法虽不一定能找到理论最优解，但在数据量大的时候可以快速找到次优解。
三、局部路径规划
局部路径规划依靠传感器获取周围环境信息和无人船的位置，将各种传感器信息融合后建立环境模型，再通过算法进行路径规划。主要的算法包括人工势场法、快速扩展随机树法和动态窗口法等。
⒈工势场法
人工势场法（APF）最早由KHATIB提出，是水面无人艇局部路径规划的一种常用算法。人工势场法具有模型结构简单、计算快速和实时性强等多个优点，但可能会出现局部最优、受力平衡、斥力大于吸引力等不利情况。综合近年来的研究，学者们对人工势场法的改进切入点包括3类：⑴修改引力和斥力的势场模型；⑵与其他算法相结合；⑶采用不同环境建模方法。MIELNICZUK将人工势场法运用于船舶航运路线生成中，利用4种不同的障碍物情景进行了有效性验证，结果表明，人工势场法能够快速、高效地找到一条安全的航线，但没有解决局部最优问题。LAZAROWSKA在一系列研究中提出了离散人工势场法（DAPF），将环境模型离散化为栅格地图，再根据COLREGS和计算规则确定了每个栅格的势能，分别在静态和动态障碍物环境下验证了算法的有效性，结果表明，该算法不仅能高效快速地计算出安全路径，而且也解决了局部最优和受力平衡等问题。LYU提出了“路径引导人工势场法”，该算法考虑了COLREGS规则和船舶操纵特性，同时在运行过程中可快速根据环境的变化及时反馈信息，并做出路径调整，但本文仅对船舶的转向角做出了限制。
⒉速扩展随机树
快速扩展随机树（RRT）最早由LAVALLE提出，该方法适合解决多自由度机器人在复杂环境下和动态环境中的路径规划，但生成的最终路径不是最优。对RRT算法的改进可以从3个方面切入：⑴引入启发信息，使探索过程不再随机化；⑵改变搜索策略，如扩展搜索方向、引入新规则；⑶与其他算法结合。CHIANG等提出了一种结合COLREGS的改进RRT算法，通过RRT的增长期间对其他船舶进行联合仿真来实现的，从而预测未来发生的碰撞。仿真结果表明，相比基于模型预测控制（MPC）与APF的避障算法，该算法拥有更高的成功率，但仿真没有考虑到风、浪、海流的影响。庄佳园等设计一种基于改进RRT算法的局部路径规划方法，在生长时加入了衡量节点探索失败次数的抑制因子，使探索不再随机发生，同时限制了最大转角，使规划航迹趋于实用。该算法提高了搜索效率，并且符合实际的无人船跟踪路径，缺点是没有考虑COLREGS规则和实际环境的影响。
⒊态窗口方法
动态窗口方法（DWA）是一种常用的路径规划方法，最初由FOX等于1997年提出。该算法在速度空间中采样多组速度值，并模拟机器人在各速度下生成的轨迹，在时间最短内达到目标点即为最优解。WANG等提出了一种DWA与A*算法结合的路径规划系统，同时考虑了路径的实用性和USV的动力学性能，并且无人船可通过选择最优速度来躲避未知的障碍物。MISSURA等对传统DWA算法进行了改进，引入了“动态碰撞模型”，在考虑障碍物运动的同时预测未来可能的碰撞。LIN等提出了一种可实时路径规划的DWA算法，该算法根据障碍物的比例用圆形或者矩形建模，简化障碍物形状，减少了空间和时间的浪费，同时可以考虑多个静态和动态障碍物，具有很强的适应性，但其缺点在于仿真过程没有考虑环境因素。
