2. 92337部队, 辽宁 大连 116023
2. Troops 92337, Dalian 116023, Chinat
现阶段水下潜器(underwater vehicle,UV)的主要导航方式为惯性导航[1],它具有能够连续工作、提供比较完备的导航参数以及短时噪声低等优点。惯性导航误差具有随时间积累,解算精度随时间下降的缺点[2],因此长期航行时UV必须通过其他导航方式进行辅助校正[3]。然而依靠卫星、天文等外部有源信息来校正惯性导航误差,会损失UV的隐蔽性[4],而重力匹配辅助惯性导航系统是利用重力场这一地球固有场信息,可以对惯性导航系统长航时条件下的误差漂移进行抑制和修正[5],以满足UV“自主性、高精度、隐蔽性”的要求[6]。
在重力辅助导航过程中,UV会经过重力变化明显的适配区域,也会经过变化平缓的非适配区域。因此,让UV航迹一直处于重力适配区而避开非适配区是保证重力辅助导航有效实施的关键之一。水下重力辅助导航最优航迹规划问题可以转换为将重力盲区作为障碍的全局路径规划问题。目前,国内外学者在路径规划方面己经作了大量的研究工作,其中包括Dijkstra算法[7]、A*算法和人工势场法[8]等传统算法,以及遗传算法[9]、人工神经网络[10]、粒子群算法[11]等智能优化算法[12],每种算法在不同的性能指标下都有自身的优点。
为进一步优选重力匹配航迹,本文综合利用主成分分析法[13]、蚁群算法和人工势场法进行重力辅助导航航迹规划。
1 蚁群算法蚁群算法(ant colony optimization, ACO)是一种在图中寻找优化路径的几率型算法[14]。该算法受蚂蚁觅食过程中的路径行为启发,蚂蚁在路径中会分泌一定浓度且具有挥发性的信息素。同时,蚂蚁在觅食过程中会倾向于选择信息素浓度大的路径。最后,经过一段时间运行,可能会出现一条最短的路径被大多数蚂蚁重复。
首先依据主成分分析法(principal component analysis,PCA)对重力场特征参数进行统计并给出重力适配区评价结果[15],利用栅格法将待匹配区域重力异常图离散化为二维栅格图,每个栅格的状态定义为“free”或“occupied”,其中适配区标定为“free”,非适配区标定为“occupied”,即为障碍物,如图 1所示。
UV会占据重力图中的一个栅格,其相邻的8个栅格为UV下一时刻可选的位置。利用蚁群算法的避让规则、移动规则和信息更新规则[16]搜索出最优航迹。具体搜索过程如图 2所示。
若蚂蚁数量为M,蚂蚁k(k=1, 2, …, M)在t时刻从位置i移动到j的概率表示为
式中,α为信息素浓度启发因子;β为期望启发因子;ηij为启发函数,是位置i与位置j之间距离dij的倒数
蚂蚁会在经过的航迹上留下信息素,信息素随时间的改变具有挥发性,信息素的更新规则如下
式中,ρ为信息素挥发系数,ρ∈(0, 1);Δτijk为蚂蚁在t到t+n位置栅格之间的信息素。
依据ant-cycle模型
式中,Q为信息素强度;Lk为蚂蚁k在本次循环中的航迹长度;Pk(begin, end)为蚂蚁k在本次循环中从起点栅格到终点栅格所走的航迹[17]。
蚁群算法在初始阶段各航迹信息素是相同的,差异主要表现在启发信息上。由于启发函数特性,蚁群首条航迹规划会偏向于距目标点近的航迹,此时蚁群算法相似于贪婪算法,在特殊环境中未必反映最优航迹,由于蚁群算法的正反馈性,导致蚁群向错误的方向规划。为解决这一问题,本文在蚁群算法进行航迹规划的基础上引入人工势场法,将人工势场法求得的航迹和UV与下一个节点之间的距离信息综合改进启发信息,利用新的转移概率确定下一个栅格的选择。同时利用最优-最差蚂蚁系统,找出最优航迹解和最差航迹解,分别进行全局信息素更新,对最优航迹进行增强,对最差航迹进行削弱。
2 改进的蚁群-势场算法 2.1 人工势场法人工势场法[18]通过模拟构建一个抽象的人造势场来进行航迹规划。人工势场由引力场和斥力场构成[19],引力场是由目标点位置产生并作用于UV,势场矢量方向由UV指向目标点,势能与到目标点的距离成反比;斥力场由障碍物产生,势场矢量方向由障碍物指向UV,势能与到障碍物的距离成反比[20]。引力场和斥力场对UV共同作用,搜索出一条不接触障碍的最优航迹。
作用于UV的势场函数和合力函数为
式中,U为总势场;Ur为斥力场;Ua为引力场;F为合力;Fr为斥力;Fa为引力。
定义引力为引力场的负梯度,则引力势场函数及引力为
式中,k为大于0的引力常量;Xg为目标点位置。
定义斥力为斥力场的负梯度,定义斥力势场函数和斥力为
式中,m为大于0的斥力常量;ρ0为障碍物的影响范围;XO为障碍物位置。
2.2 蚁群-势场算法 2.2.1 改进的启发信息函数与ACO相比,改进的蚁群-势场算法中的启发信息加入了由人工势场法影响的势场启发信息,ACO的启发信息和人工势场法的启发信息分别表示如下[21]
当前栅格位置为P,目标栅格位置为Q,d(P, G)为当前栅格与目标栅格之间的距离,a为大于0常数,F为人工势场的合力,θ为势场合力方向与下一栅格位置方向的夹角[22]。
在航迹规划前期,蚁群信息素浓度较低,启发信息较小,需加大人工势场法所控制的启发信息;航迹规划后期,信息素浓度的提升,需降低人工势场法所控制的启发信息[23]。因此,引入一个信息递减因子χ来控制人工势场法启发信息[24]
式中,Nmax为最大的迭代次数;NC为当前时刻的迭代次数。
因此蚁群-势场算法的启发函数为
从而得到改进的转移概率公式为
由于人工势场法模型简单,实时性强,将其求得的航迹引入蚁群算法的启发函数中,可有效避免蚁群算法由于启发信息所导致的局部最优问题,同时提高蚁群算法的搜索效率。
2.2.2 改进的信息素浓度更新规则在ACO中,当所有蚂蚁完成一次迭代后,会根据式(3)进行全局信息素更新。由于任何一次迭代中蚂蚁所产生的航迹都会对蚁群以后航迹规划产生影响,非最优航迹蚂蚁会对以后的蚂蚁造成误导。因此,本文引入最优-最差蚂蚁系统[25],在完成一次迭代后,找出最优航迹和最差航迹,分别进行全局信息素更新。对最优航迹进行增强,对最差航迹进行削弱[26]。最优-最差蚂蚁系统使得蚂蚁搜索更集中与当前最优航迹的范围内,并向着全局最优的方向不断发展[27]。
在一次迭代结束后,选出最优蚂蚁航迹和最差蚂蚁航迹,对最优蚂蚁按式(3)进行信息素更新,对于最差蚂蚁按式(17)进行信息素更新
式中,ε为最优-最差蚂蚁系统参数;Lw为最差蚂蚁航迹;Lb为最优蚂蚁航迹。
2.2.3 蚁群-势场算法具体步骤改进的蚁群-势场算法具体流程如图 3所示。
步骤1:初始化参数。选择起点栅格、目标栅格、迭代计数器NC=0,设置最大迭代次数Nmax,对蚂蚁数量M、信息素启发因子α、期望启发式因子β、引力常量k、斥力常量m等参数初始化。
步骤2:蚂蚁航迹选择。将M只蚂蚁放到起点栅格,并将起点栅格加入禁忌表中。采用人工势场法计算启发信息,得到新的概率信息,从而确定下一个可行栅格,并将下一个可行栅格加入禁忌表中,如此循环直到蚂蚁到达目标栅格。
步骤3:信息素全局更新。所有蚂蚁完成一次迭代后,找出本次迭代中的最优蚂蚁和最差蚂蚁,对最优蚂蚁搜索的航迹按照式(12)进行信息素更新;对最差蚂蚁搜索的航迹按照式(26)进行更新。
步骤4:结束搜索。判断迭代是否到达最大迭代次数,若达到最大迭代次数,则输出最优航迹长度;否则,清空禁忌表,令NC=NC+1,从步骤2开始重新循环搜索,直到满足循环次数NC=Nmax,输出最优航迹长度,算法结束。
3 仿真试验及结果分析 3.1 主要参数设置本文将蚁群-势场算法应用于重力辅助导航航迹规划问题中,通过多次仿真试验对比蚁群-势场算法和传统ACO,验证本文蚁群-势场算法的优越性。算法运行环境为:Windows 10 64 bit;Matlab R2014a。
由于到目前为止还没有确切的研究给出蚁群算法模型的最优参数设置,一般通过试验来选择参数。本文在参数变化范围内设置不同的参数组合,通过统计试验结果的优劣,选取最优参数组合。各个参数给出的范围如下:α∈0, 0.5, 1, 5,β∈0, 1, 3, 5, 8, 10,ε∈0, 0.5, 0.8, 1。
经过控制变量解算得出算法的主要参数为:α的最优值在1左右,β的最优值在5~10,ε的最优值在0.5左右。
3.2 人工设定10×10栅格航迹规划为对比蚁群-势场算法和传统ACO在航迹规划中的优劣程度,本文人工设定一个10×10的栅格,如图 4所示。蚁群-势场算法和传统ACO分别在此人工设定10×10栅格图上进行航迹规划。经过大量试验对算法参数进行调试,本次试验参数设定为最大迭代次数Nmax=100,蚂蚁个数M=50,α=1,β=8,ρ=0.1,ρ0=2,ε=0.5,引力常量k=2,斥力场量m=1,航迹规划结果如图 5所示。
如图 4、图 5所示,在栅格图内,白色栅格为自由栅格,黑色栅格为障碍栅格,左下方红色栅格为起点栅格,右下方绿色栅格点为目标栅格,带线圈的黑色折线为算法规划的航迹。
由图 5(a)、5(b)对比可以看出,传统ACO所得航迹并非最优航迹,而是收敛到一条较长航迹上;蚁群-势场算法则收敛到了最短航迹上。这是因为受传统ACO启发信息的影响,在第1次航迹规划迭代时蚂蚁会更趋向于选择离目标栅格较近的栅格,结合正反馈作用,之后迭代的蚂蚁也更趋向于选择这条航迹,并最终收敛于此航迹上;而蚁群-势场算法考虑人工势场法规划的航迹,并且将下一个栅格的位置信息考虑进来,对启发函数进行了重构,新的启发函数避免了传统ACO中这种情况的发生。因此,蚁群-势场算法则是收敛到了最短航迹上。
3.3 重力实测区域航迹规划为验证蚁群-势场算法在重力实测区域航迹规划的可行性,本文分别选取来自南海的两个试验区域。区域卫星测高重力异常数据来源于DTU10模型,格网分辨率为1′×1′,两个试验区域的重力异常分布如图 6所示。
首先,利用PCA对试验区域重力异常数据进行基于多特征值的重力辅助导航适配性分析。选取重力场标准差、粗糙度、相关系数、信息熵和坡度作为航迹规划衡量适配区的重力特征统计参数。求解重力统计参数贡献率和累计贡献率,当累计贡献率大于等于0.85后确定主成分个数,见表 1。根据表中的累计贡献率可以确定主成分个数k=3。通过计算区域可导航能力,导航能力大于0的区域被标记为适配区,小于0的区域被标记为非适配区,获得区域适配/非适配区标签。得到如图 7所示的二维栅格图,每个栅格包含20′×20′的重力异常数据。适配区在栅格图中标为白色,表示为自由区域;非适配区在栅格图中标为黑色,表示为障碍区域。
序号 | 区域1 | 区域2 | |||
贡献率 | 累计贡献率 | 贡献率 | 累计贡献率 | ||
1 | 0.408 8 | 0.408 8 | 0.461 8 | 0.461 8 | |
2 | 0.333 3 | 0.742 1 | 0.284 9 | 0.746 7 | |
3 | 0.179 5 | 0.921 6 | 0.172 2 | 0.918 9 | |
4 | 0.078 0 | 0.999 6 | 0.080 7 | 0.999 6 | |
5 | 0.000 4 | 1.000 0 | 0.000 4 | 1.000 0 |
从图 7可以看出,区域1的非适配区栅格分布比较集中,最终形成的障碍个数较少,形状比较规整,分布比较简单;区域2的非适配区栅格分布比较零散,且最终形成的障碍多为L形和正方形,分布较为复杂,航迹规划难度较大。所以本试验依据这两片海域的重力常数据设置了两种不同栅格环境,对蚁群-势场算法和传统ACO进行对比。
本次试验参数设定为最大迭代次数Nmax=100,蚂蚁个数M=50,α=1,β=8,ρ=0.1,ρ0=2,ε=0.5,引力常量k=2,斥力场量m=1,左上角红色栅格为起点栅格,右下角绿色栅格为目标栅格,带线圈的黑色折线为算法规划的航迹。简单环境下的航迹规划结果如图 8、图 9所示,复杂环境下的航迹规划结果如图 10、图 11所示。
由图 8与图 9对比可得,在简单环境中,通过10次试验后,蚁群-势场算法平均迭代次数为9.8次,最优航迹平均长度为16.485 3,平均用时为4.26 s;传统ACO平均迭代次数为46.7次,最优航迹平均长度为21.313 7,平均用时为9.87 s。
由图 10与图 11对比可得,在复杂环境中,通过10次试验后,蚁群-势场算法平均迭代次数为4.5次,最优航迹平均长度为14.485 3,平均用时为5.90 s;传统ACO平均迭代次数为28.6次,最优航迹平均长度为18.879 5,平均用时为10.33 s。
由以上对比分析可知,在简单环境和复杂环境两种栅格环境中,蚁群-势场算法的航迹均比传统ACO的航迹更为平滑,而且长度更短;利用蚁群-势场算法在UV重力辅助导航中进行航迹规划,航迹更优,收敛速度更快。
4 结论本文在全局静态环境下,利用栅格法对UV所经过海域的重力异常数据进行建模,针对ACO在水下重力辅助导航航迹规划中的不足,提出了一种改进的蚁群-势场算法。
蚁群-势场算法对信息素浓度更新规则进行了改进,引入了最优-最差蚂蚁系统,在有效缩小搜索最优航迹范围的同时,防止“早熟”现象的发生;利用人工势场法,依据初始路径,考虑UV当前栅格节点与下一个栅格节点之间的距离信息,对启发函数进行改进。新的启发信息能够有效避免算法在特殊环境中陷入局部最优,且利用人工势场法的先验航迹作为启发信息的参数,使得算法的收敛速度得以提高。
通过对算法的复杂度和实用性分析,并结合在特殊环境和复杂环境下的仿真结果来看,本文提出的蚁群-势场算法能够在UV重力辅助导航航迹规划中较好地躲避非适配区,顺利到达目标,且航迹平滑,航迹长度较短,能够更有效地进行航迹规划。
[1] |
李姗姗.水下重力辅助惯性导航的理论与方法研究[D].郑州: 信息工程大学, 2010: 74-81. LI Shanshan. Research on the theory and method of underwater gravity-aided inertial navigation[D]. Zhengzhou: Information Engineering University, 2010: 74-81. |
[2] |
PAULL L, SAEEDI S, SETO M, et al. AUV navigation and localization:a review[J]. IEEE Journal of Oceanic Engineering, 2014, 39(1): 131-149. DOI:10.1109/JOE.2013.2278891 |
[3] |
李姗姗, 吴晓平, 马彪. 水下重力异常相关极值匹配算法[J]. 测绘学报, 2011, 40(4): 464-469, 476. LI Shanshan, WU Xiaoping, MA Biao. Correlative extremum matching algorithm using underwater gravity anomalies[J]. Acta Geodaetica et Cartographica Sinica, 2011, 40(4): 464-469, 476. |
[4] |
文超斌, 王跃钢, 郭志斌, 等. 重力辅助导航高斯插值精化算法[J]. 测绘学报, 2015, 44(1): 13-18. WEN Chaobin, WAND Yuegang, GUO Zhibin, et al. Gravity aided navigation precise algorithm with Gauss spline interpolation[J]. Acta Geodaetica et Cartographica Sinica, 2015, 44(1): 13-18. DOI:10.11947/j.AGCS.2015.20130741 |
[5] |
李姗姗, 吴晓平, 赵东明. 导航用海洋重力异常图的孔斯曲面重构方法[J]. 测绘学报, 2010, 39(5): 508-515. LI Shanshan, WU Xiaoping, ZHAO Dongming. Coons curved surface reconstruction method of marine gravity anomaly map for navigation[J]. Acta Geodaetica et Cartographica Sinica, 2010, 39(5): 508-515. |
[6] |
ERIN B, ABIYEV R, IBRAHIM D. Teaching robot navigation in the presence of obstacles using a computer simulation program[J]. Procedia- Social and Behavioral Sciences, 2010, 2(2): 565-571. |
[7] |
王树西, 李安渝. Dijkstra算法中的多邻接点与多条最短路径问题[J]. 计算机科学, 2014, 41(6): 217-224. WANG Shuxi, LI Anyu. Multi-adjacent-vertexes and Multi-shortest-paths problem of Dijkstra algorithm[J]. Computer Science, 2014, 41(6): 217-224. |
[8] |
ZHOU Li, LI Wei. Adaptive artificial potential field approach for obstacle avoidance path planning[C]//Proceedings of the 7th International Symposium on Computational Intelligence and Design. Hangzhou: IEEE, 2014: 429-432.
|
[9] |
PANDA R K, CHOUDHURY B B. An effective path planning of mobile robot using genetic algorithm[C]//Proceedings of 2015 IEEE International Conference on Computational Intelligence & Communication Technology. Ghaziabad: IEEER, 2015: 287-291.
|
[10] |
JUANG C F, YEH Y T. Multiobjective evolution of biped robot gaits using advanced continuous ant-colony optimized recurrent neural networks[J]. IEEE Transactions on Cybernetics, 2018, 48(6): 1910-1922. DOI:10.1109/TCYB.2017.2718037 |
[11] |
NIE Zhibin, YANG Xiaobing, GAO Shihong, et al. Research on autonomous moving robot path planning based on improved particle swarm optimization[C]//Proceedings of 2016 IEEE Congress on Evolutionary Computation (CEC). Vancouver: IEEE, 2016: 2532-2536.
|
[12] |
于振中, 李强, 樊启高. 智能仿生算法在移动机器人路径规划优化中的应用综述[J]. 计算机应用研究, 2019, 36(11): 3210-3219. YU Zhenzhong, LI Qiang, FAN Qigao. Survey on application of bioinspired intelligent algorithms in path planning optimization of mobile robots[J]. Application Research of Computers, 2019, 36(11): 3210-3219. |
[13] |
王中兴, 牟琼, 李桥兴. 多属性决策的组合赋权法[J]. 应用数学与计算数学学报, 2003, 17(2): 55-62. WANG Zhongxing, MOU Qiong, LI Qiaoxing. A new combination weighting method in multiple attribute decision making[J]. Communication on Applied Mathematics and Computation, 2003, 17(2): 55-62. DOI:10.3969/j.issn.1006-6330.2003.02.008 |
[14] |
段海滨, 王道波, 朱家强, 等. 蚁群算法理论及应用研究的进展[J]. 控制与决策, 2004, 19(12): 1321-1326, 1340. DUAN Haibin, WANG Daobo, ZHU Jiaqiang, et al. Development on ant colony algorithm theory and its application[J]. Control and Decision, 2004, 19(12): 1321-1326, 1340. DOI:10.3321/j.issn:1001-0920.2004.12.001 |
[15] |
李靖华, 郭耀煌. 主成分分析用于多指标评价的方法研究——主成分评价[J]. 管理工程学报, 2002, 16(1): 38-43. LI Jinghua, GUO Yaohuang. Principal componnent evaluation:a multivariate evaluate method expanded from principal component analysis[J]. Journal of Industrial Engineering/Engineering Management, 2002, 16(1): 38-43. |
[16] |
CAO Jingang. Robot global path planning based on an improved ant colony algorithm[J]. Journal of Computer and Communications, 2016, 4(2): 11-19. DOI:10.4236/jcc.2016.42002 |
[17] |
屈鸿, 黄利伟, 柯星. 动态环境下基于改进蚁群算法的机器人路径规划研究[J]. 电子科技大学学报, 2015, 44(2): 260-265. QU Hong, HUANG Liwei, KE Xing. Research of improved ant colony based robot path planning under dynamic environment[J]. Journal of university of Electronic Science and Technology of China, 2015, 44(2): 260-265. DOI:10.3969/j.issn.1001-0548.2015.02.017 |
[18] |
于振中, 闫继红, 赵杰, 等. 改进人工势场法的移动机器人路径规划[J]. 哈尔滨工业大学学报, 2011, 43(1): 50-55. YU Zhenzhong, YAN Jihong, ZHAO Jie, et al. Mobile robot path planning based on improved artificial potential field method[J]. Journal of Harbin Institute of Technology, 2011, 43(1): 50-55. DOI:10.3969/j.issn.1009-1971.2011.01.007 |
[19] |
石为人, 黄兴华, 周伟. 基于改进人工势场法的移动机器人路径规划[J]. 计算机应用, 2010, 30(8): 2021-2023. SHI Weiren, HUANG Xinghua, ZHOU Wei. Path planning of mobile robot based on improved artificial potential field[J]. Journal of Computer Applications, 2010, 30(8): 2021-2023. |
[20] |
陈金鑫, 董蛟, 朱旭芳. 改进人工势场法的移动机器人路径规划[J]. 指挥控制与仿真, 2019, 41(3): 116-121. CHEN Jinxin, DONG Jiao, ZHU Xufang. Robot path planning based on improved artificial potential field method[J]. Command Control & Simulation, 2019, 41(3): 116-121. DOI:10.3969/j.issn.1673-3819.2019.03.025 |
[21] |
张建英, 刘暾. 基于人工势场法的移动机器人最优路径规划[J]. 航空学报, 2007, 28(S1): S183-S188. ZHANG Jianying, LIU Tun. Optimized path planning of mobile robot based on artificial potential field[J]. Acta Aeronautica et Astronautica Sinica, 2007, 28(S1): 183-188. |
[22] |
TAN Guanzheng, DOU Hongquan. ACS algorithm-based adaptive fuzzy PID controller and its application to CIP-I intelligent leg[J]. Journal of Central South University of Technology, 2007, 14(4): 528-536. DOI:10.1007/s11771-007-0103-3 |
[23] |
WANG Zhen, LI Jianqing, FANG Manlin, et al. A multimetric ant colony optimization algorithm for dynamic path planning in vehicular networks[J]. International Journal of Distributed Sensor Networks, 2015(11): 21-32. |
[24] |
CHIANG H T, MALONE N, LESSER K, et al. Path-guided artificial potential fields with stochastic reachable sets for motion planning in highly dynamic environments[C]//Proceedings of 2015 International Conference on Robotics and Automation. Seattle, WA: IEEE, 2015: 2347-2354.
|
[25] |
李康顺, 徐福梅, 张文生, 等. 一种基于启发式演化算法的最优-最差蚂蚁系统[J]. 中南大学学报(自然科学版), 2010, 41(2): 609-614. LI Kangshun, XU Fumei, ZHANG Wensheng, et al. An improved best-worst ant system based on heuristic evolutionary algorithm[J]. Journal of Central South University (Science and Technology), 2010, 41(2): 609-614. |
[26] |
MELINGUI A, MERZOUKI R, MBEDE J B, et al. A novel approach to integrate artificial potential field and fuzzy logic into a common framework for robots autonomous navigation[J]. Proceedings of the Institution of Mechanical Engineers, Part I:Journal of Systems and Control Engineering, 2014, 228(10): 787-801. DOI:10.1177/0959651814548300 |
[27] |
龚本灿, 李腊元, 蒋廷耀, 等. 基于信息素适量更新与变异的高效蚁群算法[J]. 计算机工程与应用, 2008, 44(1): 45-47. GONG Bencan, LI Layuan, JIANG Tingyao, et al. Efficient ant colony algorithm based on right pheromone updating and mutation[J]. Computer Engineering and Technology, 2008, 44(1): 45-47. DOI:10.3778/j.issn.1002-8331.2008.01.014 |