胡立華，馬 瑞，張名師，左威健

(太原科技大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，太原 030024)

路徑規(guī)劃一直是智能機(jī)器領(lǐng)域的研究熱點(diǎn)，其任務(wù)就是在具有障礙物的復(fù)雜環(huán)境內(nèi)，依據(jù)耗能最少、路徑最優(yōu)、時(shí)間最短等評(píng)價(jià)標(biāo)準(zhǔn)，尋找一條從起始點(diǎn)到目標(biāo)點(diǎn)無(wú)碰撞的最優(yōu)路徑[1]。路徑規(guī)劃方法主要有傳統(tǒng)算法和智能算法兩種，相較于傳統(tǒng)算法，智能路徑規(guī)劃算法具有運(yùn)算速度快、總體效率高的優(yōu)點(diǎn)。經(jīng)典的智能路徑規(guī)劃方法有：人工神經(jīng)網(wǎng)絡(luò)算法[2]，遺傳算法[3]，粒子群算法[4]，蟻群算法[5]等，其中由意大利學(xué)者 Dorigo 等人提出的蟻群算法對(duì)路徑規(guī)劃具有良好的全局優(yōu)化能力，且在實(shí)際路徑搜索中能對(duì)外界做出動(dòng)態(tài)響應(yīng)。

基于蟻群算法的路徑規(guī)劃典型的工作有：游曉明等人[6]提出動(dòng)態(tài)搜索誘導(dǎo)算子，有效提高優(yōu)化解的質(zhì)量；屈鴻等人[7]通過(guò)調(diào)整轉(zhuǎn)移概率限定信息素強(qiáng)度的上下界，提高算法的全局搜索能力；汪杰君等人[8]提出了一種基于混合遺傳蟻群算法的測(cè)試路徑規(guī)劃方案，提高了測(cè)試模型轉(zhuǎn)化的效率；王志中[9]設(shè)置了信息素感應(yīng)閾值，擴(kuò)大了算法前期的搜索范圍；張成等人[10]引入障礙物排斥權(quán)重和新的啟發(fā)因子到路徑選擇概率中，提高避障能力,增加路徑選擇的多樣性；謝智慧等人[11]提出采用動(dòng)態(tài)調(diào)整啟發(fā)因子、改進(jìn)信息素初始化策略，提高了算法前期搜索效率等。但是在實(shí)際應(yīng)用過(guò)程中，針對(duì)環(huán)境復(fù)雜性、障礙物頻繁的智能小車路徑規(guī)劃仍存在收斂速度慢、工作效率低的缺點(diǎn)。

因此，本文以樹(shù)莓派智能小車為對(duì)象，針對(duì)智能小車行駛在障礙物頻繁的環(huán)境中路徑規(guī)劃收斂速度慢等問(wèn)題，提出了一種基于全局動(dòng)態(tài)路徑規(guī)劃的改進(jìn)蟻群算法。該方法首先采用不均勻分配初始信息素原則，避免經(jīng)典蟻群算法螞蟻?zhàn)呋芈返膯?wèn)題；其次修改路徑上啟發(fā)信息，為后續(xù)螞蟻的路徑選擇提供依據(jù)；然后優(yōu)化經(jīng)典蟻群算法中局部信息素和全局信息素的更新方式，加快路徑規(guī)劃算法的收斂速度；最后在經(jīng)典算法的轉(zhuǎn)移概率中增加鄰域安全因子避免死鎖，提高算法的優(yōu)化效率。

1 經(jīng)典蟻群算法

經(jīng)典蟻群算法的路徑規(guī)劃是模仿螞蟻覓食尋找最優(yōu)路徑的過(guò)程，具體流程如下：

1)初始化假設(shè)螞蟻數(shù)量為num及信息素；

2)螞蟻在柵格地圖中移動(dòng)，釋放定量的信息素q，稱為初始信息素；然后螞蟻根據(jù)啟發(fā)信息隨機(jī)選擇位置向目標(biāo)點(diǎn)移動(dòng)，啟發(fā)信息定義為：

其中：d(i,j)表示i與j點(diǎn)之間的歐氏距離。allowk表示當(dāng)前螞蟻k可以選擇的下一個(gè)目標(biāo)點(diǎn)的集合。

3)所有螞蟻完成一次迭代后對(duì)該路徑上殘余信息素進(jìn)行更新，則t+1時(shí)刻在路徑(i,j)上信息素更新為：

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

其中，ρ表示信息素的揮發(fā)系數(shù)，且ρ的取值范圍為(0，1)；τij(t)表示在t時(shí)刻路徑(i，j)上的信息素濃度。Q是一個(gè)定值表示信息素的總量，在一定程度上影響算法收斂速度；Lk表示本次循環(huán)中，螞蟻k所經(jīng)過(guò)的路徑的長(zhǎng)度。

4)狀態(tài)轉(zhuǎn)移概率公式如下：

其中，α為輸入的信息素啟發(fā)因子；β為期望啟發(fā)因子。

2 基于改進(jìn)蟻群算法的動(dòng)態(tài)路徑規(guī)劃

在目標(biāo)路徑規(guī)劃過(guò)程中，基于蟻群算法的智能小車路徑規(guī)劃過(guò)程主要分為兩個(gè)階段：1)環(huán)境建模：目的是建立一個(gè)便于計(jì)算機(jī)進(jìn)行路徑規(guī)劃所使用的環(huán)境模型；2)路徑規(guī)劃：在環(huán)境模型基礎(chǔ)上，迭代蟻群算法尋找一條目的路徑，且該路徑距離最短、耗時(shí)最少、效率最高。

2.1 環(huán)境建模

目前，進(jìn)行環(huán)境建模的方法主要有幾何法[12]、可視圖法[13]、單元分解法[14]和柵格法[15]等。其中柵格法搜索路徑唯一、操作簡(jiǎn)單、發(fā)現(xiàn)路徑能力強(qiáng)、便于更新維護(hù)，更適用于尋找智能小車的最優(yōu)路徑。

在環(huán)境構(gòu)建過(guò)程中，設(shè)初始化智能小車的工作空間為二維矩形平面區(qū)域，區(qū)域范圍為R(X,Y).在柵格圖中，柵格寬度的設(shè)置對(duì)構(gòu)建地圖及規(guī)劃路徑影響很大。針對(duì)智能小車，若柵格寬度過(guò)大，環(huán)境信息量小，算法運(yùn)行時(shí)間短，路徑規(guī)劃能力弱；若柵格寬度過(guò)小，環(huán)境信息量大，算法運(yùn)行時(shí)間長(zhǎng)，路徑規(guī)劃較強(qiáng)。因此，柵格的寬度大小若剛好能容納智能小車，更易模擬小車的路徑規(guī)劃。

設(shè)小車寬度為w，將工作環(huán)境區(qū)域R劃分成大小相等的n個(gè)柵格ri，對(duì)劃分好的每一個(gè)柵格ri按從左到右、從上到下的順序進(jìn)行編號(hào)，并建立相應(yīng)的無(wú)障礙區(qū)域的存儲(chǔ)表allow、障礙區(qū)域的禁忌表Tabu，如圖1所示，白色為無(wú)障礙柵格，黑色為障礙柵格。因?yàn)檎系K物形狀大小不一，所以當(dāng)有障礙區(qū)域所占據(jù)的柵格不滿一格時(shí)，則以占一個(gè)柵格處理。柵格ri每次移動(dòng)一個(gè)步長(zhǎng)(一個(gè)柵格為一個(gè)步長(zhǎng))，且移動(dòng)后的柵格rj為柵格ri中allow的柵格，如圖2所示。

圖1 環(huán)境地圖建模Fig.1 Map modeling

圖2 柵格ri的可行路線Fig.2 Possible routes for grid ri

2.2 改進(jìn)蟻群算法

2.2.1 初始信息素不均勻分配

圖3 初始信息素分配圖Fig.3 Initial pheromone distribution

L：Ax+By+C=0

(1)

虛擬路徑對(duì)螞蟻的全局行走方向具有指導(dǎo)作用。根據(jù)螞蟻所在柵格距虛擬路徑的距離對(duì)該柵格進(jìn)行信息素的分泌，分泌規(guī)則如下：

(2)

其中，q為信息素均勻分配的初始量，ij表示由柵格i移動(dòng)到j(luò)，(i，j)表示柵格i到柵格j之間的路徑，假設(shè)柵格j的坐標(biāo)為(xj,yj)，d為螞蟻在柵格j時(shí)的坐標(biāo)值到虛擬路徑的距離，根據(jù)距離d的大小來(lái)確定柵格i到柵格j的初始信息素的分配，則距離計(jì)算公式如下：

(3)

螞蟻的全局路徑規(guī)劃往往是一條從起始點(diǎn)到目標(biāo)點(diǎn)的非閉合路徑，因此改進(jìn)的初始信息素不均勻分配有利于提高算法的收斂速度。

2.2.2 調(diào)整距離啟發(fā)函數(shù)

啟發(fā)函數(shù)ηij(t)表示在t時(shí)刻i點(diǎn)相對(duì)于j點(diǎn)的可見(jiàn)度，兩點(diǎn)之間的距離越近，對(duì)螞蟻的下一個(gè)目標(biāo)點(diǎn)的選擇影響越大。然而，在經(jīng)典蟻群算法中相鄰柵格的啟發(fā)權(quán)值差異不明顯，算法的搜索效率比較低[16]，因此依據(jù)已知目標(biāo)點(diǎn)的位置，可對(duì)目標(biāo)點(diǎn)的鄰域柵格賦予不同的啟發(fā)權(quán)值，即按比例為1∶2∶2∶3∶3∶4∶4∶5進(jìn)行調(diào)整。調(diào)整后的啟發(fā)函數(shù)提高了搜索速度，加快了路徑選擇的準(zhǔn)確性。啟發(fā)函數(shù)可定義為：

(4)

其中，λ為啟發(fā)系數(shù)，col為所建立的柵格地圖的列數(shù)。

2.2.3 信息素的更新規(guī)則

為了保證高濃度信息素在較短路徑上，低濃度信息素在較長(zhǎng)路徑上，對(duì)信息素更新過(guò)程可修改為：假設(shè)螞蟻數(shù)量足夠多，上一次迭代過(guò)程中找到的最短路徑為L(zhǎng)h，下一次迭代過(guò)程中找到的路徑集為L(zhǎng)g，且與上一次最短路徑比較，如果有路徑比上一次的最短路徑短，則更新本次迭代中的最短路徑為最短路徑；如果沒(méi)有路徑比上一次的最短路徑短，則上一次的最短路徑仍為本次迭代的最短路徑。記經(jīng)揮發(fā)后殘余信息素系數(shù)為ζ，則有：

(5)

其中，Lc為當(dāng)前迭代路徑集Lg中的隨機(jī)一條路徑。則局部信息素的更新改進(jìn)為：

(6)

全局信息素的更新為：

(7)

不同路徑長(zhǎng)度信息素的殘余系數(shù)不同，信息素的更新數(shù)量也不同，在初始信息素的局部和全局更新的驅(qū)動(dòng)下，路徑越短，該路徑積累的信息素就越多，對(duì)后續(xù)螞蟻的路徑選擇具有很大的驅(qū)動(dòng)作用，提高了算法的收斂速度，避免螞蟻陷入局部最優(yōu)。

2.2.4 改進(jìn)轉(zhuǎn)移概率

在復(fù)雜的地形環(huán)境中障礙物過(guò)多，螞蟻遍歷鄰域柵格時(shí)會(huì)出現(xiàn)重復(fù)遍歷障礙物柵格，導(dǎo)致耗時(shí)長(zhǎng)，螞蟻陷入死鎖狀態(tài)，因此文獻(xiàn)[8]提出的死鎖時(shí)回退一步方法，有利于螞蟻減少在同一個(gè)區(qū)域內(nèi)陷入死鎖的概率，但是對(duì)于復(fù)雜環(huán)境頻繁回退情況增加了算法的搜索時(shí)間，降低了算法的效率。本文利用螞蟻的鄰域安全作為螞蟻概率轉(zhuǎn)移的重要因素，假設(shè)柵格j的鄰域?yàn)閚eighbourhood，障礙物柵格為barrier，以遍歷的柵格為traverse，則鄰域安全為Nsafety定義為：

增加鄰域安全因子后的狀態(tài)轉(zhuǎn)移概率為：

其中，ω為鄰域安全權(quán)值，迭代一定次數(shù)后盡管j點(diǎn)的鄰域已大多數(shù)遍歷或?yàn)檎系K物柵格，但在迭代未收斂之前，柵格仍為可通行的。

2.2.5 改進(jìn)后算法實(shí)現(xiàn)流程

步驟一：初始化：輸入智能小車的環(huán)境信息建立柵格地圖R，初始化allow表和tabu表,設(shè)置螞蟻的數(shù)量num，為最大迭代次數(shù)max，及參數(shù)值α、β、ω、ρ、ζ等。將螞蟻放在柵格地圖的起始位置start處，開(kāi)始蟻群算法的迭代。

步驟二：螞蟻在移動(dòng)過(guò)程中每搜到一個(gè)柵格點(diǎn)，就將該柵格點(diǎn)加入tabu表中，從表allow中刪除該柵格點(diǎn)，根據(jù)公式(1)-(3)對(duì)信息素進(jìn)行初始不均勻分配，在啟發(fā)函數(shù)公式(4)的作用下對(duì)路徑進(jìn)行選擇，完成一次路徑選擇后通過(guò)公式(5)-(7)對(duì)該路徑上的信息素進(jìn)行更新；然后記錄螞蟻從起始點(diǎn)走到終止點(diǎn)的路徑長(zhǎng)度。并選出當(dāng)前路徑中的最優(yōu)路徑，一次迭代完成。

步驟三：螞蟻再次迭代，根據(jù)改進(jìn)的狀態(tài)轉(zhuǎn)移概率公式(8)確定螞蟻從當(dāng)前點(diǎn)要移動(dòng)到的下一個(gè)目標(biāo)點(diǎn)，螞蟻每次移動(dòng)更新tabu表和allow表。

步驟四：螞蟻完成路徑選擇后，淘汰未到達(dá)目標(biāo)點(diǎn)的螞蟻，更新路徑上信息素濃度，記錄路徑長(zhǎng)度信息，找出最優(yōu)路徑，如果當(dāng)前最優(yōu)路徑優(yōu)于步驟二中的最優(yōu)路徑，則更新當(dāng)前路徑為最優(yōu)路徑，否則，步驟二中的路徑仍為最優(yōu)路徑，繼續(xù)迭代。

步驟五：設(shè)置迭代閾值θ，當(dāng)?shù)螖?shù)T<θ時(shí)，螞蟻的路徑長(zhǎng)度不在發(fā)生變化，則迭代收斂；當(dāng)θ

步驟六：保存最優(yōu)路徑信息，算法結(jié)束。

3 實(shí)驗(yàn)結(jié)果與分析

為了驗(yàn)證算法的有效性，本節(jié)模擬了不同規(guī)模和不同復(fù)雜度的環(huán)境地圖進(jìn)行了兩組仿真實(shí)驗(yàn)。第一組仿真實(shí)驗(yàn)在25*25的環(huán)境下，比較了對(duì)本文算法、文獻(xiàn)[17]的算法和經(jīng)典蟻群算法的路徑規(guī)劃結(jié)果；第二組仿真實(shí)驗(yàn)在30*30的環(huán)境下，采用本文算法和經(jīng)典一群算法進(jìn)行仿真結(jié)果比較。算法運(yùn)行環(huán)境為WINDOWS 10 64 bit；MATLAB R2016a；處理器i5-4210U CPU；內(nèi)存4 GB.仿真實(shí)驗(yàn)均使用Matlab語(yǔ)言。

3.1 仿真實(shí)驗(yàn)一

首先隨機(jī)建立規(guī)模為25*25環(huán)境地圖，表1為本文方法和文獻(xiàn)[17]算法、與經(jīng)典蟻群算法的參數(shù)設(shè)置。

表1 參數(shù)設(shè)置Tab.1 Parameter setting

然后對(duì)本文算法、經(jīng)典蟻群算法和文獻(xiàn)[17]中的算法進(jìn)行仿真實(shí)驗(yàn)，其中路徑規(guī)劃起始位置可設(shè)置為：起始點(diǎn)為圖4的左上角，終止點(diǎn)為圖4的右下角。共進(jìn)行100次實(shí)驗(yàn)得到的最優(yōu)路徑如圖4所示，路徑迭代收斂曲線圖如圖5所示。

圖4 路徑規(guī)劃結(jié)果對(duì)比圖Fig.4 The comparison of path planning results

圖5 算法收斂曲線對(duì)比圖Fig.5 The comparison of algorithm convergence curve

最后對(duì)三種算法的最優(yōu)路徑長(zhǎng)度、迭代收斂次數(shù)、拐點(diǎn)數(shù)、平均消耗時(shí)間進(jìn)行了對(duì)比。對(duì)比結(jié)果如圖4-圖5所示。

從圖4中可以看出，本文算法的最優(yōu)路徑最短，拐點(diǎn)最少；從圖5中可以看出，本文改進(jìn)算法的迭代次數(shù)最少，收斂速度更快，具體的路徑規(guī)劃結(jié)果如表2所示。

表2 實(shí)驗(yàn)結(jié)果對(duì)比Tab.2 The comparison of experimental results

從表2中可以看出：本文提出的改進(jìn)蟻群算法有效縮短了路徑搜索所需要的時(shí)間，并且找到了比經(jīng)典算法和文獻(xiàn)[17]更優(yōu)的路徑，從而驗(yàn)證了本文算法的有效性。

3.2 仿真實(shí)驗(yàn)二

第二組仿真實(shí)驗(yàn)，隨機(jī)建立規(guī)模為30*30環(huán)境地圖，設(shè)置本次實(shí)驗(yàn)算法中所需要的各個(gè)參數(shù)值如表3所示。

表3 參數(shù)設(shè)置Tab.3 Parameter setting

與仿真實(shí)驗(yàn)一采用相同的步驟進(jìn)行100次實(shí)驗(yàn)后找到的最短路徑和螞蟻的迭代次數(shù)如圖6-圖7所示。

圖6 路徑規(guī)劃結(jié)果圖Fig.6 The comparison of path planning results

圖7 算法迭代收斂曲線圖Fig.7 The comparison of algorithm convergence curve

從圖6中可以看出，本文改進(jìn)的蟻群算法的最優(yōu)路徑最短，拐點(diǎn)最少；從圖7中可以看出，本文改進(jìn)算法的迭代次數(shù)最少，收斂速度更快，具體的路徑規(guī)劃結(jié)果見(jiàn)表4.

表4 實(shí)驗(yàn)結(jié)果對(duì)比Tab.4 The comparison of experimental results

由表4可以看出：在起始點(diǎn)和終止點(diǎn)坐標(biāo)相同的情況下，改進(jìn)的蟻群算法最優(yōu)路徑短、平均消耗時(shí)間少、收斂速度快。

綜合3.1與3.2的結(jié)果，可知針對(duì)復(fù)雜環(huán)境下的路徑規(guī)劃，本文算法在迭代次數(shù)更少、收斂速度更快，所搜索路徑更穩(wěn)定。

4 結(jié)束語(yǔ)

本文針對(duì)基于經(jīng)典蟻群算法的路徑規(guī)劃收斂速度慢、消耗時(shí)間長(zhǎng)、易陷入局部最優(yōu)的問(wèn)題，提出了一種基于改進(jìn)蟻群算法的動(dòng)態(tài)路經(jīng)規(guī)劃方法。該方法首先對(duì)初始信息素進(jìn)行不均勻分配，避免經(jīng)典算法中走回路現(xiàn)象；其次優(yōu)化距離啟發(fā)函數(shù)，為后續(xù)螞蟻的路徑選擇提供依據(jù)；然后改進(jìn)信息素的更新方式，增加最優(yōu)路徑上的信息素濃度，加快算法的收斂速度；最后在改進(jìn)轉(zhuǎn)移概率中引入鄰域安全因子，避免螞蟻陷入死鎖。仿真實(shí)驗(yàn)驗(yàn)證了本文算法可有效提高智能小車的路徑規(guī)劃效率。但是，對(duì)于算法在不同參數(shù)、較大規(guī)模優(yōu)化問(wèn)題下的有效性驗(yàn)證，以及是否可以將本文改進(jìn)的蟻群算法應(yīng)用在更多的優(yōu)化問(wèn)題上將是論文的下一步工作。