蟻群算法及其在移動機器人路徑規(guī)劃中的應(yīng)用講解

1、蟻群算法及其在移動機器人路徑規(guī)劃中的應(yīng)用摘要移動機器人路徑規(guī)劃是機器人研究領(lǐng)域的核心內(nèi)容之一,具有復(fù)雜性、約束性和非線性等特點。蟻群算法(ACA)是最近十幾年發(fā)展起來的仿生優(yōu)化算法,該算法在解決許多復(fù)雜問題方面已經(jīng)展現(xiàn)出其優(yōu)異的性能和巨大的發(fā)展?jié)摿?。本文主要研究靜態(tài)環(huán)境下基于蟻群算法的移動機器人全局路徑規(guī)劃。采用柵格法建立環(huán)境模型,并利用做過改進的基本蟻群算法在柵格環(huán)境模型中進行路徑規(guī)劃,這些改進有:利用偽隨機比例規(guī)則代替隨機比例規(guī)則進行路徑轉(zhuǎn)移;限制了螞蟻行至當前柵格時下一步允許選擇的柵格范圍;對啟發(fā)函數(shù)進行了重新定義;讓螞蟻根據(jù)轉(zhuǎn)移概率利用“輪盤賭”方法選擇下一個柵格。關(guān)鍵詞:蟻群算法,移

2、動機器人，路徑規(guī)劃,柵格AbstractThe path planning for mobile robots is one of the core contents of the filed of robotics research with complex,restrictive and nonlinear characteristics.The ant colony algorithm (ACA)is a new bionics optimization algorithm developed in the past decade,it shows excellent performan

3、ce and great potential for development when solving many complex problems.This thesis mainly studies global path planning for mobile robots based on ACA in static environment.Grid method is used to establish the environment model and some modifications are made to accommodate ACA to path planning in

4、 grid-based environment.These modifications include:using the proportional rule instead of the random proportional rule to choose path;limiting the scope of the next grid allowed to be chosen by the ants;redefining the heuristic function;Using the roulette to choose the next grid for the ants.Keywor

5、ds: ACA,mobile robots,path planning,grid1. 引言至今，在工業(yè)制造中，機器人學(xué)已經(jīng)取得了偉大的成功。機器人手臂或機械手在裝配線中也發(fā)揮了越來越重要的作用。但是，所有這些成功的應(yīng)用，商用機器人都存在著一個根本的缺點：缺乏機動性。相反移動機器人可以行走整個車間，靈活地在它最有效的地方施展它的才能。其中亞馬遜物流機器人已經(jīng)成功地在物流方面得到了應(yīng)用，所以移動機器人的研究存在著必要性與可行性。移動機器人導(dǎo)航的任務(wù)主要由定位、避障和路徑規(guī)劃組成,其中路徑規(guī)劃是機器人控制最為關(guān)鍵的技術(shù)。移動機器人路徑規(guī)劃是指在有障礙物的工作環(huán)境中按照一定的評價標準(如工作代價最小、

6、行走路線最短、行走時間最短等),尋找一條從起始狀態(tài)(包括位置和姿態(tài))到達目標狀態(tài)(包括位置和姿態(tài))的無碰路徑。蟻群算法是一種受到生物界中真實蟻群集覓食行為的啟發(fā)式算法,該算法在求解旅行商()和作業(yè)調(diào)度等多目標優(yōu)化問題取得了不錯的成果,且大量研究結(jié)果表明相對于其它人工智能算法,蟻群算法所取得的結(jié)果是最優(yōu)的。由于機器人路徑規(guī)劃與蟻群覓食行為有著天然的聯(lián)系,本文將蟻群算法引入到機器人路徑規(guī)劃領(lǐng)域中，通過蟻群算法對移動機器人的路徑進行規(guī)劃驗證。2.蟻群算法2.1蟻群算法的基本原理研究發(fā)現(xiàn),螞蟻尋找食物時,它們總能找到一條從巢穴到食物之間的最優(yōu)路徑，這是因為螞蟻在尋找路徑時，會在路徑上釋放出一種特殊的信

7、息素(Pheromone).當它們碰到一個還沒有走過的路口時,就隨機挑選一條路徑前行.與此同時釋放出與路徑長度有關(guān)的信息素.路徑越長,釋放的信息素濃度就越低.當后來的螞蟻再次碰到這個路口的時候, 選擇信息素濃度較高路徑的概率相對較大.最優(yōu)路徑上的信息素濃度越來越大,而其它路徑上信息素濃度卻會隨著時間的流逝而消減.不僅如此,螞蟻還能夠適應(yīng)環(huán)境的變化,當蟻群運動路線上突然出現(xiàn)障礙物時,螞蟻能夠很快地重新找到一條最優(yōu)路徑.我們根據(jù)這一特性做的仿真效果圖如下，圖中H代表蟻穴，F(xiàn)代表食物，+為未尋找到食物的螞蟻，為已找到食物的螞蟻，蟻群從開始尋找食物，到尋得一條最優(yōu)路徑的過程如圖 1.1、1.2 所示.

8、 圖1.1初始狀態(tài)螞蟻隨機挑選路徑尋找食物圖1.2經(jīng)過一段時間后螞蟻成功避開障礙物找到一條合適路徑2.2 蟻群算法的數(shù)學(xué)模型 螞蟻在運動過程中，運動轉(zhuǎn)移的方向由各條路徑上的信息量濃度決定。為方便記錄可用來記錄第 k 只螞蟻當前已走過的所有節(jié)點，這里可以稱存放節(jié)點的表為禁忌表；這個存放節(jié)點的集合會隨著螞蟻的運動動態(tài)的調(diào)整。在算法的搜索過程中，螞蟻會智能地選擇下一步所要走的路徑。 設(shè) m 表示螞蟻總數(shù)量，用表示節(jié)點 i 和節(jié)點 j 之間的距離，表示在 t 時刻連線上的信息素濃度。在初始時刻，m只螞蟻會被隨機地放置，各路徑上的初始信息素濃度是相同的。在 t 時刻，螞蟻 k 從節(jié)點i轉(zhuǎn)移到節(jié)點 j 的

9、狀態(tài)轉(zhuǎn)移概率為 其中，表示螞蟻 k 下一步可以選擇的所有節(jié)點，C 為全部節(jié)點集合；為信息啟發(fā)式因子，在算法中代表軌跡相對重要程度，反映路徑上的信息量對螞蟻選擇路徑所起的影響程度，該值越大，螞蟻間的協(xié)作性就越強；可稱為期望啟發(fā)式因子，在算法中代表能見度的相對重要性。是啟發(fā)函數(shù)，在算法中表示由節(jié)點i 轉(zhuǎn)移到節(jié)點 j 的期望程度，通?？扇?。在算法運行時每只螞蟻將根據(jù)(2-1)式進行搜索前進。 在螞蟻運動過程中，為了避免在路上殘留過多的信息素而使啟發(fā)信息被淹沒，在每只螞蟻遍歷完成后，要對殘留信息進行更新處理。由此，在t+n時刻,路徑(i,j)上信息調(diào)整如下 (2-2) (2-3) 在式中，常數(shù) 表示信

10、息素揮發(fā)因子,表示路徑上信息量的損耗程度,的大小關(guān)系到算法的全局搜索能力和收斂速度，則可用代表信息素殘留因子,表示一次尋找結(jié)束后路徑(i,j)的信息素增量。在初始時刻,表示第 k 只螞蟻在本次遍歷結(jié)束后路徑(i,j)的信息素。 由于信息素更新策略有所不同，學(xué)者Dorigo M 研究發(fā)現(xiàn)了三種不同的基本蟻群算法模型，分別記為“蟻周系統(tǒng)”(Ant-Cycle)模型、“蟻量系統(tǒng)”(Ant-Quantity)模型及“蟻密系統(tǒng)”(Ant-Density)模型，三種模型求解 方式存在不同?！跋佒芟到y(tǒng)”(Ant-Cycle)模型 第k只螞蟻走過 (2-4)“蟻量系統(tǒng)”(Ant-Quantity)模型 第k只

11、螞蟻在t和t+1之間走過 (2-5)“蟻密系統(tǒng)”(Ant-Density)模型 第k只螞蟻在t和t+1之間走過 (2-6)從上邊各公式可以看出三種模型的主要區(qū)別是：“蟻量系統(tǒng)”和“蟻密系統(tǒng)”中，信息素是在螞蟻完成一步后更新的，即采用的是局部信息；而在“蟻周系統(tǒng)”中路徑中信息素是在螞蟻完成一個循環(huán)后更新的，即應(yīng)用的是整體信息。在一系列標準測試問題上運行的實驗表明，“蟻周系統(tǒng)”算法的性能優(yōu)于其他兩種算法。因此，對螞蟻系統(tǒng)的研究正朝著更好地了解“蟻周系統(tǒng)”特征的方向發(fā)展。3 蟻群算法在移動機器人路徑規(guī)劃中的應(yīng)用3.1蟻群算法的機器人路徑規(guī)劃原理根據(jù)機器人路徑規(guī)劃的定義和蟻群算法的原理,基于蟻群算法的

12、機器人路徑規(guī)劃原理為為:將只螞蟻放在出發(fā)點H,以每只螞蟻當前節(jié)點為中心,采取一定策略選擇并走到下一個節(jié)點,對新路徑的信息素按局部更新規(guī)則進行更新。如果有螞蟻到達目標節(jié)點F,由于螞蟻最先到達,用時肯定最少,這樣它獲得的路徑在蟻群本輪尋優(yōu)中是最優(yōu)的,因此對螞蟻所得路徑進行全局信息素更新,并保存該路徑為當前最優(yōu)路徑,對當前最優(yōu)路徑進行全局信息素更新。然后從F出發(fā)以H為目標繼續(xù)尋優(yōu)。如果螞蟻找到新的路徑,那么將新路徑與當前最優(yōu)路徑進行比較,如果新路徑好于當前最優(yōu)路徑那么就用新路徑代替當前最優(yōu)路徑,同時對其全局信息素更新。如果在最近一次全局信息素更新后,又產(chǎn)生新的條路徑時,如果當前最優(yōu)路徑還沒有得到更新

13、,則對當前最優(yōu)路徑進行全局信息素更新。不斷重復(fù),直到滿足設(shè)定的結(jié)束條件或規(guī)定的代數(shù)完成。蟻群系統(tǒng)流程圖如圖3.1圖3.1蟻群系統(tǒng)流程圖3.2 機器人工作環(huán)境建模 環(huán)境模型的建立是機器人路徑規(guī)劃非常重要的一個環(huán)節(jié)。機器人的實際工作環(huán)境是一個現(xiàn)實的物理空間,而路徑規(guī)劃算法所處理的空間是環(huán)境的抽象空間。環(huán)境建模就是實現(xiàn)物理空間到抽象空間的一個映射。我們通常利用柵格法建立環(huán)境模型，模擬機器人工作的實際工作空間。采用柵格表示機器人工作的環(huán)境地圖,在處理障礙物邊界時,可避免復(fù)雜的計算。在柵格法的應(yīng)用中,柵格粒度的劃分非常關(guān)鍵:柵格粒度越小,障礙物的表示會越精確,但同時會占用大量的存儲空間,算法的搜索范圍會

14、按指數(shù)增加;柵格粒度太大,規(guī)劃出的路徑會很不精確。如圖3.2，為截取的部分柵格環(huán)境，灰色柵格為障礙格，其它柵格為自由格圖3.2柵格圖4. 結(jié)論和展望雖然優(yōu)化蟻群算法的研究才剛剛起步，但這些初步研究已顯示出了蟻群優(yōu)化算法在求解復(fù)雜優(yōu)化問題（特別是離散優(yōu)化問題）方面的優(yōu)越性，證明它是一種很有發(fā)展前景的方法。但是必須指出的，蟻群優(yōu)化算法是一種概率算法，從數(shù)學(xué)上對它們的正確性和可靠性的證明還是比較困難的。其在移動機器人路徑規(guī)劃中的應(yīng)用還有很多富有挑戰(zhàn)性的課題亟待解決。主要體現(xiàn)在以下幾方面: （1）近期對蟻群算法在移動機器人路徑規(guī)劃中的應(yīng)用研究還處于初期探索階段, 研究重點主要集中在算法模型的建立與實例仿真方面,而對于算法的理論分析、與其他算法結(jié)合等方面的研究較少; （2）近期對蟻群算法在移動機器人路徑規(guī)劃的研究主要集中于靜態(tài)環(huán)境下的路徑規(guī)劃研究,而對動態(tài)環(huán)境下的路徑規(guī)劃研究相對較少。參 考 文 獻1 范路橋，姚錫凡，卞青青，蔣梁中. 蟻群算法及其在移動機器人路徑規(guī)劃中的應(yīng)用J. 微計算機信息，2008，24：08-02. 2 杜利峰，牛永潔. 蟻群算法在MATLAB中的實現(xiàn)J. 信息技術(shù)，2011，06: 115-118.3 張銀鈴，牛小梅. 蟻群算法在移動機器人路徑