基于电子海图栅格化的无人水面艇全局路径规划

范云生， 赵永生， 石林龙,2， 张 月

(1.大连海事大学 信息科学技术学院， 辽宁 大连 116026； 2.上海船舶运输科学研究所， 上海 200135)

基于电子海图栅格化的无人水面艇全局路径规划

范云生1， 赵永生1， 石林龙1,2， 张 月1

(1.大连海事大学 信息科学技术学院， 辽宁 大连 116026； 2.上海船舶运输科学研究所， 上海 200135)

为解决无人水面艇自主避碰决策中的全局路径规划问题，提出一种基于电子海图栅格化建立环境模型的遗传算法全局路径快速搜索方法。通过对电子海图数据中的海洋环境信息进行提取，采用栅格法建立路径搜索空间的环境模型，并使用栅格标号对路径个体进行编码，利用一种随机快速搜索产生初始种群的改进遗传算法进行路径搜索，提高无人水面艇全局路径规划的收敛速度和优化效率。试验结果表明，采用改进遗传算法进行基于电子海图栅格化的无人艇全局路径规划具有一定的合理性和有效性。

无人水面艇；路径规划；电子海图；栅格法；改进遗传算法

Abstract: A global path fast search method based on genetic algorithm is proposed for the Unmanned Surface Vehicle (USV) to avoid collision autonomously. The environment model is established by rasterizing electronic chart. Marine environment information in electronic chart data is extracted. Path search space is constructed. Path individual is encoded according to the code of grid. An improved genetic algorithm that adopts heuristic random initialization population method to generate initial population is used to achieve the convergence speed and optimization efficiency of USV global path planning. The effectiveness and practicality of the algorithm are verified by experiments.

Keywords: USV； path planning； electronic chart； grid model； improved genetic algorithm

无人水面艇(Unmanned Surface Vehicle, USV)作为监测海洋环境、维护海洋权益的现代化装备，具有广阔的应用前景，己成为国内外智能化海洋装备的研究热点。[1]在复杂多变的海洋环境中，自主规划出一条从起点到终点的较优的全局路径既是保证USN安全航行和顺利完成指定任务的前提与基础[2]，也是无人水面艇智能控制技术中自主避碰决策的重点研究内容之一。

目前，国内外相关学者都在对USV的全局路径规划方法进行深入研究，并已取得一定的成果。文献[3]采用FAA*算法,在真实的卫星图像中解决USV的全局路径规划问题。文献[4]提出一种基于新BI算法的全局路径规划，并在电子海图环境中对该算法进行验证。文献[5]在考虑海洋环境和USV最大曲率的地图中设计基于A*算法的3-D曲率路径规划算法。文献[6]研究一种在网格地图中基于有限角速率的θ*路径规划算法。文献[7]在栅格环境模型中应用改进的蚁群算法完成USV的全局路径规划，验证算法的有效性。文献[8]为减少全局路径规划的时间，提出一种基于电子海图的距离寻优Dijkstra路径规划算法。文献[9]将遗传算法和分层模型的激活值应用到USV全局路径规划中，在实际地图中进行验证。文献[10]研究一种基于势场动态栅格法的USV全局路径规划方法。文献[11]研究一种基于进化遗传算法的USV全局路径规划算法。此外，还有一些USV全局路径规划算法，如基于遗传算法的人工势场法[12]、基于A*算法的速度避障法[13]、基于电子海图的A*算法[14]、基于可视图的A*算法[15]和人工鱼群算法[16]等。

为利用真实的海洋环境信息实现USV的全局路径规划，提出一种基于电子海图栅格化建立环境模型的遗传算法全局路径快速搜索方法。通过电子海图提供大量详细、准确的数字化海洋环境地理信息数据，对USV工作空间中包含陆地、岛屿和海岸等信息的海洋环境进行准确描述。在运用栅格法建立环境模型的基础上，利用改进遗传算法进行路径搜索，以降低全局路径规划的空间开销，提高USV全局路径规划的收敛速度和优化效率，为USV的自主智能避碰决策提供参考。

1 海洋环境模型的建立

对电子海图中的海洋环境地理信息进行统一描述，并采用栅格法进行环境建模。栅格化的电子海图一致性表述是提高路径搜索算法效率的基础。

1.1海洋环境信息的描述

在能反映真实海洋环境信息的环境模型中进行USV自主避碰决策的准确性取决于对多种海洋环境信息描述的精准程度。依据S-57标准定义的电子海图是一种便于进行数据交换和传输的高度压缩的数据格式，其数据结构比较复杂。因此，将电子海图应用到USV全局路径规划中，需按其对数据解析、读取和存储的标准，设计一种基于电子海图的环境数据提取和建模方法。提取电子海图中的海洋环境数据信息并对其进行描述的过程见图1。

图1 海洋环境信息数据的描述方法

S-57标准电子海图文件包括数据集的描述信息、特征记录和空间记录，利用ISO 8211 lib开源库读取电子海图文件中的每条记录，特征记录用vector容器存储，空间记录用map容器存放，将包含陆地和岛屿等障碍物的海洋环境空间描述成USV能识别的海洋环境信息。

1.2栅格法建立环境模型

利用电子海图中的海洋环境地理信息数据构建的USV工作空间是由复杂几何图形组成的，使得大多路径搜索算法都不能直接被利用，因此需解决全局路径规划中的环境建模问题，对海洋环境信息进行栅格化，转换成几何关系简单的环境模型，以提高路径搜索算法的效率。采用栅格法进行环境建模，设计适当的栅格大小、合适的编码方式及表示方法，用大小相等的栅格将电子海图量化成具有可变分辨率的栅格网图。在设定完栅格大小后，对组成环境模型的栅格进行编码，建立的栅格模型见图2。

图2 建立的栅格模型

图2中:内部含有碍航物的栅格称为障碍栅格，用黑色表示；内部不包含任何碍航物的栅格称为自由栅格，用白色表示。从栅格网络左上角的第1个栅格开始编号为0，按照从左到右、从上到下的顺序依次为每个栅格编号，则编号将与环境空间中的栅格一一对应。

USV的工作环境空间经栅格化后转化为栅格地图，栅格法的一致性和规范性使环境空间简单化，将全局路径规划问题转化为在栅格网中寻找2个栅格节点之间的最优路径问题。

2 路径规划算法的改进及实现

遗传算法是一种模拟自然界中生物的遗传和进化过程的优化搜索算法，通过对路径规划问题解集的种群进行编码和模拟生物界中的优胜劣汰、基因交叉及基因突变等过程，逐代进化出更好的种群，使搜索过程向最优解逼近，最终收敛于最优路径的近似解。

2.1初始种群的产生

在传统的遗传算法中，初始种群个体的生成是完全随机的，包括很多环路和不可行的路径，这会增加算法的运行时间,降低搜索速度和效率。对此，采用一种启发式随机初始化种群方法，其路径个体采用变长度编码方式，具体步骤如下。

1) 采用十进制编码与浮点数编码相结合的方法对USV栅格化后的海洋环境中的航行路径进行编码，其结构为

ni1(xi1,yi1)→…→nix(xix,yix)→…→nili(xili,yili)

(1)

式(1)中:nix(xix,yix)(x=1,2,…,li-1)为路径上中间路径点所在栅格的序号和经纬度坐标值，路径长度li可变。

根据当前路径点的栅格序号nix，目标点的栅格序号nili和栅格网络的总列数nLine，计算当前路径点和目标点在栅格网中的行号nLastRow和nEndRow及列号nLastLine和nEndLine，目标点与当前路径点的位置关系为

(2)

2) 在栅格网中，相邻2个栅格点的位置关系用8种方向表示，当前栅格的序号为M，数字与上述位置关系相对应(见图3)。

图3 相邻栅格的位置关系图

图3中， 8个方向上的栅格作为下个路径点的备选栅格，根据当前路径点与终点的位置关系，以正态分布概率随机选择一个栅格作为下个路径点。

3) 判断该方向的栅格是否为自由栅格，从而决定USV的下个可行路径点，重复循环上述步骤，直至到达路径终点。

这种启发式随机初始化种群的方法利用个体路径的路径点均为自由栅格的特点，因此可提高初始路径的可行性，避免初始路径出现反复和原地旋转，加快遗传算法搜索最优路径的速度。

2.2适应度函数的选取

在全局路径规划过程中需选取合适的适应度函数，即将目标函数作为评价群体中路径优劣的标准和依据。设计适应度函数时应综合考虑安全性(即碰撞危险度)、经济性(即路径长度)和光滑性(即航向变化频率和范围)。

Value(P*)=min[f1(P),f2(P),f3(P)]

(3)

式(3)中：目标函数f1(P),f2(P),f3(P)分别为USV航行路径的经济性、光滑性和安全性。

1) 路径长度f1(P)=Length(Pi)。

(4)

式(4)中：mi为第i条路径Pi中不可航行路段的个数；C1为适当的正数。

2) 路径光滑性f2(P)=Turning(Pi)。

(5)

式(5)中：路径点数li>2；aij(j=2,…,li-1)为pi(j-1)pij与pijpi(j+1)的夹角0≤aij<π；ki为aij中≥π/2的个数，即当航向角≥π/2时，对适应度值进行惩罚；mi为路径Pi中不可航行路段的个数；C2为适当的正数。

3) 安全性f3(P)=Danger(Pi)。

(6)

当路径Pi可行时，Danger(Pi)=1/di，其中di>0为无人艇航行时应与障碍物保持一定的安全距离，该安全距离与无人艇的大小有关。当路径Pi不可行时，Dange(Pi)=miC3，其中:mi为路径中路径段与障碍物距离小于安全距离的个数；C3为适当的正数。

2.3种群的更新与进化

在传统的遗传算法中，生物遗传进化过程中的优胜劣汰是通过选择适应度高的个体模拟的，新生物个体的产生是通过交叉和变异算子模拟的，这3个基本遗传算子完成种群的进化和更新。然而,对于复杂的海洋环境，仅采用基本的算子难以规划出较优的无碰路径。因此，在传统的更新与进化中加入删除和插入算子，进一步优化输出的路径。

2.3.1选择算子

利用传统遗传算法中的选择操作，以种群中每条路径的适应度值为概率，遍历每个个体的适应度值，选择概率大的第i个个体进入下一代。

2.3.2交叉算子

采用单点交叉法进行个体的交叉，如选取式(7)中的2条路径，将按一定概率随机选择的种群中第i个个体的第x个路径点nix(xix,yix)与第j个个体的第x个路径点njy(xjy,yjy)替换，重新组合成新的路径(见式(8))。

(7)

(8)

2.3.3变异算子

为避免过早地陷入局部收敛，按一定概率随机选择第i个个体上的第x个路径点nix(xix,yix)进行变异，即

ni1(xi1,yi1)…nix-1(xix-1,yix-1)…nix(xix,yix)…

nix+1(xix+1,yix+1)…nili(xili,yili)

(9)

将第x个路径点nix(xix,yix)的上一个路径点nix-1(xix-1,yix-1)和下一个路径点nix+1(xix+1,yix+1)作为可变异范围，采用与初始化种群生成新路径点方法相同的方法，随机搜索一个自由栅格作为变异后的新路径点。

2.3.4删除算子

删除操作可减小个体的路径长度，增强路径的可行性，提高算法搜索效率。2种删除算子见图4。

a) 删除算子1

b) 删除算子2

在图4a中，个体路径中的路径点所在的2条路径段都是不可行的或其中一条路径不可行，删除该路径点之后，连接相邻的路径点，变成可行路径段；在图4b中，个体路径附近无障碍物却出现转弯的情况,删除序号为44的路径点之后，连接相邻的路径点40和74，生成新的路径段,若其是可行的，则删除该路径点，否则不作操作。

2.3.5插入算子

当海洋环境中的障碍物较多时，出现不可行路段的可能性较大，且删除操作不能完全修复不可行路径，插入操作可进一步对个体中的不可行路段进行修复，从而快速生成有效的可行路径(见图5)。

图5 插入算子示意

在图5中，当有路径段穿过障碍物时，选择一个自由栅格作为新的路径点插入后,可使路径变成可行路径，从而修复该路径。

3 试验验证及结果分析

3.1构建海洋环境

在VS 2010和SQL SERVER 2008环境下完成基于电子海图栅格化的USV全局路径规划算法验证试验。海图中的物标数据信息由以下2个电子海图文件中的数据共同组成。

1) C1100103.000海图的经度范围为116.5°W～133.0°E,纬度范围为21.5°S～41.5°N，编图比例尺为1∶2 300 000，坐标乘数因子为10 000 000，水深乘数因子为10。

2) CN110011.000海图的经度范围为117.000 413°W～127.150 630°E,纬度范围为35.300 066°S～41.000 202°N，编图比例尺为1∶1 000 000，坐标乘数因子为100 000，水深乘数因子为10。纬度范围35.846 786°N～39.846 786°N和经度范围117.474 388°E～125.474 388°E所包含的区域设为海洋环境建模空间，涵盖陆地、岛屿、海床和等深线等基本的碍航物信息。根据USV工作空间范围建立基于电子海图栅格化的海洋环境模型(见图6)。

在图6中，等深面范围为-10～10 m，等深线范围为10 m，安全距离为10 m，USV工作空间的范围设定为从起点(120.171 013°E，38.621 632°N)到终点(123.532 463°E，37.019 115°N)的数据信息，搜索数据库生成以该起点和终点为中心点、经度范围为4°(120.187 309°E～124.187 309°E)、纬度范围为2°(38.219 494°N～40.219 494°N)的海洋环境(如图6a所示)，选择栅格为100×200，栅格化后建立的海洋环境模型如图6b所示。

a) 电子海图海洋环境

b) 栅格化后的海洋环境

3.2试验验证方法

利用软件VS 2010编程实现基于电子海图的无人艇全局路径规划软件程序流程(见图7)。试验中实现的主要功能有：设置无人艇和电子海图显示的环境信息；根据无人艇的参数信息获取并显示电子海图数据库中碍航物的物标空间几何信息，生成无人艇航行的海洋环境空间；完成海洋环境模型的建立，设置栅格大小，栅格化电子海图；启动遗传算法程序，完成路径规划任务。

图7 全局路径规划程序流程图

图7中，进行具体的无人水面艇全局路径规划的步骤为：

1) 设置无人艇起始点和目标点等相关信息及电子海图显示参数等。

2) 搜索电子海图数据库，查询碍航物数据表，生成无人艇航行的海洋环境信息并显示。

3) 设置栅格大小，对电子海图进行栅格化处理，生成电子海图栅格图。

4) 设置遗传算法的初始化参数，包括迭代次数、种群规模、交叉概率Pc和变异概率Pm等。

5) 初始化种群，产生初始路径，进入遗传算法迭代循环。

6) 从无人艇的安全性、路径的光滑度和路径长度等3个方面综合评价种群个体的适应度，计算适应度函数值。

7) 对种群中的路径进行选择、交叉、变异、删除和插入等进化操作，优化种群。

8) 迭代完成，输出全局路径规划的结果。

3.3试验结果分析

在试验中，设置USV的起点位置为(123.131 073°E，39.236 572°N)，终点位置为(121.243 544°E，39.202 417°N)，USV的初始航向为050°，航速为8 kn，遗传算法初始化种群选用20个个体，终止条件为迭代100代，个体编码采用变长度编码方式初始种群，个体路径段数不固定，交叉概率为0.7，变异概率为0.3，以安全、光滑和路径最短为寻优目标，采用拐点尽量少的原则对路径进行优化，完成参数设定。

基于栅格法建立的海洋环境模型见图8，规划的路径点坐标见表1。

图8 基于栅格法建立的海洋环境模型

路径节点节点栅格序号经度/(°)E纬度/(°)N开始节点09947123．13107339．236572节点112940122．99730738．929493节点216061121．41731338．609493节点316042121．03730838．609493节点413433120．85730738．869495节点511834120．87731239．029495终止节点610052121．24354639．202415

表2为图8中的路径在算法进化过程中种群适应度函数值的变化。当进化代数接近100代时，种群路径的平均适应度函数值和最优路径的适应度函数值几乎不再变化，且随着进化代数的增加，种群的平均适应度函数值越来越趋于最优值。

表2 适应度函数值变化

由试验结果可知，在实际的海洋环境下，即使是在碍航物较多的工作空间中，通过使用栅格法将电子海图转化为栅格地图，可简化USV的工作环境，利用改进遗传算法进行路径搜索，最终输出的路径也能准确地避开海洋环境中的碍航物，保证无人艇航行时的安全性；同时，在没有碍航物的可航行区域，规划出的无人艇航行路径呈直线形状，满足路径最短的要求。此外，规划出的路径的拐点较少且拐角均为钝角，保证了路径的光滑性。最终的试验结果验证了算法的可行性和有效性。

4 结束语

本文将电子海图数据与智能避碰决策方法相结合，提出一种基于电子海图栅格化的改进遗传算法无人艇全局路径规划方法。

1) 利用电子海图提供的数字化海洋环境地理信息数据对USV工作空间中的海洋环境进行准确描述，并以大小相等的栅格将环境信息量化成具有一定分辨率的栅格网，建立USV工作空间的环境模型，减小全局路径规划中的环境模型空间开销。

2) 在能反映真实海洋环境信息的电子海图栅格化的环境模型中设计一种启发式随机初始化种群方法，根据自主、安全航行等要求，将经济性、安全性和光滑性等3个评价因子加入到适应度函数中，并在选择、交叉和变异等传统进化操作的基础上结合插入操作及删除操作对种群进行优化。

3) 在VC 2010平台上编写全局路径规划算法的程序。

试验结果表明，基于电子海图栅格化的改进遗传算法USV全局路径规划方法能加快路径规划的收敛速度，提高路径优化的效率，是一种合理、有效的USV路径搜索算法。

[1] YAN Rujian, PANG Shuo, SUN Hanbing, et al. Development and Missions of Unmanned Surface Vehicle[J]. Journal of Marine Science and Application, 2010,9(4):451-457.

[2] CAMPBELL S, NAEEM W, IRWIN GW. A Review on Improving the Autonomy of Unmanned Surface Vehicles Through Intelligent Collision Avoidance Manoeuvres[J]. Annual Reviews in Control, 2012,36(2):267-283.

[3] YANG JM, TSENG CM, TSENG PS. Path Planning on Satellite Images for Unmanned Surface Vehicles[J]. International Journal of Naval Architecture and Ocean Engineering, 2015,7(1):87-99.

[4] SONG L. Path Planning Research of Unmanned Surface Vehicle Based on Electronic Chart[J]. Journal of Information and Computational Science, 2014,11(17): 6245-6254.

[5] KIM H, PARK B, MYUNG H. Curvature Path Planning with High Resolution Graph for Unmanned Surface Vehicle[M]. Berlin: Springer Berlin Heidelberg, 2013：147-154.

[6] KIM H, KIM D, SHIN JU, et al. Angular Rate-Constrained Path Planning Algorithm for Unmanned Surface Vehicles[J]. Ocean Engineering, 2014,84(4):37-44.

[7] SONG CH. Global Path Planning Method for USV System Based on Improved Ant Colony Algorithm[J]. Applied Mechanics and Materials, 2014,568:785-788.

[8] 庄佳园, 万磊, 廖煜雷, 等. 基于电子海图的水面无人艇全局路径规划研究[J]. 计算机科学, 2011,38(9):211-214.

[9] 饶森. 水面无人艇的全局路径规划技术研究[D]. 哈尔滨:哈尔滨工程大学, 2007.

[10] 刘建. 水面无人艇路径规划技术的研究[D]. 镇江:江苏科技大学, 2014.

[11] 刘佳男. 基于进化遗传算法的无人艇避碰系统研究[D]. 大连:大连海事大学, 2015.

[12] 张玉奎. 水面无人艇路径规划技术研究[D]. 哈尔滨:哈尔滨工程大学, 2008.

[13] 卢艳爽. 水面无人艇路径规划算法研究[D]. 哈尔滨:哈尔滨工程大学, 2010.

[14] 王锦川. 自主式水面航行器导航与制导算法的研究[D]. 大连:大连海事大学, 2014.

[15] 陈超, 唐坚. 基于可视图法的水面无人艇路径规划设计[J]. 中国造船, 2013(1):129-135.

[16] 马文耀, 吴兆麟, 杨家轩, 等. 人工鱼群算法的避碰路径规划决策支持[J]. 中国航海, 2014,37(3):63-67.

GlobalPathPlanningforUnmannedSurfaceVehicleBasedonGridModelofElectronicChart

FANYunsheng1，ZHAOYongsheng1，SHILinlong1,2，ZHANGYue1

(1. School of Information Science and Technology, Dalian Maritime University, Dalian 116026, China; 2. Shanghai Ship & Shipping Research Institute, Shanghai 200135, China)

U664.82

A

2016-11-24

国家自然科学基金(61374114,51609033);辽宁省自然科学基金(2015020022);中央高校基本科研业务费专项基金资金(3132016022)

范云生(1981—)，男，辽宁丹东人，讲师，硕士生导师，博士，从事船舶智能控制理论与应用、无人系统测控技术等研究。 E-mail:yunsheng@dlmu.edu.cn

1000-4653(2017)01-0047-06