馬 軍,宋栓軍,韓軍政,熊繼淙,張周強,閻文利

(1.西安工程大學 機電工程學院， 陜西 西安 710048；2.航空工業西安飛機工業(集團)有限責任公司 工具管理中心，陜西 西安 710089)

0 引 言

智能機器人是無人工廠中不可或缺的一部分,而其中最重要的就是能讓機器人對已知的環境自主進行路徑規劃。現階段有多種算法可用于機器人路徑規劃,比如傳統算法中的RRT算法[1-3]、D*算法[4-5]和動態規劃算法等[6]。上述算法雖然能找到最終路徑,但是也存在各種缺點。RRT算法進行搜索時,只要起點到終點可以連線,就會生成路徑,所以不能保證輸出結果為最優路徑;D*算法只考慮相鄰兩點的距離,極容易陷入局部最優;動態規劃算法進行搜索時,會占據大量的空間,不適合較短的路徑規劃。為了讓算法能更好適應于路徑規劃,也產生了多種改進的算法,如Nazarahari等[7]通過融合勢場和遺傳算法尋求最優解,該方法可以跳出局部最小值,但是在實際應用中還要考慮路徑規劃的實時性,因此還需要進一步的研究;滕儒民等[8]通過對A*算法的改進來尋找最優解,該方法得到的搜索點較少,能夠快速得到最優路徑;易欣等[9]通過對遺傳算法的選擇算子進行改進來求解,提出的方法能夠較為有效地避免陷入局部最優,但是收斂速度較慢;而在路徑規劃求解的問題上,蟻群算法是最成功的[10],因此眾多有關路徑規劃方面的問題都用此算法來進行求解,梁嘉俊等[11]提出使用雙蟻群搜索,可以降低陷入局部搜索的概率來進行求解;Hocaoglu等[12]通過改進蟻群算法信息素更新方式，快速求得最優解;李二超等[13]提出將模擬退火和遺傳算法等多種智能算法的融合來求解最優路徑,此種方法是對NSGA-Ⅱ算法進行改進,根據給定約束條件,將所有的解集合分為可行性和非可行性解,引導可行性解變為更好的解,可大大減少搜索的時間；劉俊等[14]提出PSO-ACO融合的算法應用于室內路徑規劃,此種改進的方法雖然對蟻群算法有時陷入“自鎖”的問題有所改進,但是當數據量增大,路徑的復雜程度增高,其性能也會有所降低。

文中提出了一種融合蟻群-A*算法來進行求解,引入A*算法的估價函數,對蟻群算法的啟發函數和信息素更新方式進行改進調整,增加了算法搜索時的指向性,降低了其陷入“自鎖”的概率,提高了其搜索的速度和精度,以便于其在數據量較大時也可快速尋找最優路徑。

1 環境建模

在路徑規劃的環境地圖構建中,大多是應用柵格法進行建模,因此本文也利用柵格法建立了2種不同環境模型下的仿真地圖,如圖1，2所示。

在Matlab中利用柵格法建立20×20的方格,大小為1 m×1 m,其中黑色為不可通行路段,白色為可通行路段,左上角S(0.5,19.5)處為起點,右下角T(19.5,0.5)處為終點。

2 融合蟻群-A*算法

2.1 蟻群算法的數學模型

蟻群算法用來解決路徑規劃等方面問題時,基本的思想就是用螞蟻行走過的路徑集合來表示要尋求解決問題的可行性方案的集合[15-17]。螞蟻尋優過程在正反饋的作用下,逐漸聚集到最優的路徑上,也就是最佳的解決方案,而其中的路徑轉移概率為[18]

(1)

(2)

整個循環中螞蟻會不斷的釋放信息素,同時先前螞蟻釋放的也會不斷消失,可以設定一個參數ρ(0<ρ<1)表示信息素的揮發程度。循環完成后,需要對其進行實時的更新,更新方式如式(3)所示:

(3)

2.2 算法改進

2.2.1 啟發函數的改進 蟻群算法雖然可用于求解最優路徑,但是其啟發函數ηij(t)并未考慮到下一個節點和目標節點之間的距離,這在一定的程度上會使得算法的搜索速度和效率降低。因此,在蟻群算法的基礎上,融合A*算法,使其遇到自鎖時可進行局部規劃,從而提高算法的效率。估價函數的表達式為

f(n)=g(n)+h(n)

(4)

式中:f(n)為當前節點的估價函數;g(n)為當前節點到下一節點的實際代價,取值為當前節點到下一節點之間的距離;h(n)為下一節點到目標節點之間的估計代價,取值為下一節點到目標節點之間距離[19-20]。從而使得改進后的蟻群算法的啟發函數變為

(5)

式中:dij相當于估計函數中的g(n);diT則相當于h(n)。

2.2.2 信息素更新策略的改進 蟻群算法中信息素更新方式容易出現“自鎖”的現象,很難尋得最優解。因此在每次更新后計算出平均路徑,并且記錄最優路徑和最長路徑,如果此次路徑長度沒有上次短,則將其引入信息素更新策略中,從而降低陷入局部最優的可能,并且又能保證快速求解的能力,新的信息素更新方式為

(6)

式中:da為平均路徑;dm為最長路徑;dl為最優路徑；k為迭代次數。

改進后的算法步驟如下:

1) 柵格地圖的構建, 建立對應的描述矩陣用于存儲障礙物情況。

2) 對算法的參數的初始化。

3) 將螞蟻放置出發點。

4) 根據轉移概率公式選擇下一節點。

5) 更新運動節點禁忌表并判斷螞蟻是否運動至目標節點, 如若螞蟻無路可走判定該螞蟻已陷入自鎖,進入步驟6)。

6) 隨機選擇是否進行操作, 若未被選擇, 則此螞蟻徹底自鎖。若被選擇, 借助 A*算法進行局部路徑規劃,并將局部路線與已經探索路線進融合拼接。

7) 對全局信息素進行更新。并將當前迭代次數的平均路徑,最優和最長路徑進行記錄。

8) 判斷當前最優路徑和上代最優路徑的大小,如果當前路徑較小,則進行下一步,否則輸出最優路徑的同時將平均路徑,最優和最長路徑引入信息素更新策略中進行下次迭代。

9) 判斷是否迭代到200次,如果是,則輸出最優路徑,否則執行步驟2)。

3 實驗與結果分析

為了驗證文中的算法,在Matlab仿真軟件上進行實驗,先后采用2種不同環境對其進行仿真實驗,初始參數設定:螞蟻代數為200代,螞蟻個數為50只,α=3,β=7,ρ=0.3,Q=1,每種環境各仿真100次。

在環境模型1中進行仿真實驗, 實驗的收斂曲線和最優路徑軌跡對比圖如圖3和圖4所示。 表1為環境1仿真結果對比, 表2為環境2仿真結果對比。

表 1 環境1仿真結果對比Tab.1 Comparison of environment 1 simulation results

表 2 環境2仿真結果對比Tab.2 Comparison of environment 2 simulation results

圖 3 環境1收斂曲線對比Fig.3 Comparison of environment 1convergence curve

從圖3可知,本文算法在前期搜索時,有一定的波動,但是隨著搜索的進行,慢慢趨于平穩,搜索的路徑越來越短。從表1可知，蟻群算法從17代進行收斂,本文算法從13代開始收斂,且收斂速度也快于蟻群算法。

圖 4 環境1最優路徑對比Fig.4 Comparison of environment 1optimal path

從圖4可知本文算法的路徑明顯優于蟻群算法,而表1中數據也顯示,將最優和最長路徑引入信息素更新策略中進行下次迭代,無論是最優路徑長度還是平均路徑長度以及算法的平均耗時都明顯優于蟻群算法,并且最優解出現的次數比蟻群算法多。

在環境模型2中進行仿真實驗,實驗的收斂曲線和最優路徑軌跡對比如圖5和圖6所示。

圖 5 環境2收斂曲線對比Fig.5 Comparison of environment 2convergence curve

圖 6 環境2最優路徑對比Fig.6 Comparison of environment 2optimal path

從圖5和圖6可知,在相對復雜的環境模型2中,本文算法相對于蟻群算法可以相對快速的進行收斂。而從表2的數據中可以具體看出相對復雜的環境下本文的算法最優路徑長度為29.799 0 m,優于蟻群算法的32.213 2 m;最優解出現的次數為63次,遠遠大于蟻群算法的31次,并且程序的耗時較蟻群算法減少了2 s。

綜上，當環境變得相對復雜時,本文的算法也可快速進行收斂,并且在最優路徑上明顯優于蟻群算法,這表明改進后的算法是有效的,并且能夠適用于不同的復雜環境。

4 結 語

蟻群算法在路徑規劃時收斂速度比較慢,并且容易陷入“自鎖”等問題,本文提出了一種改進的方法,將A*算法的估價函數思想引入蟻群算法的信息素更新方式中,給螞蟻的搜索添加一個指向性,以便快速的尋找出最優的路徑。在Matlab上進行仿真,實驗結果表明本文算法在收斂速度上優先于蟻群算法4～6代,在最優路徑上也優于蟻群算法2～3 m,程序的運行速度上也較之快了2～3 s,且在最優解出現的次數上遠遠大于蟻群算法,證明本文算法有效、實用。