基于改進蟻群優(yōu)化算法的養(yǎng)殖場機器人路徑規(guī)劃*

趙廣元，趙 英

(1.西安郵電大學自動化學院,陜西 西安 710121;2.西安郵電大學西安市先進控制與智能處理重點實驗室，陜西 西安 710121)

1 引言

隨著科技的發(fā)展，養(yǎng)殖場逐漸向規(guī)?；?、智能化發(fā)展。養(yǎng)殖場中智能巡視機器人正在逐漸替代人工，能夠有效節(jié)約人力和物力資源，而且還能有效避免工作人員被病菌感染，更加方便養(yǎng)殖場的管理。智能巡視機器人在規(guī)?；B(yǎng)殖場巡視過程中存在電量不足的情況，需要尋找一條從起始點到充電點的最短無碰撞路徑。路徑的規(guī)劃與選擇是目前解決此問題的關鍵，較好的路徑能夠提高巡視效率，節(jié)約資源[1]。

現(xiàn)有的路徑規(guī)劃研究算法主要分為經(jīng)典算法和啟發(fā)式算法。近年來，學者們提出許多人工智能算法，代表性的啟發(fā)算法有粒子群算法[2]、蟻群優(yōu)化ACO(Ant Colony Optimization)算法[3]、遺傳算法[4]、神經(jīng)網(wǎng)絡算法[5]和模擬退火算法[6]等。

蟻群優(yōu)化ACO算法是一種啟發(fā)式算法，由意大利學者Dorigo等[7]于1990年首次提出。傳統(tǒng)的蟻群優(yōu)化算法在路徑優(yōu)化方面存在一些缺陷，如路徑傳播方向不確定，收斂速度慢，容易出現(xiàn)停滯等。為避免上述缺陷，許多學者對傳統(tǒng)的蟻群優(yōu)化算法進行了改進。Yue等[8]通過改變蟻群優(yōu)化算法初始信息素濃度和信息素更新規(guī)則解決了TSP(Traveling Salesman Problem)問題。Shen[9]將遺傳算法加入到蟻群優(yōu)化算法的每次迭代中,用于焊接機器人的路徑規(guī)劃研究。

法，為了找到在障礙物環(huán)境中的最佳無碰撞路徑，本文提出一種改進的蟻群優(yōu)化IACO(Improved ACO)算利用全局環(huán)境信息構(gòu)建目標吸引函數(shù)，確定下一節(jié)點的轉(zhuǎn)移概率，使得螞蟻更加趨向于向最佳路徑方向移動。通過加入額外的信息素更新項來提高算法的收斂速度，以及改進了信息素揮發(fā)系數(shù)以提高算法后期尋優(yōu)能力。4個實驗仿真表明，改進的蟻群優(yōu)化算法可以在簡單或者復雜的障礙物環(huán)境中找到無碰撞最佳路徑。

2 用柵格法建立環(huán)境模型

移動機器人實際工作空間是三維的現(xiàn)實空間，環(huán)境地圖建模的過程就是實現(xiàn)現(xiàn)實空間到抽象空間的映射過程，環(huán)境模型的構(gòu)造采用了一種常用的網(wǎng)格映射方法。使用該方法，將機器人的工作環(huán)境映射到一個二維網(wǎng)格中，如圖1所示。

Figure 1 Two-dimensional working environment model of robot圖1 機器人二維工作環(huán)境模型

在柵格環(huán)境中，自由區(qū)域(由白色柵格表示)和障礙物區(qū)域(由黑色柵格表示)分別由二進制數(shù)字“0”和“1”代替。螞蟻只能通過自由區(qū)域，不能進入障礙物區(qū)域。地圖中柵格編號r與坐標(x,y)之間的轉(zhuǎn)換關系如式(1)所示：

(1)

其中，mod(·)為求余運算,fix(·)為取整運算。

3 傳統(tǒng)蟻群優(yōu)化算法

蟻群優(yōu)化算法是受螞蟻覓食過程中互相交流的行為啟發(fā)提出的。螞蟻在一起尋找食物的主要過程描述如下：螞蟻在覓食時，在行走的過程中釋放出信息素標識自己的行走路徑,信息素濃度與螞蟻走過的路徑長度成反比關系。隨后，許多螞蟻開始根據(jù)信息素和環(huán)境信息找到從洞穴到食物的途徑。螞蟻在選擇路徑時總是傾向于朝信息素濃度高的地方移動，越來越多的信息素被釋放在較短的路徑上，后續(xù)螞蟻選擇該路徑的概率也會越大，其他路徑上的信息素隨著時間推移不斷揮發(fā)，最后會將蟻群聚集到最短路徑上。

(2)

(3)

在搜索的初期，蟻群進行無方向的搜索。當所有螞蟻完成一次搜尋后，對路徑上的信息素進行更新，更新公式如式(4)所示：

(4)

(5)

其中，Q為螞蟻信息素強度，Lk為第k只螞蟻在本次迭代中所走過的路徑總長度。

4 改進蟻群優(yōu)化IACO算法

4.1 改進狀態(tài)轉(zhuǎn)移概率

狀態(tài)轉(zhuǎn)移概率決定了螞蟻下一步的移動方向，由啟發(fā)函數(shù)和信息素濃度確定。傳統(tǒng)蟻群優(yōu)化算法的啟發(fā)函數(shù)為當前節(jié)點到下一節(jié)點之間歐氏距離的倒數(shù)，在算法搜索前期，由于方向差異很小，缺乏原始的方向性啟發(fā)式信息，導致算法的收斂速度慢[10]。為了提高經(jīng)典蟻群優(yōu)化算法的搜索性能，提高算法收斂速度，本文利用工作環(huán)境的全局信息建立目標吸引函數(shù)，確定向下一節(jié)點目標的轉(zhuǎn)移概率，減少在算法前期搜索的盲目性，指導蟻群向最佳路徑的方向移動。目標吸引函數(shù)如式(6)所示：

(6)

(7)

改進后的狀態(tài)轉(zhuǎn)移概率方程，通過引入目標吸引函數(shù)使蟻群優(yōu)化算法更快地找到最優(yōu)路徑。

4.2 改進信息素更新機制

在傳統(tǒng)的蟻群優(yōu)化算法中，信息素更新規(guī)則如式(4)所示，采用該信息素更新規(guī)則，雖然算法能夠收斂，但無法保證算法的收斂速度[11]。為了加快算法收斂速度，提高算法搜索能力，本文通過式(8)和式(9)將額外信息素更新項添加到原始信息素更新規(guī)則中：

(8)

(9)

其中，Qextra(t)為信息素增強系數(shù)，Lavg為蟻群搜索到的平均路徑長度，LBetter為短于平均路徑長度的路徑，LWorse為長于平均路徑長度的路徑，Lelse為無法到達的路徑,ij表示節(jié)點i和節(jié)點j之間的路徑。

使用額外的信息素更新項，提高了算法搜索效率，加快了收斂速度。同時，避免了信息素在較好的路徑中無限積累而容易陷入局部極小的情況。設置信息素增強系數(shù)Qextra如式(10)所示：

(10)

其中，A和B為設置參數(shù)，N為最大迭代次數(shù),n為當前迭代次數(shù)。Qextra的值與迭代次數(shù)成反比關系，有效避免了算法搜索后期的信息素在最好路徑上的無限累積而導致算法陷入局部最優(yōu)的情況。

蟻群尋找路徑時主要通過信息素進行交流，信息素揮發(fā)系數(shù)ρ在蟻群優(yōu)化算法中至關重要[12]。在傳統(tǒng)蟻群優(yōu)化算法中，ρ是定值，一般根據(jù)先驗知識選取，主觀性太強。當處于復雜環(huán)境時，ρ值較大會增加信息素的正反饋并減小搜索空間，ρ值過小會降低算法的收斂速度[13]。隨著時間和迭代次數(shù)的增加，傳統(tǒng)蟻群優(yōu)化算法容易陷入局部最優(yōu)解。為了提高算法收斂速度同時確保尋找到全局最優(yōu)解，設置t時刻的自適應信息素揮發(fā)系數(shù)ρ(t)如式(11)所示：

(11)

其中，ρmin為信息素揮發(fā)系數(shù)ρ的最小值，μ為常數(shù)。

4.3 限定信息素閾值

在蟻群優(yōu)化算法搜索后期，由于蟻群優(yōu)化算法的正反饋機制，路徑之間信息素差異太大，算法容易過早收斂[14]。為了提高算法的全局搜索能力，算法在每次迭代后，將路徑上的信息素限制在一個固定的范圍內(nèi)，如式(12)所示：

(12)

其中，τmin為信息素最小值，τmax為信息素最大值。

4.4 IACO算法具體步驟

IACO算法基本步驟如下所示：

步驟1采用柵格法創(chuàng)建環(huán)境模型，初始化蟻群優(yōu)化算法相關參數(shù)以及機器人起始點和目標點坐標。

步驟2將螞蟻放在起始點，按照式(7)，利用輪盤賭的方法選擇下一步移動到的節(jié)點j，其轉(zhuǎn)移概率為pij，其中的目標吸引函數(shù)由式(6)確定，并將節(jié)點j加入禁忌表。

步驟3所有螞蟻都搜索到路徑之后，找出其中的最短路徑。在已有信息素基礎上增加這一代螞蟻生成的信息素，根據(jù)式(8)和式(12)完成全局的信息素更新。

步驟4如果算法達到最大迭代次數(shù)，則輸出最短路徑，否則重復步驟2和步驟3。

5 仿真結(jié)果與分析

本仿真實驗在Matlab R2016a平臺上進行，初始化時，設置改進蟻群優(yōu)化算法的參數(shù)：螞蟻種群大小m=30，最大迭代次數(shù)N=100，其他參數(shù)α=1,β=5,ρ=0.1,Q=5,A=10,B=10。為了驗證改進蟻群優(yōu)化算法的性能，在規(guī)模和障礙物覆蓋率不同的柵格環(huán)境中，將改進蟻群優(yōu)化IACO算法與傳統(tǒng)的蟻群優(yōu)化ACO算法規(guī)劃的路徑進行比較。

5.1 20×20環(huán)境中2種算法比較

在20×20的柵格環(huán)境中，分別設置簡單的柵格環(huán)境(障礙物覆蓋率為10%，如圖2a和圖2b所示)和以養(yǎng)雞場環(huán)境為模型的復雜環(huán)境(障礙物覆蓋率為39%，如圖3a和圖3b所示)。圖2a和圖3a分別為ACO算法在簡單和復雜環(huán)境中的行走路徑。圖2b和圖3b分別為IACO算法在簡單和復雜環(huán)境中的行走路徑，不同環(huán)境中2種算法的路徑迭代曲線分別如圖2c和圖3c所示。

為了避免算法結(jié)果產(chǎn)生的偶然性，在相同參數(shù)設置和同樣的工作環(huán)境中，將2種算法獨立運行10次，得到平均路徑長度和平均迭代次數(shù)，如表1所示。

Figure 2 Path comparison results by two algorithms in a 20×20 simple environment 圖2 20×20簡單環(huán)境中的2種算法規(guī)劃路徑對比結(jié)果

Figure 3 Path comparison results by two algorithms in a 20×20 complex environment 圖3 20×20復雜環(huán)境中2種算法規(guī)劃路徑對比結(jié)果

Table 1 Performance comparison between ACO algorithm and IACO algorithm in 20×20 environment表1 20×20環(huán)境中ACO算法與IACO算法性能比較

5.2 30×30環(huán)境中2種算法比較

為了進一步驗證算法的優(yōu)越性，將機器人工作環(huán)境擴大為30×30的柵格環(huán)境，分別設置簡單(障礙物覆蓋率為10%)和復雜(障礙物覆蓋率為30%)的柵格環(huán)境,如圖4與圖5所示。圖4a和圖5a分別為ACO算法在簡單和復雜環(huán)境中的行走路徑。圖4b和圖5b分別為IACO算法在簡單和復雜環(huán)境中的行走路徑，不同環(huán)境中2種算法的路徑迭代曲線分別如圖4c和圖5c所示。在30×30的柵格環(huán)境中，在相同的參數(shù)下將2種算法獨立運行10次得到平均路徑長度和迭代次數(shù),如表2所示。

Figure 4 Path comparison results by two algorithms in a 30×30 simple environment 圖4 30×30簡單環(huán)境中2種算法規(guī)劃路徑對比結(jié)果

Figure 5 Path comparison results by two algorithms in a 30×30 complex environment 圖5 30×30復雜環(huán)境中2種算法規(guī)劃路徑對比結(jié)果

Table 2 Performance comparison between ACO algorithm and IACO algorithm in 30×30 environment表2 30×30環(huán)境中ACO算法與IACO算法性能比較

從圖2～圖4可以看出，在簡單和復雜的環(huán)境中，IACO算法在路徑設計和規(guī)劃方面都要優(yōu)于ACO算法。通過2種算法的路徑迭代曲線以及表1和表2中平均路徑長度和迭代次數(shù)可以看出，在20×20的柵格環(huán)境中，本文IACO算法在簡單和復雜環(huán)境中比ACO算法的平均路徑長度縮短了2.829和5.009，平均收斂次數(shù)提升了62.190%和65.605%，在30×30的柵格環(huán)境中，相比ACO算法,本文IACO算法在簡單和復雜環(huán)境中平均路徑長度縮短了6.450和9.389，平均收斂次數(shù)提升了59.764%和60.202%。分析實驗結(jié)果可知，ACO算法搜索效率低下，且易錯過最優(yōu)路徑，本文IACO算法的最優(yōu)路徑長度更短，相比ACO算法擁有更加高效的尋徑能力和質(zhì)量。

6 結(jié)束語

本文通過對規(guī)?；B(yǎng)殖場巡視機器人路徑規(guī)劃問題的分析和建模，提出一種改進的蟻群優(yōu)化IACO算法,用于巡視機器人路徑規(guī)劃。為了縮短算法的迭代時間，采用目標吸引函數(shù)代替?zhèn)鹘y(tǒng)啟發(fā)函數(shù)，加入額外的信息素更新項加快算法的收斂速度；其次設置了自適應揮發(fā)系數(shù)，以有效克服算法后期易陷入局部最優(yōu)的缺陷。通過仿真實驗表明，本文的IACO算法用于移動機器人路徑規(guī)劃，在簡單(較少障礙物)和復雜(較多障礙物)環(huán)境中都可以找到最佳避障路徑。