趙高杰魯守銀袁魯浩

(山東建筑大學(xué) 信息與電氣工程學(xué)院，山東 濟(jì)南 250101)

0 引言

機(jī)器人路徑規(guī)劃一直是機(jī)器人領(lǐng)域的關(guān)鍵技術(shù)之一，其是指移動(dòng)機(jī)器人在特定環(huán)境中，找出一條連接起點(diǎn)與終點(diǎn)的最佳路徑[1]。路徑規(guī)劃算法具有代表性的有A*(A-Star Search Method， A*)法[2]、快速擴(kuò)展隨機(jī)樹(shù)(A Rapidly Exploring Random Tree，RRT)法[3]、人工勢(shì)場(chǎng)法[4]、神經(jīng)網(wǎng)絡(luò)算法[5]等。除此之外，還有大量仿生算法，如粒子群算法[6]、遺傳算法[7]、蟻群算法[8]等。其中，蟻群算法的應(yīng)用最廣泛，主要是因?yàn)槠渚哂姓答伈呗浴?yōu)效果好等優(yōu)點(diǎn)。

蟻群算法是根據(jù)螞蟻搜尋食物行為設(shè)計(jì)提出的，已證明具有很多優(yōu)點(diǎn)，但同時(shí)也具有穩(wěn)定性不強(qiáng)、容易陷入局部收斂等不足。因此，在此基礎(chǔ)之上，學(xué)者們?cè)O(shè)計(jì)了諸多不同的蟻群算法改進(jìn)方案。2021年，SANGEETHA 等[9]引入了一種基于能量?jī)?yōu)化的蟻群算法，考慮到規(guī)劃的路徑與消耗的能量是一一對(duì)應(yīng)的，改進(jìn)了增益函數(shù)的信息素增強(qiáng)機(jī)制，減少了動(dòng)態(tài)場(chǎng)景中路徑規(guī)劃過(guò)程消耗的總能量，從而起到路徑優(yōu)化的效果。然而，其本質(zhì)仍為傳統(tǒng)的蟻群算法，僅映射了問(wèn)題，其收斂性和最優(yōu)解情況仍有待提升。而MASOUMI 等[10]則考慮到地理信息系統(tǒng)中用戶(hù)的需求，改進(jìn)了蟻群算法目標(biāo)函數(shù)，可適應(yīng)不同優(yōu)先級(jí)的多目標(biāo)優(yōu)化問(wèn)題。這種方法有利于提升用戶(hù)的體驗(yàn)性， 但其迭代次數(shù)仍較多。ABDULAKAREEM 等[11]則引入了基于概率路線圖和三次樣條插值的改進(jìn)蟻群算法，分別采樣目標(biāo)點(diǎn)、構(gòu)造路線圖，隨后使用蟻群算法優(yōu)化，并使用三次樣條插值進(jìn)行平滑并降低路徑長(zhǎng)度從而獲得最優(yōu)路徑，然而由于環(huán)節(jié)較多，因此計(jì)算量較大、搜索時(shí)間長(zhǎng)。高茂源等[12]提出了一種基于環(huán)境改進(jìn)的蟻群算法，其基于柵格環(huán)境選擇機(jī)器人的步長(zhǎng)，改進(jìn)信息素?fù)]發(fā)因子，使其尺寸分布服從高斯分布，從而加快了改進(jìn)后蟻群算法的收斂效率，但對(duì)原始數(shù)據(jù)的分布具有較嚴(yán)格的要求，從而其應(yīng)用場(chǎng)合較為有限。此外，徐玉瓊等[13]為改進(jìn)傳統(tǒng)蟻群算法穩(wěn)定性不足的問(wèn)題，設(shè)計(jì)了一種自適應(yīng)蟻群算法，能夠依據(jù)算法中解的分布情況，動(dòng)態(tài)地更新調(diào)節(jié)信息素；同時(shí)在多步長(zhǎng)選擇模型中選取最佳步長(zhǎng)，提升算法全局搜索性能，但不足在于沒(méi)有考慮移動(dòng)機(jī)器人實(shí)際工作環(huán)境的高度因素。

綜上所述，目前對(duì)改進(jìn)蟻群算法的研究仍存在未觸及蟻群算法內(nèi)部環(huán)節(jié)和本質(zhì)、應(yīng)用場(chǎng)合受限、未考慮移動(dòng)機(jī)器人實(shí)際工作環(huán)境等問(wèn)題。針對(duì)上述問(wèn)題，文章基于移動(dòng)機(jī)器人實(shí)際的工作環(huán)境，提出了一種改進(jìn)的變步長(zhǎng)蟻群算法，主要設(shè)計(jì)了一種不定步長(zhǎng)的選擇模型，同時(shí)針對(duì)移動(dòng)機(jī)器人實(shí)際運(yùn)行時(shí)可能出現(xiàn)坡度大的環(huán)境，在啟發(fā)函數(shù)中引入高度信息。另外，改進(jìn)了算法中信息素更新模型，采用動(dòng)態(tài)揮發(fā)系數(shù)，以提升算法尋優(yōu)效率。

1 移動(dòng)機(jī)器人路徑規(guī)劃的環(huán)境建模

機(jī)器人路徑規(guī)劃問(wèn)題指的是在特定的約束下，搜尋出一條最佳路徑，由式(1)表示為

式中f(p)為路徑的目標(biāo)函數(shù)；ps、po分別為起始點(diǎn)和目標(biāo)點(diǎn)；Γ(ps，po)為起終點(diǎn)之間的路徑節(jié)點(diǎn)集合。

機(jī)器人路徑規(guī)劃中常見(jiàn)的建模方法主要有柵格地圖、三維仿真地圖、拓?fù)鋱D等。其中，柵格地圖容易構(gòu)建且易于維護(hù)，因此選定柵格圖作為研究移動(dòng)機(jī)器人建模的環(huán)境。柵格的粒徑由移動(dòng)機(jī)器人的規(guī)格決定，其大小必須可以容納移動(dòng)機(jī)器人自由運(yùn)行且保持柵格邊界與移動(dòng)機(jī)器人一定的安全距離。在柵格圖中用黑色和白色部分分別代表不可行區(qū)域和可自由通行區(qū)域。為保障移動(dòng)機(jī)器人的工作安全，假定移動(dòng)機(jī)器人工作時(shí)不能沿著障礙物邊緣及頂點(diǎn)行走。另外，如果障礙物不足一個(gè)柵格時(shí)，則將其膨化為一個(gè)柵格。

機(jī)器人柵格環(huán)境模型如圖1 所示，其中黑色區(qū)塊為障礙物，白色區(qū)塊為機(jī)器人可行走的區(qū)域。通過(guò)設(shè)定柵格圖的柵格號(hào)從下至上、從左到右都分別遞增。柵格地圖規(guī)格為m行n列，柵格號(hào)和柵格粒徑分別為N和1，每個(gè)柵格的中心點(diǎn)位置坐標(biāo)(x，y)可由式(2)表示為

圖1 柵格模型圖

式中mod 為取余操作；int 為求整。

2 移動(dòng)機(jī)器人路徑規(guī)劃蟻群算法改進(jìn)

2.1 傳統(tǒng)蟻群算法

蟻群算法是模仿蟻群尋找食物的行動(dòng)模式而設(shè)計(jì)的算法。蟻群在搜尋食物時(shí)會(huì)在路徑上分泌不等的信息素，而信息素的多少跟路徑距離有關(guān)。其他的個(gè)體則會(huì)根據(jù)路徑上信息素的濃度做出相應(yīng)決策，最終蟻群將逐步地聚攏在最短路徑上。

個(gè)體在尋優(yōu)迭代過(guò)程中的第t次，由節(jié)點(diǎn)i轉(zhuǎn)移至節(jié)點(diǎn)j的概率計(jì)算公式由式(3)表示為

式中n為個(gè)體序號(hào)；i和j分別為當(dāng)前節(jié)點(diǎn)和下一節(jié)點(diǎn)；s為所允許的轉(zhuǎn)移起始節(jié)點(diǎn)；allowedi為所允許的點(diǎn)坐標(biāo)集合；τ為信息素濃度；η為啟發(fā)函數(shù)；α、β分別為信息素和啟發(fā)式預(yù)期值；U為個(gè)體可搜尋柵格的集合。其中，節(jié)點(diǎn)i、j之間的距離d(i，j)由式(4)表示為

而在算法尋優(yōu)時(shí)，環(huán)境中信息素更新公式由式(5)和(6)表示為

式中ρ為信息素?fù)]發(fā)因子；Q為信息素強(qiáng)度；Ln為序號(hào)為n的個(gè)體走過(guò)的總路程；K為蟻群中個(gè)體總數(shù)；V為序號(hào)為n的個(gè)體走過(guò)柵格的集合。

2.2 基于傳統(tǒng)蟻群算法的啟發(fā)函數(shù)優(yōu)化

傳統(tǒng)蟻群算法中，啟發(fā)函數(shù)只和路徑長(zhǎng)度有關(guān)，只能保證距離因素，無(wú)法適應(yīng)真實(shí)工作環(huán)境中高度不定的情形。因此對(duì)啟發(fā)函數(shù)進(jìn)行改進(jìn)，由式(7)表示為

式中v為高度因素，其多元函數(shù)形式由式(8)表示為

式中h為環(huán)境中柵格的高度矩陣；λ和σ為高度調(diào)節(jié)常數(shù)；hmin、hmax分別為相鄰柵格中與當(dāng)前柵格的最小、最大高度差，m；C為常數(shù)，C＝0.001，保證在最小、最大高度差相等時(shí)分母不為零。

2.3 基于傳統(tǒng)蟻群算法的信息素更新機(jī)制改進(jìn)

2.3.1 信息素增量

為更加真實(shí)地模擬機(jī)器人可能遇到的具有高度起伏的工作環(huán)境，加入了高度啟發(fā)因素，因此對(duì)信息素增量公式做修正，由式(9)和(10)表示為

式中Zn(t)為路徑的綜合指標(biāo)；Sn(t)為路徑長(zhǎng)度，m；Hn(t)為路徑的轉(zhuǎn)彎次數(shù)，路徑的綜合指標(biāo)越低，說(shuō)明路徑越平直，路徑的收斂性和優(yōu)化程度越高。

2.3.2 揮發(fā)系數(shù)

傳統(tǒng)蟻群算法中揮發(fā)系數(shù)自始至終都是維持不變的，無(wú)法適應(yīng)實(shí)際環(huán)境。因此，為提升改進(jìn)算法的全局性，提出一種自適應(yīng)策略，在搜索前期增大ρ的值，加快收斂，而在后期減小其值，增強(qiáng)算法全局性。具體公式由式(11)表示為

式中a、b均為常數(shù)；ρmax、ρmin分別為揮發(fā)系數(shù)最大及最小值。

2.3.3 限定信息素范圍

在蟻群算法的優(yōu)化迭代過(guò)程中，設(shè)定路徑上的信息素取值由式(12)表示為

通過(guò)范圍限制，豐富了結(jié)果的多樣性，從而可以提升算法的尋優(yōu)效率。

2.4 基于傳統(tǒng)蟻群算法的變步長(zhǎng)選擇策略改進(jìn)

傳統(tǒng)蟻群算法中采用的是單步移動(dòng)的模式，且轉(zhuǎn)移的方向只能為0°、±45°、±90°、±135°、180°共8個(gè)角度。在傳統(tǒng)的單步長(zhǎng)移動(dòng)模式下，其路徑距離更長(zhǎng)，且轉(zhuǎn)折次數(shù)也更多。因此，采用變步長(zhǎng)移動(dòng)機(jī)制，此時(shí)個(gè)體在進(jìn)行移動(dòng)時(shí)不再局限于單步長(zhǎng)，且每一步的移動(dòng)方向可以任意選擇，從而減短路徑距離，此兩種步長(zhǎng)模式對(duì)比圖如圖2 所示。

圖2 兩種步長(zhǎng)模式對(duì)比圖

變步長(zhǎng)移動(dòng)機(jī)制具體方案為:

先利用改進(jìn)的蟻群算法搜尋出單步長(zhǎng)模式下最佳路徑，如圖2 中的虛線所示，再次對(duì)此路徑進(jìn)行規(guī)劃，即將當(dāng)前柵格與下一柵格直接相連，判斷路徑是否遇到障礙物，若沒(méi)有則接著尋找下一個(gè)柵格，直至碰撞障礙區(qū)域。此時(shí)形成的柵格節(jié)點(diǎn)連線為最優(yōu)路徑，如圖2 中實(shí)線所示，可以看出變步長(zhǎng)選擇策略模式下路徑距離更短且轉(zhuǎn)折次數(shù)更少。

2.5 改進(jìn)變步長(zhǎng)蟻群算法流程

基于算法的相關(guān)分析，改進(jìn)變步長(zhǎng)蟻群算法相應(yīng)的執(zhí)行流程示意如圖3 所示。

圖3 算法流程圖

其步驟主要為

(1)建立柵格地圖環(huán)境，設(shè)置算法參數(shù)初始值；

(2)設(shè)置起始及目標(biāo)位置，初始化信息素；

(3)采用變步長(zhǎng)移動(dòng)策略，根據(jù)式(3)計(jì)算轉(zhuǎn)移概率，得到下一節(jié)點(diǎn)坐標(biāo)。而在本輪迭代結(jié)束后，則需要根據(jù)式(9)～(11)更新算法中的信息素；

(4)判斷本次迭代是否結(jié)束，如果結(jié)束繼續(xù)執(zhí)行，否則需要重新計(jì)算下一節(jié)點(diǎn)坐標(biāo)；

(5)判斷算法是否超過(guò)迭代次數(shù)最大值，如果是，則輸出最優(yōu)路徑，否則繼續(xù)下輪迭代。

3 蟻群算法實(shí)驗(yàn)仿真及分析

為了驗(yàn)證所提出的變步長(zhǎng)蟻群算法在機(jī)器人路徑規(guī)劃上的有效性，通過(guò)數(shù)學(xué)軟件MATLAB 評(píng)價(jià)改進(jìn)后蟻群算法在路徑規(guī)劃上的可行性和高效性，并與張曉莉等[14]使用的傳統(tǒng)蟻群算法、WANG 等[15]提出的基于粒子群優(yōu)化 (Particle Swarm Optimization， PSO)改進(jìn)的蟻群算法進(jìn)行對(duì)比。在仿真測(cè)試中，建立了二維柵格地圖[16]，其中柵格環(huán)境模型的尺寸為30 m×30 m。實(shí)驗(yàn)中二維柵格地圖的參數(shù)設(shè)置為:單位柵格長(zhǎng)度為1 m、總長(zhǎng)30 m，機(jī)器人起始坐標(biāo)為(0.5，0.5)、終點(diǎn)為(29.5，29.5)。

在性能對(duì)比實(shí)驗(yàn)的算法參數(shù)中，設(shè)置個(gè)體數(shù)目(m值)為50，算法的迭代最大次數(shù)為50 次，信息素重要程度因子α、啟發(fā)函數(shù)重要程度因子β、信息素增加強(qiáng)度系數(shù)Q和信息素?fù)]發(fā)系數(shù)ρ分別設(shè)為1、3.2、1.1 和0.6，揮發(fā)系數(shù)的閾值ρmin和ρmax分別為0.01和0.8。選取hmax＝0.4 m、hmin＝0 m。高度調(diào)節(jié)因子選為λ ＝0.5、σ ＝0.5。除此之外，3 種算法所設(shè)定的其他參數(shù)都使用相同的參數(shù)設(shè)置。

對(duì)傳統(tǒng)蟻群算法、PSO 優(yōu)化蟻群算法以及改進(jìn)蟻群算法在相同的二維柵格地圖進(jìn)行仿真測(cè)試，所得到的路徑結(jié)果如圖4 所示，其中的綠色部分表示柵格上的高度分布情況。而3 種算法在相同的二維柵格地圖路徑規(guī)劃過(guò)程中的路徑長(zhǎng)度、轉(zhuǎn)彎次數(shù)及綜合指標(biāo)對(duì)比結(jié)果如圖5～7 所示。

圖4 傳統(tǒng)蟻群算法、PSO 優(yōu)化蟻群算法和改進(jìn)變步長(zhǎng)蟻群算法在相同二維柵格地圖路徑結(jié)果圖

圖5 3 種算法在相同的二維柵格地圖路徑長(zhǎng)度對(duì)比圖

由圖4～6 可知，傳統(tǒng)蟻群算法及PSO 優(yōu)化蟻群算法的移動(dòng)機(jī)器人路徑規(guī)劃方法的避障能力不足，使得機(jī)器人移動(dòng)過(guò)程中產(chǎn)生了一些冗余的路徑，且需要多次迭代才可找出最優(yōu)路徑，迭代次數(shù)達(dá)到設(shè)定的最大迭代次數(shù)時(shí)，其最少轉(zhuǎn)彎次數(shù)均＞10 次、最小路徑長(zhǎng)度為47 m。相對(duì)比之下，由于轉(zhuǎn)彎方向的任意選擇性，改進(jìn)變步長(zhǎng)蟻群算法規(guī)劃所得出的路徑的避障效果較好，路徑較為平直，最優(yōu)路徑僅需要9 次轉(zhuǎn)彎，最優(yōu)路徑長(zhǎng)度為44 m，相比于其他二者減小了3 m。

圖6 3 種算法在相同的二維柵格地圖轉(zhuǎn)彎次數(shù)對(duì)比圖

若綜合考慮算法的收斂性和效率，如圖7 所示，可發(fā)現(xiàn)改進(jìn)變步長(zhǎng)蟻群算法的收斂效率相比于PSO優(yōu)化蟻群算法提升了72%，比傳統(tǒng)蟻群算法提升了84%。此外，改進(jìn)變步長(zhǎng)蟻群算法的綜合指標(biāo)相比于傳統(tǒng)蟻群算法減少了33%，比PSO 優(yōu)化蟻群算法減少了12%，也就是說(shuō)其路徑規(guī)劃的效率和綜合效果是最佳的。

圖7 3 種算法在相同的二維柵格地圖綜合指標(biāo)對(duì)比圖

綜合以上評(píng)價(jià)指標(biāo)的實(shí)驗(yàn)結(jié)果可以看出，在蟻群算法基礎(chǔ)上提出的基于變步長(zhǎng)蟻群算法的移動(dòng)機(jī)器人路徑規(guī)劃方法，在路徑長(zhǎng)度、轉(zhuǎn)彎次數(shù)及綜合效果等常用的路徑規(guī)劃評(píng)價(jià)指標(biāo)方面，對(duì)比于傳統(tǒng)的蟻群算法和PSO 優(yōu)化蟻群算法的路徑規(guī)劃方法都具有更明顯的優(yōu)勢(shì)。

4 結(jié)論

在傳統(tǒng)蟻群算法基礎(chǔ)上，提出了在移動(dòng)機(jī)器人路徑規(guī)劃上應(yīng)用的一種改進(jìn)變步長(zhǎng)的蟻群算法，并對(duì)比了傳統(tǒng)蟻群算法及粒子群優(yōu)化蟻群算法，經(jīng)過(guò)分析得出以下結(jié)論:

(1)在蟻群的啟發(fā)函數(shù)中增加了高度分布函數(shù)，表征機(jī)器人移動(dòng)的高度起伏。仿真結(jié)果表明，改進(jìn)變步長(zhǎng)蟻群算法對(duì)高度函數(shù)具有穩(wěn)定性，規(guī)劃出的路徑規(guī)避了高度起伏較大的區(qū)域，并保證了一定的平直性，其轉(zhuǎn)彎次數(shù)僅為9 次，相對(duì)于傳統(tǒng)蟻群算法及PSO 優(yōu)化蟻群算法提升了約45%。

(2)改進(jìn)變步長(zhǎng)蟻群算法增加了長(zhǎng)度和方向的選擇特性，可提供根據(jù)環(huán)境不同而改變自身步長(zhǎng)的搜索模式，總路徑長(zhǎng)度相比于其他二者算法減少了約5%。

(3)在收斂性和尋優(yōu)效率方面，仿真結(jié)果表明改進(jìn)變步長(zhǎng)蟻群算法收斂所需的迭代次數(shù)僅需8 ～10 次，相比于其他二者減少了5～15 次，路徑綜合指標(biāo)提升了約30%。