朱 艷，游曉明，劉 升，袁汪凰

1.上海工程技術(shù)大學(xué) 電子電氣工程學(xué)院，上海 201620

2.上海工程技術(shù)大學(xué) 管理學(xué)院，上海 201620

1 引言

機(jī)器人路徑規(guī)劃問題是機(jī)器人學(xué)的一個重要研究領(lǐng)域，它要求機(jī)器人依據(jù)一定的優(yōu)化原則（如能量消耗最小，行走路線最短，行走時間最快等等），在其運(yùn)動空間中找到一條從運(yùn)動起點(diǎn)到目標(biāo)點(diǎn)的最優(yōu)或者接近最優(yōu)的路徑，且此路徑能安全躲避障礙[1-2]。為了解決路徑規(guī)劃問題已經(jīng)出現(xiàn)大量的算法，如人工勢場法[3]、Dijkstra算法[3-5]、A*算法[6]等。近年來學(xué)者從自然界的一些現(xiàn)象中得到啟發(fā)，提出將遺傳算法[7-8]、粒子群算法[8]、蟻群算法等智能仿生算法應(yīng)用于機(jī)器人路徑規(guī)劃的研究。

在20世紀(jì)90年代，意大利學(xué)者Dorigo、Maniezzo和Colorni等人從生物進(jìn)化的機(jī)理中受到啟發(fā)，通過模擬自然界螞蟻尋食的行為，提出了蟻群優(yōu)化算法。盡管蟻群算法已經(jīng)可以較為成功地解決路徑規(guī)劃的問題，但是算法容易陷入局部最優(yōu)，無法得到全局最優(yōu)路徑，因此許多研究人員對其進(jìn)行深入分析，提出改進(jìn)的蟻群算法[9-10]，并且得到了廣泛的應(yīng)用。文獻(xiàn)[11]針對基本蟻群算法容易陷于局部最優(yōu)解這一問題，提出使用雙種群蟻群同時進(jìn)行搜索，在迭代過程中，若判斷出算法陷入可能局部最優(yōu)，則交換兩個種群對應(yīng)路徑上的信息素，并同時雙向動態(tài)自適應(yīng)調(diào)整信息素?fù)]發(fā)系數(shù)，雖然改進(jìn)的算法在一定程度上提高了搜索的全局性，但仍然存在收斂結(jié)果不穩(wěn)定的問題。文獻(xiàn)[12]通過改進(jìn)啟發(fā)函數(shù)ηij，避免單純使用導(dǎo)致螞蟻貪婪當(dāng)前最短路徑，不僅提高了算法跳出局部最優(yōu)的能力，也加快了算法的收斂速度，但改進(jìn)算法在路徑尋優(yōu)方面還有待改善。文獻(xiàn)[13]通過設(shè)定信息素初始值，改變信息素更新規(guī)則，引入最大最小信息素系統(tǒng)，對ACS算法易陷入局部最優(yōu)這一缺陷進(jìn)行改進(jìn)，解的質(zhì)量明顯提高，但仍存在尋優(yōu)過程中搜索時間較長的問題。以上改進(jìn)雖然都對算法易陷入局部最優(yōu)的問題有所改善，但仍存在算法搜索效率不高的問題，致使搜索時間較長。

針對蟻群算法搜索效率不高以及易陷入局部最優(yōu)的問題，本文在ACS算法的基礎(chǔ)上改進(jìn)了其啟發(fā)函數(shù)。為避免螞蟻貪圖局部最優(yōu)偏離行進(jìn)方向，在路徑的后程引入了目標(biāo)點(diǎn)的方向信息，啟發(fā)螞蟻以較大概率向目標(biāo)點(diǎn)移動，提高算法搜索效率，同時在螞蟻移動過程中動態(tài)調(diào)整權(quán)重系數(shù)，以改變目標(biāo)點(diǎn)的方向信息對螞蟻行動影響的大小。仿真結(jié)果表明，本文改進(jìn)算法是有效且可行的，通過改進(jìn)確實減少了算法的搜索時間，同時也在一定程度上提高了解的質(zhì)量。

2 相關(guān)工作

2.1 A*算法

A*算法采用的是遍歷搜索，它的核心在于利用啟發(fā)函數(shù)估計路徑中當(dāng)前節(jié)點(diǎn)到目標(biāo)點(diǎn)的代價，再從中選擇付出代價最小的下一節(jié)點(diǎn)，通過這一過程減少路徑搜索范圍，搜索效率明顯提高。這樣將搜索區(qū)域進(jìn)行簡化的方法，改善了搜索環(huán)境，降低了問題的復(fù)雜度。

其中，g(n)表示起點(diǎn)到當(dāng)前節(jié)點(diǎn)n的實際代價，h(n)表示當(dāng)前節(jié)點(diǎn)n到目標(biāo)點(diǎn)的估計代價，f(n)表示當(dāng)前節(jié)點(diǎn)n的估價函數(shù)，即起點(diǎn)經(jīng)過當(dāng)前節(jié)點(diǎn)n到達(dá)目標(biāo)點(diǎn)的最優(yōu)路徑的代價。

2.2 ACS算法

螞蟻系統(tǒng)（Ant System，AS）是第一個蟻群優(yōu)化算法（ACO），它是意大利學(xué)者Dorigo在1991年最先提出，并成功地用于求解著名的組合爆炸問題TSP問題，即旅行商問題。1996年，Gambardella與Dorigo等學(xué)者在Ant-Q算法的基礎(chǔ)上進(jìn)行改進(jìn)，提出蟻群系統(tǒng)（Ant Colony System，ACS）[13-14]。

在ACS算法中，螞蟻選擇下一個節(jié)點(diǎn)時采用了不同于AS算法的狀態(tài)轉(zhuǎn)移規(guī)則，即由參數(shù)q0控制的偽隨機(jī)比率規(guī)則。公式如下：

其中q0為給定常數(shù)，q0是[0，1]中符合均勻分布的隨機(jī)數(shù)，當(dāng)q≤q0時，選擇的下一節(jié)點(diǎn)為所有可行節(jié)點(diǎn)中值最大的節(jié)點(diǎn)；當(dāng)q＞q0時，V按照下面的概率轉(zhuǎn)移公式Pijk(t)選擇下一個節(jié)點(diǎn)：

其中，allowedk表示螞蟻k可以到達(dá)的節(jié)點(diǎn)；α為信息啟發(fā)式因子，表示軌跡的相對重要性，反映了路徑上積累的信息素對后續(xù)螞蟻選擇該路徑的影響程度，α越大就表示后續(xù)螞蟻選擇之前螞蟻?zhàn)哌^路徑的可能性越大；表示邊弧(i,j)的信息素濃度；β為期望啟發(fā)式因子，表示能見度的相對重要性，反映了啟發(fā)信息對螞蟻路徑選擇的影響程度，β越大就表示該狀態(tài)轉(zhuǎn)移概率越接近于貪心規(guī)則；ηij(t)為啟發(fā)函數(shù)，表示邊弧(i,j)的能見度，公式如下：

其中，dij表示節(jié)點(diǎn)i與節(jié)點(diǎn) j之間的距離。

在每只螞蟻?zhàn)咄暌徊交蛘咄瓿蓪λ泄?jié)點(diǎn)的搜索后，對螞蟻?zhàn)哌^路徑上的信息素及時更新以提高解的質(zhì)量和算法的收斂速度[15]。ACS算法中的局部更新用于每一時刻每只螞蟻的每一步移動之中，全局更新則是在所有的螞蟻都完成一個周期的搜索之后對最好的搜索結(jié)果進(jìn)行信息素濃度的更新。對局部和全局信息素的更新規(guī)則作如下說明：

（1）局部更新規(guī)則

每只螞蟻從某一節(jié)點(diǎn)i移動到下一節(jié)點(diǎn) j后，按照以下公式更新邊弧(i,j)上的信息素。局部更新規(guī)則的公式為：

（2）全局更新規(guī)則

在AS中，全局更新規(guī)則是對一次循環(huán)中所有螞蟻經(jīng)過的路徑進(jìn)行信息素更新，而在ACS中，所有螞蟻循環(huán)完成后才進(jìn)行全局信息素更新，且只更新當(dāng)前最優(yōu)路徑上的信息素。全局更新規(guī)則的公式：

其中，ρ為全局信息素?fù)]發(fā)系數(shù)，1-ρ為信息素殘留因子；Δτijk為本次循環(huán)中第k只螞蟻在路徑(i,j)上的信息素；Lgb為從路徑構(gòu)建開始到目前搜索到的全局最優(yōu)路徑的長度。

不僅需要算法收斂速度快，還需要算法不會過早收斂于局部最優(yōu)解，這也是目前算法的矛盾方面。近年來，國內(nèi)研究人員做了大量工作，以平衡算法解的多樣性和收斂速度之間的關(guān)系，算法的應(yīng)用范圍也越來越廣。在ACS算法中，啟發(fā)函數(shù)只是當(dāng)前節(jié)點(diǎn)到下一節(jié)點(diǎn)距離的倒數(shù)，導(dǎo)致螞蟻貪圖當(dāng)前最短路徑陷入局部最優(yōu)，而本文改進(jìn)算法的啟發(fā)函數(shù)中引入了A*算法估價函數(shù)的思想，將方向信息考慮到算法中，從而提高算法搜索效率。

3 改進(jìn)算法

3.1 改進(jìn)蟻群算法啟發(fā)函數(shù)

在路徑規(guī)劃過程中，蟻群算法因其啟發(fā)函數(shù)ηij(t)僅為當(dāng)前節(jié)點(diǎn)i與下一節(jié)點(diǎn) j距離的倒數(shù)，導(dǎo)致螞蟻因貪圖當(dāng)前最優(yōu)路徑而錯過全局最優(yōu)路徑。針對蟻群算法出現(xiàn)的問題，本文借鑒A*算法的估價函數(shù)，將當(dāng)前節(jié)點(diǎn)和目標(biāo)點(diǎn)的聯(lián)系引入到蟻群算法的啟發(fā)函數(shù)中，對距離進(jìn)行歸一化處理得到：

其中，gSi為起點(diǎn)S到下一節(jié)點(diǎn) j的實際距離；hjG為下一節(jié)點(diǎn) j到目標(biāo)點(diǎn)G的估計距離。將上述二者進(jìn)行歸一化處理得到gSi'和hjG'，從而使得蟻群算法的啟發(fā)函數(shù)變?yōu)椋?/p>

式中，dij是當(dāng)前節(jié)點(diǎn)i和下一節(jié)點(diǎn) j之間的距離；dSi是起點(diǎn)S和當(dāng)前節(jié)點(diǎn)i之間的距離；dSG是起點(diǎn)S和目標(biāo)點(diǎn)G之間的距離；ε為常數(shù)，它的值取決于dSG的大小。

將下一節(jié)點(diǎn) j和目標(biāo)點(diǎn)G的關(guān)系考慮到啟發(fā)函數(shù)中，使得螞蟻在搜索路徑過程中更具方向性，算法的搜索空間得以減少，從而有效提高搜索效率。但是螞蟻在移動過程中過早受到目標(biāo)點(diǎn)方向信息的影響，初始的搜索空間太小反而會導(dǎo)致算法陷入局部最優(yōu)。所以，在螞蟻構(gòu)建路徑的初始階段不引入方向信息，當(dāng)dSi的長度大于設(shè)定閾值ε后才引入目標(biāo)點(diǎn)的方向信息，加快算法收斂速度。

w為權(quán)值，公式如下：

其中，C為常數(shù)，w∈(0,1)。

在螞蟻構(gòu)建路徑的過程中，w的值會隨著下一節(jié)點(diǎn)到目標(biāo)點(diǎn)的距離進(jìn)行動態(tài)調(diào)整，即螞蟻在移動過程中越接近目標(biāo)點(diǎn)，受到的方向信息的影響越強(qiáng)，以提高算法搜索效率。

3.2 改進(jìn)算法流程

本文應(yīng)用于機(jī)器人路徑規(guī)劃問題的蟻群算法是在ACS算法的基礎(chǔ)上改進(jìn)而來，其偽代碼形式如下：

算法參數(shù)初始化：m、α、β、ρ、τ0、NC等，將m只螞蟻放置在起點(diǎn)S處。

forNC=1toNCmax

fork=1tom

初始化禁忌表；

將起點(diǎn)移動到禁忌表中；

判斷螞蟻k所有可行的下一節(jié)點(diǎn)是否已在禁忌表中；

while（存在可選下一節(jié)點(diǎn)螞蟻沒有走到終點(diǎn)）

根據(jù)A*算法的估價函數(shù)改進(jìn)而來的啟發(fā)函數(shù)公式（10），

然后依照公式（11）動態(tài)調(diào)整權(quán)值，螞蟻個體根據(jù)

公式（2）和概率轉(zhuǎn)移公式（3）按照概率

隨機(jī)選擇下一個節(jié)點(diǎn) j；

更新禁忌表；

end

if下一節(jié)點(diǎn) j是目標(biāo)節(jié)點(diǎn)

記錄此次迭代中每只螞蟻從起點(diǎn)S到

目標(biāo)點(diǎn)G經(jīng)過的路徑節(jié)點(diǎn)及其行走的路徑長度；

end

end

記錄此次迭代全局最優(yōu)路徑的路徑長度，

按照公式（6）和（7）進(jìn)行全局信息素更新；

按照公式（5）進(jìn)行局部信息素更新；

end

4 實驗結(jié)果及分析

為了驗證改進(jìn)蟻群算法的有效性，在MATLAB平臺上進(jìn)行了仿真實驗，比較ACS算法和本文改進(jìn)算法的仿真結(jié)果，并對仿真結(jié)果進(jìn)行了分析。在不同復(fù)雜程度的障礙物環(huán)境（20×20，30×30，50×50）中進(jìn)行仿真實驗，ACS算法和本文改進(jìn)算法的路徑規(guī)劃圖以及兩種算法的迭代圖，分別如圖1、圖2、圖3所示（障礙物圖中的路徑虛線代表ACS算法，實線代表本文算法）。

在ACS算法中，啟發(fā)函數(shù)只是當(dāng)前節(jié)點(diǎn)到下一節(jié)點(diǎn)距離的倒數(shù)，而本文改進(jìn)算法的啟發(fā)函數(shù)中引入了A*算法估價函數(shù)的思想，將當(dāng)前節(jié)點(diǎn)和目標(biāo)點(diǎn)的關(guān)系考慮到算法中，若在算法中過早引入方向信息，會使初始搜索空間太小從而導(dǎo)致算法陷入局部最優(yōu)，所以本文算法在路徑的后程引入目標(biāo)點(diǎn)的方向信息，同時螞蟻在移動過程中受到目標(biāo)點(diǎn)的方向信息影響，此影響的大小由權(quán)值w調(diào)整。本文改進(jìn)算法不僅使得螞蟻在構(gòu)建路徑過程中更具方向性，算法的搜索空間得以減少，還在一定程度上提高了解的質(zhì)量。

兩種算法參數(shù)設(shè)置如表1所示。

表1 參數(shù)設(shè)置

首先，本文算法選取不同的ε值在同一障礙物環(huán)境中進(jìn)行20次獨(dú)立實驗，選取的障礙物圖是圖1中的20×20障礙物環(huán)境，結(jié)果如表2所示。

表2 同一障礙物環(huán)境不同ε值的對比實驗

由表2可得，三者之中，ε=3/5dSG時得到的最小值、最大值及平均值都是最大的，在 ε=1/5dSG和ε=2/5dSG時，本文算法都得到了最優(yōu)路徑，而在ε=2/5dSG時，不但算法得到的平均值相比ε=1/5dSG時較小，得到的標(biāo)準(zhǔn)差也小于ε=1/5dSG時得到的標(biāo)準(zhǔn)差。綜上所述，本文算法選取的ε值為2/5dSG。

本文算法和ACS算法在三種復(fù)雜度的障礙物環(huán)境下的對比實驗如下所示。

圖1為兩種不同算法在20×20障礙物環(huán)境下的仿真結(jié)果。本文算法為了避免陷入局部最優(yōu)，在螞蟻構(gòu)建路徑的初始階段啟發(fā)函數(shù)中并沒有引入目標(biāo)點(diǎn)的方向信息，算法的搜索空間相對較大，在路徑的后程將目標(biāo)點(diǎn)的方向信息引用到啟發(fā)函數(shù)中，減小了算法的搜索空間，加強(qiáng)了螞蟻構(gòu)建路徑過程的方向性。因此，從以上仿真結(jié)果可以看出，本文改進(jìn)算法的收斂速度高于ACS算法，得到的全局最優(yōu)路徑質(zhì)量也明顯優(yōu)于ACS算法，這表明本文提出的算法是可行且有效的。

圖2為兩種不同算法在30×30障礙物環(huán)境下的仿真結(jié)果。ACS算法的啟發(fā)函數(shù)中沒有目標(biāo)點(diǎn)的方向信息，容易出現(xiàn)螞蟻貪圖當(dāng)前最優(yōu)路徑而陷入局部最優(yōu)的情況；相比ACS算法，在螞蟻所走路徑的后程，本文算法在啟發(fā)函數(shù)中通過加入了目標(biāo)點(diǎn)的方向信息來影響螞蟻對下一節(jié)點(diǎn)的選擇，這樣螞蟻的移動過程會更具方向性，而且算法的搜索效率也會提高。仿真結(jié)果表明，障礙物環(huán)境（30×30）比圖2（20×20）復(fù)雜后，ACS算法陷入了局部最優(yōu)，本文改進(jìn)算法的收斂速度快，并且得到的解的質(zhì)量也優(yōu)于ACS算法。

圖3為兩種不同算法在50×50障礙物環(huán)境下的仿真結(jié)果。仿真結(jié)果表明，在障礙物環(huán)境越為復(fù)雜時，本文改進(jìn)算法的優(yōu)勢依然明顯，螞蟻在構(gòu)建路徑過程考慮到目標(biāo)點(diǎn)的影響，移動過程更具方向性，算法的搜索空間小，所以本文算法收斂速度快，而且得到的解的質(zhì)量也優(yōu)于ACS算法。

圖1 障礙物環(huán)境20×20

圖2 障礙物環(huán)境30×30

圖3 障礙物環(huán)境50×50

對ACS算法和本文算法進(jìn)行對比實驗，在每個障礙物環(huán)境中運(yùn)行20次得到的實驗數(shù)據(jù)如表3所示。在簡單的障礙物環(huán)境中本文算法的提升空間不大。但是，當(dāng)障礙物環(huán)境復(fù)雜程度提高時，相比ACS算法，本文算法用更少的迭代次數(shù)得到了較好的最優(yōu)路徑，這表明本文算法不僅加快了收斂速度，還能在一定程度上提升解的質(zhì)量。

表3 算法對比

5 結(jié)束語

傳統(tǒng)蟻群算法在機(jī)器人路徑規(guī)劃中存在搜索時間較長，容易陷入局部最優(yōu)等問題，針對這些問題，本文改進(jìn)了ACS算法的啟發(fā)函數(shù)，路徑搜索初始階段不引入目標(biāo)點(diǎn)的方向信息；后續(xù)階段引入目標(biāo)點(diǎn)的方向信息，并根據(jù)下一節(jié)點(diǎn)到目標(biāo)點(diǎn)的距離動態(tài)調(diào)整權(quán)值大小。實驗表明，本文改進(jìn)算法不僅提高了搜索效率，加快了收斂速度，還可以在一定程度上提高解的質(zhì)量。針對特殊的障礙物環(huán)境（如終點(diǎn)處存在凹形障礙物時），本文算法權(quán)重參數(shù)的調(diào)整及閾值ε的選取還存在不足之處，后續(xù)工作將對其理論模型進(jìn)行研究及完善。