基于粒子群算法和航行规则的分步多船避碰路径规划

来源:用户上传      作者:

　　摘  要： 针对宽水域多船避碰过程中路径规划难与航行规则结合的问题，提出一种分步多船避碰路径规划算法。首先将障碍船视为静态障碍物，利用极坐标空间的粒子群路径规划算法结合船舶安全领域进行静态路径规划，得到船舶避碰转向点;然后利用航行规则对转向点的转向角度进行动态修正。通过对算法进行仿真验证，能够很好地解决多船避碰路径规划的问题，为解决多船避碰问题提供一种新的思路。
　　关键词： 多船避碰; 粒子群; 安全领域; 路径规划; 航行规则; 仿真验证
　　中图分类号： TN850.6?34; U664                 文献标识码： A                       文章编号： 1004?373X（2020）02?0106?04
　　Stepwise multi?ship collision avoidance path planning based on particle swarm optimization and navigation rules
　　GAO Fei， YAN Dewen
　　Abstract： A stepwise multi?ship collision avoidance path planning algorithm is proposed to solve the problem that the route planning is difficult to combine with the navigation rules in the process of multi?ship collision avoidance in wide water area. Firstly， the obstacle ship is regarded as the static obstacle， and the static path planning is performed in combination with the field of ship safety and by means of the particle swarm route planning algorithm in polar coordinate space， so as to obtain the collision avoidance steering point. The turning angle of the steering point is modified dynamically by the navigation rules. The simulation results show that this algorithm can conduct the path planning of multi?ship collision avoidance， and provide a new idea for the solution of multi?ship collision avoidance.
　　Keywords： multi?ship collision avoidance; particle swarm optimization; security area; path planning; navigation rules; simulation verification
　　0  引  言
　　船舶避碰路径规划问题一直是船舶操纵和航运安全领域的亟需解决的课题之一[1]。其主要目的是在船舶会遇过程中找到一条从出发点到目标点最安全、最高效的路径。其难点在于规划的路径要符合船舶航行的规则约束。然而多船避碰问题更是其中的难点，更好地解决多船避碰路径规划问题才能够真正实现船舶自动避碰。
　　考虑到智能优化算法对于处理抽象和定性的影响因素具有较好的效果，更加适用于船舶避碰路径规划[2]。且智能优化算法与规则结合应用于机器人[3]和无人艇[4]的路径规划已经取得了不错的效果。粒子群算法作为一种智能优化算法机理简单，收敛速度快，在路径规划方面有其特有的优势。将智能优化算法和航行规则结合的应用在避碰领域的研究也有很多，主要是对避碰角度和单船避碰过程的寻优[5?7]。所以本文提出了采用粒子群算法与航行规则结合的分步多船避碰路径规划算法。首先将多条障碍船视为静态障碍物，利用规则对障碍船建模，并利用极坐标空间的粒子群路径规划算法进行静态路径规划，得到船舶避碰的全局路径，同时得到避碰转向点和转向角度。然后设计了利用航行规则推理的转向点和转向角度动态修正算法，在船舶航行过程中对初始路径进行动态修正。此过程中结合船员实际避碰的操纵习惯，解决了多船避碰路径规划过程中难与规则相结合的问题，使规划的路径符合航行规则的要求，提高了航行的效率和安全性。
　　1  问题描述与建模
　　对于船舶来讲，路径规划就是寻找其在海洋中航行的转向点的集合，并且由于船舶航行中主要的避碰操作多为转向操作，因此采用文献[8]基于极坐标空间的粒子群路径规划建模方法：其中S为出发点，G为目标点，以S为原点，以S与G的连线作为极坐标轴建立极坐标系。将SG进行m+1等分，得到间隔长度为[SG（m+1）]的m+1段线段，以各个等分点到S的连线为半径作圆，可以得到一系列的同心圆弧[li]。圆弧[li]与路径的交点即为路径转向点。路径规划即为寻找转向点的集合[pi={p1，p2，…，pm}]。其中转向点和相邻转向点之间不能存在障碍船的船舶领域。船舶领域（灯号的能见距离）所适用的最大距离为6 n mile，当两船距离大于6 n mile时，船舶采取任何行动都不违反规则约束，船舶避碰条款此时不适用，无需进行避碰操作。所以将目标船膨胀成半径为6 n mile的圆形领域，于6 n mile以外对船舶的航行路径进行静态规划。极坐标下路径规划示意图如图1所示。 　　第i个转向点[pi]的坐标就可以用[Rpi，θpi]表示，同时通过图1发现极径[Rpi]和极角[θpi]存在的关系：
　　[θpi=i=0mΔθpiRpi=i·SGm+1]                 （1）
　　式中，[Δθpi]为第i个转向点的转向角度。通过式（1）可以看出路径上转向点可以通过本身序号和转向角度唯一确定。考虑到船员在船舶航行过程中的主要避碰行动为转向避碰，因此一条候选路径可以用此路径上转向点的转向角度来表示：
　　[pi=Δθp1，Δθp2，…，Δθpm]
　　这样路径规划就转换成转向角度的规划，这对于避碰路径的动态修正是有利的。
　　2  基于粒子群的路径规划
　　2.1  粒子群优化算法的基本原理
　　粒子群优化算法是一种群体智能算法。模拟鸟类的捕食行为，采用速度、位置搜索模型，每一个粒子都是一个备选解，解的优劣程度由适应度决定。粒子群算法随机初始化n个粒子，每个粒子m维。第i（i=1，2，…，n）个粒子在m维解空间的位置为[xi=（x（i，1），x（i，2），…，x（i，m））]，每一次迭代粒子根据自身的飞行经验得到个体最优值[Pbesti]和群体最优值[Gbest]来确定自己的速度，调整自己的位置，逐渐向最优粒子靠拢。第i个粒子的速度为：
　　[vi=v（i，1），v（i，2），…，v（i，m）]
　　粒子的速度和位置更新公式如下[9]：
　　[vt+1i，j=ω·vti，j+c1r1pti，j-xti，jΔt+c2r2ptg，j-xti，jΔtxt+1i，j=xti，j+vt+1i，jΔt] （2）
　　式中： [vt+1i，j]，[xt+1i，j]分别表示粒子i第j维（j=1，2，…，m）分量在t时刻的速度和位置;[pti，j]是粒子i第j维分量在t时刻搜索到的最优位置;[ptg，j]表示所有粒子第j维分量到t时刻搜索到的最优位置;[Δt]为单位时间;[c1，c2]为加速常数，代表粒子向自身最优位置和全局最优位置的推进加速权值;[r1]，[r2]为随机数一般取值在（0，1）之间;[ω]为惯性权重，[ω]较大则全局搜索能力强，[ω]较小一般局部搜索能力强，且[ω]随迭代次数的线性减小，[ω]取值一般在0.4～0.9之间。
　　2.2  算法实现
　　在第i条圆弧[li]上选取一个转向点[pi] （[pi]必须是自由点），为了保证航行的安全性，其中[pi]的选取必须满足几个条件：
　　1） 在[li]的取值范围内;
　　2） 不在任何障碍船的领域内;
　　3） [pi]与其相邻的圆弧[li-1]上所选点的连线不能与任何障碍船的领域相交。
　　为满足这三个条件将[pi]在[li]上的取值范围设置为圆弧与海图的交点到圆弧与障碍船领域交点之间，粒子初始化时应事先设定取值范围;其次相邻两点之间的连线到圆心的距离应该大于障碍船的领域半径。从起始点S出发，依次连接圆弧上的各点到达目标点G，即得到一条规划的路径，接下来对路径进行寻优，即得到全局最优路径。
　　考虑到航行的经济性，路径规划的结果是期望得到航行的距离尽可能短，所以适应度函数选取为航行的路径和：
　　[Fi（x）=lp=lsp1+i=1m-1lpipi+1+lpmG=i=0mlpipi+1]   （3）
　　具體步骤：
　　Step1：初始化粒子数n、粒子的纬度m。初始化粒子[pi]，每个粒子的历史最优值即为其本身[Pbesti]。计算每个粒子的适应度值，选取适应度值最小的粒子为全局最优值[Gbest]。
　　Step2：由式（2）更新粒子的速度和位置。
　　Step3：对每个粒子[pi]，计算适应度值，若适应度值小值[Pbesti]的适应度值，则[Pbesti]=[pi]。
　　Step4：转到Step2进行迭代，直到满足精度或迭代次数要求为止。
　　3  航行规则推理的避碰路径动态修正算法
　　3.1  基本思想
　　根据研究船舶避碰采取最多的操纵行为是转向避碰，本文正是采取转向避碰的方式。首先本船把障碍船视为静态障碍并进行静态环境下的路径规划，得到最优转向点集合[pi]，当规划完初始路径以后，船舶沿着初始路径规划转向点航行，每走一点会判断下一转向点[pi+1]与最近障碍船的距离[DT]，判断本船在[pi+1]是否有碰撞危险，若[DT]大于船舶安全会遇距离，则无碰撞危险，无需对转向点进行修正，继续沿着初始规划转向点航行即可。当[DT]小于船舶安全会遇距离时，根据避碰规则确定会遇状态、避碰方式、转向角度[Δφ]，以调整去往下一转向点[pi+1]的转向角度[Δθ]，得到新的下一转向点[pnewi+1]，并更新最新的转向点到动态修正路径集合[pnewi]中。[pnewi]即船舶的动态避碰路径。
　　3.2  规则设计
　　动态避碰规则的设计考虑到船舶避碰场景的突发性，采用正向推理的办法，将规则库设计为五输入两输出的模型，减少了思考过程，增强了时效性。其中，输入包括[θT]表示下一转向点障碍船相对本船的舷角;[∠A]为本船与障碍船的速度夹角; [DT]为下一转向点本船与最近障碍船的距离;[v0]，[vt]为本船与障碍船的速度，输出[O]为本船在全局路径上根据动态障碍物调整的类型;[Δφ]为船舶在下一航迹点航向的调整量。可由式（4）更新转向点的极角：
　　[θpnewi+1=θpi+Δθpi+Δφ]   （4） 　　首先根据[θT]结合避碰规则对避碰区域进行划分。根据规则互见中的两船会遇，将行动局面划分为A，B，C，D，E，F六种区域，如图2所示。A区来船，本船应采取向右转向的避碰行动，B区来船，本船为让路船，且相对方位大，采去向左转向，在C，D，E区本船为直航船，本船不必采取行动;F区来船本船应采取向右转向。
　　让路船最佳转向角度可由式（5）得到[10]：
　　[Δφ=maxθT，arcsin 0.25-∠S′+θT]  （5）
　　式中，
　　[∠S′=arcsinvTsin（∠A+Δφ）v20+v2T-2v0vT（∠A+Δφ）]
　　安全通过距离根据不同的会遇局面有不同的划分，通过确定不同的会遇局面，确定相应的安全通过距离。安全距离通过文献[11]得到在开阔水域中船舶的安全通过距离，其与各分区对应表如表1所示。
　　通过对会遇局面、转向避碰角度、安全距离的研究得到了如表2所示的船舶动态避碰规则库。
　　以上规则根据船舶航行规则结合船舶避碰决策分析整理，将输入与输出一一对应，用于对初始路径转向点进行动态的修正，能够解决船舶相遇过程中的各种局面，得到新的动态避碰路径。
　　3.3  具体步骤
　　Step1：用粒子群算法求出初始静态状态下的最优路径转向点集合[pi]，初始化动态避碰路径转向点集合[pnewi（i=1，2，…，m）]，m为转向点数量和障碍船[Tj（j=1，2，…，n）]，[n]为障碍船数量。令i=1，用i来遍历最优的路径转向点[pi]，并指向下一转向点;令j=1，用j来遍历障碍船的数量。
　　Step2：若i>m，转Step6。获取初始静态路径的下一转向点[pi+1]，设在动态环境下的船舶航行的下一转向点为[pnewi+1]，初始化[pnewi+1=pi+1]。
　　Step3：若j>n，转Step5。获取障碍船的航行信息。若在转向点[pi+1]距离[DTj]（表示距第j条障碍船的距离）大于安全距离，则令j=j+1，转Step3。
　　Step4：船舶当前航迹点为[pi]，下一航迹点[pi+1]与[Tj]障碍船有碰撞危险，确定规则库各输入的值，得到正确的避碰决策输出[O]，得到新的[pnewi+1]。
　　Step5：令[i=i+1]，将[pnewi+1]加入到动态转向点集合[pnewi]中，转到Step2。
　　Step6：算法结束，将船舶航行的路径点保存的[pnewi]中。
　　4  仿真实验
　　为了验证算法的效果，在计算机上进行了仿真实验。本船当前位置点为S点，目标航迹点为正东方向的G点，两点相聚36 n mile，令正东方向航向为0°，顺时针为正方向，各障碍船相对本船的位置坐标和航向如表3所示。本船和障碍船的航速均为12 n，各障碍船均按航行规则行驶，粒子群算法参数设置为[c1=c2=1.5]，[ω]=0.9，种群数n=15，最大迭代次數设置为50。
　　对初始状态的路径进行规划，得到初始路径转向点如表4所示。船舶沿转向点航行，进行动态避碰，当两船间航行距离小于安全避碰距离时，即根据避碰规则库进行转向，从而改变下一转向点得到新的转向点坐标如表5所示。
　　为了便于路径在海图中显示，利用式（6）将极坐标下的转向点转换成直角坐标。
　　[xy=cos α-sin α  sin αcos α·Rpcos θpRpsin θp]       （6）
　　式中，[α]为极轴与直角坐标x轴的夹角，这里为0°。
　　在Matlab上的仿真结果如图3所示。其中，虚线为静态状态下规划的路径;实线为动态调整的路径;圆圈为初始状态下的船舶领域;箭头方向为障碍船运动方向。
　　粒子群算法迭代图如图4所示，可见在初始状态下粒子群算法能够较快地找到一条最优路径，最短路径为38.4 n mile，在迭代35次左右取得。
　　5  结  语
　　利用粒子群算法结合船舶领域与船舶航行规则，进行分步多船避碰路径规划为多船避碰辅助决策提供了新的思路。此思路解决了避碰算法难与航行规则结合的问题。经过仿真发现，该算法具有很好的避碰效果，能够真正地实现多船动态避碰。
　　参考文献
　　[1] TAM C K， BUCKNALL R， GREIG A. Review of collision avoidance and path planning methods for ships in close range encounters [J]. Journal of navigation， 2009， 62（3）： 455.
　　[2] 康与涛，朱大奇，陈伟炯.船舶避碰路径规划综述[J].船海工程，2013，42（5）：141?145.
　　[3] 徐晓睛，朱庆保.动态环境下基于多人工鱼群算法和避碰规则库的机器人路径规划[J].电子学报，2012，40（8）：1694?1699.
　　[4] 向祖权，靳超，杜开君，等.基于粒子群优化算法的水面无人艇分层局部路径规划[J].武汉理工大学学报，2015，37（7）：38?45.
　　[5] 马文耀，吴兆麟，杨家轩，等.人工鱼群算法的避碰路径规划决策支持[J].中国航海，2014，37（3）：63?67.
　　[6] 胥文，胡江强，尹建川，等.基于克隆选择优化的多船转向避碰决策[J].舰船科学技术，2018，40（1）：52?56.
　　[7] 田雨波，潘朋朋.免疫粒子群算法在船舶避碰上的应用[J].中国航海，2011，34（1）：48?53.
　　[8] 祖伟，李刚，齐正霞.基于改进粒子群优化算法的路径规划方法研究[J].弹射与制导学报，2008，28（4）：68?82.
　　[9] EBERHART， SHI Y. Particle swarm optimization： developments， applications and resources [C]// Proceedings of the 2001 Congress on Evolutionary Computation. Seoul： IEEE， 2002： 81?86.
　　[10] 郑中义，吴兆麟.船舶最佳转向避碰幅度决策模型[J].大连海事大学学报，2000，26（4）：5?8.
　　[11] 齐乐，郑中义，李国平.互见中基于AIS数据的船舶领域[J].大连海事大学学报，2011，37（1）：48?50.
　　作者简介：杲  飞（1994—），男，山东济南人，硕士，研究方向为船舶自主控制与自动化装置。
　　颜德文（1969—），男，浙江温岭人，博士，副教授，研究方向为船舶自主控制与自动化装置。
转载注明来源:https://www.xzbu.com/8/view-15122266.htm