李 海，楊小柳，徐凌樺

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

1 引言

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

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

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

2 改進(jìn)蜂巢柵格模型

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

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

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

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

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

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

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

2.2 改進(jìn)蜂巢柵格

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

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

圖3 改進(jìn)蜂巢柵格Fig.3 Improved Honeycomb Grid

3 ACS 蟻群算法

3.1 路徑選擇概率

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

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

3.2 局部與全局信息素更新

信息素更新方法分為局部信息素更新和全局信息素更新兩種。局部信息素更新是螞蟻每完成一次城市選擇就對相應(yīng)的路徑信息素進(jìn)行更新，這種對所有螞蟻?zhàn)哌^路徑均進(jìn)行信息素更新的方法可以減小路徑之間的信息素差異，增強(qiáng)算法的多樣性，提高算法全局搜索能力。局部信息素更新方法為：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.3 信息素自適應(yīng)擴(kuò)散方法

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

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

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

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

圖4 信息素擴(kuò)散方法Fig.4 Pheromone Infusion Method

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

4.4 算法流程

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

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

（2）將m 只螞蟻全部放置在起始點(diǎn)；

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

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

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

5 仿真分析

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

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

為了分析將動態(tài)分組策略、信息素更新策略和信息素自適應(yīng)擴(kuò)散策略融入蟻群算法后，對算法多樣性的改善情況，分別使用動態(tài)分組蟻群算法和ACS 蟻群算法對TSP 標(biāo)準(zhǔn)數(shù)據(jù)庫中的eil51 算例進(jìn)行路徑規(guī)劃，算法的參數(shù)設(shè)置為：蟻群規(guī)模m=50，信息素因子α=1、啟發(fā)信息因子β=4，局部揮發(fā)系數(shù)ρ=0.1，全局信息素?fù)]發(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，與設(shè)置的種群規(guī)模一致。圖中跟蹤蟻搜索的路徑數(shù)量與探索蟻搜索的路徑數(shù)量之和即為動態(tài)分組蟻群算法的路徑多樣性。分析圖5（a）可知，算法前期蟻群中以探索蟻為主，利于算法進(jìn)行大范圍搜索，同時探索蟻使用輪盤賭的選擇方式，非常有利于算法的多樣性。算法后期蟻跟蹤蟻為主，跟蹤蟻以信息素為主導(dǎo)的柵格選擇方式，有利于算法收斂于較優(yōu)的幾條路徑，同時為了防止算法過于收斂，也即為了防止算法的多樣性下降，信息素的自適應(yīng)擴(kuò)散方法起到了重要作用，因此算法后期直至迭代至2000 代時，算法多樣性依然很高，螞蟻搜索的路徑數(shù)量為38。分析圖5（b）可知，ACS 蟻群算法前期螞蟻搜索的路徑多樣性與動態(tài)分組蟻群算法相差不大，隨著算法的進(jìn)行，路徑多樣性逐漸減少，這是多數(shù)螞蟻向較優(yōu)幾條路徑不斷靠攏的結(jié)果，導(dǎo)致隨著算法的進(jìn)行路徑多樣性不斷下降。因此，動態(tài)分組策略和信息素自適應(yīng)擴(kuò)散策略對算法中路徑多樣性的保持具有明顯效果。使用動態(tài)分組蟻群算法對eil51 算例的規(guī)劃結(jié)果，如圖6 所示。

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

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

為了驗(yàn)證動態(tài)分組蟻群算法在蜂巢柵格環(huán)境下的導(dǎo)航路徑規(guī)劃性能，在圖7 所示蜂巢環(huán)境中分別使用動態(tài)分組蟻群算法和ACS 蟻群算法進(jìn)行導(dǎo)航路徑規(guī)劃，圖中柵格邊長為1m，柵格與柵格中心間的距離為圖中一種柵格為機(jī)器人起點(diǎn)位置，另一種柵格為機(jī)器人目標(biāo)點(diǎn)位置。兩種蟻群算法的最大迭代次數(shù)設(shè)置為200，其余參數(shù)與5.1 節(jié)一致，分別使用動態(tài)分組蟻群算法和ACS 蟻群算法在圖7 環(huán)境下進(jìn)行路徑規(guī)劃，兩種算法各獨(dú)立運(yùn)行 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)速度遠(yuǎn)遠(yuǎn)高于ACS 蟻群算法。以上分析表明，動態(tài)分組蟻群算法在尋優(yōu)質(zhì)量和尋優(yōu)速度都優(yōu)于ACS 蟻群算法，這是因?yàn)閯討B(tài)分組蟻群算法在制定改進(jìn)策略時既關(guān)注算法的多樣性，也關(guān)注算法的收斂性。通過蟻群的動態(tài)分組，算法前期蟻群主要為搜索蟻，搜索蟻隨機(jī)的和啟發(fā)信息主導(dǎo)的搜索方式，極大地增加了算法多樣性，在算法后期蟻群主要為跟蹤蟻，更加注重局部的細(xì)致搜索，為了繼續(xù)保持算法多樣性使用了信息素的自適應(yīng)擴(kuò)散策略。隨著算法迭代，跟蹤蟻逐漸成為蟻群的主體，以信息素為主導(dǎo)的搜索方式，極大地促進(jìn)了算法收斂。因此，動態(tài)分組蟻群算法兼顧了算法的多樣性和收斂性，反應(yīng)在尋優(yōu)性能上就是兼顧了尋優(yōu)質(zhì)量和尋優(yōu)速度。為了分析算法在路徑規(guī)劃中的性能穩(wěn)定性，統(tǒng)計算法10 次獨(dú)立運(yùn)行的參數(shù)，包括最優(yōu)路徑長度、最優(yōu)路徑長度標(biāo)準(zhǔn)差、搜索到最優(yōu)路徑時平均迭代次數(shù)、迭代次數(shù)標(biāo)準(zhǔn)差，結(jié)果如表1 所示。

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

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

6 結(jié)論

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