基于混合蚁群算法的无人船航行路径自主规划.pdf

第45卷第2 2 期2023年11月舰船科学技术SHIP SCIENCEANDTECHNOLOGYVol.45,No.22Nov.,2023基于混合蚁群算法的无人船航行路径自主规划陈宇文，徐照2（1.南京工业大学土木工程学院，江苏南京2 10 0 0 0；2.东南大学土木工程学院，江苏南京2 10 0 0 0）摘要：路径规划是无人船自主导航的核心问题。由于无人船当前位置以及目标位置的确定受到障碍物影响，最佳航行路径的获取难度较大。为此，提出基于混合蚁群算法的无人船航行路径自主规划方法。采用栅格法构建无人船工作环境模型，由上至下、由左至右的对栅格完成编号处理，划分安全区域与障碍物区域。构建无人船航行路径自主规划数学模型，设定地形与威胁、航程上限以及路径平滑度等约束条件。针对蚁群算法初始搜索效率差等问题，将其与粒子群算法相结合，提出混合蚁群算法。利用该算法求解无人船航行路径自主规划数学模型。实验结果显示，研究方法具有较高的路径规划准确性，路径长度、平均能耗及路径规划时间指标均较优。关键词：混合蚁群算法；无人船；路径规划；栅格法；数学模型；约束条件中图分类号：TP391文章编号：16 7 2-7 6 49(2 0 2 3)2 2 0 0 930 4Autonomous planning of unmanned ship navigation path based on(1.College of Civil Engineering,Nanjing Technology University,Nanjing 210000,China;2.School of Civil Engineering,Southeast University,Nanjing 210000,China)Abstract:Path planning is the core problem of unmanned ship autonomous navigation.Because the current positionand target position of unmanned ship are affected by obstacles,it is difficult to obtain the best navigation path.Therefore,anautonomous path planning method for unmanned ships based on hybrid ant colony algorithm is proposed.The working envir-onment model of unmanned ship is constructed by grid method.The grid is numbered from top to bottom and from left toright,and the safe area and the obstacle area are divided.The mathematical model of autonomous navigation path planning ofunmanned ship is constructed,and the constraint conditions such as terrain and threat,range upper limit and path smooth-ness are set.Aiming at the problem of poor initial search efficiency of ant colony algorithm,a hybrid ant colony algorithm isproposed by combining it with particle swarm optimization algorithm.This algorithm is used to solve the mathematical mod-el of autonomous navigation path planning for unmanned ships.The experimental results show that the proposed method hashigher path planning accuracy,and the indexes of path length,average energy consumption and path planning time are better.Key words:hybrid ant colony algorithm;unmanned ships;path planning;grid method;mathematical model;constraint condition0引言无人船能在人力不可为的条件下实现水面和水下目标侦察与监视等任务!，是当前水面智能体的典型代表，受到各界普遍关注。在复杂工作环境下，航行路径规划是无人船正常工作的基础与保障 2 。王立鹏等 3 在研究舰船路径规划问题过程中，以收稿日期：2 0 2 3-0 7-11作者简介：陈宇文（1995-），男，硕士，助理工程师，研究方向为路径优化。文献标识码：Ahybrid ant colony algorithmCHEN Yu-wen,XUZhao?doi:10.3404/j.issn.1672-7649.2023.22.017海图为基础，确定航线与陆地物标的对应关系，采用遗传算法对规划路径进行寻优，获取最优规划路径。该方法在目标工作环境较为复杂的条件下，规划结果精度无法保障。周怡等 4在研究舰船路径规划问题过程中，以防碰撞为目的构建航行路径规划模型，采用优化后的DDPG算法求解模型获取最优路径。该方法94在实际应用过程中无法保障收敛速度与寻优性能的平衡性。针对上述问题，提出基于混合蚁群算法的无人船航行路径自主规划方法，获取最优航行路径。1无人船航行路径的自主规划1.1环境建模无人船航行路径自主规划之前，需先构建无人船工作环境模型，由此能在无人船工作环境中明确哪些区域是安全区域，哪些区域为障碍物区域。设定无人船工作环境中的障碍物均处于静止状态，由于栅格法描述简单，易于实现，因此通过栅格法构建工作环境模型 5，以A和B分别表示安全区域与障碍物区域。以方形地图表示无人船工作环境，栅格法中包含若干个边长为1的小正方形，其中白色区域和黑色区域分别为安全区域和障碍物区域。以方便后续对无人船工作环境信息的描述为目的，由上至下、由左至右的对栅格实施编号处理。在栅格间距确定过程中的主要依据为栅格点中心位置坐标，所以，可通过式（1）描述栅格号与无人船工作环境坐标(x,y)间的对应关系：nX=0*ceil(MM）+-mod(n,M)(MM+式中：Es和ceil分别为小栅格的边长和向上取余函数；n和MM分别为小栅格的序号和栅格的整体行数；mod为余函数。1.2航行路径自主规划数学模型构建无人船工作环境模型后，再构建无人船航行路径自主规划的数学模型。无人船航行路径自主规划问题可描述为：在任意规划空间内，符合相应约束条件g()=0的基础上，依照某一航行性能评价指标J，规划确定无人船的航行路径，也就是由起始点Es至目标点EG，同时符合相应约束条件的一系列路径节点T=(Es,Ei,E2,.,En,Ecl。利用式（2）能够描述无人船航行路径自主规划数学模型：minJ=DpV(x.,)式中：D和分别为水动力系数和水密度；v和p分别为无人船航行速度和横截面积；和H分别为无人船航行路径长度和机械效率。舰船科学技术约束条件如下：1）地形与威胁约束。无人船航行过程中，为保障航行安全性，需防止与障碍物产生碰撞，因此设定无人船工作环境中，障碍物与危险区域均为不可穿越的区域 。若以R表示在无人船工作区域内不可穿越区域集合，考虑无人船自身的尺寸，同时考虑规划路径的平滑性，需对障碍物与危险区域实施膨化处理，由此保障无人船航行的安全性。以Rf=sR表示通过膨化处理的集合，也就是扩大障碍物与危险区域大小，依照无人船实际尺寸可确定膨化系数。以f(x,y)表示规划出的无人船航行路径，由此得到约束公式描述：V(x,y)Rf,f(x,y).minJ=O。(3)2）航程上限约束。无人船内部携带能量对于航行距离上限Lmax产生直接影响 7，因此在无人船航行路径自主规划过程中需设定相关约束条件，公式描述如下：f(x,y)(g+og)maxo(4)式中，g和8 g分别为规划路径长度与实际航行路径与规划路径的偏差。3）转弯角度约束。无人船航行转弯过程中受自身机动性能影响 8 ，导致角度受到一定限制，以和;分2别表示无人船允许的最大拐角与任意拐弯角，约束条(1)件公式描述如下：d;s,Vn。4）路径平滑度约束。无人船航行路径越平滑，对自身的机动性要求越低。考虑无人船航行过程中需消耗大量能量，为路径的平滑性能够降低能源消耗。描述该约束条件公式为：e(R-r)Sk=SmaxoL式中：Sk和n分别为第k条路径累积转弯角度和路径点数量；R为无人船航行路径的最大转弯角度；r和Smax分别为路径内的转弯角度和允许的最大平滑度。1.3基于混合蚁群算法的模型求解考虑蚁群算法应用过程中存在初始阶段搜索效率差、有较大概率获取局部最优结果等问题，将其与粒2Sd子群算法相结合，提出混合蚁群算法。针对式（2）无(2)2第45卷(5)(6)人船航行路径自主规划数学模型，采用混合蚁群算法进行求解。将由无人船航行路径解集内选取最优路径的问题描述为蚂蚁搜索食物的问题，设定无人船航行路径解集内各解以及最优解，分别为蚂蚁搜索食物过第45卷程中路经的城市和目标点。依照无人船航行路径自主规划的实际情况，初始化混合蚁群算法参数，设定蚁群数量与最大送代次数分别设定为2 0 0+10 0 次和150 50 次，信息素挥发系数与信息素增加浓度范围分别为0.50.2 和5.54.5，信息素初始浓度范围与启发因子关键度范围分别为5545和52，信息素关键度范围为52。计算蚂蚁个体的适应度V，其所描述的是蚂蚁种群的属性，能够描述蚂蚁的优劣水平，公式描述如下：J=Skwzi+ce(pi+si)/max(7)式中：w和zi分别为惯性权重与第i只蚂蚁的位置；c和s分别为蚂蚁个体学习因子和范围为 0,1 的随机数；p;和si分别为第i只蚂蚁个体极限与速度的第d维分量。蚂蚁依照设定的迭代次数对无人船最优航行路径实施全局搜索，每实施一次搜索即完成一次迭代过程。蚂蚁在搜索无人船最优航行路径过程中会产生信息素，所以每次迭代过程后就需更新搜索路径中遗留的信息素T(t+1)，公式描述如下：T(t+1)=3(1-p)w+T。式中：p和分别为启发因子关键度和信息素更新系数；T为与收敛次数成线性相关性的函数。为避免目标送代过程中陷人局部最优问题，对信息素上限值实施设定，公式描述如下：T(t+1)HTmax=pLmin式中，Tmax和H分别表示信息素上限值与混沌变量。约束不同搜索路径上的信息素浓度，令无人船最优航行路径搜索空间内全部路经均由被选择的概率，通过式（9）更新的蚁群位置与信息素，确定当前蚁群位置是否为个体极值，若是个体极值，就需将当前位置与全局极值进行对比；若不是个体极值，则需返回上一过程再次确定。在满足迭代标准后，即可终止运算过程，输出信息浓度最高的解作为最优解，即无人船航行路径自主规划的最优路径。2实验结果为验证本文方法在路径自主规划中的应用效果，选取某型号的无人船为研究对象，表1为研究对象相关参数。设定研究对象的工作环境大小为2 42 0 km，采用本文方法对研究对象航行路径进行自主规划。陈宇文，等：基于混合蚁群算法的无人船航行路径自主规划起始点坐标与终点坐标。201612(8)8400图1本文方法航行路径自主规划结果(9)Fig.1 The results of autonomous navigation path planning using分析图1可知，采用本文方法能够有效构建研究对象工作环境模型，同时通过计算能够有效获取研究对象最优航行路径，该路径能够有效避开全部障碍物与危险区域。为验证本文方法航行路径规划结果的优势性，对比采用本文方法前后研究对象的航行路径，结果如表2所示。分析表2 可知，采用本文方法对研究对象航行路径进行规划后，最优路径长度与采用本文方法前相比减少1.58 6 1km，平均能耗降低6.42 11kJ，路径规划时间降低3.56 5s。以上数据充分说明采用本文方法能够有效保障研究对象航行路径规划的精度与实时性，降低研究对象航行能耗，保障研究对象航行过程中的经济性。95表1研究对象相关参数Tab.1 Relevant parameters of the research object船型船体材质船体尺寸船体重量勘测系统范围勘测系统精度动力系统定位定向系统通讯控制采用本文方法获取的研究对象最优航行路径规划结果，如图1所示。图中，黑色方块为研究对象工作环境中的障碍物与危险区域，白色圆形为研究对象的48Y/kmthe method presented in this articleM型三体流线型高分子耐腐蚀100 x550 x350mm15.5kg120m0.1%h（h 表示水深m）3片式航空铝合金奖叶，直流泵喷卫星系统，内置GNSS接收机，包含432 通道数内置电台、4G网络；5.8 GHz视频与遥控通信1216202496Tab.2 Comparison results of navigation paths of research subjects对比项最优路径长度/km最优路径平均值最优路径选代次数/次收敛路径平均值收敛路径选代次数/次运行时间/s平均能耗/kJ3结语本文研究了一种基于混合蚁群算法的无人船航行路径自主规划方法，在工作环境模型基础上构建航行路径规划数学模型，并采用混合蚁群算法求解模型。实验结果显示，本文方法所构建的工作环境模型较为准确，所得最优路径规划结果路径最短、能耗最低。参考文献：1马小轩,吴韵哲，吴浩峻，等.基于改进人工势场法的水下自主航行器路径规划 J.船舶工程，2 0 2 1,43(9)：8 9-93+10 0.MA Xiaoxuan,WU Yunzhe,WU Haojun,et al.Path planning ofautonomous underwater vehicle based on improved artificial po-tential field methodJ.Ship Engineering,2021,43(9):89-93+100.2滕建平，梁霄，陶浩，等.无人水下航行器全局路径规划及有限时间跟踪控制 1.上海海事大学学报,2 0 2 2,43(1):1-7.TENG Jianping,LIANG Xiao,TAO Hao,et al.Global pathplanning and finite-time tracking control of unmanned underwa-ter vehiclesJ.Journal of Shanghai Maritime University,2022,43(1):1-7.舰船科学技术表2 研究对象航行路径对比结果3王立鹏张智，马山，等.考虑船舶操纵性约束的改进遗传算法航线规划 J.哈尔滨工程大学学报，2 0 2 1，42(7):1056-1062.采用本文方法前采用本文方法后47.223845.637747.5694446.276553.014.147.828047.107993.644.917.110213.545284.350277.9291第45卷WANG Lipeng,ZHANG Zhi,MA Shan,et al.Improved genet-ic algorithm-based ship route planning considering ship maneu-verability constraintsJ.Journal of Harbin Engineering Univer-sity,2021,42(7):1056-1062.4】刘智萍，周清华，彭吉琼，等.基于免疫遗传优化的实时交通路径诱导方法 .计算机仿真，2 0 2 2,39(2)：98-10 1+418.LIU Zhiping,ZHOU Qinghua,PENG Jiqiong,et al.Real-timetraffic path induction method based on immune genetic opti-mizationJJ.Computer Simulation,2022,39(2):98-101+418.5】胡致远,王征，杨洋，等.基于人工鱼群-蚁群算法的UUV三维全局路径规划 .兵工学报,2 0 2 2,43(7)：16 7 6-16 8 4.HU Zhiyuan,WANG Zheng,YANG Yang,et al.Three-dimen-sional global path planning for UUV based on artificial fishswarm and ant colony algorithmJ.Acta Armamentari,2022,43(7):16761684.6曹建秋，徐鹏，张广言.基于贪心策略下混合蚁群算法的无人机航迹规划 1 重庆交通大学学报（自然科学版),2 0 2 1,40(9):9-16+23.CAO Jianqiu,XU Peng,ZHANG Guangyan.Path Planning ofUAV basedon hybrid ant colony algorithm under greedy strate-gyJ.Journal of Chongqing Jiaotong University(Natural Sci-ences),2021,40(9):9-16+23.7张岳星，王轶群，李硕，等.基于海图和改进粒子群优化算法的AUV全局路径规划 J.机器人,2 0 2 0,42(1):12 0-12 8.ZHANG Yuexing,WANG Yiqun,LI Shuo,et al.Global pathplanning for AUV based on charts and the improved particleswarm optimization algorithmJ.Robot,2020,42(1):120-128.8荆学东，杜黎童，郭泰，等.基于混合参数蚁群算法的移动机器人路径规划 .机床与液压,2 0 2 2,50(9):41-47.JING Xuedong,DU Litong,GUO Tai,et al.Mobile robot pathplanning based on mixed parameter ant colony algorithm.Machine Tool&Hydraulics,2022,50(9):41-47.