基于蚁群优化算法的无人船艇航线自动生成及路径规划∗

2019-03-27张海妮

舰船电子工程 2019年3期

张海妮

（陕西交通职业技术学院基础部西安 710021）

1 引言

近年来，随着人工智能的不断发展，无人船艇的技术研发也在不断推进，逐渐被用于代替传统的人工作艇进行海面自主作业［1］。无人船艇的研究包括艇型设计、自动避碰避障和路径规划导航等方面［2］，其中，航线自动生成和路径规划是无人船艇研究的关键技术。海面环境复杂，无人船艇容易受到风浪等影响［3］，因此，展开对无人船艇航线自动生成及路径规划的研究具有十分重要的意义。国内外学者对无人船艇航线自动生成和路径规划做了大量研究，张立华等［4］提出一种基于瞬时水深模型的最短时间航线自动生成算法，能够搜索最短时间航线和动态分析航线，与传统算法相比，具有更强的实用性能。李隽［5］通过电子海图与AIS系统监控船舶航行状态相结合，实时上传海洋及船舶信息，并使用Douglas-Peuker算法依据海洋实时信息修正航线，提高了船舶航行的安全性。吴小平等［6］运用蚁群算法结合TSP问题对无人船艇进行路径规划，算法通过路径优化与路径校核对三个无人船艇的情形进行验证分析，发现该方法效率高、耗时短，为无人船艇路径规划问题提供了一个有效的方案。本文通过介绍蚁群优化算法与标准A星算法，设计无人船航线自动生成框架和基于蚁群优化算法的最佳路径捜索流程，研究了航路转向点辨识与连通性辨识标准，分析了航线的自动生成与考虑回转性能、风浪阻力、气动阻力和海流影响的路径规划，对无人船艇航线路径进行更好的规划，为相关研究提供了理论参考。

2 算法介绍

2.1 蚁群优化算法

蚁群优化算法是一种具有优良分布式、良好正反馈特性和较强鲁棒性的计算机制，源于蚂蚁觅食中搜索最短路径的行为得到的一种模拟进化算法［7］，被应用于旅行商最短路径［8］寻优问题。

假设蚂蚁总数为m，航路转向点总数为n，航路转向点i和j在t时刻之间的信息素浓度为τij（t），则第k只蚂蚁t时刻由航路转向点i到航路转向点j的转移概率为

式中，α为启发因子，体现信息素浓度的重要程度；β为期望因子，体现航路转向点之间距离的重要程度；ηij（t）为启发函数，表示航路转向点i与j之间的距离，取值为1/dij；allowedk为蚂蚁k能够选择的航路转向点。

如果蚂蚁并未选择信息素浓度最高的路径，则采用轮盘算法得到随机数r，取值［0，1］，依据r的转移概率范围作为蚂蚁航路的下一个转向点。当完成最短路径搜索之后，转向点的信息素依据式（2）进行更新。

式中，τij(t)为循环中蚂蚁k由航路转向点i到j释放信息素的增量；ρ为信息素的挥发系数。

2.2 标准A星算法

A星算法［9］根据closed链表和open链表来定位目标。假设给定终点E和起点S，步骤为：1）S添加至closed链表，其周围格子添加至open链表；2）open链表中寻找最小权值F的单元格，将其命令为下一点并添加至closed链表；3）判断最小权值F的单元格相邻单位是否处在目标单元格，得到终点E，否则将相邻单元格添加至open链表并返回上一步骤，假如open链表搜索完全而未能找到终点E，则视为无可行路径。

3 无人船艇航线自动生成

3.1 无人船航线自动生成框架设计

无人船艇航线自动生成框架设计如图1所示。

图1 无人船航线自动生成的框架设计

具体步骤如下［10～11］：

步骤一：对AIS基站收集的数据进行预处理，然后通过Douglas-Peucker算法对其进行压缩得到轨迹数据中的特征点；

步骤二：求取相邻特征点形成的恒向线航向和邻特三个特征点形成夹角的角度，根据转向阔值的设定对轨迹中的转向点进行辨识；

步骤三：根据转向点相似性度量标准，通过层次NBSCAN算法对不同航迹中的转向点进行聚类并记录其信息，依据真实航迹判断连通性；

步骤四：采用蚁群优化算法得到设定起点与终点之间的最佳航线，然后通过对比验证无人船航线自动生成方法的有效性。

3.2 航路转向点辨识和连通性辨识

通过层次NBSCAN算法对不同航迹中的转向点进行聚类得到的航路转向点为孤立的个体，而相邻航路转向点的连通性一般由其轨迹转向点的并集所决定，通常航路转向点之间的Constitu⁃tion-MMSI的并集为实集。假设两个航路转向点分布为TN1和TN2，则两者之间的连通性标准如下［12］。

只要满足图2中任意一条标准，则认为航路转向点之间具备连通性，在连通性辨识完成之后进一步得到有向图：

式中，L为航路转向点之间的连通性；TN为孤立的航路转向点。

图2 航路转向点辨识与连通性辨识标准

3.3 航线自动生成的实例研究

基于蚁群优化算法的无人船艇航线自动生成依据有向图G得到起点与终点之间的最优路径，其流程见图3。

图3 基于蚁群优化算法的最佳路径捜索流程

通过基于蚁群优化算法的最佳路径捜索流程自动生成的航线，能够符合航线设计要求，并且生成航路转向点均处于转向区内；进港航道与自动生成的航线保持一致并且可以延伸至泊位，满足船舶采用分道通航制航行的要求。

4 无人船艇航线路径规划

路径规划研究选择无人船艇模型，通过CFD仿真计算路径规划中的阻力性能参数，并通过设置恰当的路径规划计算参数和设定正确的路径规划优化目标，研究了考虑回转性能、风浪阻力和气动阻力和海流影响的路径规划，确定规划结果是否具有实际意义。

4.1 考虑回转性能的路径规划

基于A星算法中通过8邻域空间进行规划搜索，栅格点之间的运动方向均为45°的倍数，可能导致较长的路径与不必要的转折点，因此，对A星算法进行回转性能改进：保持航向角不变，选择第i个点，进而选择第i+2个点以及后续点，如果可以直接相连，则删去中间点。通过表1中两种算法对比，发现优化效果明显，回转次数减少大约2/3，路径长度减少将近5%，避免了A星算法规划路径无法达到最短的弊端。

表1 标准A星算法与回转性能改进算法对比

考虑回转性能的路径规划如图4所示，对真实海图上进行考虑回转性能的路径规划，发现在保证不改变航向的前提下，回转性能改进算法对真实海图具备有效性。

图4 考虑回转性能的路径

4.2 考虑风浪阻力和气动阻力的路径规划

以往的研究中，通常忽略气动阻力对船舶的能耗，实际航行中能耗是船舶运营成本中无法忽略的。对于无人船艇而言，采取CFD方法计算无人船在不同航速下气动阻力，并且作为输入参数进行路径规划。由于风浪具有复杂性和随机性，考虑风浪阻力的路径规划选择以储备功率研究波浪中增大的阻力、污底阻力的增值和强风导致的气动阻力增值等，并根据各阻力间的比例关系计算风浪增阻和气动阻力的增加系数，得到额外路径的连接权值，如表2所示。

表2 额外路径的连接权值

为了提高计算速率，A星算法通常采用曼哈顿距离来评估与终点的距离，路径规划过程中往往忽略风力阻力的影响，为了同时体现气动阻力与风浪阻力的影响，选择欧式距离对起点与终点距离进行评估，结果见图5。

图5 欧式距离下评估起点与终点距离

图6 连接权值10倍时的规划路径

图6为正常气动阻力连接权值的10倍得到的路径规划结果，对比图6与图5发现，选择不同的气动阻力连接权值，路径规划结果差异极大。图6中路径规划航线长度极大增加，原因在于顺风航行时，气动阻力、能耗影响和连接权值均表现为负值，当连接权值选择错误时，导致单元格间的路径影响小于气动影响，相邻栅格间总连接权值为负值，致使路径规划错误。路径规划过程中考虑能耗，栅格间连接权值不大于0更接近实际，但是参数设置不恰当，则会产生不正确的连接路径。通过CFD方法获得的参数准确无误，因此，利用CFD仿真无人船在不同风向和不同风速下气动阻力权值具有十分重要的意义。图7为同时考虑风浪增阻、气动阻力和回转性能影响的仿真结果，路径规划合理，基本实现顺风航行。

图7 考虑风浪增阻、气动阻力和回转性能的路径规划

4.3 考虑海流影响的路径规划

通常情况下，无人船航速较低，并且需要储备较大功率用于保持低航速的稳定状态，考虑海流影响的路径规划，主要研究海流对航线控制难度和无人船能耗的影响。顶海流方向行驶，无人船需要消耗额外能量；顺海流方向行驶，无人船能量节约能耗，侧海流方向行驶，不仅会增加控制难度，而且需要消耗额外能量，因此，原则上认为侧流航行最差、顶流一般、顺流最佳。通过CFD仿真模拟海流和无人船在不同航向、不同航速下的函数关系，假设海流方向为正北，考虑海流影响的连接权值如表3所示。

表3 考虑海流影响的连接权值

考虑海流影响的路径规划结果见图8。

图8 考虑海流影响的路径规划

由图8可知，初步的点状航线规划优先选择顺海流方向行驶，并且可以保持航线的稳定性。航线连接权值的总和为能耗，点状航线转向4次，航线长度为336，能耗为299，经过优化之后，航线转向3次，航线长度为324，能耗为272，由此可见，经过优化考虑船舶回转性能够有效减小转向次数和航线长度，并且能耗也有所降低，这是因为航线规划尽可能选择顺海，节约无人船能量的部分损耗。航线规划的主要影响因素为输入参数的准确程度，提高顺流参数的精准程度可以进一步优化路径规划。