郝 琨 張慧杰 李志圣 劉永磊

(天津城建大學(xué)計算機與信息工程學(xué)院， 天津 300384)

0 引言

隨著科技的發(fā)展，移動機器人已經(jīng)被廣泛應(yīng)用于地面自主導(dǎo)航[1]、水下環(huán)境勘探[2]、應(yīng)急信息采集[3]等領(lǐng)域中。路徑規(guī)劃技術(shù)是實現(xiàn)移動機器人智能化的關(guān)鍵技術(shù)之一，它是指移動機器人根據(jù)一種或多種性能指標，在復(fù)雜的空間環(huán)境中，尋找一條從起點到終點且沒有碰撞的最優(yōu)或次優(yōu)路徑[4-5]。目前移動機器人路徑規(guī)劃的主流算法分為兩大類：傳統(tǒng)算法與仿生學(xué)智能算法。其中，傳統(tǒng)算法主要有A*算法、人工勢場法等。智能算法主要有遺傳算法、蟻群算法、粒子群算法、免疫算法等[6-8]。傳統(tǒng)算法在簡單的地圖環(huán)境中性能較好，但不適用于復(fù)雜的地圖環(huán)境中。而智能仿生學(xué)算法則存在過早收斂、易陷入局部極值等問題[9]。

蟻群算法具有良好的并行性和魯棒性，因此被廣泛地應(yīng)用于路徑規(guī)劃領(lǐng)域[10-12]。但蟻群算法在路徑規(guī)劃領(lǐng)域也存在前期搜索盲目、收斂速度慢、容易陷入局部最優(yōu)和死鎖等問題。文獻[13]利用人工勢場法修改了蟻群算法的啟發(fā)值參數(shù)，并提出了吸引素使蟻群算法更快收斂。文獻[14]提出了一種基于合作博弈機制的多蟻群協(xié)同優(yōu)化算法(CCACO)來加快算法的收斂速度，但該算法在大規(guī)模地圖中運行效率低。文獻[15]將人工勢場法與蟻群算法相結(jié)合來提高算法后期的全局搜索能力。并采用基于運動路徑的幾何方法實現(xiàn)動態(tài)障礙物避障，但該算法不適合在未知環(huán)境下使用。文獻[16]提出了一種改進蟻群算法(Improved ant colony algorithm，IACO)。該算法通過使初始信息素不均勻分布避免算法的早期盲目搜索，加快算法收斂速度，并利用動態(tài)懲罰方法減少螞蟻陷入死鎖的數(shù)量，但是該方法不能有效解決深度死鎖問題。文獻[17]提出了一種改進雙層蟻群算法，將蟻群劃分為引導(dǎo)層蟻群和普通層蟻群以應(yīng)對不同的情況。然而，該算法將引導(dǎo)層蟻群與普通蟻群并行進行使引導(dǎo)層蟻群并未起到相應(yīng)作用。

針對蟻群算法在路徑規(guī)劃中存在收斂速度慢、收斂路徑質(zhì)量低、死鎖以及動態(tài)避障能力差的問題，本文提出基于改進避障策略和雙優(yōu)化蟻群算法(Double optimization ant colony algorithm，DOACO)的路徑規(guī)劃方法，該算法通過改進概率轉(zhuǎn)移函數(shù)解決蟻群算法收斂速度慢的問題；通過回溯機制結(jié)合路徑長度清零機制解決死鎖問題；并通過路徑優(yōu)化與精英保存策略進一步提高收斂路徑的質(zhì)量；同時針對動態(tài)環(huán)境中的避障問題，提出一種避障行為與局部路徑重規(guī)劃相結(jié)合的避障策略。

1 空間環(huán)境模型

采用柵格法[18]建立空間環(huán)境模型，整個二維平面被劃分為20×20大小一致的柵格，如圖1所示。其中，白色柵格表示機器人可活動的自由區(qū)域，黑色柵格表示靜態(tài)障礙物，紅色柵格表示動態(tài)障礙物。黑色柵格和紅色柵格所在區(qū)域均為機器人不可活動區(qū)域(即障礙物區(qū)域)。地圖從左到右、從上到下由1開始為柵格添加編號直到添加至右下角的第400號柵格。環(huán)境地圖中各柵格的坐標由其中心點坐標(x,y)表示，柵格編號與柵格坐標之間的轉(zhuǎn)換式為

圖1 20×20柵格地圖Fig.1 20×20 grid map

(1)

y=n+0.5-ceil(m/n)

(2)

其中

m=floor(l-y)n+ceil(x)

(3)

式中m——柵格編號

n——柵格總列數(shù)

l——柵格總行數(shù)

(x,y)——柵格的橫、縱坐標

式(1)、(2)把柵格編號轉(zhuǎn)換成柵格坐標。式(3)把柵格坐標轉(zhuǎn)換成柵格編號。mod()為取余函數(shù)，floor()為向下取整函數(shù)，ceil()為向上取整函數(shù)。

2 DOACO算法設(shè)計

2.1 DOACO算法

DOACO算法參數(shù)包括：起點柵格編號S，目標點柵格編號G，最大迭代次數(shù)Ncmax，當(dāng)前迭代次數(shù)Nc，蟻群中螞蟻的總數(shù)量K，當(dāng)前螞蟻數(shù)量k，信息素常量Q，信息素因子α，啟發(fā)式因子β，信息素揮發(fā)因子ρ，偽隨機概率調(diào)整因子q0。圖2為DOACO算法流程圖，算法流程如下：①對蟻群算法的各參數(shù)進行初始化。②令Nc=1。③令k=1。④將第k只螞蟻放置在起點位置。⑤根據(jù)改進的概率轉(zhuǎn)移公式選擇下一個路徑點。⑥判定螞蟻是否陷入死鎖狀態(tài)，若陷入死鎖，則采用死鎖處理策略使得螞蟻跳離死鎖，然后轉(zhuǎn)入步驟⑤；若未陷入死鎖，則更新第k只螞蟻的禁忌表，然后轉(zhuǎn)入步驟⑦。⑦判斷螞蟻是否到達目標點，若未到達，轉(zhuǎn)至步驟⑤；若已到達目標點，則轉(zhuǎn)到步驟⑧。⑧判斷該螞蟻是否為當(dāng)前迭代次數(shù)中的最后一只螞蟻，若不是最后一只螞蟻，則令k=k+1，然后返回步驟④；若是最后一只螞蟻，則更新信息素并判斷Nc>Ncmax是否成立，若不成立則轉(zhuǎn)入步驟⑨，否則轉(zhuǎn)入步驟⑩。⑨Nc=Nc+1，同時返回步驟③。⑩輸出收斂路徑，采用路徑優(yōu)化策略，得到最優(yōu)路徑，流程結(jié)束。

圖2 DOACO算法流程圖Fig.2 Flow chart of DOACO algorithm

2.2 偽隨機概率轉(zhuǎn)移

本文設(shè)計一種新的概率轉(zhuǎn)移方法，通過引入偽隨機概率調(diào)整因子q0來調(diào)整概率轉(zhuǎn)移函數(shù)中對優(yōu)質(zhì)路徑點的選擇程度(式(4))，避免傳統(tǒng)蟻群算法中選擇優(yōu)質(zhì)路徑點的概率過低這一問題(式(5))。

(4)

(5)

τij——路徑點i和路徑點j之間的信息素濃度

ηij——當(dāng)前路徑點i到路徑點j的啟發(fā)式信息

ak——當(dāng)前路徑點i的下一個可行路徑點的集合

w——通過偽隨機概率轉(zhuǎn)移函數(shù)所獲得的路徑點

Roulette()——利用輪盤賭策略選取路徑點的函數(shù)

q——隨機數(shù)

q0通常為固定常數(shù)，當(dāng)q≤q0時，保留最優(yōu)鄰居路徑點。當(dāng)q>q0時，利用傳統(tǒng)概率轉(zhuǎn)移方法和輪盤賭策略獲得路徑點。

在傳統(tǒng)概率轉(zhuǎn)移函數(shù)中，假設(shè)某優(yōu)質(zhì)路徑點被選擇的概率為p，此時引入偽隨機轉(zhuǎn)移概率因子q0，根據(jù)式(5)，設(shè)偽隨機概率轉(zhuǎn)移函數(shù)對該優(yōu)質(zhì)路徑點的選擇概率為p1，則p1=q0+(1-q0)p，而p1-p=q0-pq0=q0(1-p)≥0，故p1≥p，即引入偽隨機概率調(diào)整因子后，新函數(shù)中優(yōu)質(zhì)路徑點被選擇的程度大于傳統(tǒng)概率轉(zhuǎn)移函數(shù)。在已知p的情況下，新函數(shù)對優(yōu)質(zhì)路徑點的選擇程度取決于q0，因此，通過引入偽隨機概率轉(zhuǎn)移因子q0來調(diào)整優(yōu)質(zhì)路徑點被選擇的概率可行。

(6)

式中dij——路徑點i和路徑點j之間的距離

針對傳統(tǒng)啟發(fā)式信息的問題，本文設(shè)計了新的啟發(fā)式信息函數(shù)，充分考慮下一節(jié)點到目標點的關(guān)系，強化啟發(fā)式信息的引導(dǎo)作用，計算式為

(7)

式中djg——路徑點j和目標點g之間的距離

在迭代前期，信息素對蟻群的引導(dǎo)作用較弱，啟發(fā)式信息應(yīng)發(fā)揮主導(dǎo)作用。此時信息素因子應(yīng)較小，啟發(fā)式因子應(yīng)較大，強化啟發(fā)式信息的主導(dǎo)作用。隨著迭代次數(shù)的增加，各路徑段上的信息素差異逐漸增大，信息素逐漸發(fā)揮主導(dǎo)作用。此時信息素因子逐漸增大，啟發(fā)式因子逐漸減小，這樣可以強化信息素的主導(dǎo)作用?；谏鲜龇治?，本文設(shè)計了自適應(yīng)信息素因子α1、自適應(yīng)啟發(fā)式因子β1,以加快算法的收斂速度，計算式為

α1=[(Ncmax+Nc)/Ncmax]α

(8)

(9)

2.3 信息素初始化及更新

信息素初始化主要有兩種方式：均勻分布和不均勻分布。初始信息素的不均勻分布[19-20]使算法有傾向性的快速收斂于某一條路徑，當(dāng)應(yīng)對復(fù)雜地圖環(huán)境時極易導(dǎo)致算法陷入局部最優(yōu)解。而信息素均勻分布可以擴大算法對解空間的搜索范圍，增強算法的種群多樣性，降低算法陷入局部最優(yōu)解的概率。因此本文采用初始信息素均勻分布的方法。

在信息素更新方面，DOACO僅考慮對每條路徑上的信息素進行單次更新，不考慮二次更新[21-22]。信息素更新過程為

τij(t+1)=(1-ρ)τij(t)+Δτij(ρ∈(0,1))

(10)

其中

(11)

(12)

式中 Δτij——路徑段(i,j)上的信息素增量

Lk——第k只螞蟻所經(jīng)過的路徑長度

2.4 死鎖問題處理策略

采取回溯機制和路徑長度清零機制相結(jié)合的方法來解決蟻群算法的死鎖問題[23]。假設(shè)當(dāng)前螞蟻行進到了第n個路徑點且螞蟻在第n個路徑點處陷入死鎖狀態(tài)。則執(zhí)行該方法流程如下：①令i=n。②將第i個路徑點和第i-1個路徑點之間的路徑標記為不可行狀態(tài)(即路徑長度清零機制)。③螞蟻返回到第i-1個路徑點(即回溯機制)，即i=i-1。④判斷螞蟻當(dāng)前所在路徑點是否陷入死鎖現(xiàn)象。如果螞蟻當(dāng)前所在路徑點陷入了死鎖現(xiàn)象，則轉(zhuǎn)入步驟②。如果螞蟻當(dāng)前所在路徑點沒有陷入死鎖現(xiàn)象，則流程結(jié)束。螞蟻根據(jù)概率轉(zhuǎn)移函數(shù)選擇下一個路徑點。

該方法通過回溯并將路徑長度清零重新調(diào)整螞蟻尋路方向保證螞蟻百分之百的存活率，提高螞蟻對解空間的探索能力。

2.5 路徑優(yōu)化策略

DOACO算法在收斂路徑的基礎(chǔ)上對收斂路徑進行了二次優(yōu)化，從而進一步提高收斂路徑的質(zhì)量，路徑優(yōu)化策略如下：

(1)定義關(guān)鍵路徑點的概念并找到一條收斂路徑中關(guān)鍵路徑點的集合。關(guān)鍵路徑點是指可以支撐起一條路徑中某一個路徑段的核心路徑點。包括：起點、目標點、特殊的路徑點(多為路徑轉(zhuǎn)折處及障礙物附近的路徑點)。

(2)利用啟發(fā)式策略設(shè)計連接操作符。啟發(fā)式策略是尋找當(dāng)前路徑點附近的距離目標點最近的相鄰路徑點。連接操作符是指利用啟發(fā)式策略生成兩個路徑點之間的路徑段的操作。

(3)利用連接操作符生成兩個相鄰關(guān)鍵路徑點之間的新的路徑段。

(4)若兩個關(guān)鍵路徑點之間的新的路徑段比之前的路徑段好，則用新的路徑段取代舊的路徑段。若兩個關(guān)鍵路徑點之間新的路徑段比之前的路徑段差，則不作改變。

假設(shè)某條路徑中的第i個路徑點是關(guān)鍵路徑點，則該條路徑中的下一個關(guān)鍵路徑點的尋找方法如下：①令j=i，其中j為指針型變量，用作尋找關(guān)鍵路徑點。②令j=j+1。③如果第j個路徑點是終點，則第j個路徑點就是下一個關(guān)鍵路徑點，流程結(jié)束。否則，轉(zhuǎn)入步驟④。④如果第i個路徑點到第j個路徑點之間的連線不經(jīng)過障礙物柵格且第i個路徑點到第j+1個路徑點之間的連線經(jīng)過障礙物柵格，則第j個路徑點就是下一個關(guān)鍵路徑點，流程結(jié)束。否則，轉(zhuǎn)入步驟②。

本文使用二維柵格地圖中的碰撞檢測模型[24]來檢測兩個路徑點之間的連線是否與障礙物柵格發(fā)生碰撞。

3 動態(tài)避障

針對傳統(tǒng)避障策略存在的避障能力較差且實時性不足的問題[25-26]，本文利用避障行為中的等待策略，并結(jié)合局部路徑重規(guī)劃的方法來進行動態(tài)避障。局部路徑重規(guī)劃方法是指當(dāng)預(yù)測到移動機器人和動態(tài)障礙物即將碰撞時，利用啟發(fā)式策略重新生成碰撞處的局部路徑段的方法，該方法僅對全局路徑進行小幅度調(diào)整。因此局部路徑重規(guī)劃方法具有避障代價小、避障實時性強、路徑質(zhì)量高的優(yōu)點。

3.1 碰撞類型

按照不同的碰撞方式將碰撞類型分為正面碰撞、側(cè)面碰撞以及障礙物停留在全局路徑上的靜態(tài)碰撞。其中，正面碰撞又分為接觸式正面碰撞和非接觸式正面碰撞。正面碰撞是指移動機器人與動態(tài)障礙物因運動方向共線且相反而產(chǎn)生的面對面碰撞的情況。假設(shè)移動機器人當(dāng)前位置為ri(rix,riy)，移動機器人下一個位置為ri+1(ri+1x,ri+1y)。動態(tài)障礙物當(dāng)前位置為oi(oix,oiy)，動態(tài)障礙物下一個位置為oi+1(oi+1x,oi+1y)。

若移動機器人與動態(tài)障礙物發(fā)生正面碰撞時有公共碰撞點，則這種碰撞情況被稱為非接觸式正面碰撞(圖3a)。即

圖3 碰撞類型示意圖Fig.3 Schematic of collision types

(13)

若移動機器人與動態(tài)障礙物發(fā)生正面碰撞時沒有公共碰撞點，即移動機器人與動態(tài)障礙物的下一步互為行進柵格。在這種情況下雖無碰撞點但兩者也會發(fā)生碰撞，這時判斷這種碰撞情況為接觸式正面碰撞(圖3b)。即

(14)

側(cè)面碰撞是指移動機器人與動態(tài)障礙物運動方向不共線，但在某一時刻兩者恰好產(chǎn)生公共碰撞點的情況(圖3c)。即

(15)

障礙物停留在全局路徑上的靜態(tài)碰撞是指動態(tài)障礙物由于某種原因恰好停留在了全局路徑上，導(dǎo)致移動機器人與障礙物必定會發(fā)生碰撞的情況。即

(16)

3.2 避障策略

本文提出的動態(tài)避障策略包含兩種避障策略：原地等待策略和局部路徑重規(guī)劃策略。針對側(cè)面碰撞，采取等待策略來避免碰撞的發(fā)生。即在側(cè)面碰撞發(fā)生前，移動機器人原地暫停，等待動態(tài)障礙物通過后移動機器人再繼續(xù)前進。

針對接觸式正面碰撞、非接觸式正面碰撞及障礙物停留在全局路徑上的靜態(tài)碰撞，采取局部路徑重規(guī)劃策略來避免碰撞的發(fā)生。假設(shè)移動機器人位于全局路徑的第i個路徑點，則把預(yù)測的公共碰撞點視為靜態(tài)障礙物并利用啟發(fā)式策略重新規(guī)劃第i個路徑點到第i+2個路徑點之間的局部路徑。當(dāng)移動機器人沿著局部路徑避過障礙物后，移動機器人將會重新返回全局路徑。

4 仿真實驗

4.1 仿真設(shè)計

為了驗證DOACO算法的性能，本文將DOACO算法、ACO算法、IACO算法[16]分別運行在人工仿真的20×20柵格地圖與自然環(huán)境仿真圖書館的50×50柵格地圖下進行比較。20×20柵格地圖環(huán)境為人為設(shè)置，而50×50柵格地圖以真實圖書館環(huán)境為原型設(shè)置。評價指標包括：路徑生成、路徑長度、算法收斂所需的迭代次數(shù)、算法收斂所需的程序運行時間、螞蟻存活率等。另外，通過在上述自然仿真的50×50地圖中增加不同時間、不同方向出發(fā)的動態(tài)障礙物模擬圖書館中的學(xué)生來驗證動態(tài)避障策略的有效性。

4.2 人工仿真實驗

人工仿真實驗使用20×20的柵格地圖(圖1)，單位柵格長度設(shè)為1 m，移動機器人從1號柵格進入，從400號柵格離開。蟻群算法初始參數(shù)如表1所示。

表1 蟻群算法初始參數(shù)Tab.1 Parameters of ant colony algorithm

4.2.1路徑生成

圖4為ACO算法和IACO算法的機器人運動軌跡圖。從圖4a可看出，ACO算法生成路徑的質(zhì)量明顯較差，而IACO算法生成的路徑(圖4b)質(zhì)量有了一定的提高。圖5為未添加優(yōu)化策略的DOACO算法和添加優(yōu)化策略的DOACO算法的機器人運動軌跡圖。從圖5a可看出，未添加優(yōu)化策略的DOACO算法由于改進了啟發(fā)信息等以及使用精英保存策略，生成路徑的質(zhì)量明顯提高，但是該路徑仍有進一步優(yōu)化的空間。從圖5b可看出，添加優(yōu)化策略的DOACO算法生成路徑的質(zhì)量最好。實驗結(jié)果表明，DOACO算法生成的路徑明顯優(yōu)于ACO算法和IACO算法。

圖4 機器人運動軌跡圖Fig.4 Robot motion trajectory diagrams

圖5 DOACO算法的機器人運動軌跡圖Fig.5 Robot motion trajectory diagrams of DOACO algorithm

4.2.2收斂曲線分析

圖6為3種算法的收斂曲線。從圖6可看出ACO算法在108代收斂，收斂后的最優(yōu)路徑長度為37.8 m。IACO算法在41代收斂，收斂后的最優(yōu)路徑長度為37.56 m，該算法采用改進信息素的初始分布，因此收斂次數(shù)減少。而DOACO算法在15代就已經(jīng)收斂，收斂后的最優(yōu)路徑長度為34.38 m。從收斂路徑長度和收斂迭代次數(shù)來看，DOACO算法優(yōu)于ACO算法和IACO算法，這主要是由于DOACO采用了路徑優(yōu)化策略以及改進的概率轉(zhuǎn)移函數(shù)。此外，從圖6中還可以發(fā)現(xiàn)，ACO算法和IACO算法均存在數(shù)據(jù)回落現(xiàn)象，而DOACO算法由于采用了精英保存策略，有效避免了數(shù)據(jù)回落現(xiàn)象。

圖6 3種算法收斂曲線Fig.6 Comparison of convergence curves of three algorithms

4.2.3螞蟻存活率分析

3種算法的螞蟻存活率變化曲線如圖7所示。從圖7可以看出，在100代之前，隨著迭代次數(shù)的增加，ACO算法的螞蟻存活率呈逐漸上升趨勢。在100代之后，ACO算法的螞蟻存活率會有波動，但是總體上穩(wěn)定。IACO算法則是在93代之前，隨著迭代次數(shù)的增加，螞蟻的存活率逐漸上升。到了93代之后，螞蟻存活率達到1。這說明IACO算法的死鎖懲罰因子起到了一定的效果。但是在算法迭代初期的時候，螞蟻存活率依舊較低。而DOACO算法通過回溯機制保證了螞蟻可以存活，路徑長度清零機制引導(dǎo)螞蟻調(diào)整前進方向跳離死鎖，使螞蟻存活率始終保持為1，從而有效解決死鎖問題。

圖7 3種算法螞蟻存活率變化曲線Fig.7 Comparison of ant survival rate changes of three algorithms

4.2.4綜合對比

在20×20柵格地圖的仿真環(huán)境下，本文將每種算法各仿真20次取平均值，結(jié)果如表2所示。從表2可以看出，DOACO算法在平均路徑長度、平均收斂迭代次數(shù)、平均算法收斂時間這3個性能指標上均優(yōu)于ACO算法和IACO算法。算法收斂時間計算式為

表2 3種算法仿真結(jié)果Tab.2 Simulation results of three algorithms

(17)

式中T——整個程序的運行時間

Nc1——算法收斂時的迭代次數(shù)

t——算法收斂時的程序運行時間(即算法收斂時間)

本文將算法收斂時間作為衡量蟻群算法的時間尺度。如表2所示，在路徑長度方面，DOACO算法得到的路徑長度約為IACO算法的92.03%，ACO算法的91.40%，對路徑長度有一定的縮減。在收斂迭代次數(shù)方面，DOACO算法收斂所用的迭代次數(shù)約為IACO算法的25.06%，ACO算法的16.45%，收斂次數(shù)大幅度減少，同時也使得平均算法收斂時間大大縮短，充分體現(xiàn)了DOACO算法的優(yōu)越性。

4.3 自然環(huán)境仿真實驗

自然仿真環(huán)境參照我校圖書館，實景圖如圖8a所示，圖書館面積為30 m×30 m，將整個地圖劃分為50×50柵格模型，每個柵格的實際面積為0.6 m×0.6 m。圖8b為參考實際場景建立的地圖模型，其中黑色障礙物代表圖書館中的墻壁、書架和桌子等不可行區(qū)域，紅色障礙物代表圖書館中移動的行人。移動機器人從25號柵格進入，從2 449號柵格離開。蟻群算法的參數(shù)設(shè)計如表3所示。

表3 蟻群算法參數(shù)設(shè)計Tab.3 Parameters of ant colony algorithm

圖8 圖書館實景與仿真環(huán)境Fig.8 Library real scene and simulation environment

4.3.1路徑生成

圖9為ACO算法和IACO算法在圖書館自然仿真環(huán)境下的機器人運動軌跡圖。從圖9a可以看出，ACO算法生成路徑的質(zhì)量明顯較差。IACO算法生成路徑(圖9b)的質(zhì)量甚至不如ACO算法。這充分說明在路徑生成方面IACO算法并不適用于圖書館這類大規(guī)模多障礙物地圖。圖10為未添加優(yōu)化策略的DOACO算法和添加優(yōu)化策略的DOACO算法在圖書館地圖下的機器人運動軌跡圖。從圖10a可以看出，未添加優(yōu)化策略的DOACO算法生成路徑的質(zhì)量明顯更好些，但是該路徑仍有進一步優(yōu)化的空間。從圖10b可以看出，添加優(yōu)化策略的DOACO算法生成路徑的質(zhì)量最優(yōu)。實驗結(jié)果所示，DOACO算法生成的路徑明顯優(yōu)于ACO算法和IACO算法。

圖9 圖書館地圖下的機器人運動軌跡Fig.9 Robot motion trajectory diagram in library map

圖10 DOACO算法在圖書館地圖下的機器人運動軌跡Fig.10 Robot motion trajectory diagram of DOACO algorithm in library map

4.3.2收斂曲線分析

圖11為3種算法收斂曲線。從圖11可以看出，ACO算法在461代收斂，收斂后的最優(yōu)路徑長度為39.71 m。IACO算法在43代收斂，收斂后的最優(yōu)路徑長度為43.52 m。該算法主要通過改進信息素的初始分布使收斂次數(shù)減少，但同時也使算法更易陷入局部最優(yōu)解，導(dǎo)致最優(yōu)路徑長度甚至不如ACO算法。而DOACO算法在25代就已經(jīng)收斂，收斂后的最優(yōu)路徑長度為35.12 m。從收斂路徑長度和收斂迭代次數(shù)來看，在圖書館仿真場景中，DOACO算法比ACO算法和IACO算法性能更優(yōu)，充分展現(xiàn)了DOACO算法中路徑優(yōu)化策略以及改進的概率轉(zhuǎn)移方法的科學(xué)性。此外，從圖11中還可以發(fā)現(xiàn)ACO算法和IACO算法均存在數(shù)據(jù)回落現(xiàn)象，而DOACO算法由于采用了精英保存策略，有效避免了數(shù)據(jù)回落現(xiàn)象。

圖11 3種算法圖書館地圖收斂曲線對比Fig.11 Comparison of convergence curves of three algorithms in library map

4.3.3螞蟻存活率分析

3種算法在圖書館地圖下的螞蟻存活率變化曲線如圖12所示。從圖12可以看出，在388代之前，隨著迭代次數(shù)的增加，ACO算法的螞蟻存活率呈逐漸上升趨勢。在388代之后螞蟻存活率達到1并維持穩(wěn)定。文獻[16]提出的IACO算法則是在245代螞蟻存活率達到1。這說明IACO算法的死鎖懲罰因子起到了一定的效果。但是在算法迭代初期時，螞蟻存活率依舊較低。而本文提出的DOACO算法通過回溯機制保證了螞蟻可以存活，路徑長度清零機制引導(dǎo)螞蟻調(diào)整前進方向跳離死鎖，即使在實際場景較為復(fù)雜的地圖下也依然可以保證螞蟻的存活率始終為1，從而解決死鎖問題。

圖12 3種算法圖書館地圖螞蟻存活率對比Fig.12 Comparison of ant survival rate changes of three algorithms in library map

4.3.4綜合對比

在圖書館仿真環(huán)境下，將每種算法各仿真20次取平均值，結(jié)果如表4所示。由表可知，DOACO算法在平均路徑長度、平均收斂迭代次數(shù)、平均算法收斂時間這3個性能指標上均優(yōu)于ACO算法和IACO算法。在路徑長度方面，DOACO算法得到的路徑長度約為IACO算法的81.25%，ACO算法的88.71%，對路徑長度有了一定的縮減。在收斂迭代次數(shù)方面，DOACO算法收斂所用的迭代次數(shù)約為IACO算法的19.27%，ACO算法的5.23%。經(jīng)實驗驗證，在自然環(huán)境仿真地圖中DOACO算法的收斂次數(shù)大幅度減少，同時也使得平均算法收斂時間大大縮短，充分體現(xiàn)了DOACO算法的優(yōu)越性。

表4 3種算法圖書館地圖仿真結(jié)果Tab.4 Simulation results of three algorithms in library map

4.3.5動態(tài)避障

在基于圖書館地圖50×50柵格(30 m×30 m)的仿真環(huán)境中，本文在完成靜態(tài)全局路徑規(guī)劃的基礎(chǔ)上添加了動態(tài)障礙物。實驗共設(shè)置4個方向不同且出發(fā)時間不同的動態(tài)障礙物表示移動的行人，以此檢驗本文提出的避障策略的可行性和有效性。移動機器人動態(tài)避障的路徑軌跡如圖13所示。

圖13 圖書館仿真環(huán)境的動態(tài)避障軌跡圖Fig.13 Dynamic obstacle avoidance trajectory diagram in library simulation environment

圖13中動態(tài)障礙物1、2、3同時出發(fā)。動態(tài)障礙物行進速度均為每次一個單位長度。動態(tài)障礙物1由181號柵格向左行進，動態(tài)障礙物2由982號柵格向上行進，動態(tài)障礙物3由1 483號柵格向上行進。根據(jù)3.1節(jié)所述的碰撞類型檢測機制，動態(tài)障礙物1在向左行進的過程中會與移動機器人發(fā)生側(cè)面碰撞。碰撞點為178號柵格。根據(jù)3.2節(jié)的避障策略，移動機器人執(zhí)行等待行為。即當(dāng)移動機器人預(yù)測到碰撞后，移動機器人暫時停止行進，等待動態(tài)障礙物1通過后，移動機器人再繼續(xù)前進(圖13a)。

動態(tài)障礙物2、3在移動過程中分別與移動機器人發(fā)生非接觸式正面碰撞、靜態(tài)碰撞，碰撞點分別為482號柵格和1 033號柵格。根據(jù)3.2節(jié)的避障策略，移動機器人均執(zhí)行局部路徑重規(guī)劃策略。即當(dāng)移動機器人預(yù)測到碰撞后，重新規(guī)劃當(dāng)前路徑點到碰撞點之后的下一路徑點的路徑(圖13b、13c)。

動態(tài)障礙物4在移動機器人行進35步后開始運動，由2 444號柵格向上行進。當(dāng)移動機器人行進至1 944號柵格時剛好與動態(tài)障礙物4正面相遇。根據(jù)3.1節(jié)所述的碰撞類型檢測機制可以判斷兩者為接觸式正面碰撞，故無碰撞點。根據(jù)3.2節(jié)的避障策略，移動機器人采用局部路徑重新規(guī)劃來避開障礙物。即移動機器人重新規(guī)劃1 944號柵格到2 044號柵格之間的路徑。移動機器人再按照重新規(guī)劃的局部路徑繼續(xù)前進。避障完成后，移動機器人的運動軌跡如圖13d所示。

為了測試本文提出的避障策略的實時性，仿真程序統(tǒng)計了4次避障所用時間。4次避障時間依次為0.000 179、0.009 581、0.000 600、0.015 197 s。而在DOACO算法的基礎(chǔ)上用傳統(tǒng)的避障策略，4次避障的避障時間依次為18.597 6、14.834 3、7.409 0、0.778 40 s。由此可見，本文提出的避障策略的實時性方面具有較好的性能。

5 結(jié)束語

提出了能夠生成高質(zhì)量全局路徑的DOACO算法和適用于動態(tài)環(huán)境的避障策略，且適用于實際環(huán)境。首先，提出一種新的概率轉(zhuǎn)移函數(shù)優(yōu)化算法的收斂速度，解決蟻群算法收斂速度慢的問題。其次，采用精英保存策略并提出基于碰撞檢測的路徑優(yōu)化策略對收斂路徑再優(yōu)化，提高收斂路徑的質(zhì)量。此外，本文采用回溯機制和路徑長度清零機制相結(jié)合這一策略來解決蟻群算法的死鎖問題。最后，設(shè)計一種新的避障策略，移動機器人根據(jù)不同的碰撞類型采用不同的避障策略來躲避動態(tài)障礙物。新的避障策略可以有效地解決常規(guī)避障策略實時性不足等問題。仿真結(jié)果表明，DOACO算法在靜態(tài)和動態(tài)環(huán)境中均能生成可行有效的高質(zhì)量路徑，同時也能解決基本蟻群算法存在的問題。新的避障策略可以有效地應(yīng)對各種潛在的碰撞情況并且避障實時性強。