一种基于布谷鸟搜索算法的水下潜器三维路径规划方法

摘要

本发明提出一种基于布谷鸟搜索算法的水下潜器三维路径规划方法，属于水下潜器三维路径规划技术领域，具体包括：对水下潜器三维空间路径规划问题进行建模、初始化布谷鸟搜索算法、更新鸟窝位置、选出全局最优位置并判断终止条件、输出最优路径五个基本步骤。本发明基于布谷鸟搜索算法，提出一种基于布谷鸟搜索算法的水下潜器三维路径规划方法，很好地利用了布谷鸟搜索算法的简单高效性及全局搜索能力。相对于传统的水下潜器路径规划方法来说具有更好的智能性和适应性，相对于其他智能优化算法而言具有更好的灵活性、更易实现；路径规划过程在三维环境中进行，比二维环境下规划出的路径更具实用性，能够更好地满足水下潜器航行的需要。

主权项

一种基于布谷鸟搜索算法的水下潜器三维空间路径规划方法，其特征在于，包括以下步骤：步骤一：对水下潜器三维空间路径规划问题进行建模，对水下潜器三维空间路径规划的环境建模，确定评价路径的适应度函数；在水下潜器三维路径规划范围内建立全局坐标系Oxyz，其中O(x_O,y_O,z_O)表示水下潜器的起始点，P(x_P,y_P,z_P)为目标点，障碍物用包括其自身的最小外接球体代替，表示为{(Q_j(x'_j,y'_j,z'_j),r_j)|j＝1,2,…,k}，其中Q_j表示第j个障碍物的球心位置，r_j表示第j个障碍物的半径，在Ox轴方向取长度|AD|，其中|AD|的长度为目标点P到y轴的垂直距离，在Oy轴方向取长度|AB|，|AB|的长度为目标点P到x轴的垂直距离，在Oz轴方向取长度|AE|，|AE|的长度为目标点P到z轴的垂直距离，构造一个立方体区域ABCD‑EF‑GH，该立方体区域即为水下潜器路径规划空间；做过障碍物的球心Q_i且垂直于x轴的平面Ψ，并在其左右两侧按步长λ做平行于平面Ψ的平面，寻找一条从起始点O到目标点P的无碰撞路径，即寻找一个路径点的集合P＝{O,P₁,P₂,…,P_i,…,P},i＝1,2,…,m，其中m为路径点的个数，相邻点连接的路径与障碍物无碰撞，同时使从起始点到目标点的路径长度为最短；水下潜器从起始点O(x_O,y_O,z_O)到目标点P(x_P,y_P,z_P)之间的路径就由其间的各个分层上的路径点连接组成，水下潜器从点O出发，到达平面Π₁，找到第一个路径点P₁(x₁,y₁,z₁)，依次找到平面Π_i上的点P_i(x_i,y_i,z_i)，将这些点连接形成一条从起始点O(x_O,y_O,z_O)到目标点P(x_P,y_P,z_P)的路径，采用路径长度作为评价路径的适应度函数，路径长度为：$D=D_{{\mathrm{OP}}_1}+\underset{i=1}{\overset{m-1}{\Sigma }}{D}_{P_i{P}_{i+1}}+D_{P_{m}P}$其中，$D_{P_i{P}_{i+1}}=\sqrt{{(x_{i+1}-x_i)}^2+{(y_{i+1}-y_i)}^2+{(z_{i+1}-z_i)}^2},$表示点P_i和点P_i+1之间的距离，将点O作为点P₀，点P作为点P_m+1，则适应度函数为：$D=\underset{i=0}{\overset{m}{\Sigma }}\sqrt{{(x_{i+1}-x_i)}^2+{(y_{i+1}-y_i)}^2+{(z_{i+1}-z_i)}^2};$步骤二：初始化布谷鸟搜索算法；(1)初始化布谷鸟搜索算法的参数，具体包括种群大小n、布谷鸟的鸟蛋被巢主鸟发现的概率R_a，其中R_a＝0.25；(2)初始化鸟窝的位置，在搜索空间内产生n个鸟窝位置每个鸟窝位置代表一条备选路径，对每个鸟窝进行检验，查看是否遇障：$\frac{\left|\xi \right|}{\left|{\theta }_{i+1}\right|}<r_j,j=1,2,...,k$其中：$\xi =\left(\left|\begin{array}{cc}{y}_j^{\prime }-y_{i+1}& z_j^{\prime }-z_{i+1}\\ y_{i+1}-y_i& z_{i+1}-z_i\end{array}\right|\left|\begin{array}{cc}{z}_j^{\prime }-z_{i+1}& x_j^{\prime }-x_{i+1}\\ z_{i+1}-z_i& x_{i+1}-x_i\end{array}\right|\left|\begin{array}{cc}{x}_j^{\prime }-x_{i+1}& y_j^{\prime }-y_{i+1}\\ x_{i+1}-x_i& y_{i+1}-y_i\end{array}\right|\right),$θ_i＝[x_i‑x_i‑1 y_i‑y_i‑1 z_i‑z_i‑1]为第i段路径的向量，(x'_j,y'_j,z'_j)为障碍物的中心坐标，r_j表示第j个障碍物的半径，k表示障碍物的个数，若鸟窝位置不满足上述条件，该鸟窝代表的路径含有经过障碍物的路径段，则舍弃该鸟窝，并补充新的鸟窝到鸟窝种群中，直到所有鸟窝均不经过障碍物区域，找出初始全局最优位置并保留到下一代；步骤三：更新鸟窝位置：步骤3.1利用Levy飞行过程更新鸟窝位置：保留上代鸟窝的最优位置其中t为正整数，并利用下式对其他的鸟窝位置进行更新，得到一组新的鸟窝位置：$s_i^{(t+1)}=s_i^{\left(t\right)}+\alpha \oplus Levy\left(\lambda \right),i=1,2,...,n$其中，表示第i个鸟窝在第t代的鸟窝位置；为点对点乘法；α表示步长控制量，取α＝ο(1)；Levy(λ)为Levy随机搜索路径，且有Levy～u＝t^‑λ,(1＜λ≤3)；对这组新的鸟窝位置进行适应度函数测试，与上代产生的一组鸟窝位置进行对比，用测试值好的鸟窝位置代替测试值差的鸟窝位置，通过Levy飞行过程建立一组全新的鸟窝，得到鸟窝位置步骤3.2根据被发现概率更新鸟窝位置：产生服从均匀分布的随机数u∈(0,1)，与布谷鸟的鸟蛋被巢主鸟发现的概率R_a＝0.25对比，保留K_t中被发现概率小于ε的鸟窝位置，而对被发现概率大于λ的鸟窝位置进行改变，得到一组新的鸟窝位置，再对这组新的鸟窝位置进行测试，与上一步中得到的K_t中的每个鸟窝位置的测试值进行比较，用测试值大的鸟窝位置代替测试值小的鸟窝位置，得到一组鸟窝位置$S_t={(s_1^{\left(t\right)},s_2^{\left(t\right)},...,s_n^{\left(t\right)})}^T;$步骤四：选出全局最优鸟窝位置，判断是否满足终止条件：利用适应度函数测试步骤三中最后得到的一组鸟窝位置S_t，选出最后得到的S_t中最优的鸟窝位置并判断是否满足最大迭代次数，若满足，则终止循环，否则返回步骤三继续进行迭代更新，直到搜索满足终止条件为止，最终得到的最优鸟窝位置即为需要寻找的最优路径；步骤五：输出步骤四中得到的全局最优路径，水下潜器三维空间路径规划结束。