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

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

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

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

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

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

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

10、息素?fù)]發(fā)因子,表示路徑上信息量的損耗程度,的大小關(guān)系到算法的全局搜索能力和收斂速度，則可用代表信息素殘留因子,表示一次尋找結(jié)束后路徑(i,j)的信息素增量。在初始時(shí)刻,表示第 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只螞蟻?zhàn)哌^(guò) (2-4)“蟻量系統(tǒng)”(Ant-Quantity)模型 第k只

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

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

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

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