基于NSGA-II算法的AUV三维全局路径规划*

邹春明 张云雷 徐言民 关宏旭 赵俊超

(武汉理工大学航运学院1) 武汉 430063) (内河航运技术湖北省重点实验室2) 武汉 430063)(长江引航中心3) 无锡 214431)

0 引 言

自主式水下航行器(autonomous underwater vehicle，AUV)[1-3]是新的一代水下机器人，具有活动范围大、机动性好、安全、智能等优点，能够完成各种水下任务.路径规划研究是自主式水下航行器完成其任务的关键技术之一.路径规划可以分为两类：全局路径规划和局部路径规划.全局路径规划是在已知的环境中寻找可行的路径，通常优化路径是可行的，而局部路径规划则适用于环境未知或者部分未知的情况，在这种情况下，优化路径并不总是可用的.当前，仿生智能算法在AUV局部最优路径规划的应用己经相当成熟，而实现AUV三维全局最优路径规划，以保证其在海底的安全航行.

针对自主式水下航行器的路径规划研究，通常采用Dijkstra算法、A*算法、遗传算法、人工势场算法、模糊方法和粒子群优化算法[4-7]，但是传统的路径规划算法都存在一定的缺陷，例如，遗传算法在解决多目标优化问题时存在着编码复杂，搜索最优解效率低、耗时长等问题.NSGA-II算法(non dominated sorting genetic algorithm-II)能够较好地克服这种缺陷，表现出运行速度快，解集收敛性好的优点.

本研究针对AUV全局路径规划问题，通过分析海底地形建立了简单、高效的三维环境模型，根据AUV航行经济性和安全性原则建立了路径长度和威胁度评价函数模型，运用NSGA-II算法的快速Pareto排序和拥挤度距离排序方法选择最优路径点.对规划路径进行平滑处理，使得改进后的算法在复杂的三维环境中能够快速收敛获得路径最优解.

1 路径规划相关模型建立

1.1 三维空间环境模型

环境建模是AUV路径规划的首要环节，三维环境建模的方法有很多，总体上可以将建模的方法分为两类[8]：①用规则网格表示模型，如用正方形、立方体、矩形和长方体组成的规则网格表示海底表面；②用不规则网格表示模型，以三角形、多边形或不规则形状作为模型单元的基础.与常规网格地形模型相比，不规则网格建模更为复杂，占用空间更大.因此，在前人研究的基础上，采用空间分层[9]，平面网格化的基本思想建立三维空间模型，以网格为单位离散化表示水下航行器的工作区域.

1) 空间划分 首先建立O-XYZ三维直角坐标系，模拟海洋地理环境，其中Z轴正方向对应海底深度值，OX轴为水下航行器横向位移增加的方向，OY为纵向位移增加的方向.在构建好的O-XYZ坐标系后，沿着X轴方向进行空间n等分，相邻平面间距为单位长dx，见图1a).等分后的每个平面须进行网格化处理，划分出m×m个网格点，每个网格点都有相应的坐标值，用来储存路径点信息，见图1b).路径点信息用0、1表示，其中0表示平面内此路径点是危险的，不可作为下一个路径点的选取对象；1表示平面内此路径点是安全的，满足安全通过的要求.按照本文模型构建的思想，海底地形及其边界网格点储存的路径点信息默认为0.

图1 空间划分和yozi平面路径点示意图

2) 地理信息转化 经过对三维空间的分层、网格化处理，地理环境也较容易被表达出来.其中比较常用的方法是序号法和坐标法，序号法可以减少计算时的数据量，运行速度快，但是并没有减少路径点的存储数量，各个路径点的位置关系也不容易被直观判断出来.为了更好的适应文中采用的NSGA-II算法，将环境模型坐标化运用到算法的优化求解过程中.其中，转化后地理环境模型见图2.

图2 海底地形环境

1.2 路径评价函数模型

全局路径规划的本质就是搜索一条从起点S(xs,ys,zs)到终点E(xe,ye,ze)的长度最短且危险度最小的路径，而AUV在实际航行过程中要受到多种因素的影响.为便于计算，简化处理，模型中将AUV视为质点，且不考虑海洋环境下的潮流、海流等因素干扰.

AUV路径评价函数属于典型的多目标决策问题，由于不同算法研究的目的有差异，评价函数考虑的因素和侧重点也会不同.本算法重点考虑路径的长度即经济性和路径威胁度即安全性两项评价指标来定义评价函数.

1) 路径长度评价函数

J1=

(1)

式中：dx为相邻平面间隔；(xi,yi,zi)为AUV运动到yozi平面上的坐标.

2) 路径威胁度评价函数 在切面上的每个路径点，在一定的步长r(r∈Z)内，都会存在R个网格点，假设这R个网格点中有m(m<8)个点为危险点(威胁源)，则此时该路径点的危险度为

(2)

R=r2-1

(3)

将各个平面上路径点的威胁度相加，得到的AUV整条规划路径的威胁度评价函数为

(4)

3) 路径总评价函数 为了求解多目标优化问题，本文运用加权组合的方法，给路径长度和路径威胁度函数分配权重，并采用目前普遍使用的主观赋权法.设路径长度评价函数J1的权重为k，路径威胁度评价函数J2的权重设置为1-k，得到规划路径总评价函数为

minJ=kJ1+(1-k)J2=

(5)

2 NSGA-II算法路径规划

2.1 NSGA-II算法

第二代非支配排序遗传算法NSGA-II[10](non dominated sorting genetic algorithm-II，NSGA-II)是在第一代非支配排序遗传算法的基础上改进而来，降低了遗传算法的复杂性，具有运行速度快，解集收敛性好的优点，是目前最流行的多目标遗传算法之一.其改进主要体现在两个方面.

1) 提出了快速非支配排序算法，一方面降低了计算的复杂度，另一方面它将父代种群跟子代种群进行合并，使得下一代的种群从双倍的空间中进行选取，从而保留了最为优秀的所有个体.

2) 采用拥挤度和拥挤度比较算子，使得准Pareto域中的个体能均匀地扩展到整个Pareto域，保证了种群的多样性.

通过快速Pareto排序及拥挤度距离计算进行路径点选择后，在种群中的每个个体都将获得两项属性，即非支配排序层级号和拥挤度距离.

2.2 算法流程

记种群规模为PopSize，最大迭代代数为Gen，非支配层级数为L，非支配解集合为Fi(i=1，2,…，L)，拥挤度距离为Nd.符号含义见表1.

表1 符号含义

使用NSGA-II算法求解AUV三维全局最优路径的执行过程如下.

步骤1初始化算法参数，生成初始种群Pop，即初始化随机生成一条由起始点到目标终点的AUV参考路径，Pop中由起始点到目标终点顺序存储每个路径点的坐标值(xi,yi,zi).

步骤2评价当前路径的适应值.将Pop中每个路径点坐标值(xi,yi,zi)分别代入评价函数计算AUV当前路径点的长度、威胁度适应值.

步骤3执行非支配排序和拥挤度距离排序.对Pop中每个路径点坐标值与其他所有路径点坐标值，根据步骤2中适应值的计算结果分别两两比较，执行拥挤度距离计算及排序，拥挤度距离大者胜出.

步骤4执行交叉操作.对由Pop中路径点形成的两个不可行路径段进行单点交叉操作，按随机方式选择交叉点从而得到两个新的路径段.

步骤5执行变异操作.在Pop*存储的新路径中，随机选择除起始点和目标终点以外的任意路径点，根据选中的随机数，对应找到这个路径点位置执行变异操作.变异操作的新路径中由起始点到目标终点的每个路径点坐标值(xi,yi,zi)顺序存储至Pop**中.

步骤6执行合并操作，对Pop*和Pop**执行合并操作，生成备选种群MergePop.

步骤7再次执行非支配排序和拥挤度距离排序.对备选种群MergePop中每个路径点坐标值，执行与步骤3中描述相同的操作，得出关于MergePop的Fi(i=1，2,…,L)和Nd.

步骤8判断算法运行终止条件.若未达到最大迭代代数Gen，则转去执行步骤2，否则终止算法并输出最优解.

2.3 仿真实验

仿真采用matlab软件编程，设置AUV起始点坐标为SO1(1,60,100)，终点坐标为EO1(101,101,100).为了保证路径点的安全，设置路径规划总评价函数中的权值k=0.4，运用NSGA-II算法求解全局最优路径，进行20次仿真实验，选取规划效果最优的一次路径.仿真参数设置见表2.

表2 仿真参数设置

NSGA-II算法能够成功地避开海底地形障碍，规划出AUV有效可行的全局路径.但是在躲避海底地形威胁时，路径曲线不够平滑，部分转向点角度过大，导致AUV频繁转向、总航程变长.因此，为了保证规划路径的经济性，更好的适应AUV的操纵性要求，规划的路径还需进一步的优化处理.

3 规划路径的优化

由于NSGA-II算法在建立的网格环境模型下对路径进行规划，规划出路径的长度与平滑程度存在一定缺陷，并不利于水下航行器的航行，所以需要对路径进行优化处理.本文应用梯度下降法(gradient descent)，即通过多次迭代，使得目标函数取得最小值.梯度下降法是迭代法的一种，可以用于求解最小二乘问题.在求解评价函数的最小值时，可以通过梯度下降法来逐步迭代求解，得到最小化的评价函数和模型参数值.

设AUV路线规划的结果为点序列为[x1,x2,…,xn]，平滑后路线规划的点序列为[y1,y2,…,yn]，路径平滑最小化目标为alpha×‖x(i)-y(i)‖2+beta×‖y(i)-y(i+1)‖

设置参数alpha=beta=0.6，路径平滑算法流程如下：

步骤1求解y(i)使得‖x(i)-y(i)‖的平方最小.(‖x(i)-y(i)‖为平滑后的点y(i)与原始点x(i)的偏离程度).

步骤2使得y(i)满足 ‖y(i)-y(i+1)‖取值最小.(‖y(i)-y(i+1)‖为平滑后y(i)点之间的距离).

步骤3初始化y(i)=x(i)，迭代循环式(6)，直到满足最小化目标.

y(i)=y(i)+alpha×[x(i)-y(i)]+

beta×[y(i-1)-2×y(i)+y(i+1)]

(6)

在第2节仿真实验的基础上，基于梯度下降法对规划的路径进行优化处理，为了凸显优化前后路径的效果，设置起点纵坐标y=60，平滑处理后的路径见图3.

图3 优化前后路径立体图和俯视图

图3中浅色曲线为NSGA-II算法规划的路径，深色曲线为应用梯度下降法平滑处理后所产生的路径.由图3可知，改进后的路径曲线趋于平滑，路径转向点减少且部分特殊转向角变小，能够更好的符合水下航行器的航行实际.

图4为路径优化前后威胁度、长度迭代收敛曲线.总体可以看出NSGA-II算法在路径规划时得到的目标代价值较小，且能够快速响应，收敛速度较快.

图4 路径长度和长度收敛情况比较

对比分析优化前后威胁度收敛情况，平滑算法处理后，程序经过37次迭代达到了最优解，而原算法虽然中期收敛速度较快，但收敛曲线不稳定，最终在46次迭代后收敛，并且最终代价值高于平滑算法处理的结果.同样对比分析路径长度收敛情况，优化后算法收敛速度加快，经过第32次迭代达到最优解，且路径长度最优解更小.而原算法经过44次迭代达到收敛状态.

4 结 束 语

针对自主水下航行器(AUV)在三维环境中的路径规划问题，建立了简单有效的三维地理环境模型，基于改进NSGA-II算法的快速Pareto排序及拥挤度距离计算选择最优路径点，并对规划的路径进行平滑优化处理.仿真结果表明，本文采用的算法能够为AUV快速规划出三维空间下的最优路径.但由于本文将AUV视为质点，未考虑AUV的六自由度及操纵性的影响，导致仿真实验与实际的工作情况存在一定偏差，后期的路径规划研究将充分考虑AUV安全领域、操纵控制等约束条件.