电子海图作为一种专门的电子地图是一组地理空间数据的有序集合[1]。它是按照一定的地理框架组合的,带有确定坐标和属性标志的,主要描述海洋地理信息和航海信息的离散数据,是一种以数字形式存储在磁盘、磁带、光盘等介质上的地图。电子海图支持从地图图形到属性数据以及从属性数据到图形的双向检索。随着时代的发展,以海洋为主要描述对象的电子海图作为信息时代的产物,正越来越为人们广泛利用。
智能潜水器(autonomousunderwatervehicles,AUV)在海洋环境航行时,需要获得所处海域的海洋环境信息,以往AUV小范围的航行都是通过“扫海”的方法来获得相应的信息。AUV在大范围海洋环境航行时,“扫海”的方法已经不能满足航行的需要,电子海图恰好提供了详细而准确的海洋环境信息,因此,利用电子海图获得海洋环境信息进行建模是AUV发展的必然趋势。
全局路径规划技术是智能机器人领域中的核心问题之一,全局路径规划从实质上来说是一个有约束的优化问题。全局路径规划包括环境建模和路径搜索策略两个子问题。环境建模的方法主要有:可视图法、自由空间法和栅格法等;路径搜索策略的方法主要有:A＊算法、遗传算法、人工势场法和拓扑图法等[2]。
AUV通常工作在复杂可变的海洋环境中,海面再平静的海洋,其内部也涌动着暗流。因此,在海洋环境中,海流的存在是一个不可忽略的问题[3]。“基于栅格的自由区域连通法”[4]较好地解决了水下拥挤三维环境下的智能水下机器人全局路径规划问题。文献[5]提出了一种用激活值传播算法来解决考虑海流影响的AUV全局路径规划问题的方法。文献[6]提出了一种分层路径规划算法来解决大范围海洋环境下的AUV全局路径规划问题,在启发式搜索路径的算法中,考虑了能量的消耗和路径长度。
提出一种利用电子海图信息进行环境建模的方法,采用遗传(geneticalgorithms,GA)多目标优化算法进行全局路径规划,路径规划考虑了海流因素对AUV的影响。文中给出了实验结果并进行了分析。
1电子海图分析与环境建模
采用shapefile格式电子海图[7]。其中,每幅海图都包含30多个图层。Shapefile格式的海图每种属性又分为点、线、面三个图层分别进行存储。为了避免让AUV直接分析处理复杂的海图信息,需要将海图中的海洋环境信息进行前期的分析处理,转换成AUV容易识别和操作的信息。电子海图中的详细数据信息可以通过分析海图属性数据库,通过索引文件在图形文件中找到相应的图形信息,并利用GIS控件———MapObjects进行分析处理[8]。
由于AUV工作在不同海域中。其海流的大小和方向是变化的,为了便于在规划算法中考虑海流因素,采用栅格法进行环境建模。将海图信息栅格化,栅格分辨率为18″。取范围为18″×18″的正方形区域视为一个栅格节点。图1是某海域电子海图,图2为根据要求栅格化的海图信息。
2基于GA的AUV全局路径规划
2.1AUV全局路径规划问题描述
AUV的路径规划是一个多目标、多约束的优化问题。在AUV全程路径规划时,考虑能耗少、耗时少、路径短和路径平滑度高为四个优化目标,同时以AUV的速度、最小回转半径和离障碍物的安全距离为约束。在以上所描述的多个优化目标和约束条件中存在着相互矛盾的情况,因此AUV的全程路径规划是为了选择出一条满足多个约束条件的路径,同时实现多个目标尽可能优化的折衷解,即得到一组Pareto最优解。可以根据对各个目标的偏好性从这组Pareto最优解中选出一条路径作为最后的输出,而通过多目标运算所得到的这组路径在整体上都是最优的[9]。
全程路径规划优化目标:
minF(P)={D(P),S(P),T(P),E(P)}
式中:D(P)为路径长度;S(P)为路径平滑度;T(P)为航行时间;E(P)为航行过程的能耗。同时在优化过程中应该考虑的约束条件0<|vi|≤Vmax;Ri≥Rmini;di≥dmin其中,vi为AUV在Di段路径的速度;Vmax为AUV所能达到的最大速度;Rmini为AUV在速度vi下的最小回转半径;di为AUV离障碍物的距离;dmin为AUV离障碍物的最小安全距离。
2.2路径编码方案
一条从起点到终点的路径是由一系列栅格节点连接所组成的。假设起点为s,终点为d,则一条路径为path={s,…xi,xi+1,…,d},相邻节点用直线连接。障碍栅格为不可通行点。任意位置的海流速度向量为vc(x,y)。根据以上条件,路径规划问题可以阐述如下:给定起点s和终点d,障碍物位置和海流速度,找到AUV在以恒定速度c航行利用海流减少AUV自身耗能并且安全的一条路径。为简单起见规定路径在X轴方向上是严格单调递增的,即hi+1=hi+1。也就是说每条路径是固定长度m的节点序列。很显然不是所有的路径都是单调无迂回的,但在大范围海洋环境下,障碍物是十分稀疏的。在这种障碍不密集的复杂路径规划下将路径假设成单调的是比较合理的。
2.3确定适应度函数
假设任意一个个体的第i段路径是由节点xi-1,xi连接而成的,记为Xi-1Xi。定义连线Xi-1Xi方向的单位向量为ei。则ei为AUV实际航行的方向,假设AUV实际航行的速度大小为c,在沿Xi-1Xi某一位置(x,y)海流速度向量为vc(x,y),AUV若以速度大小为c航行,其自身需要提供的速度为vi(x,y)。则有如下关系式:
vi(x,y)=cei-vc(x,y),(x,y)∈Xi-1Xi
当AUV顺着海流方向航行时,按照速度c航行,自身提供小于c的速度,借助海流的速度可以节省相应的能量。当AUV逆着海流方向航行时,为达到速度c,需要克服海流对AUV的影响,提供大于c的速度,将会消耗更多的能量。AUV应在航行时充分利用海流以减少自身能量的消耗,减少逆流航行的情况,当不得不逆流航行时应尽量逆着流速小的海流航行。
能量消耗的评价函数为
E(P)=∑wi=1(vix·dix)2+(viy·diy)（1）
2(2)式中:vix和viy,dix和diy分别是AUV沿X轴和Y轴方向的分速度和航行距离;w为路径点总数。采用距离与速度的乘积来表示AUV的能耗大小。
路径长度的评价函数为
D(P)=∑wi=1Di(3)其中,Di为相邻路标点之间的距离。
路径平滑度的评价函数为
S(P)=∑wi=1θi(4)
其中,θi定义为路标点pi处的回转角度。航行时间的评价函数为
T(P)=∑wi=1Di/vi(5)
其中,Di为xi、xi+1两个路标点之间的距离;vi为xi、xi+1两个路标点之间线段上的速度。
2.4基于GA的多目标全程路径规划算法
通过对AUV的优化目标和约束条件进行分析,提出一种基于GA的多目标约束优化算法处理AUV全程路径规划问题。具体算法流程:
step1:置t=0,初始化种群P(t),种群规模为POPSIZE;
step2:计算各路径个体的Pareto强度值和约束违反程度;
step3:从P(t)中随机选择μ个个体作为父体;
step4:(选择操作)根据Pareto强度值从μ个父体中选择产生λ个后代路径个体;
step5:(移入操作)依概率从μ个父体中选择σ个最好不可行解加入到后代个体中;
step6:对于step4和step5中的μ+σ个个体,随机选择两个个体,其中一个个体由该λ个个体中Pareto强度值最大的个体替换,若Pareto强度值最大的个体不唯一,则选择约束违反程度小的个体;另一个个体由剩下的μ-1个个体根据约束违反程度,采用择优选择法产生的约束违反程度最小的路径个体替换;
step7:重复step3～step6,直至产生POPSIZE个后代;
step8:(交叉操作、变异操作、平滑操作)以概率选择个体进行交叉操作、变异操作、平滑操作。上述操作结束后的群体作为新的种群P(t+1),置t=t+1;
step9:判断是否满足结束条件(是否到达最大进化代数N),是,则结束;否,则转step2。
3试验结果及分析
AUV起点S经度为120°37′37″,纬度为37°53′49″;终点G经度为120°52′16″,纬度为37°54′36″。GA算法初始化种群选用100个个体,终止条件为迭代800次。交叉概率为0.8,变异概率为0.4。
图3显示的是单目标路径规划的各个实验结果,(a)、(b)、(c)、(d)四幅图分别对应不同的规划目标。
图4是多目标路径规划的实验结果,(a)、(b)、(c)、(d)四幅图分别对应不同的偏好选择子目标。
表1中记录的是不考虑海流因素的情况下,单目标路径规划和多目标路径规划的各项参数。
通过研究实验结果(图3)和表1中参数对比情况,可以发现以下几点:第一,单目标路径规划中,由于能耗目标、距离目标和时间目标的定义实质上是一样的,最终规划出来的路径也是基本上一样的,而对于平滑度目标则是不同的路径。第二,多目标路径规划中,Pareto强度值的引入,使得融合多个子目标成为可能,由于多目标路径规划要综合考虑多个子目标,视图规划出使得各个子目标尽可能同时达到最优状态的路径,所以多目标规划方法规划出来的有所侧重的四条路径都相差不大。第三,对于多目标路径规划规划出来的路径,虽然各个子目标没有达到单目标规划中的最优状态,但其在整体水平上达到了最优。
表2中记录的是在有海流的情况下,单目标路径规划和多目标路径规划的各项参数。
从上述实验结果以及规划参数数据可以得出,在路径规划中,海流因素的存在会对规划结果产生很大的影响,特别是在长航时、大范围的规划任务,考虑海流因素显得更加重要。海流对潜器规划最主要的影响就是能耗,如何找到一条最节能的路径,对于潜器顺利完成既定任务起到至关重要的作用。在满足节能的同时,还要考虑路径长度、平滑度等等其他子目标,采用的多约束多目标的规划算法在一定程度上解决了上述问题,在满足多个约束条件的前提下,找到了一条综合考虑能耗,路径长度、路径平滑度、航行时间等子目标的路径,较好地解决了多目标优化问题,具有可行性和有效性。但是算法中也存在一些不足,比如规划时间比较长等,这些还需要进一步改进,以获得最佳的性能比。
4结语
提出了一种以电子海图信息为基础的环境建模,解决了对大范围海洋环境建模的问题,并且利用该环境信息进行AUV的全局路径规划。采用GA算法作为AUV全局路径规划的搜索策略,该方法规划出的路径距离短,拐点少,更具有实用性。当需要考虑海流因素对AUV的影响时,AUV在航行时会充分利用海流的能量。该方法适用于大范围海洋环境下需要考虑能量耗尽问题的AUV导航。
