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

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

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

中圖分類號：TP 242" " " " " " " 文獻標(biāo)志碼：A

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

1 環(huán)境建立

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

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

式中：f（e）為路徑的目標(biāo)函數(shù)；es為起點；eo為終點；

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

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

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

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

（2）

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

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

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

2.1 蟻群算法原理

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

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

（4）

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

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

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

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

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

（6）

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

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

（7）

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

2.2 改進啟發(fā)函數(shù)

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

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

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

（9）

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

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

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

（10）

式中：θ為拐角度數(shù)。

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

（11）

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

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

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

（12）

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

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

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

（13）

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

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

（14）

2.5 算法實現(xiàn)

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

3 測試結(jié)果

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

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

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

（15）

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

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

4 結(jié)論

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

參考文獻

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

[2]卞強，孫齊，童余德.一種新的改進A算法無人機三維路徑規(guī)劃[J].武漢理工大學(xué)學(xué)報，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].機電工程技術(shù)，2020，49（12）：97-98，117.

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

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

[8]宋啟松，李少波，柘龍炫，等.基于改進遺傳算法的自動導(dǎo)引小車路徑規(guī)劃[J].組合機床與自動化加工技術(shù)，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.