基于改進蟻群算法的智能小車路徑規(guī)劃方法

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

(太原科技大學計算機科學與技術(shù)學院，太原 030024)

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

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

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

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

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

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

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

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

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

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

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

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

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

2 基于改進蟻群算法的動態(tài)路徑規(guī)劃

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

2.1 環(huán)境建模

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

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

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

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

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

2.2 改進蟻群算法

2.2.1 初始信息素不均勻分配

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

L：Ax+By+C=0

(1)

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

(2)

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

(3)

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

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

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

(4)

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

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

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

(5)

其中，Lc為當前迭代路徑集Lg中的隨機一條路徑。則局部信息素的更新改進為：

(6)

全局信息素的更新為：

(7)

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

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

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

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

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

2.2.5 改進后算法實現(xiàn)流程

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

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

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

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

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

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

3 實驗結(jié)果與分析

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

3.1 仿真實驗一

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

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

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

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

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

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

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

表2 實驗結(jié)果對比Tab.2 The comparison of experimental results

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

3.2 仿真實驗二

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

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

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

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

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

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

表4 實驗結(jié)果對比Tab.4 The comparison of experimental results

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

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

4 結(jié)束語

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