基于改進蟻群算法的家庭機器人路徑規劃研究

王學忠，徐麗萍，李美蓮

(安徽三聯學院，安徽 合肥 230601)

隨著信息和AI技術的飛速發展，各種用于家政服務的智能產品應運而生，如各種用于娛樂的機器人、協助主人做飯的烹調機器人和用于室內打掃衛生的機器人等。目前，家庭智能機器人的兩個主要研究方向就是目標定位和路徑優化問題，所謂路徑優化就是機器人能夠在復雜的家庭環境里，在起點與終點之間的無數條行走路徑的方案中，能智能地選擇一條路程最短或行走的時間最短的路線，并且能很好地避開障礙物。目前，用于路徑優化的方法很多，譬如：蟻群優化算法(ant colony optimization, ACO)、A*算法[1]、經驗圖法、遺傳法和APF算法[2]等。由于ACO具有速度快，魯棒性好以及能在較短的時間內給出一個合理的運算結果，因此，ACO算法在機器人路徑優化方法中獲得人們普遍的青睞。左大利，聶清彬，張麗萍等同志通過引入死鎖處理技術以及改進信息素更新方法等以達到提高收斂速度和收斂精度的目的[3]；王志中同志通過引入螞蟻相遇策略和螞蟻回退技術達到提高搜索最優路徑的效率并且有效地避免陷入U形陷阱[4]；屈鴻，黃利偉，柯星等同志提出改進啟發式柵格算法達到路徑優化的目的[5]。

本文針對ACO算法在家庭機器人的路徑優化中存在的易早熟、效率不高、路徑的最優值不夠準確等問題，提出了一種改進的蟻群算法(Improved ant colony optimization，IACO)。主要是在二維二值網格坐標地圖上，通過動態地調整信息素啟發因子α和 信息素增強系數Q值、調整信息素和轉移概率的計算方法等實現了算法的優化。從仿真數據看出，改進后的IACO較好地縮短了收斂的間，效率得到了提高、避免了早熟，能夠在有限時間內快速地找到最優的規劃路徑，獲得的最優路徑的值更準確穩定。

1 家庭機器人路徑規劃ACO算法

1.1 ACO算法的基本原理

ACO是一種模擬螞蟻尋找食物食的算法，最早是由莫瑞希奧·多里戈(Maurizio Dorigo)

博士于1992年在他的博士論文中首先提出的。他在長期觀察螞蟻覓食的過程中發現單個螞蟻覓食的行為表現的非常簡單，但是群體螞蟻的覓食行為則表現得非常睿智，蟻群則可以在任何復雜的環境下，都能快速地尋到一條從洞穴通向覓食地點的最短道路。經過專家的多年的觀察發現，蟻群在其活動時會在其經過的道路上分泌出一定量的信息素物質，螞蟻能敏銳地嗅到這種物質，并通過這種物質指引它的前進的方向。譬如某路徑距離較短時，就會引來更多的同伴行走該路線，那么該道路上獲得這種化學物質將更多，其他同伴嗅到這條路徑上的濃烈的化學物質，因此選擇該道路的概率就會更高，這是一個正向反饋的過程，從而逐漸接近最優路徑[6]。

1.2 基于ACO算法的二維二值網格坐標地圖法步驟

1)輸入由0和1組成的矩形表示機器人需要尋找最優的網格地圖，如圖1所示。其中，0表示此處機器人可以通過，1表示此處為障礙物。由此可以得到圖1所示的矩陣如圖2所示。

圖1 室內環境分布圖

圖2 室內環境0、1矩陣圖

2)輸入初始的信息素矩陣，選擇初始點和終止點并且設置各種參數，設置所有位置的初始信息素相等。

3)計算出即將允許被訪問地點的概率，根據計算的結果并結合輪盤法挑選出將要被訪問的新地點。

(1)

公式中，τij(t)——地圖中兩點i,j間的道路上螞蟻分泌的信息素的濃度；

ηij(t)——與地圖中兩點i,j之間的路徑相關的期望值(啟發函數)；

α——信息啟發因子；

β——期望啟發因子；

αk——K螞蟻被允許訪問的地點集合。

4)更新路徑和路程長度。

5)重復3)、4)運算過程，一直到所有螞蟻回到目的地為止。

6)更新信息素，對于沒有到達目的地的螞蟻采取放棄策略。

(2)

公式中，ρ—— 信息素揮發系數(0≤ρ≤1)。

(3)

Q—— 信息素增強系數。

7)重復3)—6)，直至螞蟻迭代結束。

2 家庭機器人路徑規劃IACO算法

2.1 設置信息素閾值、改進信息素的計算方式

ACO的核心就是蟻群通過信息素這種物質相互之間進行的交流的，螞蟻將在所經過的道路上分泌出一定量的信息素來告知其他同伴來選擇即將行走的道路。通常是道路越短，蟻群通過后剩余的信息素的濃度會更高，將招來更多的同伴選擇該道路，從而形成最優的路徑。問題的關鍵是算法運算到一定的迭代次數后，有的路徑上的信息素很高，而有的路徑上則可能接近于0，這樣就會造成大量的螞蟻會集中在某一最優的路徑上形成堵塞，使算法出現早熟、導致獲得的結果不是最優的路徑。本文在傳統信息素更新方式的基礎上進行局部改進，通過設置信息素的最大閾值τmax，采用信息素動態調整的方式[7]，目的是減小最優道路上的信息素與最差道路上信息素的差值，使螞蟻不至于過多的聚集在某一條道路上，這樣有效地避免算法的早熟。改進后的信息素計算公式如下：

(4)

2.2 改進算法部分代碼描述

While(不滿足算法終止條件)

{for (i=1,i

for(j=0;j

{for(i=0;i

根據轉移公式(1)來算出的概率來選擇螞蟻下一步所要行走的路徑；

end

}

計算出最優的結果，并付給螞蟻i；

end

{

If(最優值達到前面多次循環的最優值)

更新 信息素值τ并進行下一循環；

end

}

end

}

輸出最優值

End

2.3 動態調整信息素增強系數Q值

信息素增強系數Q值的高低對算法的搜索范圍和算法收斂時長以及搜索的最佳路徑值都會產生一定的影響。Q值越大，能夠較好地提高螞蟻的搜索能力但容易陷入早熟；Q值越低，延長了收斂的時長、使算法的效率變低。本文采取動態調整Q值的方法，即在算法初期(迭代次數小于50次)適當增加Q的值(Q=2)，以擴大算法的搜索范圍，避免早熟；在算法的中后期(迭代次數大于50次)適當減小Q的值(Q=1)，以縮短算法的收斂時長和運算效率等。

2.4 改進概率轉移的計算方法和引入隨機機制

為了更好地提高算法的搜索范圍和尋優解的多樣性，在傳統蟻群算法的基礎上進行了算法的改進，加入了路徑選擇的隨機性變化。在算法中事先設置一個選擇參數δ0(0≤δ0≤1)，再由隨機函數rand( )產生一個隨機的數δ，當δ≤δ0時，從當前螞蟻所允許的所有路徑中隨機選擇一條路徑作為下一行走的目標；當δ>δ0時，則需要根據算法轉移計算公式(6)計算出下一步將要行走的路徑。新的選取方式如下：

(5)

公式中，ak為下一次可以被螞蟻訪問的所有路徑的集合。為了更好地提高全局的搜索能力，得到最優的搜索結果，對算法的轉移公式進行改進如下：

(6)

公式中，Sj為當前位置I到目標位置J兩點間的長度，Cj為目標位置J被訪問的累加和。轉移概率與Sj、Cj近似成反比，這樣有利于提高全局搜索能力、避免早熟。同時，對信息素啟發因子α進行動態調整，在算法搜索的前期(迭代次數小于等于30)，為了擴大搜索路徑的范圍，提高全局的搜索能力，適當減小信息素啟發因子α在概率轉移公式中的作用，把α的大小設置為1/2，在搜索的中后期，這時搜索的大致方向基本明確后，為了加快算法的收斂，提高算法的效率而適當增加了信息素啟發因子α的值，把α的值由1/2增加到1。

3 實驗結果分析

3.1 實驗仿真建模

為了測試改進后IACO算法在最優路徑、運行效率、收斂速度等方面要比基本的ACO算法具有一定的優越性，利用MATLAB 2014A軟件、在WIN7操作系統下進行路徑優化仿真模擬實驗。本實驗采用20X20網格的二維二值的坐標地圖，黑色方格為1，表示道路有障礙，行走不通；白色方格為0，表示道路暢通無阻。障礙物的大小可以通過黑色方格的不同組合而得到，方格的邊長設為1 cm。出發點的起始位置S(0,20)，即地圖的左上角；完成路徑的終點位置E(20,0)，即地圖的右下角。兩種算法的初始條件相同，設螞蟻M=50(個)，α=0.5，β=5，ρ=0.3，Q=2,迭代次數為200。

3.2 實驗數據分析

圖3 環境1的收斂曲線和機器人行走路線

圖4 環境2的收斂曲線和機器人行走路線

圖3、圖4分別是在模擬兩種不一樣的室內環境，兩種環境下障礙物的分布也不完全一樣，得到了兩組ACO和IACO的收斂變化趨勢圖和行走路線圖。從圖3所示環境1的仿真數據中可看出，基本ACO的迭代次數為130次，最優路徑的長度為39.078 cm；改進后的IACO的迭代次數為67次，最優路徑的長度為38.186 cm，改進后的算法(IACO)明顯優于基本算法(ACO)。圖4的環境2要比圖3的環境1復雜，從圖4所示環境2的仿真數據中看出，基本ACO的迭代次數為92次，最優路徑的長度為33.907 cm；改進后算法(IACO)的迭代次數為48次，最優路徑的長度為31.056 cm，改進后的算法(IACO)也明顯優于基本算法(ACO)。為了較全面地測試改進后的蟻群算法(IACO)的性能，分別采用用5組不同的環境(環境設置從簡單到復雜)進行對比測試，測試的初始條件都一樣，測試五組環境下的迭代次數M、最優路徑長度L、算法時長T的對比數據如表1所示。

表1 五種環境下、ACO與IACO兩種算法的數據對比

從表1中測試的數據可以看出，調整后的IACO計算方法無論是在收斂時間、最優路徑值、運算的效率都要好于基本ACO計算方法。

4 結論

從實驗數據可以看出，將二維二值網格坐標地圖法與蟻群算法相結合，通過調整基本ACO公式中信息素的計算方法和設置信息素的閾值等措施能有效避免算法的早熟，提高全局搜索能力；通過動態調整信息素增強系數Q值，擴大算法的搜索范圍，避免了早熟，縮短了算法的收斂時間和提高效率；通過改進轉移概率的計算方法，在算法的早期適當減小啟發因子α、引入路徑選擇的隨機性機制等方法擴大了算法的全局搜索能力，使獲得的最優路徑的值更穩定、更精確。