CN109933067A - 一种基于遗传算法和粒子群算法的无人艇避碰方法 - Google Patents

Abstract

本发明涉及海事智能交通技术无人艇避碰领域，具体涉及一种基于遗传算法和粒子群算法的无人艇避碰方法。首先进行无人艇避碰路径规划中相关参数及避碰约束规则的研究，然后进行基于遗传算法的水面无人艇规避静态障碍物的路径规划，最后进行基于遗传算法与粒子群算法相结合的动态避碰路径规划，完成路径优化，输出可行的避碰路径并复航；相对于传统的无人艇避碰技术，本发明能够得到最优的路径规划，精准地避免碰撞，确保无人艇安全到达目标点。

Description

一种基于遗传算法和粒子群算法的无人艇避碰方法

技术领域

本发明涉及海事智能交通技术无人艇避碰领域，具体涉及一种基于遗传算法和粒子群算法的无人艇避碰方法。

背景技术

无人艇(USV)是一种集自主规划，自主航行，自主完成环境感知，目标探测等功能为一体的小型水面运动平台，已成为探索海洋资源必不可少的设备。

由于路径规划和避碰则是无人艇自主航行的关键所在。因此在无人艇进入水域执行任务之前，需要根据已知的海域的水文资料，规划出一条全程航行路径。由于海洋环境复杂多变，无法预知在航行过程中会出现什么状况，比如遭遇大风大浪、过往船只等。无人艇需要时刻检测周围状况，获取环境信息，准确快速调整航行状态，避开障碍物，按照任务需求到达指定的目标点，执行任务并复航。

无人艇的避碰技术从一定程度上反映了海事无人艇智能化水平的高低，是无人艇关键技术领域的重要研究内容之一。申请号为CN201610942213.5的专利，一种基于改进蚁群算法的无人艇避碰方法，利用改进蚁群算法对无人艇的安全航线进行规划，此方法有一定局限性，并且没有分别针对静态障碍物和动态障碍物的规避路径规划计算。

发明内容

本发明的目的在于提供一种基于遗传算法和粒子群算法的无人艇避碰方法，以得到最优的路径规划，精准地避免碰撞，确保无人艇安全到达目标点。

本发明实施例提供一种基于遗传算法和粒子群算法的无人艇避碰方法，包括：

步骤一：无人艇避碰路径规划中相关参数及避碰约束规则的研究：根据无人艇航行的数学模型参数所涉及的无人艇位置、速度以及障碍物位置、速度，得到两者之间相对速度、相对位置、相对方位运动参数，通过总结无人艇与障碍物正面避障、追越避障、右弦交叉和左弦交叉避障四种不同碰撞情况，得到无人艇海上避碰约束规则以及空间碰撞危险度和时间碰撞危险度；

步骤二：基于遗传算法的水面无人艇规避静态障碍物的路径规划：通过上述的无人艇航行水域环境相关参数信息，对遗传算法的相关参数进行初始化，生成路径的最初种群，并进入遗传算法的迭代循环，计算适应度函数；根据得到的适应度函数值，通过“轮盘赌”方法选出下一代的染色体进行交叉、变异、修复操作优化种群，迭代完成后得到能够规避静态障碍物的最优路径；

步骤三：基于遗传算法与粒子群算法相结合的动态避碰路径规划：实时监测海洋环境周围是否存在动态障碍物，如果存在动态障碍物，判断无人艇与动态障碍物间的距离，计算出碰撞危险度，如果可能产生碰撞，判断动态障碍物的运动状态是否可测；如果可测，采用遗传算法中的常规避碰；如果不可测，则采用粒子群算法进行动态障碍物的规避；最后完成路径优化，输出可行的避碰路径复航；

所述步骤一，包括：

对无人艇避碰路径规划中相关参数及避碰约束规则进行研究：根据无人艇航行的数学模型参数所涉及的无人艇位置、速度以及障碍物位置、速度，得到两者之间相对速度、相对位置、相对方位运动参数，通过总结无人艇与障碍物正面避障、追越避障、右弦交叉和左弦交叉避障四种不同碰撞情况，得到无人艇海上避碰约束规则以及空间碰撞危险度和时间碰撞危险度；

其中，令DCPA代表无人艇与障碍物最短相遇距离，TCPA代表最短相遇时间，所述空间碰撞危险度的计算方法为：

上式中，R_T、α_T表示无人艇与障碍物的相对距离、相对速度方向和障碍物的航向，

上式中，θ_T表示无人艇与障碍物航向的相对角度，d₂＝2×d₁；

所述时间碰撞危险度的计算方法为：

上式中，且当TCPA＞0时u_tT第二项取负号，反之取正号；

对DCPA和TCPA的计算结果进行分析研究，得出无人艇和移动物体间发生碰撞事故可能性的综合评价指标：

所述步骤二，包括：

基于遗传算法的水面无人艇规避静态障碍物的路径规划：通过上述的无人艇航行水域环境相关参数信息，对遗传算法的相关参数进行初始化，生成路径的最初种群，并进入遗传算法的迭代循环，计算适应度函数；根据得到的适应度函数值，通过“轮盘赌”方法选出下一代的染色体进行交叉、变异、修复操作优化种群，迭代完成后得到能够规避静态障碍物的最优路径；

其中，所述路径的最初种群为：

按照任务的需求以及无人艇的初始位置和目标点的相关信息生成原始的运动路径即每条染色体：

(x_i1，y_i1)→(x_i2，y_i2)→…→(x_ili，y_ili)

上式中，i(1＝0,1,2...n)代表无人艇航行的一条路径，n表示初始种群个数，并将染色体编码成实数类型，其中如果在无人艇初始位置和目标点之间并不存在障碍物体，则得出的原始路径一条光滑的最短路径，如果在无人艇初始位置和目标点之间存在障碍物体，这会在原始路径的基础上进行迭代更新产生多条新的路径，针对每条路径可以将其分为多段部分，分别对该条路径不同段部分进行计算分析，得出该条路径的相关信息，用delta表示任意条路径的划分段的长度值，k_δ作为一个正的比例参数值，d_num表示该条路径被划分出的段的总数：

上式中，(x_max,y_max)和(x_min,y_min)是仿真窗口的坐标范围，s(x_s,y_s)和e(x_e,y_e)为无人艇的初始位置和目标点；

在经过上面的路径段数的计算划分后，将通过启发式遗传群体初始化的方法进行种群初始化，生成相应的染色基因，设最初的原始路径总共有n条，将第i条路径表示为P_i,设d_num＝3，然后在第j(j＝1,2,3)段上随机任取两个点p_i(2j-1)和p_i(2j)，则在这两个点的范围内任意生成点此点横坐标被局限在范围内，纵坐标局限于路径初始位置s( x_s,y_s)和目标点e(x_e,y_e)之间的，即然后按顺序地将p_i(2j-1),，p_i(2j)相连，最终生成路径P_i：

得出可行路径集

其中，所述适应度函数为：

将个体适应度函数设置为Value(P^*)＝min[f₁(P),f₂(P),f₃(P)]：

(1)代表路径的长度，第i条染色体的路径长度为：

上式中，m_i是P_i路径里不可行的路径数目，C₁为一合适的正数；

(2)表示路径的光滑性，当染色体的路径划分基因位点的个数大于2，水面无人艇的P_i路径平均拐角值：

其中，a_ij(j＝2,…,l_i-1)为p_i(j-1)p_ij与p_ijp_i(j+1)间的夹角(0≤a_ij≤π),m_i和k_i是a_ij里不小于的数目，即如果某一个拐角不小于时，则要对目标值进行惩罚计算，C₂是一合适的正数，当l_i＝2时，路径P_i为初始点至目标点的连线，Turning(P_i)＝m_i×C₂；

(3)表示路径的安全性，如果路径P_i是可行的，danger(di)＝ 1/di，其中di＞0表示无人艇的航行路线距离静态障碍物的最小值；如果路径Pi是不可行的， danger(P_i)＝m_i×C₃，m_i为该路径个体的路径段与障碍物之间的距离小于安全距离的数量， C₃则为一适当的正数；

所述步骤三，包括：

基于遗传算法与粒子群算法相结合的动态避碰路径规划：实时监测海洋环境周围是否存在动态障碍物，如果存在动态障碍物，判断无人艇与动态障碍物间的距离，计算出碰撞危险度，如果可能产生碰撞，判断动态障碍物的运动状态是否可测；如果可测，采用遗传算法中的常规避碰；如果不可测，则采用粒子群算法进行动态障碍物的规避；最后完成路径优化，输出可行的避碰路径复航；

其中，所述基于遗传算法与粒子群算法相结合的动态避碰方法为：

将Δv分解成Δv_o和Δv_r，

假设在较短的时间内动态移动物体的速度v_obs及方向变化不大,可不予考虑，即

dv_obs＝0，dβ＝0

上式中，为v_USV、v_obs间的夹角，Δγ必须满足下面条件限制：

通过相关的设备监测周围海洋环境的动态信息，如果发现动态的障碍物，判断动态障碍物的运动状态是否可测；如果可测，由于遗传算法适应于求解复杂的优化问题，能够求出优化问题的全局最优解，则进行基于遗传算法的动态避碰；如果不可测，由于粒子群算法具有相当快的逼近最优解的速度，可以有效的对系统的参数进行优化；则进行基于粒子群算法的动态避碰；

基于遗传算法的的避碰可以看成一个多条件下的目标优化问题：

f(Δv_USV,Δα)是遗传算法中的适应度函数，求出的最优解既不会与已知静态障碍物碰撞，还需要符合无人艇海上避碰规则的约束，根据无人艇和动态障碍物的信息，算出它们之间的距离，DCPA和TCPA值，如果会发生碰撞的危险，则进行避碰处理，避碰处理可以通过改变航行方向实现：

上式中R_T为无人艇与动态障碍物间的距离；θ_T为动态障碍物的相对方位；β为相对运动线的转角；为动态障碍物与水面无人艇的航速比；ΔC为避让的角度；

通过迭代法求得转向角ΔC：

通过相关的AIS雷达等设备时刻监测周围动态障碍物的运动状态，预测其运动走向，然后将目前无人艇所处的位置设为新的初始位置，以safeD的长度为路径段的距离得出一个子目标点，通过遗传算法的迭代优化，规划出一条能规避附近障碍物到达子目标点的路径，然后再以该子目标为新的初始位置，重复上述过程，成功到达指定的目标点完成任务；

在不可预测动态障碍物运动状态的避碰过程中，无人艇的每一次前进，都要有预判，利用极坐标，描述无人艇和动态障碍物的位置，无人艇的长度为r，移动半径为ρ，当前所在位置为(A₁,B₁),下一步目标点为(A₂,B₂),动态障碍物此时的位置为(C₁,D₁)；当 表示有障碍物在无人艇安全移动的范围内，此时需要进行基于粒子群算法避碰处理；

设定惯性权重最大值为ω_max，最小值为ω_min，学习因子分别为C₁，C₂，群体为D，最大迭代次数为D_max。以当前点为原点，ρ为半径作极坐标，进行n等份。m个粒子，随机生成 m×n的粒子群，以及位置X和速度V，设置当前最优位置形成初始种群t₀；使Pbest_i代表第i个粒子搜索到的最优值，Gbest_i代表整个集群搜索到的最优值，计算初始种群的适应度值，对全局最优值Gbest_i更新，其中适应度函数包括路径长度和安全度，最短路径长度的目标函数：

上式中，(x_ji,y_ji)为路径j上的i点坐标，(x_ji-1,y_ji-1)为路径j上(x_ji,y_ji)的一个点坐标，此时，无人艇路径规划预测的下一个点坐标(x_jn,y_jn)，需要把此点和目标点(g₁,g₂)连接起来计算路径，整个路径长度函数为：

Y＝Y_fit1+Y_fit2

安全度函数：

上式中，x_k为障碍物的位置坐标；

综合以上，适应度函数：F＝A×Y+B×OB(i)，其中A，B两函数的加权因子，为大于等于零的任意实数，为了完全避碰，B<A，根据速度，位置迭代公式更新，生成新的粒子群t₁，粒子群速度迭代公式为：

V_i,j(t+1)＝ωV_i,j(t)+c₁r₁(P_i,j(t)-x_i,j(t))+c₂r₂(P_g,j(t)-x_i,j(t))

ω_k+1＝ω_min+(ω_k-ω_min)×((K_max-k)/K_max)ⁿ

上式中，r₁，r₂大于0小于1的随机实数，P_i,j是粒子i迄今为止搜到的最优位置，P_g,i是全局最优位置，ω_k为当前迭代所得的值，其初始值为ω_max，k表示当前迭代次数；K_max代表最大迭代次数；

计算新种群t₁的适应度值，若优于上一代则生成新种群t₂，否则转换成直角坐标，循环迭代生成新的种群，直到找到最优的避碰路径；

本发明的有益效果在于：

1.本发明引入了遗传算法，针对在复杂多变的海洋环境中航行的无人艇，规划出一条最优的路径，从而节省各种资源，按任务需求到达指定的目标点；

2.本发明在引入遗传算法的同时，对其进行改进，为了兼顾海上风浪流的影响，将加入删除、修复和平滑算子，使得无人艇能够在遗传算法下规划出最优的运动路径；

3.本发明引入遗传算法和粒子群算法相结合的算法，针对海洋中突然出现的动态障碍物，无人艇能快速准确做出反应，规划出最优的避碰路径，确保无人艇安全到达目标点。

附图说明

图1为本发明无人艇路径规划避碰流程图；

图2为本发明无人艇静态全局路径规划流程图；

图3为本发明障碍物到路径距离示意图；

图4为本发明避障模型示意图；

具体实施方式

为使本发明的上述目的、特征和优点能够更加明显易懂，下面结合附图对本发明做进一步描述：

本发明的技术方案是这样实现的：

1、对无人艇路径规划和避碰中相关参数及避碰约束规则进行研究：

无人艇运动的数学模型参数涉及无人艇的位置、速度以及障碍物的位置、速度。由此引出的两者相对速度、相对位置、相对方位运动参数。总结出无人艇与障碍物正面避障、追越避障、右弦交叉和左弦交叉避障四种不同的碰撞情况。引出无人艇海上避碰约束规则，并从时间和空间两个角度，引出危险度的概念，其中DCPA代表无人艇与障碍物最短相遇距离， TCPA代表最短相遇时间。

(1)空间碰撞危险度

式中R_T、α_T表示无人艇与障碍物的相对距离、相对速 度方向和障碍物的航向；

其中θ_T表示无人艇与障碍物航向的相对角度，d₂＝2×d₁。

(2)时间碰撞危险度

其中且当TCPA＞0时u_tT第二项取负号，反之取正号。

对DCPA和TCPA的计算结果进行分析研究，得出无人艇和移动物体间发生碰撞事故可能性的综合评价指标：

2、基于遗传算法的水面无人艇路径规划

无人艇路径规划的算法过程为首先获取无人艇航行水域环境参数，主要为障碍物信息、风浪等级等。然后定义种群个体的适应度函数，设定遗传算法迭代次数、染色体数量、交叉和变异的概率，最后通过选择算法进行遗传操作得出无人艇航行的全局路径。

首先按照任务的需求以及无人艇的初始位置和目标点的相关信息生成原始的运动路径即每条染色体：

(x_i1,y_i1)→(x_i2,y_i2)→…→(x_ili,y_ili)

其中i(1＝0,1,2...n)代表无人艇航行的一条路径，n表示初始种群个数，并将染色体编码成实数类型。

其中如果在无人艇初始位置和目标点之间并不存在障碍物体，则得出的原始路径一条光滑的最短路径。如果在无人艇初始位置和目标点之间存在障碍物体，这会在原始路径的基础上进行迭代更新产生多条新的路径。针对每条路径可以将其分为多段部分，分别对该条路径不同段部分进行计算分析，得出该条路径的相关信息。用delta表示任意条路径的划分段的长度值，k_δ作为一个正的比例参数值，d_num表示该条路径被划分出的段的总数。

其中，(x_max,y_max)和(x_min,y_min)是仿真窗口的坐标范围，s(x_s,y_s)和e(x_e,y_e)为无人艇的初始位置和目标点。

在经过上面的路径段数的计算划分后，将通过启发式遗传群体初始化的方法进行种群初始化，生成相应的染色基因。设最初的原始路径总共有n条，将第i条路径表示为P_i,设d_num＝3，然后在第j(j＝1,2,3)段上随机任取两个点p_i(2j-1)和p_i(2j-1)，则在这两个点的范围内任意生成点此点横坐.标被局限在范围内，纵坐标局限于路径初始位置s(x_s,y_s)和目标点e(x_e,y_e)之间的，即然后按顺序地将p_i(2j-1),，p_i(2j)相连，最终生成路径P_i：

得出可行路径集

初始种群设置好以后，将个体适应度函数设置为Value(P^*)＝min[f₁(P),f₂(P),f₃(P)]。

其中：

(1)代表路径的长度。第i条染色体的路径长度为

其中，m_i是P_i路径里不可行的路径数目，C₁为一合适的正数。

(2)表示路径的光滑性。当染色体的路径划分基因位点的个数大于2，水面无人艇的P_i路径平均拐角值：

其中，a_ij(j＝2,…,li-1)为p_i(j-1)p_ij与p_ijp_i(j+1)间的夹角(0≤a_ij≤π),m_i和k_i是a_ij里不小于π/2的数目，即如果某一个拐角不小于π/2时，则要对目标值进行惩罚计算，C₂是一合适的正数，当l_i＝2时，路径P_i为初始点至目标点的连线，Turning(P_i)＝mi×C₂

(3)表示路径的安全性

如果路径P_i是可行的，danger(d_i)＝1/d_i，其中d_i＞0表示无人艇的航行路线距离静态障碍物的最小值；如果路径P_i是不可行的，danger(P_i)＝mi×C₃，mi为该路径个体的路径段与障碍物之间的距离小于安全距离的数量，C₃则为一适当的正数。根据适应度函数的值，通过比例算法选出下一代的染色体进行交叉、变异、修复等遗传操作，从而优化种群。最后，通过迭代优化，规划出一条无障碍物的全局路径。

3、进行基于遗传算法与粒子群算法相结合的动态避碰，主要步骤如下：

如附图4避障模型示意图所示，将Δv分解成Δv_o和Δv_r。

假设在较短的时间内动态移动物体的速度v_obs及方向变化不大,可不予考虑，即

dv_Obs＝0，dβ＝0

其中为v_USV、v_obs间的夹角。Δγ必须满足下面条件限制：

通过相关的设备监测周围海洋环境的动态信息。如果发现动态的障碍物，判断动态障碍物的运动状态是否可测；如果可测，由于遗传算法适应于求解复杂的优化问题，能够求出优化问题的全局最优解，则进行基于遗传算法的动态避碰；如果不可测，由于粒子群算法具有相当快的逼近最优解的速度，可以有效的对系统的参数进行优化；则进行基于粒子群算法的动态避碰。

基于遗传算法的的避碰可以看成一个多条件下的目标优化问题：

f(Δv_USV,Δα)是遗传算法中的适应度函数，求出的最优解既不会与已知静态障碍物碰撞，还需要符合无人艇海上避碰规则的约束。根据无人艇和动态障碍物的信息，算出它们之间的距离，DCPA,TCPA值，如果会发生碰撞的危险，则进行避碰处理。避碰处理可以通过改变航行方向实现。

式中R_T为无人艇与动态障碍物间的距离；r

θ_T为动态障碍物的相对方位；

β为相对运动线的转角；

为动态障碍物与水面无人艇的航速比；

ΔC为避让的角度。

通过迭代法求得转向角ΔC：

通过相关的AIS雷达等设备时刻监测周围动态障碍物的运动状态，预测其运动走向，然后将目前无人艇所处的位置设为新的初始位置，以safeD的长度为路径段的距离得出一个子目标点，通过遗传算法的迭代优化，规划出一条能规避附近障碍物到达子目标点的路径，然后再以该子目标为新的初始位置，重复上述过程，成功到达指定的目标点完成任务。

在不可预测动态障碍物运动状态的避碰过程中，无人艇的每一次前进，都要有预判。利用极坐标，描述无人艇和动态障碍物的位置。无人艇的长度为r，移动半径为ρ，当前所在位置为(A₁,B₁),下一步目标点为(A₂,B₂),动态障碍物此时的位置为(C₁,D₁)；当表示有障碍物在无人艇安全移动的范围内，此时需要进行基于粒子群算法避碰处理。

设定惯性权重最大值为ω_max，最小值为ω_min，学习因子分别为C₁，C₂，群体为D，最大迭代次数为D_max。以当前点为原点，ρ为半径作极坐标，进行n等份。m个粒子，随机生成m×n的粒子群，以及位置X和速度V，设置当前最优位置P_i＝(p_i1,p₂...p_iD)，形成初始种群t₀。使Pbest_i代表第i个粒子搜索到的最优值，Gbest_i代表整个集群搜索到的最优值。计算初始种群的适应度值，对全局最优值Gbest_i更新。

其中适应度函数包括路径长度和安全度。

最短路径长度的目标函数：

其中(x_ji,y_ji)为路径j上的i点坐标，(x_ji-1,y_ji-1)为路径j上(x_ji,y_ji)的一个点坐标。此时，无人艇路径规划预测的下一个点坐标(x_jn,y_jn)，需要把此点和目标点(g₁,g₂)连接起来计算路径，整个路径长度函数为：

Y＝Y_fit1+Y_fit2

安全度函数：

其中x_k为障碍物的位置坐标。

综合以上，适应度函数：F＝A×Y+B×OB(i)

其中A，B两函数的加权因子，为大于等于零的任意实数，为了完全避碰，B＜A。

根据速度，位置迭代公式更新，生成新的粒子群t₁。

粒子群速度迭代公式为：

V_i,j(t+1)＝ωV_i,j(t)+c₁r₁(P_i,j(t)-x_i,j(t))+c₂r₂(P_g,j(t)-x_i,j(t))

ω_k+1＝ω_min+(ω_k-ω_min)×((K_max-k)/K_max)ⁿ

其中r₁，r₂大于0小于1的随机实数，P_i,j是粒子i迄今为止搜到的最优位置，P_g,i是全局最优位置。ω_k为当前迭代所得的值，其初始值为ω_max；k表示当前迭代次数；K_max代表最大迭代次数

计算新种群t₁的适应度值，若优于上一代则生成新种群t₂，否则转换成直角坐标。循环迭代生成新的种群，直到找到最优的避碰路径。

Claims (4)

1.一种基于遗传算法和粒子群算法的无人艇避碰方法，其特征在于，包括：

步骤一：无人艇避碰路径规划中相关参数及避碰约束规则的研究：根据无人艇航行的数学模型参数所涉及的无人艇位置、速度以及障碍物位置、速度，得到两者之间相对速度、相对位置、相对方位运动参数，通过总结无人艇与障碍物正面避障、追越避障、右弦交叉和左弦交叉避障四种不同碰撞情况，得到无人艇海上避碰约束规则以及空间碰撞危险度和时间碰撞危险度；

步骤二：基于遗传算法的水面无人艇规避静态障碍物的路径规划：通过上述的无人艇航行水域环境相关参数信息，对遗传算法的相关参数进行初始化，生成路径的最初种群，并进入遗传算法的迭代循环，计算适应度函数；根据得到的适应度函数值，通过“轮盘赌”方法选出下一代的染色体进行交叉、变异、修复操作优化种群，迭代完成后得到能够规避静态障碍物的最优路径；

步骤三：基于遗传算法与粒子群算法相结合的动态避碰路径规划：实时监测海洋环境周围是否存在动态障碍物，如果存在动态障碍物，判断无人艇与动态障碍物间的距离，计算出碰撞危险度，如果可能产生碰撞，判断动态障碍物的运动状态是否可测；如果可测，采用遗传算法中的常规避碰；如果不可测，则采用粒子群算法进行动态障碍物的规避；最后完成路径优化，输出可行的避碰路径复航。

2.根据权利要求1所述的一种基于遗传算法和粒子群算法的无人艇避碰方法，其特征在于，所述步骤一，包括：

对无人艇避碰路径规划中相关参数及避碰约束规则进行研究：根据无人艇航行的数学模型参数所涉及的无人艇位置、速度以及障碍物位置、速度，得到两者之间相对速度、相对位置、相对方位运动参数，通过总结无人艇与障碍物正面避障、追越避障、右弦交叉和左弦交叉避障四种不同碰撞情况，得到无人艇海上避碰约束规则以及空间碰撞危险度和时间碰撞危险度；

其中，令DCPA代表无人艇与障碍物最短相遇距离，TCPA代表最短相遇时间，所述空间碰撞危险度的计算方法为：

上式中，R_T、α_T表示无人艇与障碍物的相对距离、相对速度方向和障碍物的航向，

上式中，θ_T表示无人艇与障碍物航向的相对角度，d₂＝2×d₁；

所述时间碰撞危险度的计算方法为：

上式中，且当TCPA＞0时u_tT第二项取负号，反之取正号；

对DCPA和TCPA的计算结果进行分析研究，得出无人艇和移动物体间发生碰撞事故可能性的综合评价指标：

3.根据权利要求1所述的一种基于遗传算法和粒子群算法的无人艇避碰方法，其特征在于：所述步骤二，包括：

基于遗传算法的水面无人艇规避静态障碍物的路径规划：通过上述的无人艇航行水域环境相关参数信息，对遗传算法的相关参数进行初始化，生成路径的最初种群，并进入遗传算法的迭代循环，计算适应度函数；根据得到的适应度函数值，通过“轮盘赌”方法选出下一代的染色体进行交叉、变异、修复操作优化种群，迭代完成后得到能够规避静态障碍物的最优路径；

其中，所述路径的最初种群为：

按照任务的需求以及无人艇的初始位置和目标点的相关信息生成原始的运动路径即每条染色体：

(x_i1，y_i1)→(x_i2，y_i2)→…→(x_ili，y_ili)

上式中，i(1＝0，1，2...n)代表无人艇航行的一条路径，n表示初始种群个数，并将染色体编码成实数类型，其中如果在无人艇初始位置和目标点之间并不存在障碍物体，则得出的原始路径一条光滑的最短路径，如果在无人艇初始位置和目标点之间存在障碍物体，这会在原始路径的基础上进行迭代更新产生多条新的路径，针对每条路径可以将其分为多段部分，分别对该条路径不同段部分进行计算分析，得出该条路径的相关信息，用delta表示任意条路径的划分段的长度值，k_δ作为一个正的比例参数值，d_num表示该条路径被划分出的段的总数：

上式中，(x_max，y_max)和(x_min，y_min)是仿真窗口的坐标范围，s(x_s，y_s)和e(x_e，y_e)为无人艇的初始位置和目标点；

在经过上面的路径段数的计算划分后，将通过启发式遗传群体初始化的方法进行种群初始化，生成相应的染色基因，设最初的原始路径总共有n条，将第i条路径表示为P_i,设d_num＝3，然后在第j(j＝1，2，3)段上随机任取两个点p_i(2j-1)和p_i(2j)，则在这两个点的范围内任意生成点此点横坐标被局限在范围内，纵坐标局限于路径初始位置s(x_s，y_s)和目标点e(x_e，y_e)之间的，即然后按顺序地将p_i(2j-1),，p_i(2j)相连，最终生成路径P_i：

得出可行路径集

其中，所述适应度函数为：

将个体适应度函数设置为Value(P^*)＝min[f₁(P)，f₂(P)，f₃(P)]：

(1)代表路径的长度，第i条染色体的路径长度为：

上式中，m_i是P_i路径里不可行的路径数目，C₁为一合适的正数；

(2)表示路径的光滑性，当染色体的路径划分基因位点的个数大于2，水面无人艇的P_i路径平均拐角值：

其中，a_ij(j＝2，…，l_i-1)为p_i(j-1)p_ij与p_ijp_i(j+1)间的夹角(0≤a_ij≤π),m_i和k_i是a_ij里不小于的数目，即如果某一个拐角不小于时，则要对目标值进行惩罚计算，C₂是一合适的正数，当l_i＝2时，路径P_i为初始点至目标点的连线，Turning(P_i)＝m_i×C₂；

(3)表示路径的安全性，如果路径P_i是可行的，danger(di)＝1/di，其中di＞0表示无人艇的航行路线距离静态障碍物的最小值；如果路径P_i是不可行的，danger(P_i)＝m_i×C₃，m_i为该路径个体的路径段与障碍物之间的距离小于安全距离的数量，C₃则为一适当的正数。

4.根据权利要求1所述的一种基于遗传算法和粒子群算法的无人艇避碰方法，其特征在于：所述步骤三，包括：

基于遗传算法与粒子群算法相结合的动态避碰路径规划：实时监测海洋环境周围是否存在动态障碍物，如果存在动态障碍物，判断无人艇与动态障碍物间的距离，计算出碰撞危险度，如果可能产生碰撞，判断动态障碍物的运动状态是否可测；如果可测，采用遗传算法中的常规避碰；如果不可测，则采用粒子群算法进行动态障碍物的规避；最后完成路径优化，输出可行的避碰路径复航；

其中，所述基于遗传算法与粒子群算法相结合的动态避碰方法为：

将Δv分解成Δv_o和Δv_r，

假设在较短的时间内动态移动物体的速度v_obs及方向变化不大,可不予考虑，即

dv_obs＝0，dβ＝0

上式中，为v_USV、v_obs间的夹角，Δγ必须满足下面条件限制：

通过相关的设备监测周围海洋环境的动态信息，如果发现动态的障碍物，判断动态障碍物的运动状态是否可测；如果可测，由于遗传算法适应于求解复杂的优化问题，能够求出优化问题的全局最优解，则进行基于遗传算法的动态避碰；如果不可测，由于粒子群算法具有相当快的逼近最优解的速度，可以有效的对系统的参数进行优化；则进行基于粒子群算法的动态避碰；

基于遗传算法的的避碰可以看成一个多条件下的目标优化问题：

f(Δv_USV，Δα)是遗传算法中的适应度函数，求出的最优解既不会与已知静态障碍物碰撞，还需要符合无人艇海上避碰规则的约束，根据无人艇和动态障碍物的信息，算出它们之间的距离，DCPA和TCPA值，如果会发生碰撞的危险，则进行避碰处理，避碰处理可以通过改变航行方向实现：

上式中R_T为无人艇与动态障碍物间的距离；θ_T为动态障碍物的相对方位；β为相对运动线的转角；为动态障碍物与水面无人艇的航速比；ΔC为避让的角度；

通过迭代法求得转向角ΔC：

通过相关的AIS雷达等设备时刻监测周围动态障碍物的运动状态，预测其运动走向，然后将目前无人艇所处的位置设为新的初始位置，以safeD的长度为路径段的距离得出一个子目标点，通过遗传算法的迭代优化，规划出一条能规避附近障碍物到达子目标点的路径，然后再以该子目标为新的初始位置，重复上述过程，成功到达指定的目标点完成任务；

在不可预测动态障碍物运动状态的避碰过程中，无人艇的每一次前进，都要有预判，利用极坐标，描述无人艇和动态障碍物的位置，无人艇的长度为r，移动半径为ρ，当前所在位置为(A₁，B₁),下一步目标点为(A₂，B₂),动态障碍物此时的位置为(C₁，D₁)；当表示有障碍物在无人艇安全移动的范围内，此时需要进行基于粒子群算法避碰处理；

设定惯性权重最大值为ω_max，最小值为ω_min，学习因子分别为C₁，C₂，群体为D，最大迭代次数为D_max，以当前点为原点，ρ为半径作极坐标，进行n等份，m个粒子，随机生成m×n的粒子群，以及位置X和速度V，设置当前最优位置形成初始种群t₀；使Pbest_i代表第i个粒子搜索到的最优值，Gbest_i代表整个集群搜索到的最优值，计算初始种群的适应度值，对全局最优值Gbest_i更新，其中适应度函数包括路径长度和安全度，最短路径长度的目标函数：

上式中，(x_ji，y_ji)为路径j上的i点坐标，(x_ji-1，y_ji-1)为路径j上(x_ji，y_ji)的一个点坐标，此时，无人艇路径规划预测的下一个点坐标(x_jn，y_jn)，需要把此点和目标点(g₁，g₂)连接起来计算路径，整个路径长度函数为：

Y＝Y_fit1+Y_fit2

安全度函数：

上式中，x_k为障碍物的位置坐标；

综合以上，适应度函数：F＝A×Y+B×OB(i)，其中A，B两函数的加权因子，为大于等于零的任意实数，为了完全避碰，B＜A，根据速度，位置迭代公式更新，生成新的粒子群t₁，粒子群速度迭代公式为：

V_i，j(t+1)＝ωV_i，j(t)+c₁r₁(P_i，j(t)-x_i，j(t))+c₂r₂(P_g，j(t)-x_i，j(t))

ω_k+1＝ω_min+(ω_k-ω_min)×((K_max-k)/K_max)ⁿ

上式中，r₁，r₂大于0小于1的随机实数，P_i，j是粒子i迄今为止搜到的最优位置，P_g，i是全局最优位置，ω_k为当前迭代所得的值，其初始值为ω_max，k表示当前迭代次数；K_max代表最大迭代次数；

计算新种群t₁的适应度值，若优于上一代则生成新种群t₂，否则转换成直角坐标，循环迭代生成新的种群，直到找到最优的避碰路径。