基于改进A%5E%28＊%29算法融合角度信息的船舶路径规划.pdf

第44卷第2 期2023年6 月D01:10.13340/j.jsmu.2023.02.002上海海事大学学报Journal of Shanghai Maritime UniversityVol.44No.2Jun.2023文章编号：16 7 2-9 49 8(2 0 2 3)0 2-0 0 0 6-0 5基于改进 A*算法融合角度信息的船舶路径规划张浩，庞宁林，胡安康，肖英杰，陈锦标（上海海事大学商船学院，上海2 0 130 6）摘要：为解决传统A*算法在施工水域对船舶进行路径规划时搜索节点多、拐点多、节点拓展方向范围广等问题，提出一种基于改进A*算法融合角度信息的路径规划方法。首先，定义加权因子，将其引入A*算法的启发函数中，以此提高路径规划的效率；其次，引入角度信息，诱导搜索节点分布在起始点到目标点的连线附近；最后，添加转弯修正代价参数，并对路径进行二次优化，提高路径平滑性。实验结果表明，该方法在简单环境下的搜索时间能缩短45.8%，在复杂环境下的搜索时间能缩短6 3%，并且能够有效剔除余节点，使路径变得更加平滑。关键词：改进A*算法；角度融合；路径平滑；路径规划中图分类号：U675.79Ship path planning based on improved A*algorithm文献标志码：Aand adding angle informationZHANG Hao,PANG Ninglin,HU Ankang,XIAO Yingjie,CHEN Jinbiao(Merchant Marine College,Shanghai Maritime University,Shanghai 201306,China)Abstract:In order to solve the problems of multiple search nodes,many turning nodes and wide range ofnode expansion direction when the traditional A*algorithm is used to conduct the ship path planning inconstruction waters,a path planning method based on the improved A*algorithm and adding angleinformation is proposed.First,a weighting factor is defined and introduced into the heuristic function ofA*algorithm to improve the efficiency of path planning.Second,the angle information is introduced toinduce the search nodes to be distributed near the connection line from the starting point to the targetpoint.Finally,a turning correction cost parameter is added,and the path is optimized again to improvethe path smoothness.The experimental results show that,this method can reduce the search time by45.8%in simple environment and 63%in complex environment,and can effectively eliminate redundantnodes to make the path smoother.Key words:improved A*algorithm;angle fusion;path smoothing;path planning收稿日期：2 0 2 2-0 3-10 修回日期：2 0 2 2-0 5-11基金项目：2 0 2 2 年度上海市教育委员会地方院校能力建设计划（Z20228005）；上海高水平地方高校创新团队（海事安全与保障）作者简介：张浩（19 8 2 一），男，湖北襄阳人，高级工程师，博士，研究方向为航运安全与航海仿真、海上作业与海事保障，(E-mail)haozhang ;庞宁林（19 9 6 一），女，河南周口人，硕士研究生，研究方向为海上智能交通、路径规划，（E-mail)；胡安康（19 9 7 一），男，河南信阳人，硕士研究生，研究方向为海上智能交通，（E-mail)；肖英杰（19 59 一），男，广东潮州人，教授，船长，博士，研究方向为载运工具运用工程、通航安全保障，（E-mail)http:/hyxb 第2 期0引言近几年,海上施工对船舶航行产生了一定的影响,海上施工过程中的不确定因素对船舶通航安全造成威胁 。船舶在途经施工水域时,多次转弯容易引发碰撞事故，导致通行和施工效率较低。为提高航行效率，需要提前对船舶路径进行规划,并对路径进行平滑处理。无论是否涉及障碍物躲避，船舶路径规划的本质是采用一定的性能评价函数,在最小或较小的消耗代价下寻找一条从起始点到目标点的最优或次优路径 2。传统的路径规划方法主要有A算法、人工势场法、粒子群优化（particleswarmoptimization，PSO）算法和遗传算法等；近几年，还出现了一些新的路径规划方法,例如深度Q网络法 3、D*算法 4等。文献 5针对传统A*算法规划的路径存在很多穴余点和拐点的问题，改进评价函数的权重系数和路径生成策略，提高路径的平滑性，但是未能从根本上解决搜索效率低的问题。文献 6 引人领域矩阵进行障碍搜索,改善了路径的搜索效率,但是仍然存在规划的路径上穴余点和拐点过多的问题。文献7在A*算法中加人时间惩罚因子,解决了传统A*算法规划的路径上拐点过多的问题，但未能解决搜寻节点过多的问题。文献 8 采用双向搜索机制对A*算法进行改进，通过从起始点和从目标点的交替搜索减少了搜索节点的数量,但效果不太理想,在面积较大的区域内搜索节点仍然很多，且未能解决拐点过多的问题。文献 9 建立海洋气象环境影响模型,考虑海流和风浪对航速的影响来生成路径,但是以航行时间最短为目标的路径规划有时并不适用于复杂水域。文献 10 为了解决在受限水域的单目标路径规划问题，提出一种混合粒子群遗传算法，但是该智能算法存在随机性和输出路径不唯一的问题。A*算法是一种在静态路网中求解最短路径最有效的直接搜索方法,适用于全局路径规划，改进后的A*算法也可用于局部路径规划。本文在栅格化环境模型的基础上，改进A*算法并融合角度信息，提出一种改进的路径规划方法,解决传统A*算法搜索节点多、拐点多、节点拓展方向范围广等问题。利用MATLAB验证方法的有效性和可行性。1环境模型的建立环境建模的目的是将实际环境转换成简单的、方便算法实施的抽象空间。面向路径规划的环境建张浩，等：基于改进A*算法融合角度信息的船舶路径规划基于栅格法的环境建模如图1所示：将工作环境转化为一个矩形图，再将矩形图分割为多个大小相等的网格单元，每个网格单元存储着对应的信息，其中，黑色栅格为障碍物，白色栅格为自由通行区域，和分别为起始点和目标点所在栅格。栅格法的数据结构简单,便于空间分析和地表模拟,能在矩形图上清晰明了地表示所生成的路径点，且可将水域内全局路径规划问题转化为在栅格环境中寻找两节点之间的最优路径问题。2?本文方法的描述与实现2.1传统A*算法基本思想及缺点A*算法是全局路径规划中的一种智能启发式算法，因其良好的通用性和拓展性，常被广泛应用于物流配送 1、物联网 12、无人驾驶 13-4等众多领域。A算法流程 15-17：从起始点开始向相邻节点进行拓展；根据评价函数计算待拓展节点的代价，从中选取代价最小的节点作为拓展节点；当搜索到目标点时便可生成最优路径。评价函数用于确定拓展方向,是A*算法的重要组成部分,其一般形式为f(C)=g(C)+h(C)式中：g(C)为在状态空间中从起始点到当前节点C已消耗的代价;h(C)为预计从当前节点C到目标点需要消耗的代价。在评价函数中,启发函数h（C)是影响 A*算法的重要因素,是保证找到最优解的关键。将当前节点C到目标点的实际距离用d（C）表示，那么h(C)存在两种情况:若h（C)d(C),则拓展的节点多,虽然能找到最优解，但搜索范围大，其中h(C)=d(C)意味着搜索是沿着最短路径进行的，此时搜索效率最高;若h（C）d(C）,则拓展的节点少,效率高，但不能保证得到最优解，当h（C）比d(C)大很多时,只有h(C)起作用,此时仅追求搜索效率而无法获得合理路径。传统A*算法规划的路径往往不具有连续的曲率且拐点过多，与船舶的运动特性不符，并且效率http:/7模方法一般有栅格法、单元树法、空间法和拓扑地图法。因为栅格法所建立的环境模型能简单地表示地图信息，且便于维护和修改，所以采用栅格法建立环境模型。图1基于栅格法的环境建模示意图hyxb 二8低，不适用于复杂环境。在复杂环境（如施工水域）下进行船舶路径规划，不仅要寻找最短路径,还要保证路径拐点不太多。若采用传统A*算法进行复杂环境下的路径规划,则精度要求越高，耗时越长，路径拐点也越多,并且在路径拐点和障碍物处会出现卡死现象。2.2改进A*算法常用的距离估算方法主要有曼哈顿距离、欧氏距离、切比雪夫距离估算方法。从图2 可以直观看出3种距离估算方法的特点：欧氏距离估算方法可向任意方向运动；切比雪夫距离估算方法允许向8个方向移动，但若两点间存在障碍物，则估算结果可距离估算方法曼哈顿距离欧氏距离切比雪夫距离max(l x1-x2 I,I y1-y2 I)启发函数h（C）主要用于确定搜索方向，对最终路径搜索结果和搜索效率起主要作用。它表示当前节点C到目标点G的估计成本。h(C)=ICG|=xc-xel+lyc-yel式中：CG为从当前节点C到目标点G的向量。设SG为从起始点S到目标点G的向量,为CG与SG之间的夹角。为尽可能避免船舶在施工水域航行时频繁转向,对A*算法的启发函数h(C)进行改进,得到h*(C)=wh(C)+(1-cos 0)IC SG|+式中:C=|xc-xcllyc-ysl-xc-xsllyc-ycl;为转弯修正代价参数;w为加权因子。对h(C)进行加权可使算法根据当前节点所处区域进行方向调整，保证搜索朝着最有希望到达目标点的方向前进，提高搜索效率；引人角度来纠正节点拓展方向；引入转弯修正代价参数以保证优先选择直行路径。为避免在路径搜索过程中遇到相同代价的节点时出现卡死和抖动现象，对加权因子w进行选择。分别设置w=1,2，,10 进行路径搜索，得到w=3时效率最高,故选取W=3。2.3角度的选取为诱导A*算法拓展的节点分布在直线SG附http:/hyxb 上海海事大学学报能与实际结果相差较大,故适用于障碍物较少的环境；曼哈顿距离估算方法允许向上、下、左、右4个方向运动,估算结果与实际结果相差不大，距离估算准。3种距离估算方法的具体公式和优缺点见表1，其中平面坐标系内的点用（x;,y;）表示。通过比较，选择曼哈顿距离进行复杂环境下的距离估算。图2 3种距离估算方法对比表13种距离估算方法优缺点比较计算公式优点不涉及对角线的移动，计算方I xi-x2 I+I y1-y2 1便，适用于复杂环境/x1-x2)+(y1-2)2简单直观适用于允许无限制八向移动的距离估算近，在启发函数中引人角度。cos =TsGI ICGT其中，SG|=(X-X,)+(Yc-Y,)2ICG|=(Xc-Xc)+(Yc-Yc)2起始点到目标点的距离|SGI是不变的，当前节点到目标点的距离ICGI是随的变化而变化的。若0 cos 1,则SG与CG的方向基本相同,e0,90);若-1cos 0,则S与CG的方向基本相反，=（9 0,18 0;若cos=0,则G与CG相互垂直。越小,拓展的节点连出的路径更接近理想路径。在改进的启发函数h*(C)中,1-cos 用来引导算法优先选择转角小的路径，纠正节点拓展方向。2.4路径优化传统A*算法只进行一次路径规划,得到的是在其约束条件下的最佳路径。由于A*算法是寻求最小代价的路径,所以规划出的路径可能出现过多的拐点。为减少拐点，在启发函数中引人转弯修正代价参数。调整后,对已规划好的路径进行二次优化，减少不必要的路径节点，提升路径平滑性。二次路径优化时,要保证在不增加距离的基础上减少拐第44卷一曼哈顿距离切比雪夫距离欧氏距离缺点更容易给出一个更大的计算值，不太可能是最短路径未考虑两点之间是否有障碍物，稳定性不太好，过于理想化通常适用于障碍物较少的环境SG.c第2 期点。具体方法：遍历已规划好的路径中的所有节点，如果遍历的节点恰好能构成期望的直线，则跳出修正；从起始点到目标点依次取出3个连续节点进行遍历检查,判断节点与节点k+2之间是否存在障碍,若不存在,则删除中间节点k+1,并延长节点k和节点k+2所在线段拓展新的路径节点；剔除第一个节点继续进行上述步骤直到遍历完所有节点，跳出修正。张浩，等：基于改进A*算法融合角度信息的船舶路径规划93仿真验证通过MATLAB仿真验证本文方法的有效性和可行性。设置30 30 的栅格环境，包括障碍物占20%的简单环境和障碍物占40%的复杂环境，仿真结果见图3和4,其中被其他颜色覆盖的黑、白栅格代表搜索路径所遍历过的节点所在的栅格。(a）传统A*算法图3简单环境下3种算法的路径规划结果(b)改进A*算法(c）本文方法(a）传统A*算法图4复杂环境下3种算法的路径规划结果从图3和4可以看出：传统A*算法搜索范围太大,规划出的路径拐点多,还容易在搜索过程中出现卡死现象；改进A*算法能缩小7 5%的搜索范围；本文方法不仅能缩小搜索范围，还能减少拐点,规划出的路径更平滑。如图5和6 所示是用栅格法建立环境模型后传统A*算法和本文方法的路径规划结果。从图中可以明显看出，本文方法规划出的路径比传统A*算法图5传统A*算法路径图6 本文方法路径规划结果规划结果(b）改进A*算法规划出的路径更平滑。图7 是在不同障碍物占比情况下3种算法规划出的路径上拐点数量的对比。从图7 可以看出,与传统A*算法相比，改进A*算法和本文方法规划出的路径上的拐点数量都有所减少。图8 是本文方法相比传统A*算法在搜索时间和路径平滑性上的优化效果：障碍物占比越高，优化率越高。40+传统心法50搜索时间30一改进A算法+本文方法20100152025,30,3540障碍物占比/%图7 3种算法规划出的路径上拐点数量对比由表2 可知：在简单环境下，本文方法比改进A*算法少了11个路径拐点，比传统A*算法缩短了http:/(c）本文方法40路径平滑性%/7/3020100152025303540障碍物占比/%图8本文方法相比传统A*算法的优化效果hyxb 10环境简单环境拐点数量搜索节点数量655搜索时间/s6.645复杂环境拐点数量搜索节点数量66645.8%的搜索时间；在复杂环境下，本文方法比改进A*算法少了4个路径拐点，比传统A*算法缩短了63%的搜索时间。通过分析可知：剔除亢余节点会提升算法的搜索效率，并且在复杂环境下算法的搜索效率更高，能够很好地适用于复杂环境下的路径搜索；路径优化使得路径拐点减少，路径更平滑；路参考文献：1】张波菲，谢新连，何傲，基于Maklink图和布谷鸟搜索算法的施工水域路径规划 J.上海海事大学学报，2 0 2 0，41(3）：6-11.D0I：10.13340/j.jsmu.2020.03.002.【2】薛飞基于无人船的路径规划与避障问题研究 D哈尔滨：哈尔滨工程大学，2 0 17.【3韩志豪，汪益兵，张宇，等基于深度强化学习的船舶航线自动规划 J中国航海，2 0 2 1，44(1)：10 0-10 5.【4】刘逸凡，黄友锐，韩涛融合有向D*与RRT*的移动机器人路径规划算法 J.计算机仿真，2 0 2 1，38（7)：317-32 2.【5】王中玉，曾国辉，黄勃，等。改进A*算法的机器人全局最优路径规划 J.计算机应用，2 0 19，39（9)：2 517-2 52 2.【6 陈若男，文聪聪，彭玲，等改进A*算法在机器人室内路径规划中的应用 J，计算机应用，2 0 19，39(4)：10 0 6-10 11.【7】张新艳，邹亚圣，基于改进A*算法的自动导引车无碰撞路径规划 J系统工程理论与实践，2 0 2 1，41(1：2 40-2 46.【8 孔继利，张鹏坤，刘晓平，双向搜索机制的改进A算法研究 J计算机工程与应用，2 0 2 1，57(8)：2 31-2 37.9】谢新连，刘超，魏照坤：海洋气象环境影响下的复杂水域船舶路径规划 J重庆交通大学学报（自然科学版），2 0 2 1，40(2）：1-7.10 SIREGAR B,GUNAWAN D,ANDAYANI U,et al.Food delivery system with the utilization of vehicle using geographical information system(CIS)and A star algorithmJJ.Jourmal of Physics:Conference Series,2017,801(1):012038.D0I:10.1088/1742-6596/801/1/012038.11 LIU Z,LIU J X,ZHOU F,et al.A robust GA/PSO-hybrid algorithm in intelligent shipping route planning systems for maritime traffic networksJ.Journal of Internet Technology,2018,19:1635-1644.D0I:10.3966/160792642018111906001.12 HASEEB K,ISLAM N,SABA T,et al.LSDAR:a light-weight structure based data aggregation routing protocol with secure internet of thingsintegrated next-generation sensor networks J.Sustainable Cities and Society,2020,54:101995.D01:10.1016/j.scs.2019.101995.13】岳秀，张超峰，张伟，等基于A-star和改进模拟退火算法的航迹规划 J控制工程，2 0 2 0，2 7（8）：136 5-137 1.D0I：10.1410 7/ki.kzgc.170890.14杨瑶，付克昌，蒋涛，等.改进A*算法的智能车路径规划研究 J计算机测量与控制，2 0 2 0，2 8（10）：17 0-17 6.D0I：10.16 52 6/ki.11-4762/tp.2020.10.035.15 KANG N K,SON H J,LEE S H.Modified A-star algorithm for modular plant land transportationJ.Journal of Mechanical Science andTechnology,2018,32(12):5563-5571.16 YANG D,XU B,RAO K Y,et al.Passive infrared(PIR)-based indoor position tracking for smart homes using accessibility maps and A-staralgorithmJ.Sensors,2018,18(2):332.D0I:10.3390/s18020332.17劳彩莲，李鹏，冯宇基于改进A*与DWA算法融合的温室机器人路径规划 J农业机械学报，2 0 2 1，52（1）：14-2 2.上海海事大学学报表2 不同环境下仿真结果评价指标比较径的搜索方向更倾向于目标点，抖动现象有所改善。传统A*改进A*指标算法搜索时间/s1.2361315第44卷本文因此,本文方法具有一定的优势。算法方法0.6850.67019877802.7822.39215111191134结束语为提高船舶在施工水域内的航行效率，解决传统A*算法存在的搜索节点多、拐点多、节点拓展方向范围广等问题，对启发函数进行加权，并引入角度信息诱导搜索范围分布在所期望的路径附近，最后引人转弯修正代价参数对路径进行平滑处理。MATLAB仿真结果验证了本文方法的有效性和可行性。与传统A*算法和改进A*算法对比，本文方法不仅缩小了搜索范围，还提高了搜索效率和路径平滑性。然而,本文只是针对全局进行路径规划,并未考虑局部动态环境的变化,因此下一步将结合全局环境和局部环境进行研究，考虑如何与其他算法结合来获取最佳路径。(编辑赵勉)http:/hyxb