船舶全局路径规划相关算法研究综述

李元昊，段鹏飞，郭绍义，韩 洋，秦 圻

（山东交通学院航运学院，山东威海 264200）

0 引言

船舶的全局路径规划就是根据设定的评价标准，为一定航行环境中的船舶搜索出一条由起点至终点的无碰撞路径，将静态环境信息的全局规划和不确定环境因素的动态局部规划相结合可使船舶路径规划达到较为理想的状态。全局路径规划主要应用于相对稳定的环境，其普遍性相对较强。如图1所示，船舶全局路径规划算法可分为传统全局路径规划算法和智能优化全局路径规划算法。本文对各类算法的发展背景、设计原理及具体路径规划场景下的应用优化进行对比分析，并对全局路径规划算法的发展趋势进行展望。

图1 全局路径规划算法分类

1 传统全局路径规划算法

1.1 Dijkstra算法

Dijkstra算法为 Dijkstra在研究贪心算法的过程中提出的解决最短路径问题的方法，该算法属于单源路径算法，可计算质点在运动过程中由起始点运动到其他顶点时的最短距离。宋勇和王文丰等将Dijkstra算法作为路径规划初始模型，并在此基础上进一步改进和优化。杜贻群等针对无人艇进行直角和斜向转弯的航行特点对Dijkstra算法的路径搜索进行改进，提出了一种改进的多方向路径搜索算法，其转向更为平滑，可充分适应无人艇实际的航行要求，具有很好的适应性。王月鹏利用Dijkstra算法对自主规划路径进行优化，实现无人船在水质采样过程中的多点采样功能。

Dijkstra算法计算思路清晰，可有效寻找最优解。然而，当路径规划较为复杂时，计算所需的数据节点剧增，这会导致运行时间大量增加，进而降低运行效率。

1.2 A＊算法

A算法由Peterhart等提出，该算法将最佳优先搜索算法（Best-First-Search，BFS）和 Dijkstra算法结合在一起。对于静态环境下全局路径规划的最短路径问题，A算法是最有效的直接搜索算法之一。

A算法的原理：通过设置代价评估函数对节点的综合优先级进行估计，运用广度优先思想从起始点为中心向外层层扩展，直至遍历到终点时得到最短路径。

熊壬浩等对 A算法的运算过程及改进方法进行了详细的描述。武善平等和陈新等主要对A算法的启发函数提出改进，前者利用自适应的改进启发函数，并着重考虑目标点的方位信息和障碍物的安全距离；后者对启发函数、分区距离信息和角度变量进行加权处理以提高搜索效率。

由于规划路径的转折点较多、搜索范围相对较小，A算法容易形成局部最优的情况。张丹红等和高峰等分别对 A算法的搜索方式和节点搜索领域进行改进和扩展，将八角度、八邻域节点搜索扩充到多角度、多邻域的搜索，从而提高空间搜索能力和收敛速度。

相比传统的Dijkstra算法，A算法在计算目标点与下一个顶点之间的距离的同时会预估目标点与终点之间的距离，进而减少无用的计算量。目前，Dijkstra算法和A算法常与其他算法结合使用，或根据具体的应用场景适当优化以减少计算量。

1.3 模拟退火算法（Simulated Annealing 1.3 Algorithm，SA）

METROPOLIS等最早提出模拟退火算法，KIRKPATRICK等将模拟退火算法应用到组合优化领域。在船舶的路径规划中，模拟退火算法更适合用于局部搜索，但其目前在全局路径搜索的过程中仍起到不可或缺的作用。模拟退火算法通常与其他路径规划算法结合使用，以避免出现路径规划局部最优的情况。

针对模拟退火算法在水面无人艇在路径规划中全局搜索能力不足的问题，郑佳春等将模拟退火算法与粒子群算法相结合，提出Simulated Annealing Particle Swarm Optimization（SAPSO）混合算法，该算法收敛性好，且能规避局部最优解。SAPSO混合算法适用于不确定因素影响下的动态环境规划问题。

2 智能优化全局路径规划算法

智能优化算法是一种启发式优化算法，包括遗传算法、蚁群算法、禁忌搜索算法、模拟退火算法、粒子群算法等。智能优化算法一般是针对具体问题设计相关的算法，理论要求弱，技术性强。智能算法与最优化算法进行比较，相比之下，智能算法速度快，应用性强。对于未知海况环境下控制参数的约束优化问题，可采用智能算法予以有效解决。

2.1 神经网络算法

神经网络算法采用并列连接的方式，在路径规划时尽量远离障碍物以使获得的路径最短。根据神经网络算法中各神经元是否存在反馈、是否能接受外加输入与其他各节点的反馈以及自身的反馈情况，可将神经网络算法分为前馈神经网络算法和反馈神经网络算法。

神经网络算法通过参数设置实现自我学习的功能，规划速度快、结构简单、鲁棒性强。神经网络算法存在以下不足之处：1）泛化能力和记忆能力较差；2）学习速率通常不变；3）学习参数不具备存储功能。针对神经网络算法的不足之处，很多学者对其进行相应的优化和改进，或将其与其他算法组合使用。

耿晓龙等和吕扬民等通过将人工神经网络与强化学习算法中的Q学习算法相结合，以有效解决路径规划在不同领域的相关问题。其中，耿晓龙通过在强化学习中设立奖罚规则，将神经网络与Q学习算法有效结合，得到路径规划最优解，并通过实验仿真对算法进行验证。

2.2 遗传算法

遗传算法是JOHN在生物进化论的自然选择和遗传变异观点的基础上提出的。该算法通过加入选择、交叉和变异算子对初始长度编码下的种群进行运算，并将适应度作为路径解的评价标准。遗传算法的逻辑流程见表2。

图2 遗传算法的逻辑流程

遗传算法具有选择、交叉、变异的特征，故其搜索过程具有灵活多变的特点，可有效提高全局路径的搜索能力。然而，遗传算法的计算速度较慢、路径拐点较多、算法的实时性和适应性较差。

栾志玲与马建敏等对交叉变异的概率进行自适应调整以提高算法的全局搜索效率，使用自适应交叉变异概率替代现有交叉变异概率以避免早熟现象的出现。栾志玲提出一种改进遗传算法，在原来基础之上增加种群熵对种群多样性进行评估，并通过Matlab仿真验证了算法的可行性。

马丹提出使用精英保留策略方法来解决遗传算法收敛性慢的问题，提出增加免疫算子来解决遗传算法多样性减少的问题。文献[23]提出一种改进策略，通过增加插入、删除算子对路径编码进行优化，可有效提高解空间内的寻优效率。

2.3 蚁群算法

蚁群算法属于生物启发式类的算法，其最鲜明的特点在于蚂蚁群体的多样性和路径搜索的正反馈特性。在选择路径的过程中，路径选择概率和信息素挥发系数是决定全局寻优能力的重要因素，由初始信息素和启发信息的大小决定。

路径选择概率和启发信息的计算公式分别为

式（1）和式（2）中：下标和为节点；为节点数量；为时刻；和分别为信息素因子和启发函数因子，反映信息素和启发函数对蚂蚁下一步转移作用的强度；为两节点间的直线距离。

由式（1）可知，信息素和启发信息与路径选择的概率之间存在正相关关系。该算法的正反馈特性可使算法在搜索过程中不断收敛，最终逼近最优解。

启发式的概率搜索具有着跳出局部最优解的特点，多个体同时搜索的效率相比单个体搜索得到明显提高。然而，算法中个体分布情况会导致算法的收敛速度与种群多样性之间存在矛盾。随机选择探索全局空间最优解大概率可找到最短路径，但需要很长时间才能发挥正反馈的作用。

针对传统蚁群算法初期搜索效率低、收敛较慢的问题，王成等采用不均匀分布初始信息素、引入权重因子等方式对蚁群信息更新规则进行改进。贺嘉等将双向搜索算法融入传统蚁群算法，可显著提高搜索效率，模拟仿真及实船试验验证了算法的可行性。

童帮裕等针对冰区航行路径规划的特殊性，考虑航线距离、航行操作复杂度和流冰规避等影响因素，结合人工势场法对蚁群算法进行改进，利用新的启发信息函数进行路径选择。研究结果表明：该算法在在动态避让、航速控制方面仍有待改进和优化。

马小铭等提出一种改进蚁群算法，主要通过引入环境因子以调整启发函数，进而降低死锁情况的发生，该算法对于船舶路径规划问题具有重要借鉴意义。王成等通过引入惩戒因子对陷入死锁的信息素进行惩罚，进而降低死锁率。然而，该方法没有考虑发生死锁的环境细节。EBERHARTR等通过引入环境因子以增强对环境的阅读能力，进而有效避免死锁，提高有效蚂蚁的数量。

2.4 粒子群算法

粒子群算法由EBERHART等提出，属于概率型全局路径规划算法。该算法不断对个体和群体的最优位置进行搜索，直到找到全局最优解。其中，个体优劣程度的适应值评价函数直接影响到算法的执行效率，下面通过流程图的方式对算法原理进行说明。粒子群算法的逻辑流程见图3。

图3 遗传算法的逻辑流程

粒子群算法从随机解出发通过迭代寻找最优解，且可调参数较少，故其具有应用简单、收敛速度快、计算复杂程度较低等特点，但同样存在寻优过程中种群多样性和算法收敛速度上的矛盾。

王文丰等利用线性递减惯性权重粒子群算法进行路径规划，引入混沌理论对种群进行初始化，以平衡种群的全局搜索能力和局部搜索能力。宋勇对线性递减惯性权重粒子群算法以及引入混沌理论的改进算法进行了更加详细的描述，并在此基础上进行动态避障研究。通过结合局部动态的路径规划中改进的滚动窗口算法对动态威胁区域进行有效的规避，进而得到最优路径解。

针对多路径规划问题，刘利强等在粒子群算法的基础上引入小生境识别、粒子群隔离算法、交叉算子等，将种群粒子分为主群粒子和子群粒子，在此基础上完成区域内局部寻优，从而有效规划出多条最优及次优路径。

郑佳春等将粒子群算法与模拟退火算法相结合，对无人船艇的路径规划进行研究。舒宗玉采用混合粒子群算法对初始路径进行优化，并在路径最短基础上提出路径平滑和路径安全的多目标优化问题，但仍需进一步精确测量才能符合实际要求。

3 发展趋势分析

1）结合具体应用环境与算法特点优化常规算法性能

为获得路径规划的最优解并使得所规划的路径符合各种航行环境和应用场景，对各种规划算法的运用大致可分为以下3种：（1）对常规算法中的不足进行改进；（2）利用多种算法的优势进行适当的算法综合；（3）将改进优化算法与常规的某类算法进行结合产生新的混合算法。在保证路径规划有效性的同时，主要通过控制算法的收敛速度、提高全局搜索的效率、防止局部收敛的出现等方式来提高算法性能。

2）仿真与实船试验对路径规划理论计算结果验证有待进一步的完善

针对路径规划算法的研究目前大都还处于理论描述以及模拟仿真验证阶段，仅有少数的研究通过仿真和实船进行验证。通过实船对算法过程的验证往往与理论计算有一定的差距，虽然对实验设计的要求较高，但更能直观反映方法在真实海洋环境中的应用效果，可以对存在的隐患问题和突发状况进行排查，并选择更适合的解决方案以适应海洋航行的需要，降低航行突发风险的发生概率，也能使算法的实用性和推广性得到保障。

3）借鉴其他领域研究成果使全局路径规划与局部路径规划相结合

当前对路径规划的研究往往在全局路径规划的基础上对局部不确定因素下的动态规划进行综合考虑，或对多目标条件或多路径条件下的路径规划问题进行研究。对环境感知的动态路径规划算法在机器人路径规划中应用广泛，对无人船在复杂环境下的路径规划帮助很大。

4 结论

船舶路径规划算法对于无人舰艇在各种环境下的自主航行至关重要，本文对各类算法的发展背景、设计原理及具体路径规划场景下的应用优化进行对比分析，并对全局路径规划算法的发展趋势进行展望，希望为无人艇全局路径规划算法的优化提供一定指导。