基于分层思想的AUV路径规划算法研究

徐言民 昌 政 赵俊超 关宏旭 王 岩

(武汉理工大学航运学院1) 武汉 430063) (内河航运技术湖北省重点实验室2) 武汉 430063) (长江镇江航道处3) 镇江 21200)

0 引 言

新世纪以来很多国家都把海洋列为国家的长远发展计划，为了在海洋的开发中夺得先机，很多都着力于发展更为精密的海洋运载工具.AUV是一种水下机器人，习惯上称为自主式水下航行器(autonomous underwater vehicle,AUV)，AUV最初主要应用于军事和科研，如水下搜索、监视、侦查、猎雷、作战海洋学、通信、导航、反潜作战等[1].后随着AUV技术的逐渐成熟，AUV在商业领域中也崭露头角，用作海底石油管道的监测、维修，以及钻井平台附近水域溢油监测等任务.随着科学技术的进一步发展，未来AUV将会朝着小型化、混合式、群体化、远程化、智能化等方向发展[2].

AUV作为无人航行器的一种，航行在水面以下不同的深度，水中的浅滩、暗礁、岛屿、洋流等都是AUV航行过程中的障碍物.为保证AUV的航行安全，必须对其进行航路规划[3].常用路径规划算法有模拟退火法、人工势场法、禁忌搜索算法、栅格法、C空间法等[4]，但在三维空间的路径规划使用不多.随着智能仿生算法的发展，如蚁群算法、粒子群算法、遗传算法等在复杂环境的路径规划中适用性更强，在三维空间路径规划中使用更加广泛.文献[5]对萤火虫算法进行了改进，提出了一种适用于AUV 在三维空间中的路径规划方法，相比传统路径搜索算法更加灵活，通过添加辅助规划算子，实现了AUV路径的快速规划.文献[6]运用遗传算法对水中机器鱼的路径规划做了研究.文献[7]将粒子群算法和遗传算法与蚁群算法相融合，较使用传统的蚁群算法规划三维航迹，提高了航迹规划的速度与效率，增加了算法的高效性.通过对蚁群算法的改进，提高了算法在三维空间的路径规划效率.三维空间路径规划存在环境建模困难、规划约束多等难题，使得算法搜索能力欠缺、结构复杂计算量大等问题.引入分层思想来表达空间环境，降低了环境建模的难度，简洁的算法结构能高效的规划出一条安全路径.

1 环境模型的建立

针对三维空间下的通航环境建模，一般有采用的方法有两种，一种是基于分层的思想，将三维空间投射到一系列的平面上，在二维空间的平面上进行环境建模[8]；另一种方式是采用单元分解的方法，将三维空间划分为单元格，对AUV的三维路径规划中，采用了八叉树模型划分空间[9-10]，朱大奇等[11-12]在研究AUV路径规划问题时，使用了均匀栅格模型，将三维空间分割为一个均匀的栅格地图.

建立空间直角坐标系O-XYZ表示整个空间环境，将XOY划分为n×n的网格，将海底地形的深度值与Z轴对应，因Z轴方向从原点向上，将相应地形的水深数据转为高度值，用高度值表示XOY平面上每一点地形情况，最后生成相应的环境模型，为简化计算，对所涉及的长度和距离等除以选取的艇长进行量纲—的量化.图1为25×25的三维环境模型示意图.

图1 三维环境示意图

2 路径规划算法设计

2.1 规划路径的表示

根据生成的环境模型，采用分层思想，将空间沿着坐标系O-XYZ中的X轴，以dx等分成若干个YOZ平面，见图2.

图2 空间分层示意图

由图2可知，X轴被等分为n份，一共可生成n个YOZ平面，((YOZ)1,(YOZ)2,…,(YOZ)k,…,(YOZ)n).从空间中一点(xS,yS,zS)到另一点(xE,yE,zE)的路径就可以表示为一系列在YOZ平面上的点的连线.

2.2 环境信息的转化

通过将空间沿X轴等分成n个平面，将空间中的环境信息也分散到每一个YOZ平面中，即整个空间环境将被n个YOZ平面分割，每一个YOZ平面都是空间环境的一个切面.根据每一个断面上点的高度值，可以确定规划路径在每个YOZ面上的可行区域，见图3.图中虚线为环境空间中某一切面YOZ.

图3 环境切面示意图

将每个切面再进行网格化处理，分成n×n的网格点，与之对应的建立一个n×n的矩阵用来存储每一个网格点的环境信息.因为高度值并不都是整数，为了便于矩阵存储信息，同时保证路径可行区域的安全性，将高度值进行了取整加一的膨化处理，图3实线表示处理后的空间切面.

图3将切面YOZ分为25×25的网格，同时建立一个25×25的0矩阵，将高度值不为0的路径不可行区域所对应的矩阵元素全部表示为1，见图4.0对应图4中“*”，1对应图4中“g”.

图4 切面YOZ对应矩阵示意图

2.3 路径评价函数的确定

在路径规划中，总是希望所规划的路径距离障碍物越远越好，路径的长度越短越好，为了找出空间中两点间的最优的路径，就必须要对路径进行评价.考虑到AUV的续航能力以及规划航线的安全性，评价函数分别从路径的总长度和路径的危险程度两个方面对规划的路径进行评价.

路径长度的评价函数 规划的路径在切面(YOZ)i-1上的点为pi-1其坐标为(xi-1,yi-1,zi-1)，在切面(YOZ)i路径点在上的点为pi其坐标为(xi,yi,zi)，则这两个相邻面之间的路径长度可以用式(1)进行表示.

(1)

在式(1)中由于dx=xi-xi-1是一个定值，连接每个切面中的路径点就可以组成一条路径，当AUV沿着选取的路径航行时，AUV的路径长度评价值F1计算模型见式(2).

(2)

危险程度的评价函数 在切面上的每个路径点，在一定步长r(r∈Z)内，都会存在R个网格点，假设这R个网格点中有m(m<8)个点为不可行点，即代表切面矩阵中为1的元素，则此时该路径点的危险就可以记为式(3)，当选取的路径点周围全部为不可行点，即Di=1时，此时表示选取的路径点不可行，需要重新选取路径点.

R=r2-1

(3)

把规划路径中所有路径点的危险度进行相加就可以得到整条路径的危险程度评价值F2计算模型见式(4).

(4)

路径的总评价函数 路径规划的目的是使路径长度与危险程度都达到最优值，对于建立的评价函数，就相当于对两个目标进行优化求解.最直观简洁的方法就是采用加权的方法，通过对两个不同的目标设置不同的权重，然后再相加，从而把两个不同目标的优化求解转化成一个目标的优化求解，最后得到路径规划总评价函数模型，见式(5).

minF=KF1+(1-K)F2=

(5)

F为路径总评价值，权重系数K取值范围[0,1]，根据不同的环境情况，危险度和路径长度评价函数权重不同.

2.4 算法的实现

((xi,y1,z1),(xi,y1,z2),…,

(xi,yi,zi),…，(xi,ya,zb))

(6)

式中：a，b为(YOZ)i平面中横纵坐标的编号，且(a≤n,b≤n)；n为(YOZ)i平面中被分割的最大网格数量.

(7)

(8)

Li取最小时，Lj和Lk的取值都最小.Lj取最小值表示所选取的路径点与上一路径点之间的距离最短，符合路径规划中整体路径最短的要求，Lk取最小值表示平面(YOZ)i-1与平面(YOZ)i之间的路径向量pi-1pi在总体方向上与向量SE比较接近，这也符合路径规划中路程最短的要求，具体方法见图5.此时平面(YOZ)i-1与平面(YOZ)i之间的路径长度就为向量pi-1pi的绝对值|pi-1pi|，即

|pi-1pi|=

(9)

图5 路径点选取方法

平面(YOZ)i中的路径点搜索出来后，连接点与终点E，得到一条新的向量piE，此时向量piE与平面(YOZ)i到平面(YOZ)n会重新产生一系列的点，把向量piE作为选取下一个路径点时的参考向量，重复上述选取路径点的方法，依次进行就可以得到(YOZ)i平面与(YOZ)i+1平面之间最短的安全路径，见图6.把每一段最短的安全路径依次连接起来就可以构建一条从起点到终点的安全路径.

图6 路径选取示意图

3 路径规划

本文将路径规划的起终点设定在了环境障碍物两侧，起点坐标设置为[1,8,6]，终点坐标设置为[25,23,10],权值K=0.5.使用MATLAB软件对模型进行求解，为了验证所设计算法的效果，使用仿生算法中蚁群算法与本设计算法进行比较，见图7.

图7 路径规划结果示意图

由图7可知，本算法与蚁群算法均能完成路径的规划.从规划路径的长度进行比较，本算法的规划路径长度较蚁群算法的短；从规划路径中航向变化的改变幅度来看，本算法的规划路径中航向变化幅度较蚁群算法小；整体看来，本文所设计算法规划结果较蚁群算法要好，但对于规划路径中航向改变的频繁程度，两种算法都需要有所提高.

4 规划路径的优化

对应本文所建立的规划模型，规划航路为D维向量加起始点的一组向量.为了保证规划路径的精度，在规划路径时设置的维数较多，规划结果呈现出曲线或者较多段线段的形态，这也导致了规划的路径中航向变化频繁的问题，实际中并不适用.为了更贴近实际，仍需要对规划路径进行优化.

所求路径可表示为P=(p1,p2,…,pn),包括起终点，路径一共要穿过n个YOZ平面.以终点为基点，跳过相邻路径点，按反向顺序选取路径点进行检验，判断与构成线段所穿过路径点与间的所有YOZ平面是否均为可行区域，即线段与平面交点均位于相应平面的可行区域内，则从路径P中剔除与相邻的上一个路径点，选取下一个路径点pn-3进行检验;否则保留上一个路径点，再重新以为基点，重复上述操作.直至检验判断遍历至起点为止，就可得到一条优化后的路径P′,见图8.

图8 优化后路径示意图

5 结 束 语

引入分层的思想重新对环境进行表达，提出了一种适用于复杂水下三维环境的AUV路径规划方法.通过仿真实验，验证了所提出的路径规划方法的可行性，且较于常规的蚁群算法，此算法结构更简单高效，仿真结果更好，提出的路径优化方法有效减少了规划路径中的转向点，解决了频繁转向的问题，使规划结果更具实用性.