王明超

（無錫工藝職業(yè)技術(shù)學(xué)院，江蘇 宜興 214200）

1 引言

移動機器人的導(dǎo)航路徑關(guān)乎機器人自身安全、使用壽命和生產(chǎn)效率，導(dǎo)航路徑要求短而光滑，光滑路徑可以減少機器人磨損、提高行走效率[1]，因此研究機器人導(dǎo)航路徑規(guī)劃問題具有明顯的經(jīng)濟意義。

機器人導(dǎo)航路徑規(guī)劃問題分為兩大部分內(nèi)容，即環(huán)境建模與路徑規(guī)劃策略。環(huán)境建模法有柵格法、可視圖空間法、自由空間法、虛擬力場法等，可視圖優(yōu)點是線路清晰明確，容易規(guī)劃出最優(yōu)路徑，缺點是普適性差，且只能應(yīng)用于全局路徑規(guī)劃[2]；自由空間法是可視圖空間法的改進方法，適用性較好，但是在復(fù)雜環(huán)境下算法復(fù)雜度極高[3]；虛擬力場法優(yōu)點是復(fù)雜度低，缺點是空間中障礙物分布復(fù)雜時很可能求不到最優(yōu)解；柵格法優(yōu)點是簡單、容易理解、普適性極好，缺點是障礙物“膨化”方法會損失部分工作空間[4]。路徑規(guī)劃策略分為傳統(tǒng)方法和智能算法兩類，傳統(tǒng)方法有人工勢場法、模糊邏輯法等，人工勢場法原理簡單、路徑光滑性，缺點是容易陷入局部最優(yōu)，甚至在目標(biāo)點附近徘徊[5]；模糊邏輯法優(yōu)點是不需要精確的系統(tǒng)模型，但是模糊邏輯表較難制定[6]；智能算法包括遺傳算法、神經(jīng)網(wǎng)絡(luò)、蟻群算法等[7，8]，智能算法優(yōu)勢是發(fā)揮算法智能性，規(guī)劃路徑較優(yōu)，但是問題也明顯，算法本身都存在一定缺陷，如遺傳算法運算效率低，神經(jīng)網(wǎng)絡(luò)算法需要一定量的訓(xùn)練樣本，蟻群算法收斂速度慢、易陷局部最優(yōu)等。

研究了多障礙物復(fù)雜環(huán)境下的導(dǎo)航路徑規(guī)劃問題，將陷阱深度標(biāo)記策略和分種群搜索策略融入到蟻群算法中，提出了多種群蟻群算法。在多障礙物復(fù)雜環(huán)境中，多種群蟻群算法規(guī)劃的路徑長度和迭代次數(shù)明顯優(yōu)于基本蟻群算法。

2 機器人導(dǎo)航路徑規(guī)劃問題描述

2.1 環(huán)境建模

柵格法是環(huán)境建模最為簡單有效的方法，雖然在障礙物“膨化”處理時會損失部分工作空間，但是卻極大地降低了計算復(fù)雜度。

在機器人的二維工作空間中，使用固定大小的柵格劃分工作區(qū)域，當(dāng)障礙物未充滿柵格時，使用“膨化”方法使其占滿柵格。某區(qū)域的柵格模型，如圖1所示。圖中黑色柵格表示障礙物柵格，白色柵格表示不含有障礙物的自由柵格。為了區(qū)分障礙物柵格與自由柵格，為其賦不同的屬性值，其中障礙物柵格賦值為1，自由柵格賦值為0，這樣就可以將柵格模型轉(zhuǎn)化為機器人可以識別的（0～1）矩陣模型。

圖1 柵格建模法Fig.1 Grid Modeling Method

柵格的編碼方法有順序編碼法和坐標(biāo)法兩種，路徑表示時使用編碼法，距離計算時使用坐標(biāo)法，因此必須明確兩者的轉(zhuǎn)換關(guān)系，為：

式中：i—柵格順序編碼號；N—柵格規(guī)模；（xi，yi）—柵格坐標(biāo)；mod—求余運算；fix—取整運算。

在此需要強調(diào)的是，在柵格環(huán)境下，機器人路徑表示為一系列數(shù)據(jù)序列的集合｛a1，a2，…ai，…｝，使用蟻群算法在柵格環(huán)境下求解導(dǎo)航路徑時，規(guī)劃路徑的柵格數(shù)是不固定的，無需限定數(shù)據(jù)序列的維數(shù)。

2.2 建立路徑評價函數(shù)

在大多數(shù)路徑規(guī)劃問題中，一般以路徑長度作為評價路徑優(yōu)劣的唯一標(biāo)準(zhǔn)，但是當(dāng)路徑中轉(zhuǎn)彎較多、轉(zhuǎn)彎較急時，會對機器人造成轉(zhuǎn)彎磨損而影響使用效率，且轉(zhuǎn)彎的存在也會影響行走效率，所以路徑平滑度極大地影響機器人使用壽命和工作效率，因此將平滑度作為路徑的一個評價指標(biāo)。

（1）路徑長度Lk的計算。路徑長度為相鄰柵格距離的累加和，即：

式中：a—路徑中的柵格數(shù)；D（i，i+1）—第i個柵格與第i+1個柵格的距離。在柵格環(huán)境下，D（i，i+1）只能取值為1或。

（2）路徑平滑度Sk的計算。使用路徑轉(zhuǎn)彎時的拐角大小表征路徑平滑度，轉(zhuǎn)彎時拐角大小定義方法，如圖2中α所示。

圖2 拐角大小定義方法Fig.2 Definition Method of the Corner

3 蟻群算法及分析

3.1 蟻群算法原理

以旅行商問題為背景對蟻群算法進行分析，記需訪問的城市數(shù)量為n，蟻群中螞蟻數(shù)量為m，城市i與城市j間距離為dij，兩城市間在t時刻的信息素為τ（ijt），則螞蟻k在t時刻由當(dāng)前城市i轉(zhuǎn)移到城市j的概率

式中：ηij—啟發(fā)信息，表示螞蟻由城市i轉(zhuǎn)移到城市j的期望程度；α、β—信息素和啟發(fā)信息影響因子，代表信息素和啟發(fā)因子在路徑引導(dǎo)中的影響力，其值越大代表信息素或啟發(fā)因子影響力越大，路徑搜索收斂性越強，同時越容易陷入局部極值，其值越小代表路徑規(guī)劃隨機性越大，越不容易收斂，但是容易跳出局部極值；allowedk—螞蟻k可以選擇的城市集合，即allowedk=n-tabuk，tabuk表示螞蟻k的禁忌表，即螞蟻k已經(jīng)歷的城市。

螞蟻在行走過程中，邊行走邊釋放信息素，這種信息素更新方式更符合蟻群實際。信息素更新方法為：

3.2 蟻群算法應(yīng)用于柵格環(huán)境需明確的幾點問題

蟻群算法最早基于旅行商問題提出，鑒于柵格環(huán)境下路徑規(guī)劃問題與旅行商問題的區(qū)別，明確以下幾點：

（1）蟻群算法應(yīng)用于柵格環(huán)境下路徑規(guī)劃時，allowedw表示螞蟻k可以選擇的柵格集合，即與當(dāng)前柵格相鄰的自由柵格除去禁忌表tabuk中的柵格；

4 多陷阱復(fù)雜環(huán)境下改進蟻群算法

蟻群算法存在收斂速度慢、易陷入局部最優(yōu)的問題，且在多陷阱環(huán)境下這兩個問題更加突出，提出了兩種改進策略。

4.1 陷阱深度標(biāo)記策略

在柵格環(huán)境下，最典型的陷阱為U型陷阱。在多陷阱復(fù)雜環(huán)境中，存在一定數(shù)量的螞蟻陷入陷阱，目前解決陷阱問題存在螞蟻回退策略和螞蟻夭折策略兩種方法。螞蟻回退策略[9]為當(dāng)螞蟻陷入陷阱底部時，螞蟻邊倒退邊標(biāo)記陷阱柵格，直至回到離開陷阱，標(biāo)記的目的是避免后續(xù)螞蟻再次陷入陷阱。這種方法能夠保證螞蟻離開陷阱而完成路徑規(guī)劃，但是當(dāng)環(huán)境中存在較多陷阱或陷阱較深時，大量螞蟻經(jīng)過反復(fù)的后退、標(biāo)記、判斷，會消耗大量的運算時間，而已經(jīng)到達目標(biāo)的螞蟻需等待這部分未到達目標(biāo)的螞蟻，如此嚴(yán)重消耗了運算時間，降低了算法效率。

螞蟻夭折策略[10]為當(dāng)螞蟻由起始點搜索至目標(biāo)點時，路徑搜索完成，螞蟻正常死亡。當(dāng)螞蟻陷入U型陷阱時螞蟻夭折，不再進行路徑搜索，走過的路徑不再進行信息素更新。但是當(dāng)環(huán)境中存在較多陷阱時，會出現(xiàn)一定量的螞蟻夭折，降低算法在解空間中的探索深度和解的質(zhì)量。

在多陷阱復(fù)雜環(huán)境中，針對現(xiàn)有方法存在的問題，提出了陷阱深度標(biāo)記策略。分以下兩個步驟執(zhí)行：

（1）陷阱的確認(rèn)與深度計算。當(dāng)螞蟻k第一次出現(xiàn)可選柵格只有一個時，標(biāo)記螞蟻k當(dāng)前柵格的前一柵格為Trap，且開始計數(shù)用于計算陷阱深度。當(dāng)可選柵格只有一個連續(xù)出現(xiàn)且最終無柵格可選時，說明螞蟻k陷入了U型陷阱，陷阱深度記為H；

（2）螞蟻跳躍逃出陷阱。設(shè)置一個陷阱深度閾值HT，若H＆gt;HT說明陷阱較深，在陷阱中浪費時間較多，此時螞蟻夭折，以免拖慢算法效率；若H≤HT說明陷阱較淺，在陷阱中浪費時間較少，此螞蟻還可以繼續(xù)使用，此時螞蟻以跳躍方式直接跳躍至柵格Trap，同時將陷阱柵格標(biāo)記為1，視為障礙物柵格，以免后續(xù)螞蟻重蹈覆轍。

分析陷阱深度標(biāo)記策略可知，以螞蟻跳躍方式逃出陷阱，避免了回退策略中反復(fù)的回退、判斷，節(jié)省了大量的運算時間，提高了算法效率。另外，當(dāng)螞蟻陷入U型陷阱時，沒有像夭折策略一樣直接扼殺，而是將陷入不深的螞蟻進行了保留，與螞蟻夭折策略相比保留了種群規(guī)模，提高了解的質(zhì)量。

4.2 分種群搜索策略

式中：d（i，j）—柵格 i與柵格 j的距離；d（j，Goal）—下一柵格與目標(biāo)柵格距離；k1、k2—近鄰啟發(fā)因子和目標(biāo)啟發(fā)因子的影響因子，分別表征算法的隨機性和目的性。

對于第一個種群group1，設(shè)置k1＆gt;＆gt;k2＆gt;0，k1＆gt;＆gt;k2保證了算法初期具有足夠的隨機性，使螞蟻擁有足夠的自由充分探索解空間，避免算法在初期由于啟發(fā)作用過于明顯而陷入局部最優(yōu)；k2＆gt;0而不允許取為0，保證了算法具有一定的啟發(fā)引導(dǎo)作用，避免算法因完全的隨機而嚴(yán)重偏離目標(biāo)方向。對于第二個種群group2，設(shè)置k2＆gt;＆gt;k1且k1=0，這種設(shè)置方式使第二種群對路徑規(guī)劃具有較好的引導(dǎo)作用，提高算法收斂速度，且避免算法陷入極差解。

4.3 分種群蟻群算法流程

將陷阱深度標(biāo)記策略與分種群搜索策略融入到蟻群算法中，得到分種群蟻群算法步驟為：

（1）參數(shù)初始化，包括種群數(shù)量m1和m2，信息素影響因子α、啟發(fā)信息影響因子β、揮發(fā)系數(shù)ρ、陷阱深度閾值HT、近鄰啟發(fā)因子影響因子k1、目標(biāo)啟發(fā)因子影響因子k2、算法最大迭代次數(shù)N等；

（2）將兩個種群的蟻群全部放置在起始點，螞蟻按照式（5）和式（7）計算選擇臨近柵格的概率，而后使用輪盤賭的方法確定下一柵格；當(dāng)可選柵格只有一個時，啟動陷阱深度標(biāo)記策略；所有螞蟻邊行走邊進行信息素更新；

（3）當(dāng)除夭折外的所有螞蟻均到達目標(biāo)點時，計算所有螞蟻搜尋路徑的長度并比較，輸出算法本次循環(huán)的最優(yōu)路徑；

（4）判斷算法循環(huán)次數(shù)是否達大于N，若否則算法轉(zhuǎn)至（2）；若是則算法結(jié)束，同時輸出最優(yōu)路徑。

5 實例驗證

為了驗證分種群蟻群算法在多陷阱復(fù)雜環(huán)境中路徑規(guī)劃的有效性，使用MATLAB軟件分別仿真出多U型障礙物環(huán)境和多障礙物兩種復(fù)雜環(huán)境，使用蟻群算法與多種群蟻群算法分別進行路徑規(guī)劃，對比路徑優(yōu)劣。

參數(shù)設(shè)置為：種群數(shù)量m1=25、m2=5，信息素影響因子α=1、啟發(fā)信息影響因子β=6、揮發(fā)系數(shù)ρ=0.3、陷阱深度閾值HT=4、算法最大迭代次數(shù)N=50。

5.1 多U型障礙物復(fù)雜環(huán)境

仿真出20×20的U型障礙物密集分布環(huán)境，如圖3所示。環(huán)境中U型障礙物多且深，柵格環(huán)境中1號柵格為起始點，標(biāo)記為S，400號柵格為目標(biāo)點，標(biāo)記為G?；鞠伻核惴ㄊ褂梦浵伝赝瞬呗詰?yīng)對U型障礙物環(huán)境，多種群蟻群算法使用陷阱深度標(biāo)記策略應(yīng)對U型障礙物，兩種算法各運行100次，兩算法規(guī)劃的最優(yōu)路徑結(jié)果，如圖3所示。圖中虛線為基本蟻群算法規(guī)劃的最優(yōu)路徑，實線為多種群蟻群算法規(guī)劃的路徑。

圖3 多U型障礙物環(huán)境Fig.3 Multiple U-Shaped Obstacle Environment

統(tǒng)計兩種算法的最優(yōu)路徑長度、算法平均運行時間與平均迭代次數(shù)結(jié)果，如表1所示。

表1 兩蟻群算法的運行結(jié)果Tab.1 Computational Result of the Two Ant Colony Algorithm

由表3可以看出，基本蟻群算法在多U型障礙物環(huán)境中規(guī)劃出的路徑折線特別多，這是因為螞蟻后退到陷阱第一個柵格時不再后退而繼續(xù)規(guī)劃路徑，導(dǎo)致規(guī)劃出的路徑非常不合理；而基本蟻群算法在陷入陷阱時會將前一柵格標(biāo)記為，待確認(rèn)陷入陷阱時以跳躍的方式直接回到柵格，使路徑不存在折線。

由表1中數(shù)據(jù)可知，多種群蟻群算法規(guī)劃的最優(yōu)路徑長度短于基本蟻群算法，且平均運行時間與平均迭代次數(shù)不足基本蟻群算法的一半，這是因為基本蟻群算法陷入U型陷阱時，螞蟻反復(fù)的回退、判斷嚴(yán)重拖慢了算法運行時間、增加算法迭代次數(shù)；而多種群蟻群算法在確認(rèn)陷入U型陷阱時，直接跳躍至柵格，沒有反復(fù)的回退與判斷過程，極大地節(jié)省了運算時間、減少了迭代次數(shù)。

5.2 多障礙物復(fù)雜環(huán)境

仿真出20×20的多障礙物復(fù)雜環(huán)境，如圖4所示。柵格環(huán)境中1號柵格為起始點，標(biāo)記為S，400號柵格為目標(biāo)點，標(biāo)記為G。分別使用基本蟻群算法與多種群蟻群算法各進行100次路徑規(guī)劃，兩算法規(guī)劃的最優(yōu)路徑結(jié)果，如圖5所示。虛線為基本蟻群算法規(guī)劃的最優(yōu)路徑，實線為多種群蟻群算法規(guī)劃的路徑。算法迭代過程中，最優(yōu)路徑長度隨迭代次數(shù)的變化情況，如圖5所示。

圖4 多障礙物環(huán)境Fig.4 Multiple Obstacles Environment

圖5 最優(yōu)路徑長度隨迭代次數(shù)變化曲線Fig.5 Changing Curve of Optimal Path Length with Iteration Time

由圖4可以看出，多種群蟻群算法規(guī)劃出的路徑明顯短于基本蟻群算法規(guī)劃出的路徑，多種群算法規(guī)劃路徑拐點數(shù)為5個，而基本算法規(guī)劃路徑拐點數(shù)為17個，說明多種群算法規(guī)劃路徑的平滑性明顯優(yōu)于基本蟻群算法。由圖5可以看出，基本蟻群算法搜索到最優(yōu)路徑時迭代了26次，而多種群算法搜索到最優(yōu)路徑時迭代了13次。為了進一步比較多種群蟻群算法與基本蟻群算法在多障礙物環(huán)境中的路徑規(guī)劃性能，統(tǒng)計兩算法的路徑規(guī)劃結(jié)果，如表2所示。

表2 兩蟻群算法的路徑規(guī)劃結(jié)果Tab.2 Path Planning Result of the Two Ant Colony Algorithm

分析表2中數(shù)據(jù)可知，與基本蟻群算法相比，多種群蟻群算法規(guī)劃路徑的平均長度減少了24.8%，最優(yōu)路徑長度減少了18.2%，平均迭代次數(shù)減少了約39.1%，最少迭代次數(shù)減少了50%，以上數(shù)據(jù)充分說明多種群蟻群算法不僅規(guī)劃路徑短于基本蟻群算法，而且迭代次數(shù)也明顯減少。這是因為多種群蟻群算法將蟻群分為兩個種群，分別設(shè)置不同的啟發(fā)信息，使螞蟻搜索路徑時具有不同的傾向性，兼顧了算法的隨機性、目的性和收斂性，達到了提高算法收斂速度和尋優(yōu)精度的目的。

6 結(jié)論

建立了多陷阱復(fù)雜環(huán)境下的柵格模型，提出了多種群蟻群算法用于路徑規(guī)劃，經(jīng)仿真驗證可以得出以下結(jié)論：（1）在多U型陷阱環(huán)境下，陷阱深度標(biāo)記策略規(guī)劃的最優(yōu)路徑比螞蟻回退策略減少了4.7%，平均運行時間和平均迭代次數(shù)減少了一倍以上，說明了陷阱深度標(biāo)記策略的規(guī)劃效率和結(jié)果遠遠優(yōu)于螞蟻回退策略；（2）在多障礙物復(fù)雜環(huán)境下，與基本蟻群算法相比，多種群蟻群算法規(guī)劃的路徑平均長度減少了24.8%，平均迭代次數(shù)減少了近一倍，說明多種群算法中每個種群使用不同的啟發(fā)信息，可以兼顧算法的隨機性、目的性和收斂性，提高算法收斂速度和尋優(yōu)精度。