1. 引言
水面无人艇(Unmanned Surface Vehicle, USV)是一种通过自主方式在水面航行的智能舰艇。近年来，我国愈发重视水面无人艇的研发，人们已经发展了各式各样的具有感知、决策和作业能力的水面无人艇。但是不管水面无人艇用途如何，其为人类提供的所有服务都是以导航控制为基础的。而导航控制中，路径规划(Path Planning)则是很关键的一个环节。此外，由于路径规划的好坏会影响无人艇智能水平，因此，路径规划需注重研究。
路径规划通常划分为全局路径规划和局部路径规划。本文主要介绍全局路径规划算法，按照传统路径规划算法和智能仿生学路径规划算法的分类，对水面无人艇经典算法的基本思想以及目前的发展成果进行归纳和总结。
2. 传统路径规划算法
2.1. 广度优先搜索
广度优先搜索(Breadth First Search, BFS)是指按照广度方向搜索，遍历全图，直到找到目标为止。
BFS在搜索时呈波状推进形式，它是一种以时间换空间的方法，能够保证搜索到的路径是最优的。为了实现波状推进搜索特性，BFS采用队列(Queue)作为openlist的数据结构。队列设置open指针和closed指针，当open等于closed时，表示队列空；当open大于队列长度时，表示队列溢出 [1]，如图1 [1] 所示。
该算法的优点是不会发生死循环，且若只有一个解，那么广度优先搜索就会找到这个解；若存在多个解，则将找到最优解。这种方法的缺点是占用内存大，因为它要将所有节点都搜索一遍，且完成遍历的时间长 [2]。图2 [2] 为广度优先搜索过程。
Figure 2. [2] Breadth first search process
图2. [2] 广度优先搜索过程
2.2. Dijkstra算法(迪科斯彻算法)
Dijkstra算法 [3] 是荷兰科学家迪科斯彻在1959年提出的。Dijkstra算法是利用广度优先搜索的单源最短路径算法。该算法体现了贪心思想，首先记录起点到所有点的距离，找到最短的，然后进行一次松弛操作，即将刚才找到的最短距离点作为中转点，遍历全图，再找到最短的，若该点与中转点距离更近则更新距离，这样在搜索完所有点后，保存起点到所有其他点的最短距离。
经典Dijkstra算法虽然原理简单易懂，但占用的内存将随着地图复杂度的增加而急剧增大且该算法适合进行直接规划，生成路径，所以对于复杂的大规模环境的路径规划不太适用。
王超 [4] 等在经典Dijkstra算法中加入红外技术，使得无人机在复杂作业环境中能有效避开障碍物，使路径规划达到最优效果。而针对Dijkstra算法计算内存大的问题，汤伟 [5] 等引入自动机，建立能够描述行走逻辑的自动机模型，使得该算法在得到相同路径的情况下，执行命令减少，遍历节点减少；王芝麟 [6] 等则使用最小二叉堆作为该算法的辅助数据结构，经过优化的算法运算次数有效降低，计算效率显著提高。
2.3. A*算法
A*(A-Star)算法是由Hart [7] 等提出的一种最优路径规划算法，其基于Dijkstra算法，是一种启发式算法。
A*算法的优点是占用内存少，因为其使用启发函数，使算法的搜索深度和所需搜索的节点数量都减少了。因此，这也可能使算法在搜索过程中遗漏大量节点，从而导致最终结果是次优结果，甚至是死循环。
针对传统A*算法路径规划实时性差且路线为折线问题，岳高峰 [8] 等提出了了一种基于双向平滑A-star算法的路径规划策略，通过优化算法代价函数提高实时性并对规划路径进行平滑化处理，解决算法折线多的问题，极大提高了算法的正确性和可行性；葛文雅 [9] 等通过扩展搜索领域，在启发函数中引入新的评价指标并对安全性进行量化处理，大大增加了算法的路径质量和安全性；谭宝成 [10] 等采用两点间的欧氏距离作为估价函数并交替进行前向和后向搜索有效缩短搜索路径长度和算法运行时间。
2.4. 可视图法
可视图是由通过边连接的节点组成的图，可视图法将机器人看作为点，障碍物看作为多边形，然后将起点、终点、多边形顶点连接，并且任何连线都不能穿透障碍物，建立可视图，并通过优化算法求解获得最优路径。
可视图法原理简单，算法容易实现，但是在障碍物数量较多或形状复杂的情况下，该方法不适用并且其缺乏灵活性，即一旦起点和目标点发生改变，就要重新构造可视图。
为提高路径规划的效率，彭小丹 [11] 提出了一种提取环境有用信息，动态生成障碍物辅助顶点的方法改进可视图法，使得较优或最优路径生成的在低计算时间下实现。杨淮清 [12] 等通过将复杂障碍物近似看作矩形或多个矩形的组合，来简化建模，以此来描述障碍物边界地图，有效实现机器人的路径规划。
2.5. 基于采样的运动规划算法
基于采样的运动规划 [13] (Sampling-based Motion Planning, SBMP)算法主要包含概率路线图 [14] (Probabilistic Roadmap, PRM)法和快速扩展随机树 [15] (Rapidly Exploring Random Tree, RRT)法。
PRM法是一种基于图搜索的路径规划算法，其通过少量随机采样点，在空间中搜寻路径。该算法的优点是采样点可以重复利用，搜索效率比一般的图搜索法高。但是，当地图发生变化时，需要重新采样且采样点较少或分布不合理时，该方法是不完备的。
RRT法是通过增量式的方法快速扩张出像树一样的路径密集填充在整个空间，然后搜索空间并找到可通行的路径。该方法最大特点是其随机性，即不需要知道具体的空间信息，仅通过反复的随机试探就能找到合适的路径，因此对于动态变化的地图特别适用。其缺点则是随机树可能无法均匀经济地搜索空间并且对于过窄的空间通道，该方法有一定概率无法找到其路径。
夏炎 [16] 等基于节点增强法与几何平滑策略，有效降低了PRM法的搜索路径长度并提高了路径平滑度。贺颖 [17] 等在PRM法均匀撒点基础上融合人工势场法，提高了采样点利用率，实现了路径优化。薛阳 [18] 等用局部敏感哈希算法代替PRM法中的近邻搜索，使得构建无向路径图时间大幅减少，大大提高了算法效率。
郑维 [19] 等提出了一种新的基于分级随机采样与扩展的弱随机RRT算法，相较传统算法缩短了求解时间，提高了迭代速度。彭君 [20] 等提出了一种目标偏向性的改进RRT算法，减少了采样点数量，提高了路径平滑度，使机器人更适应于复杂环境。李娟 [21] 等将滚动规划与RRT算法相结合，使得算法的遍历能力提高，加快了航行器的目标搜索速度。
3. 智能仿生学路径规划算法
3.1. 蚁群算法
蚁群算法(Ant Colony Optimization, ACO)是Dorigo [22] 等提出的一种智能仿生学算法。蚁群算法的基本原理就是蚂蚁在路径上释放信息素(蚂蚁个体间通过信息素交流)，碰到岔路路口，就随机挑选一条路走，同时释放信息素(信息素浓度与路径长度成反比)，之后的蚂蚁来到该路口时，就选择信息素浓度高的路径。因此长度短的路径上的信息素浓度越来越大，该路径最终成为蚁群觅食的最优路径。蚁群算法就是通过算法模拟蚂蚁觅食的过程来寻找最优路径。
蚁群算法是一种采用正反馈的算法，同时结合启发式概率搜索，使得搜索结果为全局最优，但是当缺少信息素或算法参数出错时，运算速度将变慢并陷入局部最优。
针对蚁群算法收敛速度慢，易陷入局部最优等问题，马小陆 [23] 等提出了一种基于万有引力搜索策略的蚁群算法，有效提升了算法收敛速度和解决了局部最优问题。鲁飞 [24] 等通过对初始信息素不均匀分配和在启发函数中引入夹角因素，提高了蚁群算法的可行性和有效性。杜力 [25] 等在蚁群算法中引入萤火虫算法，提出了一种混合算法，实验表明混合算法明显提升了传统蚁群算法的综合效果。
3.2. 遗传算法
遗传算法(Genetic Algorithms, GA)是Holland [26] 提出的一种随机搜索算法。其原理是依据适者生存，优胜劣汰的原则，通过选择、交叉、变异等操作，将适应度较高的个体更多地遗传到下一代，这样在群体中终将会得到一个优良的个体即为最优解。
遗传算法鲁棒性强，是一种自适应全局优化概率搜索算法，适合用于解决复杂问题或非线性问题以及求解复杂路径的优化问题。但是该算法收敛速度慢且不能胜任实时性高要求的局部搜索。
针对遗传算法效率低，局部搜索能力差等问题，王吉岱 [27] 等提出一种基于改进模糊自适应遗传算法，通过可行性筛选和模糊逻辑控制等手段，改进了遗传算法的有效性。谢冲冲 [28] 等将遗传算法和鲸鱼算法融合，弥补了遗传算法收敛度不高的问题并且提升了算法的优化准确率。王豪 [29] 等通过改进轮盘赌选择法，提出了一种自适应遗传算法，实验表明，新的算法有效缩短了平均最短路径并且使得路径拐点数量和算法迭代次数都显著减少。
4. 总结
随着海洋工程装备的需求越来越大，无人水面艇的发展也越发得到重视。但是，现阶段我国的无人艇技术还存在许多不足之处，为了使其能适应更加丰富复杂的工作环境，水面无人艇路径规划算法还需要有更多创新。要使算法的有效性和准确性进一步提升，未来可从以下方面展开探索与研究：
1) 进一步提高和完善现有的路径规划算法的实用性，使其适应更多应用场景。
2) 思考多种算法融合以及全局路径规划算法与局部路径规划算法融合的方法。
3) 开展多个无人水面艇的协同工作的算法研究。
基金项目
2022年研究生科研与实践创新计划项目支持。
参考文献