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

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

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

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

1 環(huán)境建立

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

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

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

λ（es，eo）為2個(gè)點(diǎn)之間的路徑點(diǎn)集合。

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

柵格的粒徑大小是由機(jī)器人的規(guī)格和型號(hào)決定的，需要保證移動(dòng)機(jī)器人可以自由移動(dòng)，同時(shí)，還必須保證兩者之間有安全距離。在尋跡過(guò)程中，設(shè)定機(jī)器人不可以沿著障礙物邊緣以及頂點(diǎn)移動(dòng)。當(dāng)柵格中的障礙物填不滿1個(gè)柵格時(shí)，將這個(gè)柵格認(rèn)定為1個(gè)柵格。在圖1中，白色柵格是自由柵格，路徑規(guī)劃可以自由使用，黑色柵格是障礙物，在果園噴霧機(jī)器人路徑規(guī)劃的過(guò)程中可以利用白色柵格避開(kāi)黑色柵格，在柵格中，X方向的柵格號(hào)的順序?yàn)閺淖蟮接?，Y方向的柵格號(hào)的順序?yàn)閺南碌缴希笙陆菫槠瘘c(diǎn)，右上角為終點(diǎn)[4]。

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

（2）

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

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

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

2.1 蟻群算法原理

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

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

（4）

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

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

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

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

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

（6）

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

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

（7）

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

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

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

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

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

（9）

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

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

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

（10）

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

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

（11）

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

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

改進(jìn)后的信息素增量如公式（12）所示。

（12）

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

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

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

（13）

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

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

（14）

2.5 算法實(shí)現(xiàn)

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

3 測(cè)試結(jié)果

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

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

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

（15）

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

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

4 結(jié)論

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

參考文獻(xiàn)

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

[2]卞強(qiáng)，孫齊，童余德.一種新的改進(jìn)A算法無(wú)人機(jī)三維路徑規(guī)劃[J].武漢理工大學(xué)學(xué)報(bào)，2022，44（7）：80-88.

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

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

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

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

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

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