无人船艇航线自动生成研究现状及展望

张树凯, 刘正江, 蔡 垚,4, 史国友, 梁伟珍2,

(1.上海海事大学 商船学院， 上海 201306； 2.招商局集团 招商蛇口邮轮事业部， 深圳 518067；3.大连海事大学 航海学院， 辽宁 大连 116026； 4.交通运输部 政策研究室， 北京 100736)

无人船艇可承担大范围、长时间和低成本的海洋作业任务。2007年美国海军就发布了《海军无人艇计划》。[1]2012年9月，欧盟委员会资助挪威海事技术研究所、查尔默斯大学等8家单位联合开展名为“MUNIN”[2]的研究项目，该项目以200 m散货船为研究对象，旨在提出无人驾驶船舶的设计概念并搭建自主航行系统框架。挪威航运巨头威尔森(Wilhelmsen)和康士伯(Kongsberg)于2018年8月投入运营全球首家无人船航运公司“Massterly”，业务涵盖设计、开发、控制系统、物流服务和船舶运营等方面。[3]

无人船艇在水面执行任务时面临着许多独特的挑战，其研究属于多学科交叉、多领域融合的综合项目，包括艇型设计、水面物标探测识别、自动避碰避障、运动控制、路径规划等多个方面[4]，近年来许多专家学者取得了卓有成效的研究成果。全自主型无人船艇是其发展的终极目标，要求其能够自主完成任务，航线自动生成是自主作业研究中的重要组成部分和关键技术之一。本文先阐述国内外无人船艇航线自动生成的研究现状，然后对其中关键的两个步骤分别加以小结，并在此基础上，对未来的研究方向予以展望。

1 无人船艇航线自动生成研究现状

传统的航线设计主要依靠人工分析纸质海图，通过查阅《世界大洋航路》《航路设计图》《航路指南》等航海图书资料中的航路和航法，手工绘制航线。这种传统的航线设计方法不仅效率低，且航线的质量主要依靠航海人员的业务水平和工作态度。

随着船舶智能化的发展，国内外专家学者开始尝试将智能算法应用到航线设计中，探索航线自动生成问题，取得了卓有成效的研究成果。

无人船艇的航线自动生成是指基于任务要求，在一定的约束条件下，按照安全性、经济性的原则自动地规划从起点到终点的无障碍路径。目前，航线自动规划的平台一般基于电子海图、雷达图像以及通过卫星等拍摄的大范围水域照片和热敏图像，采用的算法包括Dijkstra算法、A*算法等启发式搜索算法、蚁群算法、遗传算法等仿生优化算法，以及可视图法、人工势场法、模拟退火算法等。

1.1 基于电子海图平台的航线自动规划

在电子海图显示与信息系统(Electronic Chart Display and Information Systern,ECDIS)已广泛应用的今天，ECDIS中蕴含的丰富数据成为航线自动生成研究的重要数据源之一。[5]基于ECDIS平台的航线自动规划首先从电子海图中提取岸线、水深等数据，将ECDIS划分为可航和不可航水域，其中：陆地、岛屿等为不可航水域，满足安全水深要求的为可航水域；然后在可航水域中采用智能搜索算法搜索最短路径。

文献[6]采用二维栅格化模型构建海洋环境，将海图离散化为小型网格，并根据水深等条件将每个网格定义为可航或不可航，然后采用双惩罚函数和距离函数对航迹长度、路径平滑度等进行处理，提出一种基于遗传算法的多目标优化路径规划算法。类似地，文献[7]综合考虑安全性约束、终点姿态约束等定义路径规划公式，并采用遗传算法设计无人艇路径规划求解问题。文献[8]和文献[9]提出一种动态网格模型，将方格属性分为完全可航、不完全可航和完全不可航，采用8字节表示每个方格与其邻接的8个方格之间的连通性，然后基于二分查找法进行路径寻优。文献[10]以“航行带”宽度为单位进行海图网格的划分，以避免生成的航线穿越危险区域，然后采用蚁群算法在可航网格中搜索最短航线。文献[11]根据海图比例尺的大小确定网格尺寸的大小，并采用蚁群算法和遗传算法组合的方法在可航网格中搜索最短航线。文献[12]依据S-57的规定对障碍物边缘进行扩充并采用栅格表示障碍区和可航区的环境信息。文献[13]将分析水域网格化，通过叠加船舶航迹统计网格内轨迹点频数，然后采用A*算法规划航线。文献[14]和文献[15]先采用栅格划分海域并识别碍航物所在的方格，然后采用8邻域边界追踪法提取碍航物包围盒，之后采用Elasticity算法在由障碍物包围盒和可航水域组成的环境模型中搜寻最短路径，在此基础上，文献[16]和文献[17]基于天气和海况因素等海域模型构建限制搜索区域，通过改进Z3-2算法快速求取多边形凸壳建立简化的环境模型。文献[18]～文献[20]依据电子海图数据将航行环境分为碍航区、缓冲区和安全区域，然后采用绕行碍航区的航路二叉树方法研究最短航线的生成问题。在此基础上，文献[21]和文献[22]将海域潮位模型融入海图静态水深，构建基于瞬时水深模型的碍航区动态提取方法。文献[23]和文献[24]考虑无人艇的操纵性和航行时的碰撞等风险采用栅格法和Voronoi图法进行路径规划。文献[25]通过栅格动态细化电子海图的方式建立环境模型，然后采用改进势场法搜索最优路径。文献[26]采用动态栅格法建立环境模型，采用Dijkstra算法进行路径规划。文献[27]利用分层和激活值相结合、分层和遗传算法相结合的方法进行路径规划。文献[28]基于栅格化的光栅电子海图采用迷宫算法研究航路优化问题。文献[29]通过增加转向次数的惩罚因子对这一算法进行改进。

1.2 基于雷达图像的航线自动规划

文献[30]～文献[32]基于雷达图像对无人船艇路径规划问题进行研究，对环境进行建模时利用自适应阈值法和边缘保持的去噪平滑算法对雷达图像进行处理，从而辨识出可航水域。

文献[30]以湖上和海上的典型雷达图像为环境模型，通过引入距离启发信息和限定转角以兼顾路径最短和无人艇的操控性能，采用改进的快速扩展随机树算法进行路径规划。文献[31]通过雷达、水下声呐和多摄像头构建立体视觉系统检测水面和水下障碍物生成航行水域的障碍物地图，并采用基于可视图的A*算法进行路径规划。文献[32]基于雷达图像采用Dijkstra算法进行路径规划。

1.3 基于广域图像的航线自动规划

文献[33]～文献[39]基于卫星等拍摄的大范围水域照片或热敏图像进行无人船艇航线自动规划的研究，对环境进行建模时采用MATLAB等工具将卫星照片、热敏图像转换为黑白二值图像，其中:陆地、岛屿等不可航水域转换为“黑色”，可航水域转换为“白色”，然后在可航水域中进行路径规划。

文献[33]基于卫星照片采用Dijkstra算法在可航水域中搜寻最短路径。文献[34]考虑无人艇动力学和回转性能方面的限制，提出角度限制下的快速步进方格算法。文献[35]～文献[37]同样采用改进的快速步进方格算法对无人艇的路径规划进行试验。文献[38]也考虑了无人艇回转性能的限制，为使规划的路径平滑，提出有限角A*算法并基于卫星热敏图像进行路径规划试验。类似地，文献[39]考虑无人艇转向时的角速率限制提出一种改进的Theta*算法并基于卫星照片进行路径规划试验。

1.4 基于模拟环境的航线自动规划

文献[40]～文献[44]在模拟环境下对无人船艇航线自动规划问题进行研究。文献[40]采用广义Voronoi图在模拟环境下进行航线自动规划，并与采用A*算法规划的路径进行性能比较；文献[41]采用栅格图模拟无人艇航行环境，采用蚁群算法搜寻最短路径；文献[43]利用遗传算法和人工势场法在栅格化的模拟环境中设计无人艇路径规划方法；文献[42]针对人工势场法存在的目标不可达和局部极小值点问题提出一种改进人工势场算法并在随机生成障碍物的模拟环境下进行路径规划试验，文献[44]也做了类似研究。

1.5 局部路径规划研究

无人船艇的局部路径规划是指无人船艇在航行过程中遇到其他船舶、漂浮物等障碍物时，通过采取适当的避碰行动驶离原规划路径避免危险而实时规划的路径。文献[45]～文献[48]等对无人艇的局部路径规划问题进行研究，由于无人船艇的局部路径规划问题属于智能避碰的研究范畴，因此不对此进行详细综述。

2 环境建模方法

通过对国内外无人船艇航线自动生成研究现状综述可看出，无论基于何种平台，航线自动生成方法大致遵循两个基本步骤：

1) 建立航行水域环境模型。

2) 搭建好的环境模型中依据优化目标根据设置的起点和终点搜寻最短路径。

第1步建立环境模型的主要目的是将真实的航行环境通过适当的方式转化为适用于航线规划的简化模型，一般是从图形学角度出发，其中最重要的是障碍物的表示方法。根据障碍物表示方法的不同可分为基于栅格化模型的建模方法和基于障碍物包围盒模型的建模方法两类。

(1) 基于栅格化模型的环境建模方法将ECDIS、雷达图像、卫星热敏图像等进行细粒度的网格划分，从而将空间分割成可航行的自由空间和不可航行的障碍物空间。例如，文献[6]～文献[13]采用正方形的网格对电子海图进行栅格化。针对网格大小的问题，文献[10]以“航行带”宽度为单位，文献[11]根据海图比例尺的大小确定网格尺寸的大小，文献[12]在采用栅格表示环境信息时对障碍物区域的边缘进行扩充并息。

(2) 基于障碍物包围盒模型的环境建模方法将航行环境中由复杂多边形表示的障碍物简化为可包围该障碍物的包围盒，例如包围圆、包围凸多边形等。在简化的过程中，为后续路径寻优的方便，一般将船舶简化为一个质点，同时将障航物的边界依据船舶参数进行膨胀处理。简化后的障碍物在方便求取切线的同时减少碰撞检测次数，有效提高路径寻优效率。文献[49]和文献[50]将岛礁、沉船等障碍物采用最大包含圆形表示。文献[51]采用最小凸多边形包围盒表示障碍物，创新之处在于通过限定搜索区域减少障碍物数量。文献[52]也通过建立安全区的方法减小搜索范围、提高效率，然后采用最小包围圆表示碍航物。除考虑陆地、岛礁等固定障碍物外，文献[16]和文献[17]综合考虑天气和海况因素等海域模型提取潜在的碍航区，构建由多边形凸壳表示的环境模型。文献[21]和文献[22]综合考虑海图水深和潮位模型，构建基于瞬时水深模型的碍航区动态提取方法。

3 最短路径搜索算法

无人船艇航线自动生成主要步骤中的第2步是在搭建好的环境模型中，依据优化目标，采用启发式搜索算法、仿生优化算法等搜寻最短路径。

在基于栅格化环境建模的研究中，文献[28]和文献[29]通过改进的迷宫算法进行最优航线的搜索，但是由于该搜索算法基于单位格点进行逐步搜索，因此航线可能不是最短的。文献[8]～文献[13]采用Dijkstra算法、A*算法、二分法、蚁群算法、遗传算法等进行最短航线搜索，但随着海域的增大，一是网格的数量以平方级迅速增长，计算量迅速增大，二是随着海域的增大和复杂化，岸线的边缘检测与方格可航性的判定计算量也随之增大，效率明显下降。

在基于障碍物包围盒方法进行环境建模的研究中，文献[14]～文献[22],文献[49]～文献[54]通过求取碍航物包围盒之间的公切线，然后采用Dijkstra算法、蚁群算法、遗传算法等在所有公切线中搜索最短航线；或者通过求取绕行碍航物多边形区的左、右子结点建立航路子二叉树，然后通过遍历航路二叉树的方法搜索最短航线。这两种方法在小范围海域时，由于碍航物的数量较少，碍航物的包围盒及其公切线、航路二叉树的求取工作量相对较少，具有较好的适用性；但当面向全球大范围水域的航线自动生成时，随着碍航物数量的增加和形状的复杂化，求取碍航物包围盒和其公切线、航路二叉树的计算量急剧增大，算法的效率也随之下降。

4 研究总结与展望

现阶段的航线自动生成方法研究模式可大致概括为：将电子海图或从雷达、卫星获取的图像进行栅格化或二值化阈值处理，将处理后的电子海图或图像分为可航和不可航水域，然后在可航水域中采用智能搜索算法(如Dijkstra、A*算法等)、航路二叉树法、人工势场法、可视图法等搜索从指定起点到终点的最短路径。

随着太阳能、风能等清洁能源作为无人船艇的动力驱动源，无人船艇的续航能力大大增强，且随着船舶智能化水平的不断提高，大型无人驾驶船舶也逐步有了实现的可能。因此，从宏观角度出发面向大范围水域且符合航海实际的航线自动生成方法是亟待研究的一个重要问题，现有的技术和手段仍需关注以下问题：

1) 传统的面向小范围水域的航线自动生成方法具有一定的局限性，需补充从宏观角度出发面向大范围水域的航线自动生成方法。传统的航线自动生成方法在进行可行性验证时都是面向小范围的水域，但是，随着海域的增大，在面向全球海域范围时，将电子海图、卫星热敏图像等进行栅格化方法的网格数量以平方级迅速增长且岸线的边缘检测与方格可航性的判定计算量也随之增大，效率明显下降；通过求取障碍物包围盒和包围盒公切线、航路二叉树的方法，随着碍航物数量的增加和形状的复杂化，计算量也急剧增大，算法的效率也随之下降。

随着无人船艇研发技术的不断提升，船舶的尺度更大、续航能力更强和安全性要求更高的无人驾驶船舶正逐步成为可能。因此，从提高算法效率和符合无人驾驶船舶发展趋势的角度出发，必须要探索一种从宏观角度出发适用于全球海域范围的高效航线自动生成方法。

2) 传统的航线自动生成方法忽视了在航海实践中必须遵守的航线设计原则和航行规则，需探索基于海量船舶历史轨迹数据和数据驱动技术的航线自动生成方法。传统的航线自动生成方法主要基于电子海图平台、遥感图像等，通过栅格化方法或提取障碍物包围盒的方法识别出可航水域和不可航区域，然后在可航水域中采用智能搜索算法寻找出从指定起点到终点的最短航线。在该模式下生成的“最佳航线”仅是计算机图形学角度下的最佳航线，但理论分析的结果和实际应用之间还存在一定差距。例如，采用智能搜索算法提取的航线无法智能识别分道通航水域和推荐交通流方向等国际海事组织规定的需要特别注意的航路或航道，从而造成在这些地区无法按照规则行驶。

船舶轨迹数据中存储丰富的航行相关信息是真实航行情况的客观反应，如果能够充分地分析、挖掘这些信息，从已被实际航行证实可行的历史轨迹数据中提取出航路相关信息，则可为航线自动生成提供重要的借鉴和参考，同时，这也符合航线设计时“参考他船具体航行经验”的思想。因此，在轨迹数据呈现出爆炸性增长趋势且全球联网的船舶轨迹数据库已建立的今天，在数据科学崛起的大背景下，借鉴大数据策略和管理分析模式，采用轨迹分析与处理技术，提出基于数据驱动技术和海量船舶历史轨迹数据、且符合航海实际的航线自动生成方法势在必行。

3) 传统的航线自动生成方法忽略了航线安全检测环节，需综合考虑宏观交通流特征、船舶运动参数以及风浪流作用下的船舶漂移量，建立具有一定宽度的“航线领域”模型，并基于电子海图数据对航线所在领域自动进行安全检测。文献[55]～文献[61]基于船舶自动识别系统(Automatic Indentification System，AIS)数据对船舶定线制、船舶习惯航路等问题进行研究，然而，船舶在实际航行中并非严格按照生成的航线行驶，而是会有一定的偏移量，特别是在转弯的时候需要一定的旋回水域，传统的航线自动生成方法忽略了这一点。

因此，需要综合考虑航迹带宽度、交通流特征参数、船舶自身运动参数、风浪流作用下的漂移量以及偏航极限和航道安全富余宽度等建立“航线领域”模型，然后根据国际海事组织(International Maritime Organization，IMO)对航线安全检测的要求，基于国际航道组织(International Hydrographic Organization，IHO) S-63标准的策略结构和工作流程对ECDIS数据进行解析，通过提取“航线领域”内的水深、障碍物等点、线、面海图要素进行航线安全检测，确保自动生成航线的安全性。

5 结束语

本文对无人船艇航线自动生成方面的国内外研究现状进行系统的梳理与总结，介绍基于不同平台的无人船艇航线自动规划研究现状，阐述并分析航线自动生成中的主要步骤。本文还通过总结现有航线自动生成技术的研究模式，分析现有方法的不足之处，并对未来的研究方向进行展望，对可行的研究思路提出建议。随着船舶智能化水平的逐步提高，无人船艇的研发也在不断加快，航线自动生成相关理论和技术也将逐步提高、完善，为工业化应用奠定基础。