多目标遗传算法在水下机器人路径规划中的应用

《多目标遗传算法在水下机器人路径规划中的应用》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第35卷第4期武汉大学学报#信息科学版Vol.35No.42010年4月GeomaticsandInformationScienceofWuhanUniversityApr.2010文章编号:167128860(2010)0420441205文献标志码:A多目标遗传算法在水下机器人路径规划中的应用1,22曹江丽孙潮义(1哈尔滨工程大学计算机科学与技术学院,哈尔滨市南岗区南通大街145路,150001)(2武汉数字工程研究所,武汉市珞喻路718号,430074)摘要:依据VCF电子海图,提出了一种对水下机器人

2、进行路径规划的多目标遗传算法,采用可变长的实数坐标编码、适应度函数评价了影响航路优劣的多个因素,设计了选择、交叉、变异、修补、删除等遗传算子以及种群置换方法。在生成初始种群和设计遗传算子时引入领域知识,使所生成路径尽量不穿越障碍区域,有效地提高了大范围路径规划算法的收敛速度。试验表明,采用该MOGA算法进行路径规划可提高算法的收敛速度和全局寻优能力。关键词:多目标遗传算法;路径规划;VCF;适应度函数中图法分类号:P237.9;TP242自主式水下机器人(autonomousunderwater图中深度低于

3、一定数值的岛屿、干出滩、明礁、暗vehicle,AUV)依据使命要求进行水下自主导航和礁区域、禁航区等表示为障碍区域,另外,还将海自主控制,在水下航行时跟踪预先规划好的航线,流速度高于AUV最大抗流能力的高海流区域表并根据环境的变化进行动态局部规划。AUV的航示为障碍区域。在海图中这些区域都以多边形描线设计就是在已知海图上进行全局路径规划,路径述,这些多边形的顶点按顺时针方向顺序存储。规划是AUV研究及实用化的重要问题之一。在图形文件(*.shp)记录了海图要素的坐标位数字地图中寻找从出发地到目的地的最优路

4、径的置数据,海图要素根据其几何特征分为点状要素、[1,2]方法有很多,AUV在海洋环境中的路径规划问线状要素、面状要素3类基本要素。面状要素在题有其自身特点,可以利用这些方法的基本原理。海图上是由一条或一组线段包围的封闭区域,如本文根据VectorChartFormat(VCF)矢量陆地、岛屿、湖泊、干出滩等。在海洋陆地层的图数字海图,利用海洋/陆地、障航物、区域界线等要形文件中,一片陆地是多个地理位置相邻的多边素逻辑层提供的面状海岸地形信息以及水文/磁形区域的并集,它由这些多边形区域拼接而成。要素逻辑层提

5、供的点状洋流/潮流信息进行全局通过分析多边形之间的拓扑关系提取了陆地的完路径规划。本文采用多目标遗传算法(multi2ob2整轮廓,供路径规划使用,图1显示了海岸陆地轮jectivegeneticalgorithm,MOGA)进行路径规廓提取的结果。[325]划,与传统的遗传算法不同,在环境建模中充水下机器人在自主航行中需要绕开一些区域分考虑了领域知识,并对VCF海图上的有关区域如海中岛屿、明礁等,这些区域自然边界复杂,本进行预处理,以提高遗传算法的搜索效率。文对其进行凸包计算,用所得凸包近似替代障碍区域,

6、降低了对海洋环境建模的复杂性。本文利1环境建模用海图要素多边形顶点的有序性这一特性,删除非凸包顶点,对多边形顶点进行以下两道检查:本文AUV的活动范围在中国东海区域,通¹判定顶点在线段的哪一侧以及顶点角的大小过解析这个区域的VCF数字海图文件,将其转成决定多边形顶点的删/留,留下的点按多边形顶点可以利用的环境模型。在环境建模中,将数字海的顺序连接,而且这些顶点角的大小按递增顺序收稿日期:2010201220。项目来源:/十一五0国防预研项目(51316080202)。442武汉大学学报#信息科学版2010年

7、4月滑程度、抗流等影响规划路径质量的因子作为评价因素。一般来说,航程越短,航行时间也越短,在评价函数设计中就不再考虑航渡时间了。一条包含n个路径节点的可行路径p通过以下函数来评价:fFit(p)=wd@dist(p)+wc@clear(p)+ws@smooth(p)+wa@antiflow(p)(1)图1陆地轮廓提取式中,wd、wc、ws、wd是权系数;dist(p)、clearFig.1ExtractionofTerrainContour(p)、smooth(p)、antiflow(p)分别为航程距离、航

8、行路径的安全程度、航行路径的光滑程度和海流排列;º对这些顶点用Graham扫描方法删去非对航行路径的影响程度,其定义式如下:凸包顶点,最后得到多边形的凸包顶点。算法的n-1时间复杂性为O(n),而计算平面上无序的n个点dist(p)=Ed(mi,mi+1)(2)i=1的凸包需要的时间为O(nlgn)。图2(a)为未经处式中,d(mi,mi+1)是两相邻节点mi和mi+1之间理的原图,该图右下方的海上岛屿经凸包计算