郝 琨 張慧杰 李志圣 劉永磊

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

0 引言

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

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

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

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

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

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

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

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

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

2 DOACO算法設(shè)計(jì)

2.1 DOACO算法

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

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

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

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

(4)

(5)

τij——路徑點(diǎn)i和路徑點(diǎn)j之間的信息素濃度

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

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

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

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

q——隨機(jī)數(shù)

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

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

(6)

式中dij——路徑點(diǎn)i和路徑點(diǎn)j之間的距離

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

(7)

式中djg——路徑點(diǎn)j和目標(biāo)點(diǎn)g之間的距離

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

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

(8)

(9)

2.3 信息素初始化及更新

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

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

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

(10)

其中

(11)

(12)

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

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

2.4 死鎖問題處理策略

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

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

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

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

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

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

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

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

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

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

3 動(dòng)態(tài)避障

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

3.1 碰撞類型

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

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

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

(13)

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

(14)

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

(15)

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

(16)

3.2 避障策略

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

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

4 仿真實(shí)驗(yàn)

4.1 仿真設(shè)計(jì)

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

4.2 人工仿真實(shí)驗(yàn)

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

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

4.2.1路徑生成

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

圖4 機(jī)器人運(yùn)動(dòng)軌跡圖Fig.4 Robot motion trajectory diagrams

圖5 DOACO算法的機(jī)器人運(yùn)動(dòng)軌跡圖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，該算法采用改進(jìn)信息素的初始分布，因此收斂次數(shù)減少。而DOACO算法在15代就已經(jīng)收斂，收斂后的最優(yōu)路徑長度為34.38 m。從收斂路徑長度和收斂迭代次數(shù)來看，DOACO算法優(yōu)于ACO算法和IACO算法，這主要是由于DOACO采用了路徑優(yōu)化策略以及改進(jìn)的概率轉(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算法的螞蟻存活率呈逐漸上升趨勢(shì)。在100代之后，ACO算法的螞蟻存活率會(huì)有波動(dòng)，但是總體上穩(wěn)定。IACO算法則是在93代之前，隨著迭代次數(shù)的增加，螞蟻的存活率逐漸上升。到了93代之后，螞蟻存活率達(dá)到1。這說明IACO算法的死鎖懲罰因子起到了一定的效果。但是在算法迭代初期的時(shí)候，螞蟻存活率依舊較低。而DOACO算法通過回溯機(jī)制保證了螞蟻可以存活，路徑長度清零機(jī)制引導(dǎo)螞蟻調(diào)整前進(jìn)方向跳離死鎖，使螞蟻存活率始終保持為1，從而有效解決死鎖問題。

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

4.2.4綜合對(duì)比

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

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

(17)

式中T——整個(gè)程序的運(yùn)行時(shí)間

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

t——算法收斂時(shí)的程序運(yùn)行時(shí)間(即算法收斂時(shí)間)

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

4.3 自然環(huán)境仿真實(shí)驗(yàn)

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

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

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

4.3.1路徑生成

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

圖9 圖書館地圖下的機(jī)器人運(yùn)動(dòng)軌跡Fig.9 Robot motion trajectory diagram in library map

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

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

4.3.3螞蟻存活率分析

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

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

4.3.4綜合對(duì)比

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

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

4.3.5動(dòng)態(tài)避障

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

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

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

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

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

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

5 結(jié)束語

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