2. 西安测绘研究所, 西安 710054;
3. 地理信息工程国家重点实验室, 西安 710054
2. Xi'an Research Institute of Surveying and Mapping, Xi'an 710054, China;
3. Stake Key Laboratory of Geo-information Engineering, Xi'an 710054, China
利用惯性导航系统开展水下作业任务,具有自主性、抗干扰性、隐蔽性等优点(郑晖等,2012;Han et al., 2016;郑伟等,2019).惯导系统自身存在误差积累,当缺少其他手段辅助作用时,惯导系统的输出坐标位置会偏离真实航迹,加大航行风险,因而有必要对其进行及时修正(Indelman et al., 2012;Panahandeh and Jansson, 2014;Cui et al., 2015;Wang et al., 2019).与天文导航、声学导航、无线电导航、卫星导航等方法相比,重力匹配导航无需在接近水面的地方工作,不易受外界环境干扰,其自身携带的重力测量仪器具备实时数据采集处理功能,能够满足运载体长时间水下航行的安全性和隐蔽性要求(Yang et al., 2014;Canciani and Raquet, 2017).
不同海域的水下重力匹配导航效果不尽相同,原因在于重力场适配性存在差异(Wang et al., 2016;杨元喜等,2017).对重力场适配性开展预先评价,有助于提高匹配精准度,有效规避海洋洋流、海洋暗礁等不利干扰.适配性通常采用统计特征参数进行表征,包括重力异常标准差、坡度标准差、粗糙度、重力异常差异熵、分形维数等,针对特征参数评价指标单一,评价结果不全面等方面的问题,有学者相继提出新型分层邻域阈值搜索法(李钊伟等,2019a)、主成分加权平均归一化法(李钊伟等,2019b)、支持向量机的背景场适配/误配区自动识别和划分方法(张凯等,2013)等进行归纳和综合处理.
在适配性评价基础上规划导航路径,是为了在起始点和目标点之间搜索出一条合理、便捷、高效的优化路径,目前常用的规划算法有A*算法(Persson and Sharf, 2014)、人工势场算法(张建英等,2006)、蚁群算法(陈余庆等,2019)、粒子群优化算法(谌剑等,2012)和可视图算法(Mali et al., 2018)等.作为一种典型的启发式搜索算法,A*算法以其原理简单、易于实现、效率高、速度快且一定能搜索到最优解等优点得到广泛关注,被认为是在静态路网中求解最短路径最有效的直接搜索算法.针对传统A*算法规划路径在平滑性方面存在的不足,陆泽橼和蔡体菁(2010)改进A*算法,通过重力坡度值表示重力导航启发信息,使用自适应确定对应阈值,增加预处理步骤以解决任意起始点和终止点的航迹规划问题,使得规划航迹的重力导航信息更加丰富;张红梅等(2018)根据节点与障碍物的最小距离定义该节点存在的安全威胁代价,将其引入A*算法估价函数,并对规划路径进行平滑优化,同时引入路径评价机制以保证平滑路径代价值不会增大;吴鹏等(2019)采用双向搜索的方式,对传统A*算法加以改进,该算法在路径规划过程中,可同时进行正反向路径搜索,同时采用正反向搜索交替机制,保证了最终目标节点搜索在连线中点区域内相遇,从而缩短了寻路计算时间.
A*算法多用于移动机器人、无人机等的避障,是一种人工智能算法,海洋重力场特征参数属于地球物理学范畴,将地球物理信息和人工智能算法结合以规划水下航行路径,目前在此方面的研究和应用尚不多见.本文选定某海域作为研究对象,基于重力异常标准差、粗糙度及其卷积结果,通过设定合理阈值划定适配区和非适配区.采用A*算法得到起始点和目标点间的规划路径,通过前后向对比分析,对单个路径节点进行筛选过滤,去除不必要节点,改善曲折路径,减少多余航向调整,得到了改进A*算法优化路径.
1 海洋重力场特征参数重力异常作为稳定物理场,通常采用标准偏差、粗糙度、信息熵、相关系数、地形坡度等参数描述其细节变化,这些特征参数代表了区域内重力异常数据的离散性、不同数据之间的相似性以及变化幅度(马越原等,2016).下面给出各参数定义:
1.1 重力异常标准差
(1) |
(2) |
式中,m, n为移动窗口内重力场x和y方向网格数目,σ为重力异常标准差,主要反映窗口内重力异常离散程度及其整体起伏程度;g(i, j)为(i, j)处重力异常,
粗糙度σz反映重力场局部起伏程度:
(3) |
(4) |
(5) |
式中,Rlongitude和Rlatitude分别是异常值沿经向和纬向的绝对粗糙度.σz为计算窗口内重力异常的平均平滑,可以描述相对细微的局部变化.
1.3 标准差和绝对粗糙度卷积重力异常标准差反映了宏观尺度上的整体特征,粗糙度反映了微观尺度的变化幅度.本文采用的重力异常参考图为1′×1′分辨率,倘若相邻格网点间重力异常值变化很小,甚至达不到1 mGal,重力仪测量精度的变化,可能被重力仪测量噪声所淹没.为了解决这个问题,Wang等(2017)提出将重力异常标准差和绝对粗糙度整合为一个参数Γij,如下:
(6) |
(7) |
(8) |
式中,Slatitude和Slongitude为纬度和经度方向上计算点(i, j)与相邻距离为k的两点之间重力异常差异的平方和,Γ(i, j)为单个计算点(i, j)的重力异常特征参数,图 1示出了计算点(i, j)的卷积参数计算原理图,为了利用窗口内m×n网格反映较大区域范围特征值,构造以下函数:
(9) |
海洋重力场参考图是卫星测高、船测重力、卫星重力等多种类型海洋重力测量手段的信息融合(欧阳明达,2015).选择某海域作为本文研究对象,图 2示出了该海域重力异常参考图,参考图采用斯克里普斯海洋研究所1′×1′全球海洋重力异常模型grav.img 24.1 (Sandwell et al., 2014),其精度为3~8 mGal (孔敏等,2016;张春灌等,2017),格网点数为361×421,最大值为180 mGal,最小值为-170 mGal,平均值为7.81 mGal,标准差为26.85 mGal.目前,最新的LaCoste&romberg型和kss31型海洋重力仪在相对恶劣海况条件下的测量精度为±1.0 mGal,考虑到其他类型误差(零点漂移校正、Eotvos校正、不准确定位、空间校正)影响,保守估计仪器测量精度可以达到±1.0 mGal至±2.0 mGal(Krasnov et al., 2011),能够用于开展重力匹配导航.
为了对研究海域重力场统计特征参数进行分析,需要定义移动计算窗口.由于相邻距离k的限制,10′×10′分辨率能够满足参数计算要求,以得到不同相邻距离k下的重力异常统计特征参数.在窗口内积分计算时,仅考虑与流动点相邻距离k为1至6时的积分结果,当Γk=4, 5, 6大于9.3时,该区域重力匹配导航能够达到约±kmax(Γk)/2 nm的最佳定位精度(Wang et al., 2017).
海洋重力异常参考图是水下运载体水下导航路径规划的基础,图 3和图 4分别示出了该参考图粗糙度和标准差,图 5示出了当k=1, 2, 3, 4, 5, 6时的卷积特征参数值.通过与图 2的对比可知,重力异常和特征参数值相关性较弱,各参数值受重力异常变化程度影响较大,具体表现在中部和西北部海域,重力异常呈现出急速下降又陡然上升的变化态势,各特征参数值越大,反映出重力异常细节丰富程度和复杂程度越高,与此同时,不同特征参数之间也具有较强的相关性.卷积特征参数随着k值的不断增大,参与计算的格网点数据增多,则Γ值增幅越大.总的来看,重力异常变化越显著的海域,其对Γ值贡献率越大,重力异常变化平缓地区,如南部海域,其对Γ值的贡献非常微小.
基于特征参数的重力场适配区划分可以采用交集运算、主成分加权平均归一化法、骨架提取等方法,关于划分方式的探讨非本文研究重点.Wang等(2017)认为,综合考虑重力异常参考图精度和海洋重力测量设备噪声水平,当k=4,参数Γ大于9.3时,重力匹配导航达到0.5个格网间隔(1个格网=1n mile=1′)的整体精度水平,即为适配区.为了研究方便,在重力异常参考图中采用特定代码标注水下运载体航行起始点和目标终点,适配区和非适配区采用不同颜色模块进行区分.经计算,得到重力异常适配格网模型,其表达形式为
(10) |
其中,mapij=0表示水下运载体起始位置,mapij=1表示适配区单元格网,mapij=2表示非适配区单元格网,mapij=3表示目标终点位置.
值得注意的是,重力异常和海底地形在一定波长范围具有相关性(Sandwell et al., 2006;欧阳明达等,2014),即异常变化信息越丰富的海域海山存在的可能性越大,当水下运载体在海山附近地区航行,搁浅、撞山等现实威胁会严重危害航行安全,这部分区域应当被列入非适配区.实际工作中,应当同时顾及海洋深度模型和重力场特征参数,以形成适配格网模型.由于深度模型非本文研究重点,试验中默认海山不存在现实威胁.
2.2 路径选取原理A*算法是在Dijkstra算法基础上发展起来的,其核心思想是在路径搜索过程中不断寻找估价函数最小的节点进行扩展,以使搜索过程可以沿着最优路径方向进行,从而减小搜索节点数目(陆泽橼和蔡体菁,2010;Persson and Sharf.,2014;张红梅等,2018;吴鹏等,2019).每个节点估价函数f(x, y)的计算公式为
(11) |
式中,(x, y)为当前节点坐标,g(x, y)为起始点到当前点的实际距离,h(x, y)为当前点到目标终点的启发式估计代价函数,一般描述为欧氏距离形式.
(12) |
式中,(xgoal, ygoal)为目标终点位置.
A*算法实现过程中需要不断更新两个集合:open集和close集.open集是开启列表,用于保存待考查的节点,close集是关闭列表,用于保存所有经过的节点和参考图中标识的非适配节点.A*算法不断将当前位置周围节点加入open列表,并选择open列表中f值最小点作为当前位置,直到当前位置临近点出现目标点或open表为空.A*算法具体流程如下:
(1) 把起始节点放入open列表;
(2) 检查开启列表是否为空,如果为空,则搜索失败;不为空,则执行下一步;
(3) 选取open列表中f值最小的节点作为当前扩展节点,对该节点周围节点作如下判断及处理:①周围节点是close列表中的节点,则无任何动作;②周围节点不在open列表中,则添加进周围节点到open列表,并将当前扩展节点作为父节点,计算周围节点的f和g;③当周围节点在open列表中,如果当前扩展节点为父节点,周围节点的g比原来更低,则把当前扩展节点作为父节点,重新计算周围节点f和g,否则不作任何改变;
(4) 将当前扩展节点放入close列表中,检查终点是否在open列表.如果不在open列表中,则返回(2)继续搜索;否则,结束搜索,返回最优路径结果;
(5) 从终点开始,沿着每一个父节点移动,回到起始点,得到最终路径.
2.3 规划路径的平滑优化传统A*算法规划路径存在冗余点多、转折次数多等问题,这将导致路径总长度和总转折角度增大.本文提出一种改进算法,能够有效缩短路径长度、减少转折角度.
图 6示出了改进A*算法路径规划流程图.采用循环方法,从起始点开始,将两个节点连线,遍历其周围区域,判定是否存在非适配区.判定过程中,以下三种情况可以认为连线不经过非适配区:一是连线与非适配区无交集,二是连线仅与非适配区块某条边共线,三是连线仅与非适配区块某一顶点相交.据此,若判定连线经过非适配区,则将连线起始端点存入新路径集合,更改连线终点之前一个节点为新的连线起始端点,同时新的连线终点移至下一个节点,重新开始循环计算.若连线不与非适配区产生交集,则直接进入循环,连线终点移至下一个节点,并对路径终点进行判别,存入新路径集合.经过上述改进算法,最终得到一条优化的平滑路径节点集合,该集合的节点数量较未优化线路节点数量大大减少,反映在图形上则是转折路径减少,路径长度缩短.
沿用2.1节算例,采用传统A*算法和改进A*算法得到规划路径.如图 7所示,黄色三角点为水下运载体起始出发点,东经131°45′30″、北纬28°45′30″,黄色圆点为目标终点,东经134°45′30″、北纬23°5′30″.背景图中灰色部分为适配区域,彩色部分显示为区域重力异常,为非适配区(依据2.1节标准差和粗糙度卷积特征参数Γ判定),非适配区面积约占区域总面积的50%.图 7a红色线段为传统A*算法规划路径,图 7b中为改进A*算法路径,由此可知,改进算法对传统A*算法规划路径进行了有效的平滑优化,折线点数从20个降低至7个,路径长度缩短约8.9%,减少了重力匹配导航路径的复杂程度,便于进一步开展后续研究.
本文利用特征参数对某海域重力场适配性进行评价,通过改进A*算法实现了水下运载体航行路径的有效规划,得到以下结论:
(1) 单一重力场特征参数仅包含局部信息,重力异常标准差和粗糙度卷积特征参数顾及移动窗口整体特征,具有良好的统计学意义,可以将其作为适配区评价标准,用以制备重力场适配格网参考图.
(2) 提出一种改进A*算法,实现了对水下运载体航行路径的合理规划,在有效规避非适配区的同时,进一步减少了路径折线段数量,缩短了路径长度,达到了路径平滑优化的目的.
(3) 给出了重力匹配导航路径规划的基本处理方法、步骤和流程,实现了地球物理场信息与人工智能算法的有机结合,不足之处在于缺少实测惯性导航数据的试验验证.
Canciani A, Raquet J. 2017. Airborne magnetic anomaly navigation. IEEE Transactions on Aerospace and Electronic Systems, 53(1): 67-80. DOI:10.1109/TAES.2017.2649238 |
Chen Y Q, Li T X, Yu S H, et al. 2019. Global path planning of robots based on potential field ant colony algorithm. Journal of Dalian University of Technology (in Chinese), 59(3): 316-322. |
Cui R X, Guo J, Mao Z Y. 2015. Adaptive backstepping control of wheeled inverted pendulums models. Nonlinear Dynamics, 79(1): 501-511. |
Han Y R, Wang B, Deng Z H, et al. 2016. An improved TERCOM-based algorithm for gravity-aided navigation. IEEE Sensors Journal, 16(8): 2537-2544. DOI:10.1109/JSEN.2016.2518686 |
Indelman V, Gurfil P, Rivlin E, et al. 2012. Real-time vision-aided localization and navigation based on three-view geometry. IEEE Transactions on Aerospace & Electronic Systems, 48(3): 2239-2259. |
Kong M, Tian X D, Liu Z J, et al. 2016. Accuracy analysis of marine gravity data shared internationally. Science of Surveying and Mapping (in Chinese), 41(6): 14-17, 22. |
Krasnov A A, Nesenyuk L P, Peshekhonov V G, et al. 2011. Integrated marine gravimetric system. Development and operation results. Gyroscopy and Navigation, 2(2): 75-81. DOI:10.1134/S2075108711020052 |
Li Z W, Zheng W, Wu F, et al. 2019a. Improving the matching efficiency of underwater gravity matching navigation based on a new hierarchical neighborhood threshold method. Chinese Journal of Geophysics (in Chinese), 62(7): 2405-2416. DOI:10.6038/cjg2019M0086 |
Li Z W, Zheng W, Fang J, et al. 2019b. Optimizing suitability area of underwater gravity matching navigation based on a new principal component weighted average normalization method. Chinese Journal of Geophysics (in Chinese), 62(9): 3269-3278. DOI:10.6038/cjg2019M0346 |
Lu Z C, Cai Q J. 2010. Gravity aided navigation path plan research based on A* algorithm. Journal of Chinese Inertial Technology (in Chinese), 18(5): 556-560. |
Ma Y Y, Ouyang Y Z, Huang M T, et al. 2016. Selection method for gravity-field matchable area based on information entropy of characteristic parameters. Journal of Chinese Inertial Technology (in Chinese), 24(6): 763-768. |
Mali P, Manna S K, Mukhopadhyay A, et al. 2018. Multifractal analysis of multiparticle emission data in the framework of visibility graph and sandbox algorithm. Physical A:Statistical Mechanics and its Applications, 493: 253-266. DOI:10.1016/j.physa.2017.10.015 |
Ouyang M D, Sun Z M, Zhai Z H. 2014. Predicting bathymetry in South China Sea using the gravity geologic method. Chinese Journal of Geophysics (in Chinese), 57(9): 2756-2765. DOI:10.6038/cjg20140903 |
Ouyang M D. 2015. Theory and Methodology of bathymetry inversion using the oceanic gravity data[Master thesis] (in Chinese). Zhengzhou: Information Engineering University.
|
Panahandeh G, Jansson M. 2014. Vision-aided inertial navigation based on ground plane feature detection. IEEE/ASME Transactions on Mechatronics, 19(4): 1206-1215. |
Persson S M, Sharf I. 2014. Sampling-based A* algorithm for robot path-planning. The International Journal of Robotics Research, 33(13): 1683-1708. DOI:10.1177/0278364914547786 |
Sandwell D T, Smith W H F, Gille S, et al. 2006. Bathymetry from space:rationale and requirements for a new, high-resolution altimetric mission. Comptes Rendus Géoscience, 338(14-15): 1049-1062. DOI:10.1016/j.crte.2006.05.014 |
Sandwell D T, Müller R D, Smith W H F, et al. 2014. New global marine gravity model from CryoSat-2 and Jason-1 reveals buried tectonic structure. Science, 346(6205): 65-67. DOI:10.1126/science.1258213 |
Shen J, Li H, Zhang J Y. 2012. Optimal path planning method for underwater terrain-aided navigation. Torpedo Technology (in Chinese), 20(4): 276-280. |
Wang B, Zhu Y W, Deng Z H, et al. 2016. The gravity matching area selection criteria for underwater gravity-aided navigation application based on the comprehensive characteristic parameter. IEEE/ASME Transactions on Mechatronics, 21(6): 2935-2943. DOI:10.1109/TMECH.2016.2587804 |
Wang B, Zhu J W, Deng Z H, et al. 2019. A characteristic parameter matching algorithm for gravity-aided navigation of underwater vehicles. IEEE Transactions on Industrial Electronics, 66(2): 1203-1212. DOI:10.1109/TIE.2018.2831171 |
Wang H B, Wu L, Chai H, et al. 2017. Characteristics of marine gravity anomaly reference maps and accuracy analysis of gravity matching-aided navigation. Sensors, 17(8): 1851. DOI:10.3390/s17081851 |
Wu P, Sang C J, Lu Z H, et al. 2019. Research on mobile robot path planning based on improved A* algorithm. Computer Engineering and Applications (in Chinese), 55(21): 227-233. |
Yang Y X, Xu T H, Xue S Q. 2017. Progresses and prospects in developing marine geodetic datum and marine navigation of China. Acta Geodaetica et Cartographica Sinica (in Chinese), 46(1): 1-8. |
Yang Z L, Zhu Z S, Zhao W G. 2014. A triangle matching algorithm for gravity-aided navigation for underwater vehicles. Journal of Navigation, 67(2): 227-247. DOI:10.1017/S0373463313000660 |
Zhang C G, Yuan B Q, Zhang G L. 2017. Quality evaluation of land gravity data in the latest global gravity database V23. Advances in Earth Science (in Chinese), 32(1): 75-82. |
Zhang H M, Li M L, Yang L. 2018. Safe path planning of mobile robot based on improved A* algorithm. Computer Simulation (in Chinese), 35(4): 319-324. |
Zhang J Y, Zhao Z P, Liu D. 2006. A path planning method for mobile robot based on artificial potential field. Journal of Harbin Institute of Technology (in Chinese), 38(8): 1306-1309. |
Zhang K, Zhao J H, Wang Q. 2013. Study on recognition and classification of appropriate matching area for underwater navigation based on SVM. Journal of Geodesy and Geodynamics (in Chinese), 33(6): 72-77. |
Zheng H, Wang Y, Wang H B. 2012. Simulation of geomagnetic aided submarine navigation based on EMAG2. Progress inGeophysics (in Chinese), 27(4): 1795-1803. DOI:10.6038/j.issn.1004-2903.2012.04.063 |
Zheng W, Li Z W, Wu F. 2019. Research progress in improving the accuracy of underwater inertial/gravity integrated navigation based on the new generation of GNSS-R constellation sea surface altimetry principle. Science Technology and Engineering (in Chinese), 19(36): 21-36. |
陈余庆, 李桐训, 于双和, 等. 2019. 基于势场蚁群算法的机器人全局路径规划. 大连理工大学学报, 59(3): 316-322. |
孔敏, 田先德, 刘志杰, 等. 2016. 国外共享海洋重力数据精度分析. 测绘科学, 41(6): 14-17, 22. |
李钊伟, 郑伟, 吴凡, 等. 2019a. 基于新型分层邻域阈值搜索法提高水下潜器重力匹配导航的匹配效率. 地球物理学报, 62(7): 2405-2416. DOI:10.6038/cjg2019M0086 |
李钊伟, 郑伟, 房静, 等. 2019b. 基于新型主成分加权平均归一化法优选水下重力匹配导航适配区. 地球物理学报, 62(9): 3269-3278. DOI:10.6038/cjg2019M0346 |
陆泽橼, 蔡体菁. 2010. 基于A*算法的重力辅助导航航迹规划. 中国惯性技术学报, 18(5): 556-560. |
马越原, 欧阳永忠, 黄谟涛, 等. 2016. 基于重力场特征参数信息熵的适配区选择方法. 中国惯性技术学报, 24(6): 763-768. |
欧阳明达, 孙中苗, 翟振和. 2014. 基于重力地质法的南中国海海底地形反演. 地球物理学报, 57(9): 2756-2765. DOI:10.6038/cjg20140903 |
欧阳明达. 2015.利用海洋重力数据反演海底地形的理论与方法[硕士论文].郑州: 解放军信息工程大学.
|
谌剑, 李恒, 张静远. 2012. 水下地形辅助导航最优航路规划. 鱼雷技术, 20(4): 276-280. |
吴鹏, 桑成军, 陆忠华, 等. 2019. 基于改进A*算法的移动机器人路径规划研究. 计算机工程与应用, 55(21): 227-233. |
杨元喜, 徐天河, 薛树强. 2017. 我国海洋大地测量基准与海洋导航技术研究进展与展望. 测绘学报, 46(1): 1-8. |
张春灌, 袁炳强, 张国利. 2017. 最新全球重力数据库V23中陆域重力资料质量评估. 地球科学进展, 32(1): 75-82. |
张红梅, 李明龙, 杨乐. 2018. 基于改进A*算法的移动机器人安全路径规划. 计算机仿真, 35(4): 319-324. |
张建英, 赵志萍, 刘暾. 2006. 基于人工势场法的机器人路径规划. 哈尔滨工业大学学报, 38(8): 1306-1309. |
张凯, 赵建虎, 王锲. 2013. 基于支持向量机的水下地形匹配导航中适配区划分方法研究. 大地测量与地球动力学, 33(6): 72-77. |
郑晖, 王勇, 王虎彪. 2012. 地球磁场异常格网(EMAG2)辅助潜艇导航仿真研究. 地球物理学进展, 27(4): 1795-1803. DOI:10.6038/j.issn.1004-2903.2012.04.063 |
郑伟, 李钊伟, 吴凡. 2019. 基于新一代GNSS-R星座海面测高原理提高水下惯性/重力组合导航精度研究进展. 科学技术与工程, 19(36): 21-36. |