基于改進避障策略和雙優(yōu)化蟻群算法的機器人路徑規(guī)劃

郝 琨 張慧杰 李志圣 劉永磊

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

0 引言

隨著科技的發(fā)展，移動機器人已經(jīng)被廣泛應(yīng)用于地面自主導航[1]、水下環(huán)境勘探[2]、應(yīng)急信息采集[3]等領(lǐng)域中。路徑規(guī)劃技術(shù)是實現(xiàn)移動機器人智能化的關(guān)鍵技術(shù)之一，它是指移動機器人根據(jù)一種或多種性能指標，在復雜的空間環(huán)境中，尋找一條從起點到終點且沒有碰撞的最優(yōu)或次優(yōu)路徑[4-5]。目前移動機器人路徑規(guī)劃的主流算法分為兩大類：傳統(tǒng)算法與仿生學智能算法。其中，傳統(tǒng)算法主要有A*算法、人工勢場法等。智能算法主要有遺傳算法、蟻群算法、粒子群算法、免疫算法等[6-8]。傳統(tǒng)算法在簡單的地圖環(huán)境中性能較好，但不適用于復雜的地圖環(huán)境中。而智能仿生學算法則存在過早收斂、易陷入局部極值等問題[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]提出了一種改進雙層蟻群算法，將蟻群劃分為引導層蟻群和普通層蟻群以應(yīng)對不同的情況。然而，該算法將引導層蟻群與普通蟻群并行進行使引導層蟻群并未起到相應(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，當前迭代次數(shù)Nc，蟻群中螞蟻的總數(shù)量K，當前螞蟻數(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)到步驟⑧。⑧判斷該螞蟻是否為當前迭代次數(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——當前路徑點i到路徑點j的啟發(fā)式信息

ak——當前路徑點i的下一個可行路徑點的集合

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

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

q——隨機數(shù)

q0通常為固定常數(shù)，當q≤q0時，保留最優(yōu)鄰居路徑點。當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ā)式信息的引導作用，計算式為

(7)

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

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

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

(8)

(9)

2.3 信息素初始化及更新

信息素初始化主要有兩種方式：均勻分布和不均勻分布。初始信息素的不均勻分布[19-20]使算法有傾向性的快速收斂于某一條路徑，當應(yīng)對復雜地圖環(huán)境時極易導致算法陷入局部最優(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è)當前螞蟻行進到了第n個路徑點且螞蟻在第n個路徑點處陷入死鎖狀態(tài)。則執(zhí)行該方法流程如下：①令i=n。②將第i個路徑點和第i-1個路徑點之間的路徑標記為不可行狀態(tài)(即路徑長度清零機制)。③螞蟻返回到第i-1個路徑點(即回溯機制)，即i=i-1。④判斷螞蟻當前所在路徑點是否陷入死鎖現(xiàn)象。如果螞蟻當前所在路徑點陷入了死鎖現(xiàn)象，則轉(zhuǎn)入步驟②。如果螞蟻當前所在路徑點沒有陷入死鎖現(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ā)式策略是尋找當前路徑點附近的距離目標點最近的相鄰路徑點。連接操作符是指利用啟發(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ī)劃方法是指當預(yù)測到移動機器人和動態(tài)障礙物即將碰撞時，利用啟發(fā)式策略重新生成碰撞處的局部路徑段的方法，該方法僅對全局路徑進行小幅度調(diào)整。因此局部路徑重規(guī)劃方法具有避障代價小、避障實時性強、路徑質(zhì)量高的優(yōu)點。

3.1 碰撞類型

按照不同的碰撞方式將碰撞類型分為正面碰撞、側(cè)面碰撞以及障礙物停留在全局路徑上的靜態(tài)碰撞。其中，正面碰撞又分為接觸式正面碰撞和非接觸式正面碰撞。正面碰撞是指移動機器人與動態(tài)障礙物因運動方向共線且相反而產(chǎn)生的面對面碰撞的情況。假設(shè)移動機器人當前位置為ri(rix,riy)，移動機器人下一個位置為ri+1(ri+1x,ri+1y)。動態(tài)障礙物當前位置為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)障礙物由于某種原因恰好停留在了全局路徑上，導致移動機器人與障礙物必定會發(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個路徑點之間的局部路徑。當移動機器人沿著局部路徑避過障礙物后，移動機器人將會重新返回全局路徑。

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)障礙物模擬圖書館中的學生來驗證動態(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算法通過回溯機制保證了螞蟻可以存活，路徑長度清零機制引導螞蟻調(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)解，導致最優(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)移方法的科學性。此外，從圖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算法通過回溯機制保證了螞蟻可以存活，路徑長度清零機制引導螞蟻調(diào)整前進方向跳離死鎖，即使在實際場景較為復雜的地圖下也依然可以保證螞蟻的存活率始終為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í)行等待行為。即當移動機器人預(yù)測到碰撞后，移動機器人暫時停止行進，等待動態(tài)障礙物1通過后，移動機器人再繼續(xù)前進(圖13a)。

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

動態(tài)障礙物4在移動機器人行進35步后開始運動，由2 444號柵格向上行進。當移動機器人行進至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)對各種潛在的碰撞情況并且避障實時性強。