徐玉瓊，婁柯，李志錕

（1. 廣州大學(xué)松田學(xué)院 電氣與汽車工程系，廣東 廣州 511370; 2. 高端裝備先進(jìn)感知與智能控制教育部重點(diǎn)實(shí)驗(yàn)室，安徽 蕪湖 241000; 3. 安徽工程大學(xué) 安徽省電氣傳動(dòng)與控制重點(diǎn)實(shí)驗(yàn)室，安徽 蕪湖 241000）

在移動(dòng)機(jī)器人領(lǐng)域，路徑規(guī)劃技術(shù)一直都是重要研究?jī)?nèi)容，其任務(wù)是在地圖環(huán)境中為移動(dòng)機(jī)器人從起點(diǎn)至終點(diǎn)避開障礙物而規(guī)劃出的最優(yōu)路徑。目前國(guó)內(nèi)外學(xué)者針對(duì)路徑規(guī)劃技術(shù)做了諸多研究，并取得相應(yīng)成果，常用的傳統(tǒng)路徑規(guī)劃算法有遺傳算法、模擬退火算法、人工勢(shì)場(chǎng)法、A*算法[1]等。隨著人工智能技術(shù)的高速發(fā)展，群智能算法在路徑規(guī)劃技術(shù)中得到廣泛應(yīng)用和發(fā)展，如人工魚群算法、蜂群算法、蟻群算法[2-4]、蛙跳算法等，人工魚群算法是一種擅長(zhǎng)隨機(jī)搜索的算法，其算法原理簡(jiǎn)單，對(duì)初始值要求較低，但在算法后期存在收斂速率緩慢、計(jì)算結(jié)果不夠精確。蜂群算法作為模仿蜜蜂行為提出的啟發(fā)式算法，通過(guò)對(duì)單一的蜜蜂進(jìn)行局部尋優(yōu)，突出全局最優(yōu)值，容易陷入局部最優(yōu)，其算法魯棒性不強(qiáng)。傳統(tǒng)的群智能算法已經(jīng)無(wú)法滿足移動(dòng)機(jī)器人在復(fù)雜環(huán)境下進(jìn)行路徑規(guī)劃，因此，大量學(xué)者通過(guò)對(duì)傳統(tǒng)的群智能算法進(jìn)行改進(jìn)，如多策略人工魚群算法[5-7]、雙層蟻群算法[8]、啟發(fā)機(jī)制下的蟻群算法[9]等。改進(jìn)的群智能算法已經(jīng)明顯提高復(fù)雜環(huán)境下移動(dòng)機(jī)器人的路徑規(guī)劃[10-15]能力。

蟻群算法作為啟發(fā)式全局優(yōu)化算法是由意大利學(xué)者Dorigo在1992年提出，該算法得益于采用正反饋機(jī)制，收斂性能大幅提升，通過(guò)分布式計(jì)算方式進(jìn)行搜索以及不同個(gè)體同時(shí)并行計(jì)算，提高了該算法的運(yùn)算效率以及計(jì)算能力，但仍存在收斂速度慢以及死鎖問(wèn)題。因此，文獻(xiàn)[9]對(duì)蟻群算法進(jìn)行改進(jìn)，提出了基于啟發(fā)式機(jī)制的蟻群算法，該算法通過(guò)當(dāng)前節(jié)點(diǎn)到終點(diǎn)的距離動(dòng)態(tài)的調(diào)整啟發(fā)函數(shù)，當(dāng)算法處于局部最優(yōu)時(shí)，引入懲罰函數(shù)機(jī)制，降低最優(yōu)路徑的信息素，減少蟻群算法的正反饋影響而跳出局部最優(yōu)。文獻(xiàn)[14]主要針對(duì)于蟻群算法收斂速度慢進(jìn)行改進(jìn)，合理分配信息素初始濃度，動(dòng)態(tài)調(diào)整信息素?fù)]發(fā)因子，進(jìn)行二次路徑規(guī)劃，有效縮短了移動(dòng)機(jī)器人的路徑長(zhǎng)度。文獻(xiàn)[8]設(shè)計(jì)了雙層蟻群算法，對(duì)移動(dòng)機(jī)器人二維柵格環(huán)境進(jìn)行凸化處理，同時(shí)用外層蟻群探索出一條路徑作為一個(gè)小環(huán)境，內(nèi)層蟻群在該環(huán)境下重新探索，兩條路徑擇優(yōu)篩選，提高蟻群算法路徑搜索質(zhì)量。

為了提高蟻群算法收斂速度以及縮短路徑長(zhǎng)度，本文提出變步長(zhǎng)蟻群算法，尋找移動(dòng)機(jī)器人可以達(dá)到的跳點(diǎn)，得到不同長(zhǎng)度的路徑，根據(jù)路徑長(zhǎng)度的不同，不均勻分配初始信息素濃度，以降低邊緣障礙物對(duì)移動(dòng)機(jī)器人的影響，從而提高算法的計(jì)算能力。改進(jìn)啟發(fā)式信息矩陣，提高蟻群避障能力，增強(qiáng)蟻群全局路徑搜索能力，快速找到最優(yōu)路徑。

1 蟻群算法原理

1.1 環(huán)境表示

移動(dòng)機(jī)器人需要在二維空間環(huán)境下進(jìn)行路徑規(guī)劃，因此，需要對(duì)移動(dòng)機(jī)器人工作環(huán)境進(jìn)行建模，常規(guī)環(huán)境建模方法如柵格圖法[16-18]、可視圖空間法、自由空間法、幾何信息法等。本文選取柵格圖法對(duì)移動(dòng)機(jī)器人二維空間進(jìn)行建模，將柵格分為黑色區(qū)域和白色區(qū)域，其中黑色區(qū)域?yàn)檎系K物柵格，白色區(qū)域?yàn)樽杂蓶鸥?，機(jī)器人可以在白色區(qū)域自由移動(dòng)，如圖1所示，假設(shè)每個(gè)柵格為邊長(zhǎng)為1 m的正方形，不考慮機(jī)器人自身身高和體積的影響，機(jī)器人始終處于正方形的正中心位置。

圖 1 柵格地圖Fig. 1 Raster map

1.2 搜索方式

傳統(tǒng)蟻群算法中蟻群為單步長(zhǎng)[19-20]移動(dòng)方式，每步移動(dòng)距離為1或個(gè)單元格，在不碰撞障礙物的情況下，可以向四周共8個(gè)方向移動(dòng)，如圖2所示。

圖 2 移動(dòng)方式Fig. 2 Moving method

蟻群在尋路過(guò)程中，利用信息素相互通信，在經(jīng)過(guò)的路徑上釋放信息素，當(dāng)某一條路徑通過(guò)的螞蟻越來(lái)越多時(shí)，該路徑的信息素濃度就越高，其他螞蟻選擇該路徑的概率就越大，起到正反饋?zhàn)饔?，同時(shí)也容易陷入局部最優(yōu)及存在死鎖現(xiàn)象。信息素會(huì)隨著時(shí)間的增長(zhǎng)而揮發(fā)，動(dòng)態(tài)的調(diào)整各路徑的信息素濃度，螞蟻在選擇路徑時(shí)，會(huì)對(duì)信息素濃度、啟發(fā)因子、路徑方向等因素進(jìn)行綜合判斷選擇下一步移動(dòng)位置，并利用輪盤算法計(jì)算當(dāng)前節(jié)點(diǎn)到下一到達(dá)節(jié)點(diǎn)的概率：

式中：τij為路徑(i,j) 上的信息素；ηij為位置i到位置j的啟發(fā)因子；ak為螞蟻k下一步可到達(dá)節(jié)點(diǎn)的集合；α 表征信息素重要程度；β表征啟發(fā)因子重要程度；dij是螞蟻從位置i到位置j構(gòu)建的路徑長(zhǎng)度。

為了避免螞蟻選擇已經(jīng)達(dá)到過(guò)的節(jié)點(diǎn)，采用禁忌表記錄螞蟻k當(dāng)前所達(dá)到過(guò)的位置，經(jīng)過(guò)t時(shí)刻，所有螞蟻都已完成了一次路徑規(guī)劃，計(jì)算所有螞蟻完成的有效路徑長(zhǎng)度，篩選出最短路徑長(zhǎng)度，同時(shí)更新各路徑上的信息素，經(jīng)過(guò)時(shí)間的增長(zhǎng)，信息素將揮發(fā)一部分：

式中：ρ 是信息素?fù)]發(fā)系數(shù)，同時(shí)，螞蟻也將在路徑中釋放信息素：

式中：Δτkij是第k只螞蟻在所經(jīng)過(guò)的路徑上釋放的信息素，定義如下：

由式(5)可知，螞蟻所構(gòu)建的路徑長(zhǎng)度dij越小，那么各路徑將得到更多的信息素，在以后的迭 代中該路徑被其他螞蟻選擇的概率也將更大。

2 變步長(zhǎng)蟻群算法

傳統(tǒng)蟻群算法步長(zhǎng)選擇為單步長(zhǎng)，蟻群僅能向相鄰柵格位置移動(dòng)，不能滿足移動(dòng)機(jī)器人實(shí)際需求，且搜索效率低及路徑長(zhǎng)度無(wú)法滿足最優(yōu)，因此，本文提出變步長(zhǎng)選擇策略，在避開障礙物的條件下，移動(dòng)機(jī)器人可以從當(dāng)前位置向全局地圖的任何位置移動(dòng)，大幅提高移動(dòng)機(jī)器人搜索效率。

2.1 步長(zhǎng)選擇策略

跳點(diǎn)的選擇即步長(zhǎng)的選擇，所謂跳點(diǎn)就是移動(dòng)機(jī)器人在搜索過(guò)程中從當(dāng)前節(jié)點(diǎn)可以到達(dá)下一步的節(jié)點(diǎn)。如圖3所示。移動(dòng)機(jī)器人從起點(diǎn)到終點(diǎn)有4條路徑可供選擇，方案1為當(dāng)前節(jié)點(diǎn)1跳躍至節(jié)點(diǎn)2再到終點(diǎn)3，節(jié)點(diǎn)1到節(jié)點(diǎn)2步長(zhǎng)為3.16 m，節(jié)點(diǎn)2至節(jié)點(diǎn)3路徑長(zhǎng)度為2 m，因此，方案1路徑總長(zhǎng)度為5.16 m，方案2為節(jié)點(diǎn)1變步長(zhǎng)跳躍至節(jié)點(diǎn)4再到節(jié)點(diǎn)5，最后由節(jié)點(diǎn)5單步移動(dòng)至終點(diǎn)3，方案2路徑總長(zhǎng)度為4.65 m，方案3為傳統(tǒng)蟻群算法的單步長(zhǎng)移動(dòng)方式，從當(dāng)前節(jié)點(diǎn)1到節(jié)點(diǎn)6，再移動(dòng)到節(jié)點(diǎn)7，再移動(dòng)到節(jié)點(diǎn)8，最后再到終點(diǎn)3，該方案路徑總長(zhǎng)度為4.83 m，方案4為節(jié)點(diǎn)1跳躍至節(jié)點(diǎn)9，從節(jié)點(diǎn)9單步長(zhǎng)移動(dòng)到節(jié)點(diǎn)8，最后移動(dòng)到終點(diǎn)3，該方案路徑總長(zhǎng)度為5.16 m，顯然，方案2作為變步長(zhǎng)移動(dòng)方式優(yōu)于其他方案，變步長(zhǎng)蟻群算法在尋路過(guò)程中，對(duì)每種方案的路徑長(zhǎng)度進(jìn)行評(píng)估，最終挑選出路徑最短的方案。

圖 3 步長(zhǎng)選擇Fig. 3 Step size selection

在圖3中，節(jié)點(diǎn)1為起始點(diǎn)，節(jié)點(diǎn)3為終點(diǎn)，移動(dòng)機(jī)器人進(jìn)行路徑規(guī)劃時(shí)，將節(jié)點(diǎn)1作為父節(jié)點(diǎn)，通過(guò)變步長(zhǎng)選擇策略，將下一步移動(dòng)機(jī)器人要到達(dá)的節(jié)點(diǎn)4作為子節(jié)點(diǎn)，再將節(jié)點(diǎn)4作為父節(jié)點(diǎn)確定下一子節(jié)點(diǎn)，以此方法進(jìn)行迭代，最終確定了本輪迭代后的最優(yōu)路徑{1,4,5,3}，結(jié)合變步長(zhǎng)蟻群算法的優(yōu)點(diǎn)，移動(dòng)機(jī)器人對(duì)于下一步所選擇的節(jié)點(diǎn)越接近于終點(diǎn)，則可以減少節(jié)點(diǎn)轉(zhuǎn)折的次數(shù)，同時(shí)，轉(zhuǎn)折點(diǎn)越接近于障礙物，則可以減少無(wú)效路徑，因此，為了縮短移動(dòng)機(jī)器人路徑長(zhǎng)度，引入終點(diǎn)誘導(dǎo)因子 φ 及障礙物誘導(dǎo)因子 μ，其選擇概率為

式中：k為常數(shù)，保證概率范圍為(0,1)；ε 為終點(diǎn)誘導(dǎo)系數(shù)；ω 為障礙物誘導(dǎo)系數(shù)； γis為移動(dòng)機(jī)器人當(dāng)前節(jié)點(diǎn)到下一步可到達(dá)所有節(jié)點(diǎn)的距離總和，σ 為移動(dòng)機(jī)器人下一步到達(dá)的節(jié)點(diǎn)與終點(diǎn)之間的距離，其值越小，則距離終點(diǎn)越近，被選擇的概率也將越大，λ 為移動(dòng)機(jī)器人下一步到達(dá)的節(jié)點(diǎn)與其最近的障礙物之間的距離，優(yōu)先考慮障礙物相鄰的節(jié)點(diǎn)，可以有效縮短無(wú)效路徑，提高移動(dòng) 機(jī)器人避障能力。

2.2 信息素分布策略

在移動(dòng)機(jī)器人路徑規(guī)劃之前，需要給柵格地圖環(huán)境的信息素進(jìn)行初始化，初始化信息素采用不均勻分布，障礙物柵格的信息素設(shè)置為0，加強(qiáng)起點(diǎn)至終點(diǎn)直線所涉及到柵格的信息素濃度，平行的向外衰減，將柵格地圖建立直角坐標(biāo)系，如圖4所示。

圖 4 信息素分布策略Fig. 4 Pheromone distribution strategy

連接移動(dòng)機(jī)器人的起始點(diǎn)及終點(diǎn)，則該直線方程為

在本文中，C取值為20或30，分別對(duì)應(yīng)簡(jiǎn)單柵格環(huán)境和復(fù)雜柵格環(huán)境，令τij(0)=τ0為信息素濃度的初始值，根據(jù)初始信息素濃度的衰減方式，障礙物柵格的初始信息素 τ0直接取0，非障礙物柵格初始信息素取值如下：

式中：T為調(diào)整系數(shù)，T∈(1,20)，初試信息素的分布有利于蟻群提高搜索速度，快速收斂。

為了防止某條路徑的信息素過(guò)高或過(guò)低，避免螞蟻集中在某條路徑上，將每條路徑的信息素設(shè)置上下限為 [τmin,τmax]，當(dāng)該條路徑信息素濃度低于信息素下限時(shí)，將該條路徑信息素設(shè)置為τmin，當(dāng)該條路徑信息素濃度高于信息素上限時(shí)，該條路徑信息素設(shè)置為 τmax，這樣可以避免算法陷入局部最優(yōu)解，當(dāng)蟻群經(jīng)過(guò)一輪迭代后，挑選出最優(yōu)路徑，對(duì)其信息素進(jìn)行更新，加強(qiáng)對(duì)最優(yōu)路徑的利用，當(dāng)所有螞蟻完成一次迭代后，對(duì)路徑上的信息素進(jìn)行全局更新：

為了提高搜索效率，一只螞蟻在一輪迭代中走過(guò)的完整路徑將不被以后的螞蟻所選擇，對(duì)于需要更新信息素的路徑，可以是本輪迭代的最優(yōu)解 ，也可以是全局最優(yōu)解。

2.3 改進(jìn)啟發(fā)函數(shù)

結(jié)合變步長(zhǎng)蟻群算法的優(yōu)點(diǎn)，在直角坐標(biāo)系中，利用蟻群下一步到達(dá)的節(jié)點(diǎn)距離起點(diǎn)至終點(diǎn)連線的長(zhǎng)短，對(duì)啟發(fā)函數(shù)進(jìn)行改進(jìn)，傳統(tǒng)蟻群算法的啟發(fā)函數(shù)為蟻群下一步所選擇的節(jié)點(diǎn)到終點(diǎn)之間距離的倒數(shù)，如式(2)所示，該函數(shù)收斂性不強(qiáng)，且容易使蟻群尋優(yōu)路徑冗長(zhǎng)，改進(jìn)后的啟發(fā)函數(shù)如下：

式中，(xi,yj) 為下一步所選擇節(jié)點(diǎn)的坐標(biāo)，當(dāng)其距離起點(diǎn)至終點(diǎn)對(duì)角線的長(zhǎng)度越小，被選擇概率則越大，與傳統(tǒng)蟻群算法的啟發(fā)函數(shù)相比，改進(jìn)后的啟發(fā)函數(shù)促使移動(dòng)機(jī)器人將下一步選擇的節(jié)點(diǎn)趨近于移動(dòng)機(jī)器人起點(diǎn)到終點(diǎn)連線處，使移動(dòng)機(jī)器人在路徑尋優(yōu)中能更快地找到最優(yōu)解，提高了算法的收斂速度，因此，改進(jìn)后的啟發(fā)函數(shù)作用得到加強(qiáng)，有利于提高算法的收斂速度，提高算法的全局搜索能力。

3 改進(jìn)算法步驟

圖5為變步長(zhǎng)蟻群算法的流程圖，算法的具體步驟如下：

1) 針對(duì)各項(xiàng)相關(guān)參數(shù)進(jìn)行初始化：路徑規(guī)劃的起始點(diǎn)及終點(diǎn)、信息素重要程度參數(shù) α、啟發(fā)因子重要程度參數(shù) β、迭代次數(shù)、螞蟻數(shù)量、信息素?fù)]發(fā)系數(shù)及增強(qiáng)系數(shù)等相關(guān)參數(shù)，建立地圖二維柵格模型，鄰接矩陣模型。

2) 初始化信息素采用不均勻分布，加強(qiáng)起點(diǎn)至終點(diǎn)直線所涉及柵格的信息素濃度，平行的向外衰減；改進(jìn)啟發(fā)式信息矩陣，調(diào)整移動(dòng)機(jī)器人當(dāng)前位置到終點(diǎn)位置的啟發(fā)函數(shù)計(jì)算方法，建立啟發(fā)式信息矩陣。

3) 建立禁忌表以及對(duì)禁忌表初始化，將起點(diǎn)、障礙物節(jié)點(diǎn)、引起死鎖的節(jié)點(diǎn)均加入禁忌表中。

4) 計(jì)算啟發(fā)信息，根據(jù)信息素濃度以及概率公式確定螞蟻下一步可以到達(dá)的節(jié)點(diǎn)，記錄路徑并更新，更新禁忌表。

5) 當(dāng)所有螞蟻完成一次迭代后，保存最優(yōu)路徑，更新信息素及禁忌表，如果沒(méi)有完成一次迭代，則繼續(xù)開始下一只螞蟻路徑尋優(yōu)。

6) 如果螞蟻完成所有迭代次數(shù)，則輸出最優(yōu)路徑及收斂迭代次數(shù)，如果沒(méi)有完成所有迭代次數(shù)，則繼續(xù)開始下一次迭代。

圖 5 變步長(zhǎng)蟻群算法流程Fig. 5 Flow chart of variable step size ant colony algorithm

4 算法仿真

為了驗(yàn)證變步長(zhǎng)蟻群算法的有效性，本文分別在簡(jiǎn)易環(huán)境和復(fù)雜環(huán)境下進(jìn)行仿真對(duì)比，簡(jiǎn)易環(huán)境為 20 ×20 的柵格環(huán)境，對(duì)傳統(tǒng)蟻群算法、本文算法進(jìn)行仿真，與文獻(xiàn)[8]進(jìn)行對(duì)比，復(fù)雜環(huán)境為 3 0×30 的柵格環(huán)境，對(duì)本文算法進(jìn)行仿真，與文 獻(xiàn)[8]進(jìn)行對(duì)比。

4.1 20×20 柵格環(huán)境

在 20×20 的柵格環(huán)境下，對(duì)傳統(tǒng)蟻群算法和本文算法進(jìn)行仿真，其中，路徑規(guī)劃仿真分別如圖6、7所示，實(shí)驗(yàn)數(shù)據(jù)如表1所示，傳統(tǒng)蟻群算法路徑規(guī)劃長(zhǎng)度為30.870 m，文獻(xiàn)[8]算法路徑規(guī)劃長(zhǎng)度為32.1421 m，本文算法路徑規(guī)劃長(zhǎng)度為28.042 m，顯然，本文算法在路徑規(guī)劃方面優(yōu)于文獻(xiàn)[8]算法及傳統(tǒng)蟻群算法，本文算法較文獻(xiàn)[8]算法、傳統(tǒng)蟻群算法的路徑長(zhǎng)度分別縮短了12.76%及9.16%。本文算法提出信息素不均勻分布策略，提高了最優(yōu)路徑上節(jié)點(diǎn)被選擇的概率，通過(guò)節(jié)點(diǎn)距離起點(diǎn)至終點(diǎn)對(duì)角線的距離，改進(jìn)啟發(fā)函數(shù)，提高了算法的全局搜索能力，有效縮短了全局 最優(yōu)路徑的長(zhǎng)度。

圖 6 傳統(tǒng)蟻群算法路徑規(guī)劃(20×20)Fig. 6 Path planning of traditional ant colony algorithm

圖 7 本文算法路徑規(guī)劃(20×20)Fig. 7 Algorithm path planning in this paper

表 1 各算法實(shí)驗(yàn)結(jié)果對(duì)比Table 1 Comparison of experimental results of various algorithms

收斂迭代仿真分別如圖8、9所示，傳統(tǒng)蟻群算法收斂迭代次數(shù)為25次，文獻(xiàn)[8]算法收斂迭代次數(shù)為4次，本文算法收斂迭代次數(shù)為2次，顯然，本文算法在收斂速度方面優(yōu)于文獻(xiàn)[8]算法及傳統(tǒng)蟻群算法，本文算法較文獻(xiàn)[8]算法、傳統(tǒng)蟻群算法的收斂迭代次數(shù)分別減少了50%及92%。圖10為本文算法在該環(huán)境下各代螞蟻?zhàn)顑?yōu)路徑規(guī)劃路線，各代路線集中于起點(diǎn)至終點(diǎn)的連線處，表明信息素不均勻分布的有效作用，在 2 0×20 柵格環(huán)境中，本文算法無(wú)論是在最優(yōu)路徑上還是在收斂速度上，都優(yōu)于其他兩 種算法。

圖 8 傳統(tǒng)蟻群算法收斂曲線Fig. 8 Convergence curve of traditional ant colony algorithm

圖 9 本文算法收斂曲線Fig. 9 Convergence curve of the algorithm presented inthis paper

圖 10 本文算法各代蟻群最優(yōu)路徑規(guī)劃(20×20)Fig. 10 Optimal path planning of each generation of ant colony in this algorithm (20×20)

4.2 3 0×30 柵格環(huán)境

在 30×30 柵格環(huán)境下，采用文獻(xiàn)[8]中的同一個(gè)柵格地圖，對(duì)本文算法進(jìn)行仿真實(shí)驗(yàn)，實(shí)驗(yàn)數(shù)據(jù)如表2所示，本文算法的路徑規(guī)劃如圖11所示，本文算法的最佳路徑長(zhǎng)度為41.961 m，文獻(xiàn)[8]的最佳路徑長(zhǎng)度為45.112 7 m，本文算法較文獻(xiàn)[8]關(guān)于最佳路徑長(zhǎng)度縮短了6.99%，因此，在復(fù)雜柵格環(huán)境下，本文算法依然保持良好的路徑規(guī)劃能力，通過(guò)變步長(zhǎng)蟻群算法，有效地縮短了最優(yōu)路徑長(zhǎng)度，收斂迭代效率如圖12所示，本文算法的收斂迭代次數(shù)為6次，文獻(xiàn)[8]算法的收斂迭代次數(shù)為8次，本文算法較文獻(xiàn)[8]算法關(guān)于收斂迭代次數(shù)減少了25%，柵格地圖越復(fù)雜，本文算法的優(yōu)越性越明顯，各代最優(yōu)路徑規(guī)劃路線如圖13所示，各代路徑規(guī)劃的路線依然集中于起點(diǎn)至終點(diǎn)的連線處，移動(dòng)機(jī)器人將快速的尋找出最優(yōu)路 徑。

表 2 兩種算法實(shí)驗(yàn)結(jié)果對(duì)比Table 2 Comparison of experimental results of various algorithms

圖 11 本文算法路徑規(guī)劃(30×30)Fig. 11 Algorithm path planning in this paper (30×30)

圖 13 本文算法各代蟻群最優(yōu)路徑規(guī)劃(30×30)Fig. 13 Optimal path planning of each generation of ant colony in this algorithm (30×30)

4.3 實(shí)驗(yàn)研究

本文采用自主搭建的移動(dòng)機(jī)器人進(jìn)行實(shí)驗(yàn)驗(yàn)證，如圖14及圖15所示，一個(gè)紙箱代表兩個(gè)正方形障礙物柵格，空白場(chǎng)地為自由柵格，實(shí)驗(yàn)場(chǎng)景為 2 0×20 的柵格環(huán)境，實(shí)驗(yàn)數(shù)據(jù)如表3所示，本文算法路徑規(guī)劃最優(yōu)長(zhǎng)度為3.26 m，移動(dòng)機(jī)器人從起點(diǎn)至終點(diǎn)耗時(shí)13.56 s，傳統(tǒng)蟻群算法路徑規(guī)劃最優(yōu)長(zhǎng)度為5.13 m，耗時(shí)19.67 s，驗(yàn)證了本文算法在移動(dòng)機(jī)器人實(shí)際應(yīng)用中能夠較快地找到最優(yōu)路徑，有效地提高了路徑規(guī)劃的工作 效率。

圖 14 移動(dòng)機(jī)器人起點(diǎn)位置Fig. 14 Starting position of mobile robot

圖 15 移動(dòng)機(jī)器人運(yùn)行過(guò)程Fig. 15 Mobile robot running process

表 3 各算法路徑規(guī)劃實(shí)驗(yàn)數(shù)據(jù)Table 3 Experimental data of path planning for each algorithm

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

傳統(tǒng)蟻群算法在移動(dòng)機(jī)器人路徑規(guī)劃中存在搜索效率低、路徑過(guò)長(zhǎng)、收斂較慢等問(wèn)題，本文在傳統(tǒng)蟻群算法的基礎(chǔ)上引入了變步長(zhǎng)策略對(duì)其進(jìn)行改進(jìn)，擴(kuò)充蟻群可以到達(dá)節(jié)點(diǎn)的集合，在不觸碰障礙物的條件下，從蟻群當(dāng)前位置的相鄰位置擴(kuò)大至全局地圖的任意自由柵格位置，達(dá)到變步長(zhǎng)策略，改進(jìn)信息素分布策略以及調(diào)整啟發(fā)函數(shù)計(jì)算方法，大幅提高本文算法的收斂速度，快速地尋找到最優(yōu)路徑。本文基于變步長(zhǎng)蟻群算法在收斂速度和路徑尋優(yōu)方面有著較好的性能，不僅適用于簡(jiǎn)單柵格環(huán)境，也適用于復(fù)雜的柵格環(huán)境，使本文算法在實(shí)際應(yīng)用場(chǎng)景中得到較好的應(yīng)用，通過(guò)對(duì)整個(gè)地圖狀態(tài)空間的探索點(diǎn)進(jìn)行采樣，能夠增加搜索區(qū)域，適合解決移動(dòng)機(jī)器人在復(fù)雜環(huán)境下的路徑規(guī)劃。