李 海，楊小柳，徐凌樺

（1.中山職業(yè)技術(shù)學院機電工程學院，廣東 中山 528404；2.貴州大學電氣工程學院，貴州 貴陽 550025）

1 引言

當前機器人的應用范圍和應用領(lǐng)域在極速擴張，緩解了人類的工作強度，同時有效提高了工作效率和產(chǎn)品成品率。定位技術(shù)、通信技術(shù)、導航技術(shù)等是機器人工作的關(guān)鍵技術(shù)，其中導航的基礎是路徑規(guī)劃[1]，機器人行駛路徑與機器人安全、工作效率等息息相關(guān)，因此研究導航路徑規(guī)劃意義重大。

導航路徑規(guī)劃問題可以分為兩個問題進行解決：（1）將已知環(huán)境建立為精確的數(shù)學模型，從而將現(xiàn)實工作環(huán)境轉(zhuǎn)化為機器人可識別的數(shù)字環(huán)境，當前使用的方法包括可視圖法、柵格法、人工勢場法等，每種方法在特定環(huán)境下都能取得較好的建模結(jié)果，但是缺點也很明顯，可視圖法無法處理圓形障礙物且耗時較長[2]，人工勢場法存在“目標不可達”“局部最優(yōu)”的先天缺陷[3]，柵格法轉(zhuǎn)彎角大、避障路徑長[4]。（2）在大規(guī)模和復雜環(huán)境下的路徑規(guī)劃算法，常見方法有神經(jīng)網(wǎng)絡、蟻群算法、粒子群算法、遺傳算法及以上算法的改進算法等，文獻[5]將確定性選擇和隨機性選擇融入到蟻群算法中，實現(xiàn)了室內(nèi)機器人的路徑規(guī)劃；文獻[6]在粒子群算法中引入了跳出機制和牽引機制，并將改進算法應用于路徑規(guī)劃中，改善了路徑平滑度，同時降低了路徑長度；文獻[7]使用編輯距離相似度方法對蟻群初始化改進，使用自適應函數(shù)對交叉變異概率改進，節(jié)省了規(guī)劃時間，提高了路徑安全性和平滑性。以上研究成果在自身設定的環(huán)境中取得了較好的路徑規(guī)劃結(jié)果，總的來講，導航路徑規(guī)劃還有兩個方面的問題需要解決：（1）對地圖信息的處理與建模如何兼顧可行域最大與快速搜索問題；（2）單一算法或原始算法存在收斂時間長、局部最優(yōu)、迭代次數(shù)多等問題，設計合適的高線算法是另一需解決問題。

研究了機器人點對點的導航路徑規(guī)劃問題，建立了機器人可識別的蜂巢柵格環(huán)境模型，提出了動態(tài)分組蟻群算法的路徑規(guī)劃方法，此方法兼顧了蟻群在路徑搜索時的多樣性和收斂性，最終能夠降低路徑長度，同時減少算法迭代次數(shù)。

2 改進蜂巢柵格模型

2.1 傳統(tǒng)柵格與蜂巢柵格機理分析與對比

傳統(tǒng)方形柵格分為四叉樹法和八叉樹法，四叉樹法是指機器人立足于當前柵格，能夠選擇的柵格為正上、正下、正左、正右等4 個柵格；八叉樹法是指能夠選擇的柵格除上述四個柵格外，還包括左上、左下、右上、右下等共8 個柵格。以圖1（a）為例，避障時八叉樹法允許從A 點直接運動到C 點，四叉樹法只能從A點到B 點再到C 點，雖然八叉樹法路徑較短，但是路徑安全性遠遠差于四叉樹法，而安全性是機器人工作的首先條件。但是四叉樹法在避障中存在路徑長、轉(zhuǎn)彎角大的問題，為了解決傳統(tǒng)方形柵格存在的問題，提出了改進蜂巢柵格法。

如圖1（b）所示，使用邊長為1 的蜂巢柵格將機器人工作環(huán)境進行分割，這樣柵格與柵格間距離為，圖中黑色柵格為障礙物柵格。機器人為避開障礙物由A’柵格運動到B’柵格再運動到C’柵格，這種運動方式的安全性遠遠優(yōu)于方形柵格的八叉樹法；從避障路徑長度方面來講，蜂巢柵格避開單位長度障礙物行駛的距離為，四叉樹法避開單位長度障礙物行駛距離為，因此避開障礙物過程中，蜂巢柵格的有效路徑比更佳。另外，從A 到C 點避障時，四叉樹法的轉(zhuǎn)彎角為90°，而蜂巢柵格的轉(zhuǎn)彎角僅為30°，遠遠小于四叉樹法，說明蜂巢柵格的避障路徑更加平滑。

圖1 方形柵格與蜂巢柵格Fig.1 Square Grid and Honeycomb Grid

在戶外和外太空，多數(shù)障礙物的二維投影為圓形，對比方形柵格和蜂巢柵格對圓形障礙物的有效面積比，如圖2 所示。單位半徑圓與其外切方形面積比為，與其外切蜂巢形的面積比為，這意味著覆蓋同樣面積的圓形障礙物，蜂巢柵格面積小于方形柵格面積，即蜂巢柵格的有效面積比大于方形柵格。

圖2 有效面積比Fig.2 Valid Area Ratio

由以上分析可知，從避障時的有效路徑比、安全性、轉(zhuǎn)彎角大小、對圓形障礙物覆蓋的有效面積比等多個角度講，蜂巢柵格優(yōu)于傳統(tǒng)的方形柵格，兼顧了路徑的安全性和有效性。

2.2 改進蜂巢柵格

由2.1 節(jié)可知，每個蜂巢柵格被6 個柵格包圍，也即在沒有障礙物的情況下具有6 個柵格可選，在多障礙物的復雜環(huán)境下，尤其是多U 型障礙物的復雜環(huán)境下，使用蟻群算法選擇柵格時，很容易使螞蟻鎖死在U 型障礙物區(qū)域。解決這一問題一般可以從兩個角度出發(fā)：（1）從算法角度出發(fā)，遇到這種情況時令螞蟻原路返回，直至逃出U 型區(qū)域，但是這種方法會嚴重拖慢算法的循環(huán)；（2）從環(huán)境模型角度出發(fā)，建模時就避免此類情況發(fā)生，這種處理方法更加高效，因此針對U 型障礙物問題，提出了改進蜂巢柵格。

如圖3 所示，當某一柵格周圍的5 個柵格全部為障礙物柵格時，則將此柵格設置為障礙物柵格，而后判斷此柵格轉(zhuǎn)化為障礙物柵格后的其他柵格是否需要轉(zhuǎn)化。圖3 中柵格1 周圍的5 個柵格全部為障礙物柵格，則將柵格1 設置為障礙物柵格；柵格1變?yōu)檎系K物柵格后，柵格2 周圍的5 個柵格也全部為障礙物柵格，則再將柵格2 設置為障礙物柵格，如此就能夠從環(huán)境上消除U 型障礙物，避免螞蟻陷入U 型陷阱。

圖3 改進蜂巢柵格Fig.3 Improved Honeycomb Grid

3 ACS 蟻群算法

3.1 路徑選擇概率

在ACS 蟻群算法中，螞蟻由城市到城市的選擇方法使用偽隨機概率進行構(gòu)造[8]，即：

式中：S—螞蟻最終選擇的城市；allowedi—城市i 的可選城市；τij—城市 ij 間的信息素濃度；α—信息素因子；ηij—城市 ij間的啟發(fā)信息，在旅行商問題中設置為城市ij 間距離的倒數(shù)，在這里設置為城市j 與目標點距離；β—啟發(fā)信息因子；q0—（0，1）間的一個常數(shù)；q—（0，1）間的隨機數(shù)；當 q≤q0時使用式（1）中的偽隨機比例公式選擇下一城市j，當q>q0時使用輪盤賭選擇下一城市j，即：

3.2 局部與全局信息素更新

信息素更新方法分為局部信息素更新和全局信息素更新兩種。局部信息素更新是螞蟻每完成一次城市選擇就對相應的路徑信息素進行更新，這種對所有螞蟻走過路徑均進行信息素更新的方法可以減小路徑之間的信息素差異，增強算法的多樣性，提高算法全局搜索能力。局部信息素更新方法為：

式中：ρ—局部信息素揮發(fā)率；τ0—信息素初始值。

全局信息素更新是所有螞蟻完成一次迭代后只對最優(yōu)路徑上的信息素進行更新，這種信息素更新方式會逐漸拉大較優(yōu)路徑與較差路徑上的信息素濃度差距，促進算法收斂，但是卻容易陷入局部最優(yōu)。全局信息素更新方法[9]為：

式中：?—全局信息素揮發(fā)率；Δτij—路徑ij 上信息素增量；Lop—最優(yōu)路徑長度。

4 動態(tài)分組蟻群算法

基本ACS 蟻群算法具有先天缺陷：（1）由于算法前期信息素分布過于均勻，使算法搜索缺少指導性，同時收斂速度極慢；（2）由于信息素的正反饋機制使算法極易陷入局部最優(yōu)，而且越陷越深而無法跳出。為了解決基本ACS 蟻群算法的先天缺陷，做出以下改進：（1）將貓群算法中的分組思想引入到基本ACS 蟻群算法中，同時將貓群算法中的固定比例分組改進為隨迭代次數(shù)的動態(tài)比例分組；（2）將信息素更新改進為全局信息素更新與局部信息素更新相結(jié)合，兼顧全局大范圍搜索與局部小范圍探索；（3）將傳統(tǒng)局部信息素更新方式改進為信息素自適應擴散，促進局部細致搜索。

4.1 引入貓群思想的動態(tài)分組

在貓群算法中，根據(jù)固定的分組比例將貓群分為跟蹤貓和搜索貓兩類，其中跟蹤貓執(zhí)行跟蹤算子，搜索貓執(zhí)行搜索算子，每完成一次算法迭代則再次隨機地按比例將貓群分為2 組[10]。貓群算法的優(yōu)點是采用了貓的搜索和跟蹤兩種行為模式，兼顧了算法的局部細致搜索和大范圍搜索，搜索貓的存在使算法很容易跳出局部最優(yōu)。貓群算法的缺點是使用固定分組比例隨機進行分配，使算法初始時就存在一定比例的跟蹤貓，此時沒有較優(yōu)區(qū)域供跟蹤貓參考，同時此類貓缺乏探索全局的能力，就造成了貓資源的浪費，降低了算法初期的多樣性；而算法后期依然存在一定比例的探索貓，此時算法應該快速地向最優(yōu)區(qū)域靠攏，而此時大范圍的探索沒有太多意義，反而降低了算法收斂速度。

吸取貓群算法的分組優(yōu)點并改進其缺點，提出了動態(tài)分組蟻群算法。將蟻群按照搜索路徑長度分為搜索蟻和跟蹤蟻兩類，其中搜索蟻復雜算法的大范圍搜索，也即算法的多樣性，跟蹤蟻復雜算法的小范圍細致搜索，也即算法的收斂性。當完成一次迭代后，將蟻群進行重新分配，分組比例隨迭代次數(shù)自適應變化，使算法初期蟻群主要為搜索蟻，提高算法多樣性，算法后期蟻群主要為跟蹤蟻，促進算法收斂和提高解的質(zhì)量。

記蟻群規(guī)模為m，在算法中引入動態(tài)分組算子ξ，每當完成一次迭代后按照路徑長度對螞蟻進行排序，將長度較短的前mξ只設置為跟蹤蟻，其余設置為探索蟻。動態(tài)分組算子ξ 隨迭代次數(shù)的變化方法為：

式中：t—當前迭代次數(shù)；tmax—最大迭代次數(shù)。

在分類時，跟蹤蟻來自于路徑較優(yōu)的螞蟻，這意味著跟蹤蟻具有天然的路徑優(yōu)勢，因此設置跟蹤蟻的柵格選擇方式時應加強信息素的引導作用，基于以上思想，將跟蹤蟻的柵格選擇方式設置為：

式中：j—最終選擇的城市，為了實現(xiàn)信息素引導的主導作用，要求參數(shù)設置時有α>β。

探索蟻在分類時便由路徑較差的螞蟻組成，此類螞蟻曾經(jīng)搜索出的路徑和留下的信息素沒有太大參考價值，而為了實現(xiàn)其全局的大范圍探索能力，應削弱信息素對探索蟻的引導作用，而加強啟發(fā)信息的啟發(fā)作用和隨機因素的隨機作用，基于以上思想，將探索蟻的柵格選擇方式設置為式（2），即使用輪盤賭這種較為隨機的柵格選擇方式，同時為了削弱信息素的引導作用，參數(shù)設置時要求α<β。

4.2 全局與局部結(jié)合的信息素更新

經(jīng)前文分析可知，全局信息素更新側(cè)重于加快算法的收斂速度，而局部信息素更新側(cè)重于開發(fā)較優(yōu)子路徑，達到提高路徑多樣性的效果，為了兩者兼顧，將兩者信息素更新方式全部應用于算法中，規(guī)定螞蟻每走一步則進行一次信息素更新，算法每完成一次迭代則進行一次全局信息素更新，全局信息素更新方法與式（4）一致，局部信息素更新方法改進為：

對比式（3）和式（7）可知，改進的局部信息素更新方式比傳統(tǒng)信息素更新方式多了一項此部分信息素是對跟蹤蟻的額外獎勵信息素，當跟蹤蟻立足于柵格i 選擇某一柵格時，就在柵格i 上獎勵一定濃度的信息素，此信息素向其鄰近路徑ij 上擴散，擴散到路徑上的信息素即為。

4.3 信息素自適應擴散方法

基本ACS 算法中，螞蟻之間的協(xié)作機制較少，為了加強螞蟻彼此間的協(xié)作與影響，提出了信息素自適應擴散方法。當跟蹤蟻立足于柵格i 選擇柵格j 時便在柵格i 處留下獎勵信息素，而后信息素以柵格i 為中心，以dij為半徑進行擴散，當半徑范圍內(nèi)沒有柵格時，則獎勵信息素自動散去，當半徑范圍內(nèi)包含柵格時，如圖4 中柵格g，則獎勵信息素在路徑ig 上自適應擴散，且柵格g距離中心柵格i 越近則擴散的信息素濃度越大，獎勵信息素在路徑ig 上的擴散量設置為：

式中：Q—獎勵信息素總量；dij—柵格ij 間距離。

上述獎勵信息素的擴散量在蜂巢柵格環(huán)境下并不適用，在蜂巢柵格環(huán)境下將其改進為：

式中：nfr—蜂巢i 相鄰的可行使柵格數(shù)量。

圖4 信息素擴散方法Fig.4 Pheromone Infusion Method

由信息素的自適應擴散方式可知，獎勵信息素不僅會對后代螞蟻選擇路徑產(chǎn)生影響，同時對當代螞蟻選擇路徑時也會產(chǎn)生一定影響，在一定程度上加強了螞蟻間的合作。另外，當蟻群陷入局部最優(yōu)時，信息素擴散機制可以使局部最優(yōu)路徑的子路徑及附近的較優(yōu)子路徑信息素濃度增加，增加了后代螞蟻選擇較優(yōu)子路徑的概率；同時可選較優(yōu)子路徑較多，也增加了跳出局部最優(yōu)的能力；另外，局部最優(yōu)解附近的較優(yōu)子路徑很大可能是全局最優(yōu)解的一部分路徑，因此信息素自適應擴散方式還有助于提高解的質(zhì)量。

4.4 算法流程

根據(jù)動態(tài)分組策略、信息素更新策略和信息素自適應擴散策略的工作原理，將其融入到基本ACS 蟻群算法中，得到動態(tài)分組蟻群算法的迭代步驟為：

（1）初始化算法參數(shù)，包括蟻群規(guī)模m、算法最大迭代次數(shù)tmax、信息素因子α、啟發(fā)信息因子β 等；

（2）將m 只螞蟻全部放置在起始點；

（3）探索蟻和跟蹤蟻分別按照式（2）和式（6）選擇下一柵格，每行走一步結(jié)合信息素自適應擴散策略進行一次局部信息素更新；

（4）當所有螞蟻到達目標點，進行全局信息素更新，同時按照螞蟻路徑長度進行動態(tài)分組，迭代次數(shù)加1；

（5）判斷是否達到最大迭代次數(shù)，若是輸出最優(yōu)螞蟻，算法結(jié)束；若否則轉(zhuǎn)至（2）直至算法結(jié)束。

5 仿真分析

仿真實驗分為2 個部分，第一部分分析動態(tài)分組蟻群算法在迭代過程中的多樣性變化情況，第二部分比較動態(tài)分組蟻群算法與其他蟻群算法的路徑規(guī)劃性能。

5.1 動態(tài)分組蟻群算法多樣性分析

為了分析將動態(tài)分組策略、信息素更新策略和信息素自適應擴散策略融入蟻群算法后，對算法多樣性的改善情況，分別使用動態(tài)分組蟻群算法和ACS 蟻群算法對TSP 標準數(shù)據(jù)庫中的eil51 算例進行路徑規(guī)劃，算法的參數(shù)設置為：蟻群規(guī)模m=50，信息素因子α=1、啟發(fā)信息因子β=4，局部揮發(fā)系數(shù)ρ=0.1，全局信息素揮發(fā)率?=0.3，q0=0.7，獎勵信息素濃度Q=1，算法最大迭代次數(shù)tmax=2000。統(tǒng)計動態(tài)分組蟻群算法中探索蟻、跟蹤蟻數(shù)量隨迭代過程變化情況，統(tǒng)計探索蟻、跟蹤蟻搜索的不同路徑數(shù)量隨迭代過程變化情況，統(tǒng)計ACS 蟻群算法中螞蟻搜索路徑數(shù)量隨迭代過程的變化情況結(jié)果，如圖5 所示。

圖5 路徑多樣性分析Fig.5 Path Diversity Ananlysis

圖5（a）中探索蟻與跟蹤蟻數(shù)量之和一直為50，與設置的種群規(guī)模一致。圖中跟蹤蟻搜索的路徑數(shù)量與探索蟻搜索的路徑數(shù)量之和即為動態(tài)分組蟻群算法的路徑多樣性。分析圖5（a）可知，算法前期蟻群中以探索蟻為主，利于算法進行大范圍搜索，同時探索蟻使用輪盤賭的選擇方式，非常有利于算法的多樣性。算法后期蟻跟蹤蟻為主，跟蹤蟻以信息素為主導的柵格選擇方式，有利于算法收斂于較優(yōu)的幾條路徑，同時為了防止算法過于收斂，也即為了防止算法的多樣性下降，信息素的自適應擴散方法起到了重要作用，因此算法后期直至迭代至2000 代時，算法多樣性依然很高，螞蟻搜索的路徑數(shù)量為38。分析圖5（b）可知，ACS 蟻群算法前期螞蟻搜索的路徑多樣性與動態(tài)分組蟻群算法相差不大，隨著算法的進行，路徑多樣性逐漸減少，這是多數(shù)螞蟻向較優(yōu)幾條路徑不斷靠攏的結(jié)果，導致隨著算法的進行路徑多樣性不斷下降。因此，動態(tài)分組策略和信息素自適應擴散策略對算法中路徑多樣性的保持具有明顯效果。使用動態(tài)分組蟻群算法對eil51 算例的規(guī)劃結(jié)果，如圖6 所示。

圖6 eil51 算例的最優(yōu)路徑Fig.6 Optimal Path of eil51 Example

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

為了驗證動態(tài)分組蟻群算法在蜂巢柵格環(huán)境下的導航路徑規(guī)劃性能，在圖7 所示蜂巢環(huán)境中分別使用動態(tài)分組蟻群算法和ACS 蟻群算法進行導航路徑規(guī)劃，圖中柵格邊長為1m，柵格與柵格中心間的距離為圖中一種柵格為機器人起點位置，另一種柵格為機器人目標點位置。兩種蟻群算法的最大迭代次數(shù)設置為200，其余參數(shù)與5.1 節(jié)一致，分別使用動態(tài)分組蟻群算法和ACS 蟻群算法在圖7 環(huán)境下進行路徑規(guī)劃，兩種算法各獨立運行 10 次，搜索到的最優(yōu)路徑，如圖7（a）、圖7（b）所示。搜索到最優(yōu)路徑的迭代過程，如圖8 所示。

圖7 兩種算法搜索的最優(yōu)路徑Fig.7 Optimal Path Searched by Two Kind of Algorithms

圖8 最優(yōu)路徑迭代過程Fig.8 Iteration Process of Optimal Path

分析圖7 和圖8 可以看出，動態(tài)分組蟻群算法搜索的最優(yōu)路徑短于ACS 蟻群算法搜索的最優(yōu)路徑，經(jīng)計算，ACS 蟻群算法規(guī)劃的最優(yōu)路徑長度為34.64m，動態(tài)分組蟻群算法規(guī)劃的最優(yōu)路徑長度為31.18m，比ACS 蟻群算法規(guī)劃的路徑長度減少了9.99%。從圖8 的迭代過程可以看出，動態(tài)分組蟻群算法迭代至48 步時路徑長度不再下降，算法搜索到最優(yōu)路徑；而ACS 蟻群算法在迭代過程中的路徑長度一直緩慢下降，直至迭代至120 步時路徑長度趨于穩(wěn)定，而后路徑長度只有極小的下降，這表示動態(tài)分組蟻群算法的尋優(yōu)速度遠遠高于ACS 蟻群算法。以上分析表明，動態(tài)分組蟻群算法在尋優(yōu)質(zhì)量和尋優(yōu)速度都優(yōu)于ACS 蟻群算法，這是因為動態(tài)分組蟻群算法在制定改進策略時既關(guān)注算法的多樣性，也關(guān)注算法的收斂性。通過蟻群的動態(tài)分組，算法前期蟻群主要為搜索蟻，搜索蟻隨機的和啟發(fā)信息主導的搜索方式，極大地增加了算法多樣性，在算法后期蟻群主要為跟蹤蟻，更加注重局部的細致搜索，為了繼續(xù)保持算法多樣性使用了信息素的自適應擴散策略。隨著算法迭代，跟蹤蟻逐漸成為蟻群的主體，以信息素為主導的搜索方式，極大地促進了算法收斂。因此，動態(tài)分組蟻群算法兼顧了算法的多樣性和收斂性，反應在尋優(yōu)性能上就是兼顧了尋優(yōu)質(zhì)量和尋優(yōu)速度。為了分析算法在路徑規(guī)劃中的性能穩(wěn)定性，統(tǒng)計算法10 次獨立運行的參數(shù)，包括最優(yōu)路徑長度、最優(yōu)路徑長度標準差、搜索到最優(yōu)路徑時平均迭代次數(shù)、迭代次數(shù)標準差，結(jié)果如表1 所示。

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

從表1 中可以看出，動態(tài)分組蟻群算法規(guī)劃的最優(yōu)路徑短于ACS 蟻群算法，而且最優(yōu)路徑長度的標準差也遠遠小于ACS蟻群算法，在迭代次數(shù)上也具有同樣的情況。這說明動態(tài)分組蟻群算法的尋優(yōu)精度和尋優(yōu)速度等性能穩(wěn)定性遠遠優(yōu)于ACS 蟻群算法，這是因為動態(tài)分組蟻群算法在整個迭代過程中的路徑多樣性均保持較高水平，使得算法在整個迭代過程中都有較多路徑可選，探索區(qū)域多而廣；而ACS 蟻群算法在迭代過程中路徑多樣性逐漸下降，使得算法的可選路徑較少，因此動態(tài)分組蟻群算法的尋優(yōu)穩(wěn)定性好于ACS 蟻群算法。

6 結(jié)論

研究了機器人點對點的導航路徑規(guī)劃問題，建立了蜂巢柵格環(huán)境模型，提出了動態(tài)分組蟻群算法的規(guī)劃方法。經(jīng)驗證可以得出以下結(jié)論：（1）蜂巢柵格模型的有效路徑比、安全性、轉(zhuǎn)彎角大小、對圓形障礙物覆蓋的有效面積比等多個方面均優(yōu)于方形柵格；（2）通過將動態(tài)分組策略、信息素自適應擴散機制添加到蟻群算法中，兼顧了算法的多樣性和收斂性，提高了算法的尋優(yōu)精度和尋優(yōu)速度；（3）動態(tài)分組蟻群算法通過維持算法迭代過程中的多樣性，使得算法的尋優(yōu)穩(wěn)定性優(yōu)于ACS 蟻群算法。