基于蟻群算法的機器人全局路徑規(guī)劃算法改進

摘 要：為了解決在復雜環(huán)境中果園噴霧機器人全局路徑規(guī)劃效率不高的問題，本文提出一種新的路徑規(guī)劃算法。本算法利用蟻群算法的基本原理進行優(yōu)化，引入高度矩陣對啟發(fā)函數進行優(yōu)化。利用角度數評價函數、物數量評價函數等參數對信息素增量進行優(yōu)化，在尋徑過程中更高效地躲避障礙物，避免進入死循環(huán)，同時減少迭代次數；設定信息素濃度值的最大值和最小值，可以避免算法早熟和停滯。本文進行對比測試，測試結果表明，與基本蟻群算法相比，使用本文算法，最優(yōu)路徑減少7.896 m，迭代次數降低23次，運行時間減少18.195 s，環(huán)境越復雜，本文算法的優(yōu)勢越明顯。

關鍵詞：復雜環(huán)境；果園機器人；路徑規(guī)劃；信息素增量

中圖分類號：TP 242" " " " " " " 文獻標志碼：A

水果產業(yè)在農業(yè)生產中的地位越來越重要[1]。為了減少果園生產管理的負擔，降低生產作業(yè)成本，使用果園噴霧機器人噴灑農藥可以降低人力成本[2]。國內外學者對路徑規(guī)劃領域研究越來越多，應用比較廣泛的路徑規(guī)劃方法有A*算法、DWA以及蟻群算法等。采用A*算法在一定程度上可以得到較好的路徑規(guī)劃，但是該算法存在拐點大、平滑性不足和運算時間長的問題。DWA算法可以對局部路徑進行規(guī)劃，避障效果很好，但是該算法存在局部最優(yōu)死循環(huán)，會導致整個路徑規(guī)劃失敗。蟻群算法的基本原理是模擬螞蟻覓食的行為，對起點至終點進行路徑規(guī)劃[3]。蟻群算法的優(yōu)點包括正反饋高、魯棒性強等，但是該算法的缺點是初期搜索效率不高，算法整體收斂速度慢，還存在局部最優(yōu)解。因此，本文提出一種新的路徑規(guī)劃算法，對傳統(tǒng)的蟻群算法進行改進，在啟發(fā)函數中引入1個重要的參數，這個參數是高度信息，同時對信息素模型進行優(yōu)化，利用動態(tài)揮發(fā)系數得到最佳的路徑規(guī)劃。

1 環(huán)境建立

路徑規(guī)劃是在特定的環(huán)境中找到起點至終點的最佳路線，如公式（1）所示。

min f（e），e∈λ（es，eo）" " " " " " " "（1）

式中：f（e）為路徑的目標函數；es為起點；eo為終點；

λ（es，eo）為2個點之間的路徑點集合。

常用的路徑規(guī)劃工具主要有柵格地圖、三維仿真地圖等，三維仿真地圖不易構建且維護較難，柵格地圖便于構建，精度高，維護簡單，因此本文使用柵格地圖作為果園噴霧機器人的工作環(huán)境空間，柵格模型如圖1所示。

柵格的粒徑大小是由機器人的規(guī)格和型號決定的，需要保證移動機器人可以自由移動，同時，還必須保證兩者之間有安全距離。在尋跡過程中，設定機器人不可以沿著障礙物邊緣以及頂點移動。當柵格中的障礙物填不滿1個柵格時，將這個柵格認定為1個柵格。在圖1中，白色柵格是自由柵格，路徑規(guī)劃可以自由使用，黑色柵格是障礙物，在果園噴霧機器人路徑規(guī)劃的過程中可以利用白色柵格避開黑色柵格，在柵格中，X方向的柵格號的順序為從左到右，Y方向的柵格號的順序為從下到上，左下角為起點，右上角為終點[4]。

每個柵格與其中心左邊的關系如公式（2）、公式（3）所示。

（2）

式中：xn為n點的橫軸坐標；mod為余數運算；n為圖中柵格的編號，n=0，1，…，399；Q為行和列的柵格的數量；yn為n點的縱軸坐標；fix為舍入運算。

n=（xn-1）+（yn-1）Q " " " " " " （3）

2 果園噴霧機器人路徑規(guī)劃算法設計

2.1 蟻群算法原理

蟻群算法利用1個重要的參數來引導整個搜索過程，這個參數是信息素，其核心原理是模擬螞蟻覓食的行為。在覓食的過程中，螞蟻會在路徑中留下痕跡，這個痕跡就是信息素，當別的螞蟻再次經過時可以感知。信息素為路徑選擇做出引導，最終得到最優(yōu)路徑[5]。

設m為節(jié)點，m、n之間轉移的概率計算過程如公式（4）所示[6]。

（4）

式中：Mj （i）為m、n之間的轉移概率；δm，n（i）為m和n之間i點的信息素濃度；γ為信息素啟發(fā)因子；?m，n（i）為i點的啟發(fā)函數；ε為啟發(fā)式因子；p為起始節(jié)點；allowedm為可以轉移點的坐標集合；δm，e（i）為m與e之間i點的信息素濃度；?m，e（i）為i點的啟發(fā)函數；G為自由柵格的集合。

m與n之間啟發(fā)信息如公式（5）所示。

φm，n（i）=1/l（m，n） " " " " " " " " "（5）

式中：l（m，n）為m與n之間的歐氏距離。

在進行尋優(yōu)的過程中，須對信息素濃度進行更新[7]，如公式（6）所示。

（6）

式中：σ為信息素揮發(fā)系數；R為蟻群的總量；i為迭代次數；Δδj （i）為信息素增量。

Δδj （i）計算過程如公式（7）所示[8]。

（7）

式中：D為信息素強度；Lj為路徑總長度；W為尋優(yōu)過程中路過的總柵格的集合；otherwise為其他情況。

2.2 改進啟發(fā)函數

在傳統(tǒng)的算法中，啟發(fā)函數只考慮了路徑長度這個參數，在運行過程中只能解決環(huán)境中的距離問題。但是，在實際工作中，果園噴霧機器人須考慮環(huán)境高度問題，傳統(tǒng)的啟發(fā)函數并沒有涉及這個問題，機器人在進行路徑規(guī)劃的過程中就會出現(xiàn)無法適應真實工作環(huán)境中高度不定的情況，因此需要進一步改進，如公式（8）所示。

φ（m，n）=l（m，n）-1+μ（i，j） " " " " " " " " （8）

式中：φ（m，n）為m點至n點的啟發(fā)函數；l（m，n）為m點至n點的距離信息；μ為高度，μ（i，j）為高度函數。同時可以表示其多元函數，如公式（9）所示[9]。

（9）

式中：gmax為相鄰2個柵格的最大差值；g（m）為m點的高度信息；g（n）為n點的高度信息；η、β為可以進行高度調節(jié)的常數；gmin為2個柵格的最小差值；C為常量，C的值在通常情況下為0.001。

2.3 信息素增量更新規(guī)則改進

在通常情況下，果園的環(huán)境是非常復雜的，當尋徑時需要考慮拐角的因素，這樣才能減少機器人的功耗，因此引入拐角度數評價函數f （θ），如公式（10）所示。

（10）

式中：θ為拐角度數。

在機器人尋徑的過程中，如果障礙物數量比較多，就容易陷入死局。因此，引入障礙物數量評價函數f（t），這樣能夠提升搜索效率[10]，如公式（11）所示。

（11）

式中：t為障礙物數量，其值設定在7以下。

在尋徑過程中，這個函數越小，確定這個節(jié)點的概率越高。

改進后的信息素增量如公式（12）所示。

（12）

式中：α為拐角平衡系數；ψ為障礙物數量平衡系數。

2.4 信息素更新規(guī)則改進

在傳統(tǒng)的蟻群算法中，信息素揮發(fā)系數σ是固定不變的，不但會影響全局搜索能力，而且會影響快速收斂能力。因此，需要使用信息素自適應揮發(fā)因子，前期增加σ的值來增加收斂速度，后期降低σ的值使全局搜索能力更強，改進后如公式（13）所示。

（13）

式中：σ（i）為i點的信息素揮發(fā)系數；a、b都為常數，a為信息素持久度常數的整數部分，b為信息素持久度常數的小數部分。

由公式（13）可知，改進后設定了信息素濃度值的最大值和最小值，避免出現(xiàn)算法的早熟和停滯，提升了算法的尋優(yōu)效率，因此能夠在[δmin，δmax]表示改進后的信息素濃度，如公式（14）所示。

（14）

2.5 算法實現(xiàn)

改進后的算法主要包括以下5個步驟。第一步，建立柵格地圖，將主要參數初始化。第二步，設置螞蟻搜索的起點和終點，清空禁忌表， 設置開始路徑點集合為空，同時將起點加入禁忌表，螞蟻開始搜索。第三步，利用公式（4）計算轉移概率，根據公式（9）和公式（12）得到下個節(jié)點的坐標，更新路徑長度。繼續(xù)這個循環(huán)，直至螞蟻到達終點。第四步，根據公式（13）、公式（14）更新信息素濃度，同時設置信息素濃度的最大值和最小值。第五步，判斷迭代次數的數量，如果迭代次數小于最大值，那么迭代次數加1，繼續(xù)從第二步執(zhí)行，如果迭代次數大于最大值，那么輸出最優(yōu)路徑。

3 測試結果

為了驗證本文算法的正確性，本文利用Matlab進行一系列對比測試，不僅對20×20柵格進行測試，還對更復雜的30×30柵格進行測試，20×20柵格路徑軌跡仿真結果對比如圖2所示，20×20 柵格路徑長度迭代對比如圖3所示，30×30柵格路徑軌跡仿真結果如圖4所示，30×30柵格路徑長度迭代對比如圖5所示，3種算法測試結果對比見表1、表2。

由圖2～圖5、表1和表2可知，采用3種算法都可以順利到達終點，基本蟻群算法迭代次數最多，路徑也最長。雖然AGV蟻群算法的路徑有所縮短，但是沒有考慮果園環(huán)境的復雜程度，在尋找最優(yōu)路徑的過程中需要更多的迭代次數，容易陷入死循環(huán)。由于地面高低不平，因此本文算法引入高度矩陣、角度數評價函數以及物數量評價函數等參數，不僅最優(yōu)路徑最短，而且迭代次數減少，避免死循環(huán)，在30×30柵格環(huán)境中，本文的優(yōu)勢更加明顯。

為了進一步驗證本文算法的優(yōu)勢，對更復雜的30×30柵格環(huán)境使用所尋路徑對環(huán)境的覆蓋這個參數進行量化分析，如公式（15）所示。

（15）

式中：ζ為所尋路經對環(huán)境的覆蓋率；QP為尋徑過程中檢測到的方格數量；Qf為自由方格數。

使用公式（15）對3種算法的所尋路徑對環(huán)境的覆蓋進行計算，基本蟻群算法的計算結果為57.69%，AGV蟻群算法計算結果為71.25%，而本文算法可達到79.36%，計算結果越大就證明在進行最優(yōu)路徑搜索的范圍越廣，進一步證明的本文算法的優(yōu)勢。

4 結論

本文研究復雜環(huán)境中果園噴霧機器人全局路徑規(guī)劃方法，該算法對傳統(tǒng)的蟻群算法進行改進，引入高度矩陣、拐角平衡系數和障礙物數量平衡系數等參數對啟發(fā)函數、信息素增量更新規(guī)則和信息素濃度更新規(guī)則進行優(yōu)化。由測試結果可知，不僅最優(yōu)路徑最短，而且減少迭代次數，縮短算法運行時間，避免死循環(huán)。在30×30柵格環(huán)境中，與傳統(tǒng)的蟻群算法相比，尋優(yōu)路徑對環(huán)境的覆蓋率可以提高21.67%。

參考文獻

[1]王超，王銀花.一種改進Dijkstra算法的UAV路徑規(guī)劃[J].信息技術與信化，2021（10）：217-219.

[2]卞強，孫齊，童余德.一種新的改進A算法無人機三維路徑規(guī)劃[J].武漢理工大學學報，2022，44（7）：80-88.

[3]王洪斌，郝策，張平，等.基于A～*算法和人工勢場法的移動機器人路徑規(guī)劃[J].中國機械工程，2019，30（20）：2489-2496.

[4]張麗珍，何龍，吳迪，等.改進型蟻群算法在路徑規(guī)劃中的研究[J].制造業(yè)自動化，2020，42（2）：55-59.

[5]楊嘉，劉虎，楊新坤，等.基于遺傳算法的移動機器人路徑規(guī)劃[J].機電工程技術，2020，49（12）：97-98，117.

[6]劉志海，薛媛，周晨，等.基于遺傳算法的機器人路徑規(guī)劃的種群初始化改進[J].機床與液壓，2019，47（21）：5-8.

[7]徐國生，徐祖永，周俊杰，等.基于遺傳算法的巡檢機器人路徑規(guī)劃算法的研究[J].機械設計與制造工程，2021，50（6）：93-98.

[8]宋啟松，李少波，柘龍炫，等.基于改進遺傳算法的自動導引小車路徑規(guī)劃[J].組合機床與自動化加工技術，2020（7）：88-92.

[9]YANG K，YOU X M，LIU S，et al.A novel ant colony optimization

based on game for traveling salesman problem[J].Applied Intelligence，2020，50（12）：4529-4542.

[10]SANGEETHA V，KRISHANKUMAKR R，RAVICH AND

R ，et al.Energy－ efficient green ant colony optimization for path planning in dynamic 3D environments[J].Soft computing，2021，25（6）：4749-4769.