柵格環(huán)境下機器人導(dǎo)航路徑的雙種群蟻群規(guī)劃

李維維，李建東

（唐山工業(yè)職業(yè)技術(shù)學院自動化工程系，河北唐山 063299）

1 引言

當前，移動機器人廣泛應(yīng)用于工業(yè)生產(chǎn)、軍事偵查、醫(yī)療保健等諸多領(lǐng)域，導(dǎo)航是實現(xiàn)移動機器人智能化的關(guān)鍵技術(shù)之一。路徑規(guī)劃是機器人導(dǎo)航的基礎(chǔ)，主要內(nèi)容是根據(jù)已知的工作環(huán)境設(shè)計一條從起始點到目標點的安全路徑[1]。導(dǎo)航路徑的優(yōu)劣決定了機器人的工作效率和安全性，具有極大的研究價值。

根據(jù)研究重點的不同，機器人路徑規(guī)劃的研究可分為兩個階段。前一階段的研究重點為環(huán)境建模方法，研究成果包括可視圖法[2]、Voronoi圖、柵格法等。可視圖法在1979年提出，由于此方法安全性不高，因此出現(xiàn)了Voronoi圖法，此方法要求路徑與障礙物保持一定距離，因此安全性得到了較大提高[3]。柵格法是環(huán)境建模簡單而有效的方法[4]，其缺點在于障礙物膨脹時損失了部分自由行駛空間。路徑規(guī)劃后一階段的研究重點為智能算法，以前一階段建立的環(huán)境模型為基礎(chǔ)，嘗試將不同的智能算法應(yīng)用于路徑規(guī)劃中。文獻[5]針對遺傳算法在路徑規(guī)劃時初始種群具有盲目性和隨機性的問題，對初始化方法進行了改進，在不同環(huán)境下均得到了較優(yōu)路徑；文獻[6]以農(nóng)田用機器人為研究對象，提出自適應(yīng)蟻群算法的最短路徑規(guī)劃方法，實現(xiàn)了在作物種植區(qū)的路徑優(yōu)化；文獻[7]將路徑最短和轉(zhuǎn)彎次數(shù)最少同時作為規(guī)劃目標，將兩者融入到目標函數(shù)中，使用遺傳算法進行求解，得到了轉(zhuǎn)彎次數(shù)較少的平滑路徑。針對不同使用環(huán)境、使用背景和任務(wù)要求，機器人路徑規(guī)劃目標和所用算法差別較大，因此機器人路徑規(guī)劃在較長時間內(nèi)仍是研究的熱點問題。

研究了移動機器人在柵格環(huán)境下的導(dǎo)航路徑規(guī)劃問題，提出了啟發(fā)式信息素交流異構(gòu)雙種群蟻群算法，使用啟發(fā)式信息素交流方式將蟻群系統(tǒng)和精英螞蟻系統(tǒng)進行有效融合，實現(xiàn)優(yōu)勢互補，將融合算法命名為啟發(fā)式信息素交流雙種群蟻群算法，使用此算法進行柵格環(huán)境下路徑規(guī)劃，縮短了機器人的工作路徑，同時提高了規(guī)劃穩(wěn)定性。

2 兩種基礎(chǔ)算法與優(yōu)勢互補分析

2.1 精英螞蟻系統(tǒng)

精英螞蟻系統(tǒng)（Elite Ant System，EAS）依據(jù)啟發(fā)因子和信息素濃度構(gòu)造選擇概率，算法每完成一次迭代則對最優(yōu)路徑進行額外信息素獎勵。狀態(tài)轉(zhuǎn)移概率為[8]：

式中：p kij(t)—螞蟻k迭代t次時由城市i轉(zhuǎn)移到j(luò)的概率；τij(t)—城市ij間的信息素濃度；α—信息素因子；ηij(t)—城市ij間的啟發(fā)信息；β—啟發(fā)信息因子；allowed i—城市i的可選城市。

完成一次迭代后，對最優(yōu)路徑的信息素濃度進行額外獎勵，更新方法為[9]：

式中：m—螞蟻數(shù)量，Δτk

ij—螞蟻k留下的信息素濃度，e—最優(yōu)路徑獎勵因子，Δτbs

ij—最優(yōu)路徑獎勵的信息素濃度，C bs—最優(yōu)路徑長度，T bs—最優(yōu)路徑。

2.2 蟻群系統(tǒng)

蟻群系統(tǒng)（Ant Colony System，ACS）與精英螞蟻系統(tǒng)的區(qū)別體現(xiàn)在三個方面：一是城市選擇規(guī)則不同，二是全局信息素更新規(guī)則不同，三是增加了局部信息素更新。

在蟻群算法中，下一城市選擇規(guī)則為[10]：

式中：q0∈(0,1)—一個常數(shù)，用于調(diào)節(jié)選擇規(guī)則；q—［0，1］間隨機數(shù)；j—選擇的下一城市；J—使用輪盤賭（即式（1））選擇的下一城市。

蟻群算法的信息素全局更新方法為：

式中：ρ—信息素揮發(fā)率。

全局信息素更新在所有螞蟻完成一次迭代后實施，而局部信息素更新實時完成，螞蟻每走一步則進行一次信息素更新。局部信息素更新為：

式中：τ0—信息素濃度初值。

局部信息素更新可以有效降低不同路徑上的信息素濃度差異，對種群多樣性的保持具有重要意義。

2.3 算法優(yōu)勢分析與優(yōu)勢互補

分析精英螞蟻系統(tǒng)和蟻群系統(tǒng)可以看出，精英螞蟻系統(tǒng)使用的全局信息素更新方法，可以使螞蟻迅速聚集在當前最優(yōu)路徑附近，具有極快的收斂速度。其缺點是螞蟻的多樣性下降較快，且容易陷入局部最優(yōu)路徑。

蟻群系統(tǒng)信息素更新方法為全局更新與局部更新的疊加，局部信息素使用實時更新方法，可以有效降低不同路徑的信息素濃度差別，可以有效保持螞蟻的路徑多樣性。其缺點是算法的收斂速度慢。

由精英螞蟻系統(tǒng)和蟻群系統(tǒng)的優(yōu)缺點分析可以看出，兩種算法在優(yōu)勢上具有極強的互補性，因此可以將這兩種算法進行融合，通過信息交流實現(xiàn)優(yōu)勢共享。

3 啟發(fā)式信息素交流雙種群蟻群算法

為了實現(xiàn)精英螞蟻系統(tǒng)與蟻群系統(tǒng)的優(yōu)勢互補，使用啟發(fā)式信息素交流方式構(gòu)造了異構(gòu)雙種群蟻群算法。算法前期降低兩個種群間的交流頻率，使兩種算法各自進行搜索，可以有效提高路徑多樣性，擴大算法對搜索空間的覆蓋率；算法后期提高種群交流頻率，對路徑上的信息素濃度分布進行交流，強化公共最優(yōu)路徑上的信息素濃度，可以提高算法在后期的收斂性。

3.1 路徑偏離度

算法每完成一步迭代，精英螞蟻系統(tǒng)與蟻群系統(tǒng)都會產(chǎn)生各自的解集，記精英螞蟻系統(tǒng)搜索到的路徑集合為m1=，蟻群系統(tǒng)搜索到的路徑集合為m2=。路徑偏離度定義為當前路徑集合的聚合程度或偏離程度，用于衡量每次迭代完成后路徑與最優(yōu)路徑的偏離程度，即：

式中：σ—路徑偏離度；Cexp—期望路徑長度，在測試函數(shù)中定義為測試庫的最優(yōu)路徑標準值，在路徑規(guī)劃中定義為當前最優(yōu)路徑長度C bs；C i—螞蟻i的路徑長度。

分析式（6）可知，當螞蟻搜索的路徑集中在當前最優(yōu)路徑附近時，路徑聚集程度高，此時σ值較小。當螞蟻搜索的路徑分散度較大，也即路徑多樣性較好時σ值較大。因此可以使用路徑偏離度σ描述路徑的分散程度。算法運行初期，路徑的多樣性好，相對于最優(yōu)路徑的分散程度較高，因此σ值較大；隨著算法運行，當前最優(yōu)路徑上的信息素濃度不斷提高，螞蟻搜索路徑向當前最優(yōu)路徑附近集中，路徑多樣性下降，同時路徑分散程度降低，此時σ值不斷減小且趨于穩(wěn)定。

3.2 種群間啟發(fā)式交流頻率

種群間信息交流頻率對算法性能影響較大，若每完成一步迭代就進行一次信息交流，不僅增加了算法復(fù)雜度，也會造成公共最優(yōu)路徑上信息素濃度的過快積累，極易使算法陷入局部最優(yōu)。

算法前期，兩種算法迭代次數(shù)較少，各自的最優(yōu)路徑參考價值不高，因此應(yīng)該適當降低交流頻率，保持兩個種群各自的多樣性；隨著算法運行，兩種算法均經(jīng)過較為充分的搜索，各自的最優(yōu)路徑具有較大的參考價值，此時應(yīng)適當提高種群間的交流頻率，通過公共最優(yōu)路徑的疊加作用，使算法快速收斂。基于以上考慮，本文提出了啟發(fā)式算法用于調(diào)節(jié)種群間的交流頻率，達到降低算法復(fù)雜度和提高算法性能的目的。啟發(fā)式函數(shù)為：

式中：T—要執(zhí)行的操作；Q—種群間進行信息交流；Qˉ—種群間不進行信息交流；q—（0，1）間隨機數(shù)；k—待定常數(shù)，當優(yōu)化問題規(guī)模較小時，偏離度σ的下降趨勢明顯，此時應(yīng)當設(shè)置較大的k值，當優(yōu)化問題規(guī)模較大時，偏離度σ的下降趨勢緩慢，此時應(yīng)設(shè)置較小的k值調(diào)節(jié)Q的發(fā)生概率。

分析式（7）可以看出，算法前期路徑分散程度較大，偏離度σ值較大，信息交流發(fā)生的概率較小，兩種算法各自按照自身模式搜索，使更多路徑被螞蟻探索，非常有利于路徑多樣性的保持和算法復(fù)雜度的降低。隨著算法運行，兩種算法各自搜索的路徑價值較高，σ值不斷減小，信息交流頻率增加，具有價值的路徑信息在種群間進行交流，公共最優(yōu)路徑的信息素濃度疊加，對算法收斂具有重要作用。

3.3 種群間信息交流方式

種群間信息交流方式多種多樣，本文為了充分發(fā)揮精英螞蟻系統(tǒng)和蟻群系統(tǒng)各自的優(yōu)勢，實現(xiàn)兩種算法之間的優(yōu)勢互補，設(shè)計了種群間信息素交流方式為：

根據(jù)前文的分析，精英螞蟻系統(tǒng)在算法前期的搜索性能較強，且算法的收斂速度較快，式（8）將這兩個優(yōu)勢有效融入到了蟻群系統(tǒng)中。分析式（8）可知，算法前期σ值較大，因此大概率地使用精英螞蟻系統(tǒng)的最優(yōu)路徑信息素濃度替換蟻群系統(tǒng)的一個隨機路徑濃度，使精英蟻群算法的優(yōu)質(zhì)解給蟻群系統(tǒng)提供參考。隨著算法迭代，兩個算法的最優(yōu)路徑重合度越來越高，σ值也逐漸減小，大概率地使用精英螞蟻系統(tǒng)的最優(yōu)解替換蟻群系統(tǒng)的最差解，實現(xiàn)了公共最優(yōu)路徑的信息素濃度疊加，可以有效加快算法收斂。因此式（8）有效的將精英螞蟻系統(tǒng)的優(yōu)勢融入到了蟻群系統(tǒng)中。

3.4 啟發(fā)式信息素交流雙種群蟻群算法流程

結(jié)合精英螞蟻算法與蟻群算法的運行原理，將啟發(fā)式信息素交流方式融入其中，得到啟發(fā)式信息素交流雙種群蟻群算法（Heuristic Pheromone Communication Two Population Ant Colony Algorithm，HEC—TPAC）流程為：

Step1：初始化算法參數(shù)，包括種群規(guī)模m、最大迭代次數(shù)tmax、信息素因子α、啟發(fā)信息因子β、揮發(fā)系數(shù)ρ、常數(shù)q0；

Step2：精英螞蟻系統(tǒng)和蟻群系統(tǒng)根據(jù)自身規(guī)則進行路徑搜索，每完成一次迭代則計算路徑偏離度，而后根據(jù)式（7）判斷是否執(zhí)行信息素交流，若需要進行信息素交流則進入Step3，否則轉(zhuǎn)至

Step4；

Step3：根據(jù)式（8）確定進行信息素交流的方式；

Step4：判斷是否達到最大迭代次數(shù)，若否則轉(zhuǎn)至Step2；若是則輸出最優(yōu)路徑，算法結(jié)束。

4 雙種群蟻群算法性能分析與測試

4.1 測試集確定及參數(shù)設(shè)置

為了檢驗啟發(fā)式信息素交流雙種群蟻群算法的性能，使用標準TSP測試集的函數(shù)對算法性能進行檢驗。性能測試實驗環(huán)境為：Windows 7操作系統(tǒng)，Intel酷睿i5處理器，2.5Hz主頻，4G內(nèi)存，仿真軟件為Matlab R2018a。

從標準TSP測試集中隨機選擇3個中小規(guī)模城市作為測試案例，分別為KroA100、D198、KroB200。為了形成對比效果，分別使用雙種群蟻群算法（HEC—TPAC）、精英螞蟻系統(tǒng)（EAS）、蟻群系統(tǒng)（ACS）進行旅行商路徑規(guī)劃。為了防止隨機性影響，三種算法對三個測試案例分別進行15次路徑規(guī)劃。三種算法的參數(shù)設(shè)置，如表1所示。

表1 算法參數(shù)Tab.1 Algorithm Parameters

4.2 測試結(jié)果分析

首先將三種算法對三個測試案例的最優(yōu)規(guī)劃結(jié)果迭代過程以圖片形式給出，如圖1所示。

從圖1中三種測試案例的路徑規(guī)劃結(jié)果可以得出以下結(jié)論：（1）三種算法中，精英螞蟻系統(tǒng)在算法前期的收斂速度最快，且算法極易陷入局部最優(yōu)，這是因為精英螞蟻系統(tǒng)對全局最優(yōu)路徑額外的信息素獎勵，使算法具有較快的收斂速度，但是也容易陷入局部最優(yōu)；（2）蟻群系統(tǒng)的規(guī)劃質(zhì)量一般優(yōu)于精英螞蟻系統(tǒng)，但是收斂速度差于精英螞蟻系統(tǒng)，這是因為螞蟻系統(tǒng)的信息素局部更新方法有利于保持路徑多樣性，但是也導(dǎo)致了收斂速度較慢；（3）三種測試案例中，雙種群蟻群算法規(guī)劃的路徑最短，從收斂速度看，接近于精英蟻群算法，從這個角度講，雙種群蟻群算法有效融合了精英螞蟻系統(tǒng)和蟻群系統(tǒng)的優(yōu)勢。

圖1 測試案例規(guī)劃結(jié)果Fig.1 Planning Result of Testing Case

為了進一步分析雙種群蟻群算法的性能，統(tǒng)計三種算法對三種測試案例的最優(yōu)解、平均解、平均迭代次數(shù)，如表2所示。在此給出三個測試案例的路徑最優(yōu)解實際值，KroA100最優(yōu)路徑長度實際值為21282，D198最優(yōu)路徑長度為15780，KroB200最優(yōu)路徑長度為29437。

分析表2中數(shù)據(jù)，從最優(yōu)解誤差看，HEC—TPAC算法規(guī)劃的路徑質(zhì)量最高，與最優(yōu)路徑實際值的誤差最小；從路徑平均值看，HEC—TPAC算法規(guī)劃的路徑長度平均值最接近最優(yōu)路徑實際值，說明HEC—TPAC算法的路徑規(guī)劃穩(wěn)定性最高；從平均迭代次數(shù)看，三種算法的收斂迭代次數(shù)相差不大，精英螞蟻系統(tǒng)收斂次數(shù)最少，雙種群蟻群算法與其幾乎相當，螞蟻系統(tǒng)平均收斂次數(shù)最大。以上分析結(jié)果表明，HEC—TPAC算法有效融合了精英螞蟻系統(tǒng)和蟻群系統(tǒng)的優(yōu)勢，不僅具有最高的規(guī)劃路徑質(zhì)量，而且算法穩(wěn)定性最高。

表2 三種測試案例規(guī)劃統(tǒng)計Tab.2 Planning Result Statics of Three Testing Case

5 移動機器人路徑規(guī)劃

5.1 柵格環(huán)境模型

首先建立機器人能夠識別的環(huán)境模型，而后使用雙種群蟻群算法進行路徑規(guī)劃。柵格環(huán)境模型原理簡單、易于實現(xiàn)。使用一定大小的柵格對工作環(huán)境進行分割，當柵格中具有障礙物時則將柵格屬性賦值為1，不存在障礙物的柵格屬性賦值為0。當柵格中存在障礙物但未充滿時，使用膨脹法使其占滿一個柵格。此方法可將抽象的工作環(huán)境轉(zhuǎn)化為機器人可識別的0—1矩陣。

如圖2所示的某一工作環(huán)境，圖中黑色區(qū)域為障礙物分布區(qū)域，使用柵格法得到的0—1矩陣模型為：

圖2 真實工作環(huán)境Fig.2 Real Working Environment

使用雙種群蟻群算法進行路徑規(guī)劃時，將所有螞蟻放置于起始點，使用式（1）或式（3）計算選擇周圍相鄰“0”屬性柵格的概率，并依據(jù)各自規(guī)則確定最終選擇的0屬性柵格；而后立足于當前柵格，再次依據(jù)式（1）或式（3）選擇周圍相鄰“0”屬性柵格，直至到達目標點。在此需要強調(diào)的是，在旅行商問題中，式（1）和式（3）中的ηij(t)表示城市i j間距離的倒數(shù)，但是在機器人路徑規(guī)劃中表示城市j與目標點間距離的倒數(shù)，從而使目標點對螞蟻的移動具有引力作用。

5.2 路徑規(guī)劃性能驗證

為了檢驗啟發(fā)式信息素交流雙種群蟻群算法在柵格環(huán)境中的路徑規(guī)劃性能，設(shè)計了兩種20×20柵格規(guī)模下的工作環(huán)境，兩種工作環(huán)境主要區(qū)別體現(xiàn)在障礙物形狀方面。由前文分析可知，精英蟻群系統(tǒng)極易陷入局部最優(yōu)，規(guī)劃能力最弱，因此本節(jié)使用蟻群系統(tǒng)和雙種群蟻群算法兩種算法進行規(guī)劃并比較。兩種算法對兩種工作環(huán)境各自獨立規(guī)劃10次，選擇兩個算法規(guī)劃的最優(yōu)路徑進行展示結(jié)果，如圖3所示。

圖3 兩種工作環(huán)境下的規(guī)劃結(jié)果Fig.3 Planning Result under the Two Environments

從圖3中可以直觀地看出，啟發(fā)式信息素交流雙種群蟻群算法規(guī)劃的路徑優(yōu)于蟻群系統(tǒng)，為了進一步比較算法穩(wěn)定性和收斂速度，統(tǒng)計兩種算法在兩種工作環(huán)境下的最優(yōu)解、平均解、路徑方差、收斂次數(shù)（搜索到最優(yōu)解時的迭代次數(shù)），如表3所示。

表3 路徑規(guī)劃統(tǒng)計結(jié)果Tab.3 Path Planning Statistics Result

從表3中數(shù)據(jù)可以看出，在環(huán)境一中，HEC—TPAC算法的最優(yōu)路徑比ACS算法的最優(yōu)路徑縮短了5.57%；在環(huán)境二中，HEC—TPAC算法的最優(yōu)路徑比ACS算法的最優(yōu)路徑縮短了3.34%，說明HEC—TPAC算法的規(guī)劃能力明顯優(yōu)于ACS算法。從路徑方差看，HEC—TPAC算法在兩種環(huán)境下的方差均遠小于ACS算法，說明HEC—TPAC算法的規(guī)劃穩(wěn)定性極好。從收斂次數(shù)看，HEC—TPAC算法與ACS算法相差不大，但是HEC—TPAC算法略有優(yōu)勢，說明HEC—TPAC算法收斂速度略優(yōu)于ACS算法。

綜合以上分析可以看出，HEC—TPAC算法的規(guī)劃質(zhì)量、規(guī)劃穩(wěn)定性遠優(yōu)于ACS算法，收斂速度略優(yōu)于ACS算法。

6 結(jié)論

研究了柵格環(huán)境下移動機器人的導(dǎo)航路徑規(guī)劃問題，提出了啟發(fā)式信息素交流異構(gòu)雙種群蟻群算法，構(gòu)造了基于此算法的路徑規(guī)劃方法。經(jīng)性能測試和路徑規(guī)劃性能檢驗，得出了以下結(jié)論：（1）啟發(fā)式信息素交流方式可以有效融合蟻群系統(tǒng)和精英螞蟻系統(tǒng)的優(yōu)勢；（2）啟發(fā)式信息素交流異構(gòu)雙種群蟻群算法的規(guī)劃能力、規(guī)劃穩(wěn)定性優(yōu)于蟻群系統(tǒng)和精英螞蟻系統(tǒng)。