張 強(qiáng) 陳兵奎 劉小雍 劉曉宇 楊 航

(1.遵義師范學(xué)院工學(xué)院， 遵義 563006； 2.重慶大學(xué)機(jī)械傳動國家重點實驗室， 重慶 400044)

0 引言

路徑規(guī)劃是移動機(jī)器人研究領(lǐng)域的一個重要課題，是機(jī)器人完成各種自主移動任務(wù)的關(guān)鍵環(huán)節(jié)之一。根據(jù)對環(huán)境信息的掌握程度，可將路徑規(guī)劃分為兩大類：基于環(huán)境信息已知的全局路徑規(guī)劃和基于環(huán)境信息未知或局部已知的局部路徑規(guī)劃[1]。目前，用于全局路徑規(guī)劃的算法主要有人工勢場法[2-3]、A*算法[4-5]、粒子群算法[6-7]、蟻群算法[8-9]、遺傳算法[10]以及神經(jīng)網(wǎng)絡(luò)算法[11]等。人工勢場算法是基于數(shù)學(xué)模型的傳統(tǒng)方法，其原理簡單、計算量小，但應(yīng)用于復(fù)雜環(huán)境時，容易陷入局部最優(yōu)或出現(xiàn)死鎖現(xiàn)象。其他智能算法在使用時大都存在計算量大、收斂速度慢、參數(shù)不易確定、易于陷入局部最優(yōu)等問題。近年來又出現(xiàn)了許多改進(jìn)型算法[12-15]和混合型算法[16-20]。其中，勢場蟻群算法就是在綜合人工勢場算法和蟻群算法各自優(yōu)點的基礎(chǔ)上產(chǎn)生的一種混合算法。

相比蟻群算法，勢場蟻群算法具有更好的收斂性和全局尋優(yōu)特性，部分學(xué)者對其進(jìn)行了相關(guān)研究[21-23]。然而，由于人工勢場算法本身存在的缺陷以及蟻群算法迭代時存在計算量大等問題，導(dǎo)致勢場蟻群算法在迭代過程中耗時長、收斂緩慢以及解的最優(yōu)性較差。

基于此，本文提出一種改進(jìn)的勢場蟻群算法。該算法先對傳統(tǒng)的人工勢場算法進(jìn)行改進(jìn)，利用障礙物的邊界條件替代原有的斥力場函數(shù)，使路徑可緊貼障礙物的同時避免死鎖現(xiàn)象；迭代過程中通過搜尋有效障礙物和路徑中間點，逐一進(jìn)行局部路段的規(guī)劃，以減少對無效障礙物的冗余計算，從而有效縮減算法的計算量。再以改進(jìn)人工勢場算法的規(guī)劃結(jié)果重構(gòu)蟻群算法的啟發(fā)信息，用以避免算法初期由于蟻群盲目搜索導(dǎo)致的收斂速度慢等問題；在迭代過程中利用收斂次數(shù)構(gòu)建負(fù)反饋通道，使全局和局部信息素的更新速率可自適應(yīng)調(diào)節(jié)，以協(xié)調(diào)收斂速度與全局搜索能力之間的固有矛盾。

1 基于柵格法的環(huán)境建模

柵格法是移動機(jī)器人環(huán)境建模中一種常用的方法[18,23-25]，其基本原理是利用棋盤的思想將機(jī)器人的移動空間離散化為若干個柵格，并根據(jù)柵格的可通過性將其分為自由柵格和障礙物柵格。對于障礙物而言，目前主要的柵格化方法有腐蝕法和膨脹法兩種[26]，不同算法所得到的障礙物柵格存在較大的差別，如圖1所示。

圖1 障礙物的柵格化Fig.1 Grid processing of obstacle

設(shè)機(jī)器人可移動的平面矩形范圍為l×h，其中起點為原點(0,0)，目標(biāo)點為矩形中的對角點(l,h)，取正方形柵格尺寸為a×a，則長寬方向上的柵格數(shù)分別為

(1)

式中Nh——寬度方向上的柵格數(shù)目

Nl——長度方向上的柵格數(shù)目

ceil——向上取整函數(shù)

根據(jù)每個柵格所在行和列的編號生成相應(yīng)的坐標(biāo)(x,y)，取左下角柵格的坐標(biāo)為(0,0)。由于自由柵格在遍歷過程中需要被遍歷，而障礙物的柵格在遍歷過程中無法被遍歷，因此對每個柵格設(shè)定一個屬性值γ(x,y)，取值如下

(2)

圖2 兩種仿真示例環(huán)境Fig.2 Two example environments for simulation

為考查本文算法對不同環(huán)境的適用性，在Matlab中建立如圖2所示的兩種仿真示例環(huán)境，其中右下角柵格代表機(jī)器人的起始點，左上角柵格代表目標(biāo)點。

2 基于改進(jìn)人工勢場算法的局部路徑規(guī)劃

2.1 人工勢場算法的基本原理

人工勢場算法是由KHATIB和KROGH最早提出來的一種虛擬力法[27]。它的基本思想是在機(jī)器人的運動環(huán)境中施加一種虛擬的人工力場，其中障礙物對機(jī)器人產(chǎn)生斥力，目標(biāo)點對機(jī)器人產(chǎn)生吸引力，機(jī)器人在兩種力的共同作用下運動。設(shè)二維平面內(nèi)機(jī)器人所處的位置為X=[xy]，目標(biāo)點所處的位置為XM=[xmym]。定義引力勢場函數(shù)[28]為

(3)

式中kg——引力場的增益系數(shù)，為正數(shù)

相應(yīng)的引力FG(X)為引力勢場函數(shù)的負(fù)梯度，計算公式為

(4)

其中

ξ1=‖X-XM‖

式中ξ1——機(jī)器人和目標(biāo)點之間的距離

α1——從機(jī)器人所處位置指向目標(biāo)點的單位向量

由此可見，引力與機(jī)器人到目標(biāo)點的距離呈線性關(guān)系。定義各障礙物產(chǎn)生的斥力場函數(shù)為

(5)

式中ξ——機(jī)器人與障礙物邊緣之間的最短距離

ξ0——障礙物所影響的最大范圍距離，其值需結(jié)合實際環(huán)境進(jìn)行優(yōu)化得到

k0——斥力場的增益系數(shù)，為正數(shù)

式(5)表明機(jī)器人位于距障礙物邊緣ξ0的范圍內(nèi)將受到障礙物斥力的影響，而超出這一范圍時機(jī)器人將不再受其斥力的作用。相應(yīng)的斥力F0(X)為斥力場函數(shù)的負(fù)梯度，計算公式為

(6)

機(jī)器人所受的合力F(X)為

F(X)=FG(X)+F0(X)

(7)

傳統(tǒng)人工勢場算法在進(jìn)行機(jī)器人路徑規(guī)劃和避障時，存在如下問題：

(1) 當(dāng)所有障礙物產(chǎn)生的斥力之和與引力大小相等，方向相反時，即形成了所謂的死鎖現(xiàn)象(Deadlock)[29]，機(jī)器人在該點處將無法移動，如圖3所示。

(2) 當(dāng)目標(biāo)點處于障礙物附近時，由于斥力作用的影響，可能導(dǎo)致目標(biāo)點不可達(dá)的問題。

(3) 當(dāng)障礙物較多時，計算每個障礙物所產(chǎn)生的斥力，將導(dǎo)致算法的計算效率急劇下降。

(4) 受斥力的影響，機(jī)器人無法緊貼障礙物運動，從而導(dǎo)致所規(guī)劃的避障路徑不一定最短，甚至在一些障礙物較為密集的區(qū)域出現(xiàn)規(guī)劃失敗的情況。

圖3 機(jī)器人運動過程中的死鎖現(xiàn)象Fig.3 Deadlock in process of robot movement

2.2 改進(jìn)人工勢場算法

改進(jìn)人工勢場算法的基本思路是先利用障礙物檢測算法識別出有效障礙物及一個路徑中間點，再利用終點的引力和各障礙物邊界條件進(jìn)行起點到中間點的局部路徑規(guī)劃，最后將中間點置為新的起點，重復(fù)以上過程，直至起點迭代至目標(biāo)點為止。

2.2.1障礙物檢測算法

障礙物檢測算法主要用于檢測對機(jī)器人移動路徑有影響的障礙物，稱其為有效障礙物，并在其周邊搜尋到一個合適的點作為路徑中間點。障礙物檢測算法的基本思想是：先構(gòu)建一條從起點到終點的直線，然后從起點處沿直線方向進(jìn)行搜索，當(dāng)發(fā)現(xiàn)存在障礙物時，將其置為有效，同時計算該障礙物每個邊沿點到直線的距離，找出正負(fù)方向上的兩個極值點，取其絕對值最小的點作為路徑中間點。

設(shè)機(jī)器人的起點為XS=[xsys]，終點為XD=[xdyd]，則柵格環(huán)境地圖中起點到終點的直線Σl方程定義為

(8)

式中 round——取整函數(shù)

設(shè)機(jī)器人移動的環(huán)境范圍為{(x,y)|0≤x≤Nh且0≤y≤Nl}，定義柵格到直線Σl的距離為

(9)

式中i、j——柵格的橫、縱坐標(biāo)

K——常數(shù)，取較大的正整數(shù)

將環(huán)境邊界柵格到直線的距離定義為較大值，可避免將其選作中間點。由式(9)可知，對于非邊界柵格，其到直線Σl的距離可為正數(shù)也可為負(fù)數(shù)，因此對于有效障礙物Ω的邊沿柵格，必存在兩個點到直線Σl的距離分別為正數(shù)的最大值和負(fù)數(shù)的最小值，設(shè)該兩柵格坐標(biāo)分別為Xmax,ω=[xmax,ωymax,ω]、Xmin,ω=[xmin,ωymin,ω]，各自對應(yīng)的最大距離和最小距離分別為dmax,ω和dmin,ω，則障礙物Ω周邊存在的路徑中間點坐標(biāo)Xl,ω=[xl,ωyl,ω]為

(10)

(11)

2.2.2人工勢場算法的改進(jìn)

在柵格地圖環(huán)境中，規(guī)定機(jī)器人可進(jìn)行8鄰域的移動[30]，即機(jī)器人每次只能移動到相鄰的某個柵格內(nèi)。據(jù)此規(guī)定機(jī)器人在柵格環(huán)境中只能受8個方向上的作用力，用3×3的矩陣來存儲，并稱其為力向矩陣，其中各元素所代表的力方向如圖4所示。

傳統(tǒng)人工勢場算法中，由于障礙物對機(jī)器人存在斥力作用，致使機(jī)器人無法緊貼障礙物移動，因此本文去掉障礙物對機(jī)器人的斥力作用，而引入一個與障礙物有關(guān)的邊界條件，即機(jī)器人在鄰近障礙物方向上的受力始終為零。故機(jī)器人在各方向上的受力只與終點產(chǎn)生的引力和其所處的外部環(huán)境有關(guān)，定義機(jī)器人在X處的力向矩陣為

(12)

式中Eij——環(huán)境約束矩陣

*——卷積運算

環(huán)境約束矩陣Eij主要反映機(jī)器人周邊8鄰域柵格的狀態(tài)，本文取3×3階的矩陣，各元素定義如下

(13)

(14)

最優(yōu)分解是指矩陣中各元素滿足

(15)

式中m——FG(X)矩陣元素的行代號，m∈{-1,0,1}

n——FG(X)矩陣元素的列代號，n∈{-1,0,1}

αij——X處機(jī)器人可移動的方向向量，αij=(m，n)

規(guī)定機(jī)器人進(jìn)行局部路徑規(guī)劃時總是向受力最大的方向運動，則路徑點的迭代公式為

X′=X+λij

(16)

式中λij——X處機(jī)器人所受最大引力分量的方向向量

X′——下一路徑點的位置向量

2.3 改進(jìn)人工勢場算法的具體步驟

基于改進(jìn)人工勢場算法的局部路徑規(guī)劃步驟如下：

(2)運用障礙物檢測算法搜索到有效障礙物及一個中間點，將中間點置為局部路徑的終點，重復(fù)調(diào)用障礙物檢測算法進(jìn)行搜索，直至沒有發(fā)現(xiàn)新的有效障礙物和新的中間點為止，此時的終點即為第1個有效中間點，并將最后一個有效障礙物的柵格屬性數(shù)據(jù)從ZX復(fù)制到ZS中。

(4)將終點置為新的起點，將目標(biāo)點置為新的終點，重復(fù)步驟(2)和步驟(3)，直至起點變?yōu)槟繕?biāo)點為止，則路徑規(guī)劃結(jié)束，所得的各段局部最優(yōu)路徑即構(gòu)成機(jī)器人從起點到目標(biāo)點的全局路徑。

改進(jìn)的人工勢場算法利用若干中間點來進(jìn)行各局部路段的規(guī)劃，由于每段局部路徑之間不存在新的障礙物以及新的中間點，因此規(guī)劃過程中不會出現(xiàn)死鎖現(xiàn)象；同時由于改進(jìn)算法中取消了障礙物的斥力作用，因此只在引力場作用下的機(jī)器人可以緊貼障礙物運動，從而獲得長度更短的局部路徑。

3 基于改進(jìn)蟻群算法的全局最優(yōu)路徑規(guī)劃

由于人工勢場算法在進(jìn)行路徑規(guī)劃時只考慮局部障礙物的影響，因此其計算量小、規(guī)劃速度快，但其所得的路徑卻不具備全局最優(yōu)特性。為了獲得全局最優(yōu)路徑，往往還需借助其他全局規(guī)劃算法做進(jìn)一步的路徑規(guī)劃，其中蟻群算法因其簡單、智能等特性而受到廣泛應(yīng)用[21-23]。

3.1 蟻群算法的基本原理

蟻群算法最早由DORIGO等[31]于1996年提出，并首先使用在解決旅行商問題上。它模擬螞蟻覓食的過程，通過螞蟻群體與環(huán)境之間的信息交互來實現(xiàn)最優(yōu)路徑搜索。

蟻群算法涉及到兩個關(guān)鍵的步驟：概率選擇和信息素更新[23]。所謂概率選擇，是指每只螞蟻在經(jīng)過路口時都按一定的概率去選擇下一個將要訪問的節(jié)點。蟻群算法采用偽隨機(jī)比例原則來選擇下一個節(jié)點的位置，其路徑選擇規(guī)則為

(17)

其中

(18)

ηij(t)=1/djg

(19)

ak——螞蟻k下一步被允許訪問的節(jié)點集合

τij(t)——t時刻螞蟻從節(jié)點i轉(zhuǎn)移到節(jié)點j的信息素濃度

τis(t)——t時刻螞蟻從節(jié)點i轉(zhuǎn)移到節(jié)點s的信息素濃度

ηij(t)——t時刻螞蟻從節(jié)點i轉(zhuǎn)移到節(jié)點j的啟發(fā)信息

ηis(t)——t時刻螞蟻從節(jié)點i轉(zhuǎn)移到節(jié)點s的啟發(fā)信息

α——信息素啟發(fā)因子

β——期望啟發(fā)因子

q——均布在[0,1]區(qū)間的隨機(jī)變量

q0——概率常數(shù)，q0∈[0,1]

J——隨機(jī)變量，由式(17)的概率分布而產(chǎn)生

djg——節(jié)點j到目標(biāo)節(jié)點g的歐氏距離

所謂信息素更新，是指螞蟻在訪問過的節(jié)點中會留下一種被稱為信息素的物質(zhì)，其大小與螞蟻所走過的路徑長度有關(guān)。通過各節(jié)點上信息素的累積和揮發(fā)，可引導(dǎo)后續(xù)螞蟻進(jìn)行路徑選擇，從而尋找一條最優(yōu)的路徑。為了兼顧全局搜索和局部搜索的能力，基本蟻群算法采用全局信息素更新和局部信息素更新的策略，相應(yīng)的公式為

(20)

τij(t+1)=(1-ε)τij(t)+ετ0

(21)

式中ρ——全局信息素?fù)]發(fā)系數(shù)，ρ∈(0,1]

Tbs——蟻群單次迭代完成后搜索到的最優(yōu)路徑

ε——局部信息素?fù)]發(fā)系數(shù)，ε∈(0,1]

τ0——初始信息素

由式(20)知，全局更新的作用是使最優(yōu)路徑中各節(jié)點的信息素得到加強(qiáng)，以形成正反饋，從而加快算法收斂。由式(21)知，局部更新的作用是使螞蟻每次所經(jīng)過路徑中的各節(jié)點信息素得到減弱，以減少螞蟻重復(fù)訪問的概率，從而增強(qiáng)算法的全局搜索能力。

3.2 蟻群算法的改進(jìn)

由蟻群算法的路徑選擇規(guī)則式(17)、(18)可知，信息素濃度τij和啟發(fā)信息ηij是決定螞蟻進(jìn)行路徑選擇的兩個重要因素。在早期，由于路徑點上的信息素濃度較低，因此起主要作用的是啟發(fā)信息ηij，而傳統(tǒng)蟻群算法中ηij只與待選節(jié)點到目標(biāo)節(jié)點的歐氏距離djg有關(guān)，卻忽略了障礙物的影響，從而導(dǎo)致某些環(huán)境中初始路徑陷入局部最優(yōu)的情況。在后期，啟發(fā)信息的作用減弱，信息素的作用增強(qiáng)，雖然傳統(tǒng)蟻群算法中采用局部信息素更新策略改善了算法后期的全局搜索能力，但同時也降低了算法前期的收斂性，從而使算法整體的收斂速度降低；同理，全局信息素更新策略雖然改善了算法前期的收斂性，但也影響了后期的全局搜索能力。基于此，本文對傳統(tǒng)蟻群算法的啟發(fā)信息和信息素更新策略進(jìn)行相應(yīng)改進(jìn)。

3.2.1啟發(fā)信息的改進(jìn)

結(jié)合人工勢場算法計算速度快的優(yōu)點，在考慮障礙物的情況下，用改進(jìn)人工勢場算法得到的待選節(jié)點j到目標(biāo)點g的距離rjg來代替?zhèn)鹘y(tǒng)的歐氏距離djg，同時為了更加準(zhǔn)確地反映當(dāng)前節(jié)點與目標(biāo)節(jié)點的距離，將當(dāng)前節(jié)點i與待選節(jié)點j的距離dij也考慮進(jìn)來。此外，在算法后期，為了削弱啟發(fā)信息的作用，以提高算法的全局搜索能力，引入一個啟發(fā)信息誘導(dǎo)因子ζ，因此啟發(fā)信息的改進(jìn)公式為

(22)

式中NCmax——最大迭代次數(shù)

NC——當(dāng)前迭代次數(shù)

ζ——啟發(fā)信息誘導(dǎo)因子，ζ∈(0,1]

當(dāng)ζ∈(0,0.5)時，算法早期，由于(1-ζ)/ζ>1，因此啟發(fā)信息的作用將得到加強(qiáng)，從而有利于加快算法收斂速度；在算法后期，由于(NCmax-NC)/NCmax?1，因此啟發(fā)信息的作用將受到削弱，從而有利于提高算法的全局搜索能力。

3.2.2信息素更新策略的改進(jìn)

由分析知，全局信息素更新和局部信息素更新各自所起的作用不同，然而在算法的整個過程中，不同階段有不同的性能要求，因此固定式的全局更新和局部更新策略無法使算法的性能達(dá)到最優(yōu)?；诖耍疚奶岢隽艘环N信息素更新的動態(tài)調(diào)整策略，其基本思想是在算法收斂速度較慢時，加強(qiáng)全局信息素更新的作用同時抑制局部信息素更新的作用，在算法收斂速度較快時，加強(qiáng)局部信息素更新作用同時抑制全局信息素更新的作用。全局信息素及局部信息素的更新公式如下

(23)

τij(t+1)=(1-ε)δτij(t)

(24)

其中

δ=NS/N0

式中δ——自適應(yīng)變量N0——常數(shù)

由式(23)和式(24)知，當(dāng)NSN0時，δ>1，則全局路徑更新時最優(yōu)路徑中各節(jié)點信息素的增強(qiáng)效果將得到削弱，同時局部更新時螞蟻所經(jīng)歷節(jié)點信息素的衰減效果將得到加強(qiáng)。以上對全局和局部信息素的自適應(yīng)調(diào)整策略，相當(dāng)于利用收斂次數(shù)構(gòu)建了一條負(fù)反饋通道，以此保證全程中算法收斂速度和全局搜索能力的平穩(wěn)和協(xié)調(diào)。

3.3 改進(jìn)蟻群算法的具體步驟

圖5為改進(jìn)蟻群算法的流程圖，具體步驟如下：

圖5 改進(jìn)蟻群算法流程圖Fig.5 Flow chart of improved ant colony algorithm

(1)初始化各項參數(shù)：起始位置XS、目標(biāo)位置XM、收斂計數(shù)器NS、迭代計數(shù)器NC，設(shè)置最大迭代次數(shù)NCmax、蟻群數(shù)量N、信息素啟發(fā)因子α、期望啟發(fā)因子β、啟發(fā)信息誘導(dǎo)因子ζ、全局信息素?fù)]發(fā)系數(shù)ρ、局部信息素?fù)]發(fā)系數(shù)ε、信息素矩陣T及其他相關(guān)參數(shù)。

(2)蟻群路徑迭代：從起點處釋放N只螞蟻，同時將起點位置XS放入禁忌表中，采用改進(jìn)的人工勢場算法計算出待選節(jié)點j到目標(biāo)節(jié)點g的距離rjg，并代入式(22)中得到啟發(fā)信息ηij(t)的值，再依據(jù)式(17)和式(18)確定下一個可行節(jié)點j，同時將所選的節(jié)點加入禁忌表中，按相同過程進(jìn)行循環(huán)迭代直至螞蟻到達(dá)目標(biāo)點為止。

(3)更新局部信息素：螞蟻每建立一條路徑便按式(24)進(jìn)行局部信息素更新。

(4)更新全局信息素：當(dāng)N只螞蟻的一次迭代完成后，找出最優(yōu)路徑，并按式(23)進(jìn)行全局信息素更新。

(5)搜索結(jié)束判斷：當(dāng)單次迭代完成后，檢測當(dāng)前迭代次數(shù)NC是否等于最大迭代次數(shù)NCmax。如果相等，則結(jié)束算法并輸出最優(yōu)路徑長度；如果不等，則跳轉(zhuǎn)至步驟(2)。

4 仿真實驗分析

為驗證所述改進(jìn)勢場蟻群算法的有效性，在Matlab R2010a中進(jìn)行仿真實驗，計算機(jī)操作系統(tǒng)為Windows 7，CPU為Core i5-650，內(nèi)存為8 GB，仿真環(huán)境為20×20的平面柵格環(huán)境，其中障礙物的設(shè)置如圖2所示。同時，為了驗證本文算法的優(yōu)越性，在相同環(huán)境中將本文算法所得結(jié)果分別與基本蟻群算法以及文獻(xiàn)[23]中改進(jìn)蟻群算法的結(jié)果進(jìn)行比較。

4.1 主要參數(shù)優(yōu)化

蟻群算法中，影響其綜合性能的參數(shù)有許多，由于這些參數(shù)之間存在緊密的耦合作用，因此很難通過理論的方式確定出最優(yōu)參數(shù)組合[32-33]，目前常見的方法主要是通過多次實驗進(jìn)行反復(fù)試湊而得[18]。

圖6 簡單環(huán)境中3種算法所得的路徑規(guī)劃結(jié)果Fig.6 Path planning results of three algorithms in simple environment

由于信息素和啟發(fā)信息是影響螞蟻進(jìn)行路徑選擇的兩個關(guān)鍵因素，因此本文重點考查與該兩個因素有直接聯(lián)系的5個參數(shù)：信息素啟發(fā)因子α、期望啟發(fā)因子β、啟發(fā)信息誘導(dǎo)因子ζ、全局信息素?fù)]發(fā)系數(shù)ρ、局部信息素?fù)]發(fā)系數(shù)ε，其他參數(shù)的取值如表1所示。選取復(fù)雜仿真環(huán)境(圖2b)，為避免偶然情況所引起的較大誤差，對每組選定的參數(shù)組合進(jìn)行10次仿真，并將所得結(jié)果求平均值后用于比較。為了避免仿真實驗的次數(shù)過多，在各參數(shù)大致范圍內(nèi)選取5個點進(jìn)行分析，分別為α∈{0,0.5,1,2,4},β∈{0,3,6,9,12},ζ∈{0.1,0.2,0.3,0.4,0.5},ρ∈{0.1，0.3，0.5，0.7，0.9},ε∈{0.1，0.3，0.5，0.7，0.9}。同時，為方便對單一的參數(shù)進(jìn)行分析，設(shè)定一組默認(rèn)參數(shù)值為：α=1，β=6，ζ=0.3，ρ=0.5，ε=0.5。每次實驗時只改變其中一個參數(shù)的取值，其他4個參數(shù)均采用默認(rèn)值，相應(yīng)的實驗結(jié)果如表2所示。

表1 本文算法涉及到的相關(guān)參數(shù)Tab.1 Parameters of proposed algorithm

表2 主要參數(shù)優(yōu)化實驗結(jié)果Tab.2 Experimental results of main parameters optimization

由表2中的實驗結(jié)果可知，參數(shù)α的最優(yōu)值在2附近，參數(shù)β的最優(yōu)值在6附近，參數(shù)ζ的最優(yōu)值在0.2附近，參數(shù)ρ的最優(yōu)值在0.7附近，參數(shù)ε的最優(yōu)值在0.5附近，因此，針對本文所提的改進(jìn)算法，其主要參數(shù)選取為：α=2，β=6，ζ=0.2，ρ=0.7，ε=0.5。

4.2 簡單環(huán)境下的實驗結(jié)果對比

在簡單仿真環(huán)境中，由于障礙物設(shè)置較少，因此從實驗結(jié)果可觀察出每種算法的特點。在圖2a所示的簡單仿真環(huán)境中，3種算法的實驗結(jié)果如圖6和圖7所示。

圖7 簡單環(huán)境中3種算法的收斂曲線Fig.7 Convergence curves of three algorithms in simple environment

由圖6和圖7知，基本蟻群算法在搜尋過程中陷入了局部最優(yōu)解，其主要原因是在第1次避開中間凸形障礙物的過程中，受啟發(fā)信息的誤導(dǎo)，致使螞蟻選擇了距目標(biāo)點歐氏距離較小的右邊節(jié)點，后續(xù)在正反饋的作用下使蟻群搜索的路徑不斷收斂于該局部解。由于文獻(xiàn)[23]和本文所述的算法對蟻群的啟發(fā)信息進(jìn)行了改進(jìn)，所以避免了這種問題，同時由于人工勢場算法為蟻群提供了較為正確的初始啟發(fā)信息，致使蟻群獲得了較優(yōu)的初始路徑，從而提高了算法的收斂速度。但是由于文獻(xiàn)[23]采用傳統(tǒng)人工勢場算法來構(gòu)建啟發(fā)信息，導(dǎo)致蟻群的初始路徑與最優(yōu)路徑相差較大，從而影響了算法后續(xù)的收斂速度。相比較而言，本文所述的算法由于對傳統(tǒng)人工勢場算法進(jìn)行了改進(jìn)，因此提高了初始路徑的最優(yōu)性，從而大大提高了算法的收斂速度。從圖7可知，在簡單環(huán)境中，由于利用改進(jìn)人工勢場算法所規(guī)劃出的路徑恰為最優(yōu)路徑，因此使蟻群算法在進(jìn)行3次迭代之后即收斂于最優(yōu)解。如表3所示，在簡單環(huán)境中，相較于另外兩種算法，本文算法不僅具有較高的收斂速度，同時運行時間也最短，為0.892 s。

表3 簡單環(huán)境中3種算法仿真結(jié)果對比Tab.3 Simulation results comparison of three algorithms in simple environment

4.3 復(fù)雜環(huán)境下的實驗結(jié)果對比

為了解算法在復(fù)雜環(huán)境中的適用情況，在圖2b所示的復(fù)雜環(huán)境中對3種算法進(jìn)行仿真實驗，結(jié)果如圖8、9所示。

圖8 復(fù)雜環(huán)境中3種算法所得的路徑規(guī)劃結(jié)果Fig.8 Path planning results of three algorithms in complex environment

由圖8和圖9可知，在復(fù)雜環(huán)境中基本蟻群算法搜索到的路徑仍陷入了局部最優(yōu)的情況。本文算法搜索到的最優(yōu)路徑長度與文獻(xiàn)[23]算法搜索到的路徑長度一致，均為31.556 m。但是由于本文算法采用改進(jìn)后的人工勢場算法來啟發(fā)蟻群進(jìn)行搜索，因此初始路徑明顯優(yōu)于文獻(xiàn)[23]算法的初始路徑。本文算法初始搜索到的路徑長度為38.314 m，而文獻(xiàn)[23]算法初始搜索到的路徑長度為40.142 m。

圖9 復(fù)雜環(huán)境中3種算法的收斂曲線Fig.9 Convergence curves of three algorithms in complex environment

另外，在算法迭代過程中，由于全局信息素和局部信息素的交替作用，致使算法收斂曲線存在一定的波動性，嚴(yán)重影響了算法的收斂速度。在本文算法中，由于利用收斂次數(shù)構(gòu)建了一條負(fù)反饋通道，因此有效降低了算法迭代過程中的波動性，使算法的收斂過程趨于平穩(wěn)，從而提高了算法的收斂速度。在38.314 m這一相同的初始路徑長度下，本文算法只需經(jīng)過8次迭代即可收斂到最優(yōu)解，文獻(xiàn)[23]算法需要進(jìn)行10次迭代方可收斂到最優(yōu)解，而基本蟻群算法至少需要進(jìn)行15次迭代方可收斂到最優(yōu)解。

此外，從表4中可以看出，本文算法進(jìn)行最優(yōu)路徑規(guī)劃的時間明顯低于其他兩種算法，其中除了本文算法的迭代次數(shù)較少之外，還因為在改進(jìn)的人工勢場算法中省去了對無效障礙物以及斥力場的計算，因此有效減少了算法的計算量，從而縮短了算法的運行時間。

為了進(jìn)一步了解本文算法的全局搜索能力，在相同的復(fù)雜環(huán)境中，分別導(dǎo)出3種算法中所有螞蟻的搜索路徑，如圖10所示，其中藍(lán)色粗實線表示對應(yīng)算法所得的最優(yōu)路徑。為了量化算法的全局搜索能力，用蟻群所尋路徑對環(huán)境的覆蓋率φ來表示，

表4 復(fù)雜環(huán)境中3種算法仿真結(jié)果對比Tab.4 Simulation results comparison of three algorithms in complex environment

圖10 3種算法的全局搜索結(jié)果對比Fig.10 Global searching result comparison of three algorithms

計算公式為

(25)

式中Npass——蟻群搜索到的柵格個數(shù)

Nfree——環(huán)境中自由柵格的個數(shù)

由圖10可知，文獻(xiàn)[23]和本文算法中蟻群搜索的環(huán)境范圍明顯較基本蟻群算法中蟻群搜索的范圍廣，因此該兩種算法找到最優(yōu)路徑的可能性更高。由式(25)計算可得，基本蟻群算法所尋路徑對環(huán)境的覆蓋率為57.09%，文獻(xiàn)[23]算法所尋路徑對環(huán)境的覆蓋率為72.83%，本文算法所尋路徑對環(huán)境的覆蓋率為73.63%。因此，本文算法所尋路徑對環(huán)境的覆蓋率最大，搜尋到最優(yōu)路徑的可能性也最大，故而相應(yīng)的全局尋優(yōu)能力最強(qiáng)。

5 結(jié)論

(1)通過理論分析，發(fā)現(xiàn)傳統(tǒng)人工勢場算法存在死鎖及局部路徑欠優(yōu)等問題，利用其規(guī)劃的結(jié)果作為先驗知識啟發(fā)蟻群進(jìn)行初始搜索，會降低初始路徑的優(yōu)越性。因此，本文對傳統(tǒng)人工勢場算法進(jìn)行了改進(jìn)，通過障礙物檢測算法識別有效障礙物和路徑中間點，并用障礙物邊界條件替換原有的斥力場函數(shù)。仿真實驗表明，利用改進(jìn)人工勢場算法的結(jié)果啟發(fā)蟻群進(jìn)行搜索，可以提高蟻群算法初始路徑的優(yōu)越性。

(2)針對基本蟻群算法中全局信息素和局部信息素的內(nèi)在矛盾，提出一種新的信息素更新策略，以收斂次數(shù)構(gòu)建一條負(fù)反饋通道，以便根據(jù)收斂次數(shù)的變化來動態(tài)調(diào)整全局信息素和局部信息素的更新速度，從而保證全程中算法收斂性和全局搜索能力的協(xié)調(diào)與統(tǒng)一。

(3)采用組合實驗的方法，對改進(jìn)勢場蟻群算法中的5個重要參數(shù)進(jìn)行優(yōu)化，獲得了一組較優(yōu)的參數(shù)組合方案：α=2，β=6，ζ=0.2，ρ=0.7，ε=0.5。

(4)采用柵格法構(gòu)建機(jī)器人的兩種環(huán)境模型，并在Matlab中對基本蟻群算法、文獻(xiàn)[23]算法以及本文算法進(jìn)行相同的仿真對比實驗，結(jié)果表明，本文算法的運行時間最短，收斂速度最快，全局尋優(yōu)能力最強(qiáng)。