[發(fā)明專利]一種基于改進麻雀搜索算法的水下多AUV路徑規(guī)劃方法

有效

• 申請?zhí)枺?/td>: 202110918390.0
• 申請日: 2021-08-11
• 公開（公告）號: CN113485371B
• 公開（公告）日: 2023-04-25
• 發(fā)明（設計）人: 黃浩乾;金超;王冰;魏嘉穎;唐家成
• 申請（專利權(quán)）人: 河海大學
• 主分類號: G05D1/02
• 分類號: G05D1/02
• 代理公司: 南京蘇高專利商標事務所(普通合伙) 32204
• 代理人: 郭楠

1.一種基于改進麻雀搜索算法的水下多AUV路徑規(guī)劃方法，其特征在于：包括以下步驟：

(1)利用柵格法構(gòu)建海洋環(huán)境二維地圖，對水下機器人AUV的工作環(huán)境進行單元分割；并區(qū)分出障礙物和自由區(qū)域；

(2)針對多機器人多目標，利用粒子群算法對每個水下機器人進行任務分配；具體步驟如下：

(2.1)通過粒子群算法搜索粒子的最佳位置，每個粒子看作D維搜索空間的一個搜索個體，將粒子的速度V_id更新為公式(1)，粒子的位置X_id更新為公式(2)：

V′_id＝ωV_id+C₁r₁(P_id-X_id)+C₂r₂(P_gd-X_id)???(1)

X′_id＝X_id+V′_id???(2)

其中，ω為慣性因子，ω的值為非負，較大時全局尋優(yōu)能力強；較小時，局部尋優(yōu)能力強；C₁和C₂為學習因子，均為常數(shù)；r₁和r₂是[0，1]隨機數(shù)，P_id為個體最優(yōu)解，P_gd為全局最優(yōu)解；V′_id為更新后的粒子速度；X′_id為更新后的粒子位置；

(2.2)根據(jù)目標與AUV之間的距離和AUV到達目標的理想時間得出粒子群的適應值函數(shù)；

所述適應值函數(shù)Fitness(i)公式如下：

Fitness(i)＝d(i)·0.5+d(i)/V_E????(3)

其中，i表示第i個粒子，d(i)表示第i個粒子生成的路徑長度；V_E表示AUV期望的速度，d(i)/V_E表示AUV到達目標的理想時間；

(2.3)采用粒子群算法根據(jù)式(1)和(2)不斷更新，尋找最優(yōu)解，在迭代完成后，輸出每個水下機器人和目標的匹配情況，完成任務分配；

(3)采用基于速度合成法并融合洋流的改進麻雀搜索算法進行多AUV的路徑規(guī)劃，具體過程如下：

(3.1)在洋流速度已知的情況下，通過調(diào)節(jié)AUV的速度和方向并利用洋流來進行路徑規(guī)劃，此時水下機器人AUV期望的速度V_E為公式(4)：

α₁為Vc和x軸之間的夾角；α₂為V_E和x軸之間的夾角；α₃為V_A和x軸之間的夾角；V_c為洋流速度矢量；

根據(jù)公式(4)，以及水下機器人AUV與該AUV對應的目標之間的歐式距離構(gòu)建了改進麻雀搜索算法的適應值函數(shù)F(i)如公式(5)：

F(i)＝d(i)·0.5+d(i)/V_E+C·100????(5)

其中，d(i)為粒子生成路徑的總長度，如公式(6)所示；C為穿過障礙物的懲罰系數(shù)；C如公式(7)所示：

當麻雀組成的路徑穿過障礙物時，E為大于其他粒子適應值的正常數(shù)；而當路徑?jīng)]有穿過障礙物時，C為0；

D為麻雀的維度，D也代表AUV在路徑規(guī)劃中生成的中間路徑點；x_id為當前麻雀在二維地圖中橫坐標的值，y_id為當前麻雀在二維地圖中縱坐標的值，x_id-1表示第i只麻雀搜索路徑的第d-1個路徑點的橫坐標，y_id-1表示第i只麻雀搜索路徑的第d-1個路徑點的縱坐標；

(3.2)設置麻雀種群規(guī)模為M，迭代次數(shù)為T，發(fā)現(xiàn)者個數(shù)為M*0.2，預警者個數(shù)為Sd，搜索空間為D維，針對k個AUV，每個AUV分配D/k個維度的搜索空間；

(3.3)假設有M只麻雀在D維搜索空間中，則第i只麻雀在D維空間的位置X_i為公式(8)，適應值F_i為公式(9)：

X_i＝[x_i1，...，x_ij，...，x_MD]????(8)

F_i＝f[x₁，...，x₂，...，x_M]；????(9)

其中，x_i1代表第i只麻雀在第1維的位置，x_ij代表第i只麻雀在第j維的位置，x_MD代表第M只麻雀在第D維的位置；x₁代表第1只麻雀，x₂代表第2只麻雀，x_M代表第M只麻雀；

(3.4)根據(jù)麻雀的適應值大小進行排序，選取適應值最佳的麻雀作為發(fā)現(xiàn)者去發(fā)現(xiàn)地圖中的更優(yōu)位置并為加入者提供優(yōu)化的方向；其中，發(fā)現(xiàn)者的更新公式為(10)：

代表在第t+1次迭代時第i個麻雀在第j維的位置；代表第t次迭代時第i個麻雀在第j維的位置；a代表0～1的隨機數(shù)，Q代表0和1之間的隨機數(shù)；t代表當前迭代數(shù)，T_max為最大迭代次數(shù)；R₂為預警值，ST為安全值；L是一個1*D的矩陣，矩陣中的每個元素都為1；

當R₂＜ST時，表明此時的搜索空間沒有遇到捕食者，發(fā)現(xiàn)者搜索最優(yōu)位置；當R₂≥ST時，表明有麻雀遭遇到了捕食者，并向整個麻雀種群中其他麻雀發(fā)出危險警告；

(3.5)加入者根據(jù)發(fā)現(xiàn)者發(fā)現(xiàn)的更優(yōu)位置，不斷更新自己的位置；加入者的位置更新公式為(11)：

代表截止t+1次迭代時麻雀發(fā)現(xiàn)的最佳位置，A⁺代表A⁺＝A^T(AA^T)^-1，其中，A^T表示A的轉(zhuǎn)置矩陣；A為一個1*D的矩陣；表示第i只麻雀在第t次迭代時的位置，j表示解的維數(shù)；X_worst為目前發(fā)現(xiàn)者所發(fā)現(xiàn)的全局最差的位置；

(3.6)預警者是意識到危險的麻雀，預警者的位置更新公式為如下：

其中，β為均值等于0，方差為1服從正態(tài)分布的隨機數(shù)；K為-1和1之間的隨機數(shù)，f_i為第i個麻雀的適應度，f_g為第i個麻雀的當前最佳適應值，a是一個避免分母等于零的情況的常數(shù)；K為麻雀移動的方向同時也是步長控制參數(shù)；fw表示當前麻雀的最差適應值；代表第t次迭代時所有麻雀發(fā)現(xiàn)的最佳位置，表示這個位置的麻雀是種群中最佳位置；代表第t+1迭代時所有麻雀發(fā)現(xiàn)的最佳位置；

當f_i＞f_g，表明此時的麻雀處于整個種群的邊緣，受到捕食者的威脅；

當f_i＝f_g時，表明處于種群中間的麻雀發(fā)現(xiàn)了威脅，前往其他位置來避免危險。