張曉玲,王正存,吳作君

(中國石油大學勝利學院 機械與控制工程學院,山東 東營 257061)

機器人路徑規(guī)劃問題是指,在已知機器人的起始和目的地坐標,明確環(huán)境信息條件下,找到一條能連接起始坐標和目的地坐標的最短路徑。現(xiàn)有的機器人路徑規(guī)劃方法有蟻群算法(Ant Colony Algorithm,ACO)[1],神經(jīng)網(wǎng)絡算法[2],人工勢場法[3],模擬退火算法[4]等。其中智能路徑規(guī)劃算法中的蟻群算法在機器人路徑規(guī)劃中被廣泛應用。蟻群算法是由意大利學者M.Dorigo[5]在1991年提出的一種受自然界生物的自催化行為啟發(fā)而產(chǎn)生的通用啟發(fā)式進化算法。它采用正反饋機制、分布式計算方法,具有較強的優(yōu)化能力和較強的魯棒性[6],經(jīng)常用來解決各種分布式環(huán)境下的組合優(yōu)化問題。蟻群算法不足之處在于,尋優(yōu)過程中當問題規(guī)模變大時,存在收斂精度變低問題。筆者采用改進的蟻群算法在搜索路徑過程中,使用模擬退火算法迭代和蟻群算法進行搜索路徑,利用回火條件,可以尋找到最優(yōu)路徑。

1　機器人運行環(huán)境建模

機器人路徑規(guī)劃首先需要對其運行環(huán)境或工作空間建模,考慮到柵格分解法具有精度高、方便實現(xiàn)等優(yōu)點,因此選用柵格法對機器人環(huán)境進行劃分。

設機器人的工作環(huán)境為二維平面上的方格區(qū)域,起始坐標和目的地坐標分別表示為S和T。每個柵格采用經(jīng)緯度坐標進行位置標示,并以地圖左下角的柵格S為機器人的起點,右上角柵格T為機器人的目的地。采用序號法對圖1中每一個柵格進行編號,其中黑色方塊表示環(huán)境中的障礙物,并采用八叉樹表示路徑搜索方向。

如果機器人在柵格地圖上t時刻所在的經(jīng)緯度為Lt(xt,yt),則在下一時刻的位置為Lt+1(xt+1,yt+1),此次移動長度dt為

(1)

假設從設置的起始點開始移動,要經(jīng)過n步到達所設目標終點,則此次所尋找路徑的長度為

(2)

用柵格法建立機器人的運行環(huán)境和工作空間模型后,下一步則需要結合合理有效的優(yōu)化方法尋找所有路徑中最短的路徑。

圖1　柵格地圖模型

2　基于傳統(tǒng)蟻群算法的路徑規(guī)劃

2.1　蟻群覓食分析

研究發(fā)現(xiàn),每只螞蟻覓食過程中在其行走路徑上會留下一種為信息素的化學物質,一定范圍內的其他螞蟻能感覺到這種物質,且傾向于朝信息素濃度高的方向移動[7]。如果在某一條所走過的路徑上被留下的信息素總量的濃度越高,則其他螞蟻傾向選擇這條路徑的概率就會越大,因此有了信息素這種媒介物質,最終使得絕大多數(shù)螞蟻選擇最短的路徑行走。

2.2　基于傳統(tǒng)蟻群算法的機器人路徑規(guī)劃步驟

步驟1:將算法中各類參數(shù)初始化,如蟻群中螞蟻數(shù)量、最大迭代次數(shù)等;

步驟2:在柵格地圖初始化時,將機器人看做一只螞蟻,螞蟻運動時受到各路徑上信息素濃度影響,根據(jù)每條路徑上的信息濃度決定下一步方向。螞蟻在t時刻當前位置為i,往位置j移動的概率Pij(t)為

(3)

式中,α,β為控制信息素和啟發(fā)信息影響大小的參數(shù);allowed是可選的前進方向集合。

步驟3:計算每個螞蟻所產(chǎn)生的路徑長度。

步驟4:更新信息素濃度。

τij(t+1)=ρτij(t)+Δτij(t,t+1).

(4)

(5)

式中,τij(t+1)為在第t次迭代時邊ij上的螞蟻釋放的信息素;ρ為信息素維持因子;Δτij(t,t+1)為每個螞蟻在某個邊ij上留下所產(chǎn)生信息素之和。

步驟5:使所有螞蟻執(zhí)行步驟2,得到n條路徑,找出所有路徑中最短的可行路徑,并按式(4)更新信息素矩陣。

步驟6:將當前迭代值與設定的最高迭代值進行比較,若超過限定值則終止循環(huán)迭代,否則回到步驟2,進入下一次迭代過程,直到滿足該條件退出。

3　基于改進蟻群算法的路徑規(guī)劃

3.1　模擬退火算法

模擬退火算法是對金屬退火過程的模擬,先用高溫將金屬融化,然后逐漸冷卻,直到形成良好的晶體結構,即進入一種具有最小能量的狀態(tài)[8]。模擬退火算法也可用于路徑規(guī)劃算法以避免陷入局部最優(yōu)。

模擬退火算法迭代過程如下。

第一步:某個溫度T下得到一個解(結合蟻群算法時,指用蟻群算法優(yōu)化得到的解)。

第二步:若當前溫度T下得到的解比前一時刻溫度的解好,則采用這個新的解,否則轉第三步。

第三步:計算溫度T下接受劣解的概率。

(6)

其中,隨機產(chǎn)生一個[0,1]區(qū)間的隨機數(shù)X,如果X

從P的計算公式可以看到,隨著溫度T的上升,P的值是越來越小的,隨著迭代的進行,接受劣解的概率下降,與自然界中晶體退火結晶的過程非常相似,從而實現(xiàn)了模擬退火算法。

3.2　帶回火的模擬退火-蟻群算法路徑規(guī)劃步驟

采用模擬退火-蟻群算法進行路徑尋優(yōu)時,加入回火,回火機制是指當溫度低于設定回火下限溫度時,溫度慢慢升溫到回火上限溫度?；鼗鸨举|上是在一段溫度范圍內反復循環(huán)降溫過程,使得當前解不斷得到優(yōu)化,可以得到更好的解,消除快速降溫時產(chǎn)生的局部最優(yōu)[8]。因此帶回火的模擬退火-蟻群算法的迭代步驟如下。

步驟1:初始化算法中各類參數(shù),如蟻群中螞蟻的數(shù)量antnumber,迭代次數(shù)maxgen,冷卻系數(shù)q,初始溫度T0,回火溫度下限Tmin,回火溫度上限Tmax,回火次數(shù)Hmax等。

步驟2:設置蟻群算法的啟發(fā)值和信息素濃度的初始大小進行模擬退火-蟻群算法的尋優(yōu)。

步驟3:進行螞蟻搜索,設置起點并根據(jù)式(3)計算螞蟻向各個方向移動的概率Pij,并根據(jù)概率公式移動到新位置后再進一步計算下一步移動的概率并移動,重復這個過程直到搜索到所設定的目的地或者找不到目的地直接退出。

步驟4:計算目標函數(shù),判斷新路線是否優(yōu)于原有路線,如果優(yōu)于則接受新路線,轉到步驟5;否則根據(jù)模擬退火機制按照式(6)計算接受較劣新線路(劣解)的概率,若概率滿足條件則接受劣解,否則放棄。

步驟5:根據(jù)式(4)、(5)進行信息素濃度更新,并更新溫度(模擬退火冷卻過程,溫度逐漸降低),判斷是否滿足回火條件(回火次數(shù)未達到或者溫度低于最小回火溫度),滿足則進行回火,回火次數(shù)自增1。

步驟6:判斷模擬退火算法迭代過程是否已經(jīng)完成,若未完成則繼續(xù)下一步迭代運算,相反,若完成則結束迭代循環(huán)。

步驟7:輸出結果,算法運行結束。

4　仿真研究

首先隨機生成一個15×15的柵格地圖仿真機器人路徑搜索的運行環(huán)境,然后基于同一地圖,分別運用傳統(tǒng)蟻群算法和帶回火的模擬退火-蟻群算法進行機器人路徑規(guī)劃的仿真研究,得到結果如圖2～5所示。

比較圖2和圖4的目標函數(shù)值(最優(yōu)路徑長度)可以看出,傳統(tǒng)蟻群算法穩(wěn)定在175左右,改進的帶回火模擬退火-蟻群算法穩(wěn)定在163左右。圖3和圖5的路徑搜索線路也表明,相對傳統(tǒng)的標準蟻群算法,本文提出改進后的優(yōu)化方法查找到的移動路徑明顯更短。但通過觀察圖2和圖4兩種算法下的迭代次數(shù),發(fā)現(xiàn)改進蟻群算法在迭代次數(shù)(63次)上稍遜于傳統(tǒng)蟻群算法(57次)。為更合理地對比傳統(tǒng)蟻群和改進蟻群算法,在不同大小的柵格地圖上對兩種算法進行多次仿真試驗,結果如表1所示,分別記錄了各自的迭代次數(shù)、最短路徑值和平均運行時間。

圖2　傳統(tǒng)蟻群算法優(yōu)化過程

圖3　傳統(tǒng)蟻群算法最優(yōu)路徑

圖4　改進蟻群算法優(yōu)化過程

圖5　改進蟻群算法最優(yōu)路徑

柵格地圖大小迭代次數(shù)傳統(tǒng)算法改進算法最優(yōu)路徑長度傳統(tǒng)算法改進算法運行時間/s傳統(tǒng)算法改進算法 11×114574165.8155.25.96.3 15×155763174.9163.214.914.4 20×205379191.2188.233.731.0 25×254759199.6182.682.880.6 30×307479200.0208.4195.0193.3 35×359196248.1208.7274.9257.0 40×407474222.7199.1452.1438.0

對表1分析可得,改進算法在迭代次數(shù)上雖不占優(yōu)勢,略高于傳統(tǒng)算法,但兩種算法基于同一大小的柵格環(huán)境下實際運行時間相差無幾,反而在柵格不斷增多的情況下,改進算法的收斂速度要快于傳統(tǒng)蟻群算法。從最優(yōu)路徑方面比較,除了在30×30大小的柵格地圖上改進算法得到的最優(yōu)路徑相對傳統(tǒng)算法稍長,其他結果均明顯優(yōu)于傳統(tǒng)蟻群算法。因此,綜合看來,在機器人尋找最優(yōu)路徑上,改進蟻群算法有一定的優(yōu)越性。

5　結束語

針對基本的蟻群算法在解決移動機器人路徑規(guī)劃尋找最優(yōu)搜索路徑時存在收斂精度不夠的問題,引入帶回火的模擬退火原理處理蟻群算法得到的路徑值,從而提出一種改進算法。最終的改進蟻群算法相比傳統(tǒng)蟻群算法,具有更強的尋優(yōu)能力,能夠找到更好的機器人移動路徑。