[發明專利]一種基于蟻群算法的室內AGV路徑規劃方法

在審

• 申請號: 202111149575.6
• 申請日: 2021-09-29
• 公開（公告）號: CN113848919A
• 公開（公告）日: 2021-12-28
• 發明（設計）人: 肖金壯;余雪樂;周振;孫可可
• 申請（專利權）人: 河北大學
• 主分類號: G05D1/02
• 分類號: G05D1/02
• 代理公司: 石家莊國域專利商標事務所有限公司 13112
• 代理人: 胡素梅

1.一種基于蟻群算法的室內AGV路徑規劃方法，其特征是，包括如下步驟：

a、構建柵格地圖，為AGV設定好起始節點和目標節點；

b、初始化蟻群算法各項參數；蟻群算法各項參數包括：螞蟻數量m，最大迭代次數NC，信息素重要程度因子α，信息素初始濃度τ_ij(0)，啟發函數重要因子最大值β_max和最小值β_min，信息素揮發因子ρ，自適應狀態轉移概率選擇參數q₀，信息素強度Q，精英螞蟻個數ε；

c、將螞蟻放在起始節點上；

d、按照改進的自適應偽隨機概率選擇下一節點，改進的自適應偽隨機概率轉移規則如下面公式所示：

其中，q為0-1之間的隨機值，為傳統蟻群算法的輪盤賭隨機選擇模型，的計算公式如下所示：

其中，τ_ij(t)為柵格節點(i，j)間的信息素濃度，η_ij(t)為啟發函數，allowed為AGV下一待選節點的集合；β為啟發函數重要程度影響因子；

β的計算公式如下：

β＝β_max-(β_max-β_min)×(N/NC)

其中，N是當前迭代次數；

啟發函數η_ij(t)的計算公式如下：

其中，(x_e，y_e)表示目標節點的坐標，(x_j，y_j)表示下一節點的坐標；C_ij為方向因子，ψ為上一節點與當前節點之間的直線和當前節點與下一節點之間的直線組成的夾角；a和b分別為調整方向和距離的影響程度參數，且a+b＝1；

q₀的計算公式如下：

e、判斷當前螞蟻是否到達目標節點，如果是則執行步驟f，否則執行步驟d；

f、判斷是否達到最大螞蟻數；如果是，則執行步驟g；否則螞蟻數加1，執行步驟c；

g、記錄本次迭代過程中一級螞蟻找到的最優路徑長度、二級螞蟻找到的較優路徑長度，以及普通螞蟻找到的最差路徑長度，同時計算出整個蟻群中所有存活螞蟻找到的路徑均值，基于改進差異化-分級螞蟻更新策略對信息素進行動態調整；

所述一級螞蟻指當前迭代過程中找到最優路徑長度的螞蟻，所述二級螞蟻指當前迭代過程中找到較優路徑長度的螞蟻，除一級螞蟻和二級螞蟻之外的其他螞蟻均為普通螞蟻；所述存活螞蟻指能從起始節點到達目標節點的螞蟻；

基于改進差異化-分級螞蟻更新策略對信息素進行動態調整，具體公式如下：

τ_ij(t+1)＝(1-ρ)τ_ij(t)+ρΔτ_ij+Δτ_ij′-Δτ_ij″

其中，L_k為第k只螞蟻找到的路徑長度，L_b為本次迭代的最優路徑長度，L_w為本次迭代的最差路徑長度，L_a為本次迭代的平均值路徑長度；L_gb為全局最優路徑長度，L_gw為全局最差路徑長度；

h、判斷是否達到了最大迭代次數，如果是則執行步驟i；如果否，則使迭代次數加1，然后執行步驟c；

i、在最優路徑的基礎上，利用三次均勻B樣條曲線進行路徑平滑，輸出最終路徑。

2.根據權利要求1所述的基于蟻群算法的室內AGV路徑規劃方法，其特征是，步驟i中，利用三次均勻B樣條曲線進行路徑平滑，具體計算公式如下：

P_t為給定n+1個控制點P_t(i＝0,1,2，……，n)的坐標，F_l，n為B樣條基函數；

F_l，n的表達式如下：

t為自變量。

3.根據權利要求2所述的基于蟻群算法的室內AGV路徑規劃方法，其特征是，n＝3，三次B樣條曲線的基函數如下所示：