趙廣元，趙 英

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

1 引言

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

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

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

法，為了找到在障礙物環(huán)境中的最佳無碰撞路徑，本文提出一種改進(jìn)的蟻群優(yōu)化IACO(Improved ACO)算利用全局環(huán)境信息構(gòu)建目標(biāo)吸引函數(shù)，確定下一節(jié)點的轉(zhuǎn)移概率，使得螞蟻更加趨向于向最佳路徑方向移動。通過加入額外的信息素更新項來提高算法的收斂速度，以及改進(jìn)了信息素?fù)]發(fā)系數(shù)以提高算法后期尋優(yōu)能力。4個實驗仿真表明，改進(jìn)的蟻群優(yōu)化算法可以在簡單或者復(fù)雜的障礙物環(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ū)域(由黑色柵格表示)分別由二進(jìn)制數(shù)字“0”和“1”代替。螞蟻只能通過自由區(qū)域，不能進(jìn)入障礙物區(qū)域。地圖中柵格編號r與坐標(biāo)(x,y)之間的轉(zhuǎn)換關(guān)系如式(1)所示：

(1)

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

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

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

(2)

(3)

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

(4)

(5)

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

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

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

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

(6)

(7)

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

4.2 改進(jìn)信息素更新機制

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

(8)

(9)

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

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

(10)

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

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

(11)

其中，ρmin為信息素?fù)]發(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)化算法相關(guān)參數(shù)以及機器人起始點和目標(biāo)點坐標(biāo)。

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

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

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

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

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

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

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

為了避免算法結(jié)果產(chǎn)生的偶然性，在相同參數(shù)設(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復(fù)雜環(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種算法比較

為了進(jìn)一步驗證算法的優(yōu)越性，將機器人工作環(huán)境擴大為30×30的柵格環(huán)境，分別設(shè)置簡單(障礙物覆蓋率為10%)和復(fù)雜(障礙物覆蓋率為30%)的柵格環(huán)境,如圖4與圖5所示。圖4a和圖5a分別為ACO算法在簡單和復(fù)雜環(huán)境中的行走路徑。圖4b和圖5b分別為IACO算法在簡單和復(fù)雜環(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復(fù)雜環(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可以看出，在簡單和復(fù)雜的環(huán)境中，IACO算法在路徑設(shè)計和規(guī)劃方面都要優(yōu)于ACO算法。通過2種算法的路徑迭代曲線以及表1和表2中平均路徑長度和迭代次數(shù)可以看出，在20×20的柵格環(huán)境中，本文IACO算法在簡單和復(fù)雜環(huán)境中比ACO算法的平均路徑長度縮短了2.829和5.009，平均收斂次數(shù)提升了62.190%和65.605%，在30×30的柵格環(huán)境中，相比ACO算法,本文IACO算法在簡單和復(fù)雜環(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ī)劃問題的分析和建模，提出一種改進(jìn)的蟻群優(yōu)化IACO算法,用于巡視機器人路徑規(guī)劃。為了縮短算法的迭代時間，采用目標(biāo)吸引函數(shù)代替?zhèn)鹘y(tǒng)啟發(fā)函數(shù)，加入額外的信息素更新項加快算法的收斂速度；其次設(shè)置了自適應(yīng)揮發(fā)系數(shù)，以有效克服算法后期易陷入局部最優(yōu)的缺陷。通過仿真實驗表明，本文的IACO算法用于移動機器人路徑規(guī)劃，在簡單(較少障礙物)和復(fù)雜(較多障礙物)環(huán)境中都可以找到最佳避障路徑。