《電子技術(shù)應(yīng)用》
您所在的位置:首頁(yè) > 嵌入式技術(shù) > 設(shè)計(jì)應(yīng)用 > 基于改進(jìn)型蟻群算法的滅火機(jī)器人路徑規(guī)劃研究
基于改進(jìn)型蟻群算法的滅火機(jī)器人路徑規(guī)劃研究
2014年微型機(jī)與應(yīng)用第13期
何少佳,鄧子信,高韻灃,石旅光,陳志丹,閆 偉
桂林電子科技大學(xué) 機(jī)電工程學(xué)院,廣西 桂林
摘要: 在傳統(tǒng)蟻群算法基礎(chǔ)上,采用隨機(jī)選擇和慣性保持相結(jié)合的方式搜尋節(jié)點(diǎn),在獲得不同路徑的同時(shí)提高算法收斂速度。從已獲得的路徑兩端沿慣性方向逼近優(yōu)化,將無(wú)障礙中間節(jié)點(diǎn)剔除,減少機(jī)器人在最短路徑上轉(zhuǎn)彎次數(shù)的同時(shí)增強(qiáng)算法的搜索性能。通過(guò)自適應(yīng)方式動(dòng)態(tài)調(diào)整信息素,改善算法適應(yīng)能力。仿真結(jié)果表明,通過(guò)以上改進(jìn)能有效提升路徑質(zhì)量,可有效降低滅火機(jī)器人在室內(nèi)環(huán)境中尋找火源的時(shí)間,提高滅火效率。
Abstract:
Key words :

  摘  要: 在傳統(tǒng)蟻群算法基礎(chǔ)上,采用隨機(jī)選擇和慣性保持相結(jié)合的方式搜尋節(jié)點(diǎn),在獲得不同路徑的同時(shí)提高算法收斂速度。從已獲得的路徑兩端沿慣性方向逼近優(yōu)化,將無(wú)障礙中間節(jié)點(diǎn)剔除,減少機(jī)器人在最短路徑上轉(zhuǎn)彎次數(shù)的同時(shí)增強(qiáng)算法的搜索性能。通過(guò)自適應(yīng)方式動(dòng)態(tài)調(diào)整信息素,改善算法適應(yīng)能力。仿真結(jié)果表明,通過(guò)以上改進(jìn)能有效提升路徑質(zhì)量,可有效降低滅火機(jī)器人在室內(nèi)環(huán)境中尋找火源的時(shí)間,提高滅火效率。

  關(guān)鍵詞: 蟻群算法;慣性方向;逼近優(yōu)化;自適應(yīng)

  滅火機(jī)器人路徑優(yōu)化技術(shù)能夠使機(jī)器人更加智能,從而可以代替消防員在火災(zāi)危險(xiǎn)環(huán)境下進(jìn)行救援工作[1]。對(duì)于滅火機(jī)器人而言,以最高效率找到一條從起始位置到目標(biāo)位置(起火點(diǎn))的最優(yōu)無(wú)碰撞路徑,是其可靠的基礎(chǔ)。智能體路徑規(guī)劃問(wèn)題[2]一直是機(jī)器人研究領(lǐng)域的一個(gè)重要組成部分,其由環(huán)境構(gòu)建和規(guī)劃方法兩個(gè)方面構(gòu)成。由于在日常生活中火災(zāi)發(fā)生具有不確定性,導(dǎo)致滅火機(jī)器人尋找火源的過(guò)程變得復(fù)雜,本文為了問(wèn)題的簡(jiǎn)化將創(chuàng)建全局柵格地圖,為滅火機(jī)器人路徑規(guī)劃提供靜態(tài)環(huán)境模型。

  目前基于柵格模型的路徑規(guī)劃有許多方法,如:蟻群算法、粒子群算法、A*、遺傳算法等[3]。蟻群算法是一種仿生學(xué)算法,是模仿螞蟻尋找食物過(guò)程中的行為,利用留在地面上信息素的釋放和揮發(fā),給后面的螞蟻提供一定指向,當(dāng)大群螞蟻反復(fù)行走后,最終找到一條通往食物的最優(yōu)路徑[4]。同時(shí),蟻群還能適應(yīng)環(huán)境的變化,當(dāng)蟻群運(yùn)動(dòng)路徑上突然出現(xiàn)障礙物時(shí),螞蟻也能很快地重新找到最優(yōu)路徑。作為一種智能算法蟻群算法有其突出的優(yōu)點(diǎn):(1)蟻群算法具有自組織性,系統(tǒng)能在沒(méi)有外界特定干預(yù)的情況下實(shí)現(xiàn)從無(wú)序到有序的變化;(2)作為并行算法,它具有空間多點(diǎn)同時(shí)進(jìn)行獨(dú)立解搜索的能力,不僅具有較高的可靠性,也具有較強(qiáng)的全局搜索能力;(3)具有較強(qiáng)的魯棒性;(4)參數(shù)數(shù)目少,設(shè)置簡(jiǎn)單,易于實(shí)現(xiàn)其他組合優(yōu)化問(wèn)題的求解。傳統(tǒng)的蟻群算法也存在其不足,如收斂速度較慢、求解的精度不高、容易陷入局部最優(yōu)等問(wèn)題[5]。為此,許多改進(jìn)方案被提出,如最大最小螞蟻系統(tǒng)MMAS(Max-Min Ant System)算法[6]、帶有變異策略的蟻群算法和多蟻群算法等,但仍無(wú)法避免陷入死鎖狀態(tài)。

  本文立足室內(nèi)滅火機(jī)器人路徑規(guī)劃,主要從路徑搜索策略、優(yōu)化方法和信息素更新三個(gè)方面對(duì)蟻群算法進(jìn)行改進(jìn),并通過(guò)仿真實(shí)驗(yàn)驗(yàn)證該算法的可行性和有效性。

  1 算法設(shè)計(jì)

  首先,以柵格法建立機(jī)器人工作環(huán)境,構(gòu)建一個(gè)全局靜態(tài)環(huán)境模型。其次,將算法分為兩步施行。第一步實(shí)現(xiàn)路徑搜索,采用隨機(jī)選擇和慣性保持相結(jié)合的策略,搜索過(guò)程不釋放信息素。第二步進(jìn)行路徑優(yōu)化,對(duì)已獲得的所有路徑采取端點(diǎn)逼近慣性優(yōu)化,并對(duì)優(yōu)化后的路徑實(shí)現(xiàn)信息素動(dòng)態(tài)更新。

  1.1 構(gòu)建工作環(huán)境

  柵格法[7]是環(huán)境構(gòu)建過(guò)程中被廣泛使用的方法之一,它將智能體的工作空間轉(zhuǎn)化為對(duì)應(yīng)的柵格模型。用大小相同的柵格劃分工作空間,灰色柵格代表障礙物,其他柵格代表自由空間。柵格法的特點(diǎn)是簡(jiǎn)單、易于實(shí)現(xiàn),為路徑規(guī)劃帶來(lái)很大方便,而且具有表示不規(guī)則障礙物的能力,適合于大規(guī)模并行處理機(jī)的實(shí)現(xiàn)。

  本文采用柵格法構(gòu)建工作環(huán)境,將一個(gè)平面空間等分成許多小格,一個(gè)小格就代表一個(gè)小區(qū)域,區(qū)域長(zhǎng)寬為1個(gè)單位,任意兩個(gè)節(jié)點(diǎn)的距離為兩柵格中心點(diǎn)上的連線距離,并將小格按從左至右、從上到下的順序編號(hào)。環(huán)境地圖建完后,里面的顏色就代表空間的狀況,如白色(0)代表可行,灰色(1)代表障礙物,綠色代表起始點(diǎn),紅色代表目標(biāo)點(diǎn)。圖1為柵格法表示的工作環(huán)境。

001.jpg

  智能體在柵格空間節(jié)點(diǎn)的運(yùn)行方向及節(jié)點(diǎn)距離由矩陣D表示,G為環(huán)境模型矩陣。

  h=size(G,1)//矩陣行數(shù)

  l=size(G,2)//矩陣列數(shù)

  D=zeros(h*l,h*l);

  for i=1:h

  for j=1:l

  if G(i,j)==0

  for m=1:h

  for n=1:l

  if G(m,n)==0//自由空間

  im=abs(i-m);jn=abs(j-n);

  if im+jn==1||(im==1&&jn==1)

  D((i-1)*h+j,(m-1)*l+n)=(im+jn)^0.5;

  //可選節(jié)編號(hào)及距離

  end

  end

  end

  end

  end

  end

  1.2 路徑搜索

  第一步以式(1)選擇節(jié)點(diǎn):

  FZXD961(P47[1S6LOZH)]}F.png

  其中,Pij表示智能體在位置i時(shí)下一步選擇節(jié)點(diǎn)j的概率;τij為節(jié)點(diǎn)i、j之間的信息素濃度;啟發(fā)因子?濁jo為節(jié)點(diǎn)j到目標(biāo)位置o之間距離的倒數(shù),以引導(dǎo)智能體向距離目標(biāo)最短的方向移動(dòng);?琢為信息素的重要程度;?茁為啟發(fā)因子的重要程度;D為下一步可選擇目標(biāo)的集合;q為(0,1]的隨機(jī)值;q0為[0.7-0.8]之間的閾值。

  采用此方式能使智能體以較大的概率q0向信息素和啟發(fā)因子乘積最大的目標(biāo)位置移動(dòng),而以較小的概率(1-q0)使用隨機(jī)比例原則選擇目標(biāo)位置[8]。這樣既保證了智能體選擇的方向性,又增加了智能體搜索的多樣性,在避免搜索過(guò)程陷入死循環(huán)的同時(shí),有效地提升了搜索時(shí)間。

  1.3 端點(diǎn)逼近慣性優(yōu)化

  當(dāng)M只螞蟻完成一輪搜索后,將形成M條從起點(diǎn)到終點(diǎn)的路徑,這些路徑雜亂無(wú)序,傳統(tǒng)的蟻群算法由于信息素更新模式的問(wèn)題容易造成局部最優(yōu)解,一般的解決方法在解決局部最優(yōu)解的過(guò)程中容易導(dǎo)致運(yùn)算時(shí)間延長(zhǎng)。采用端點(diǎn)逼近慣性優(yōu)化方法能進(jìn)一步優(yōu)化最短路徑,把一些曲折的地方變成直線,減少轉(zhuǎn)彎次數(shù),同時(shí)增強(qiáng)算法的搜索性能。

  端點(diǎn)逼近慣性優(yōu)化的原理是:每次循環(huán)結(jié)束后,只對(duì)本輪搜尋的最短路徑進(jìn)行優(yōu)化,從起始點(diǎn)(S)和目標(biāo)點(diǎn)(O)開(kāi)始同時(shí)相向遍歷每個(gè)節(jié)點(diǎn),當(dāng)路徑中有中間節(jié)點(diǎn)滿足慣性條件時(shí)刪除此節(jié)點(diǎn),添加優(yōu)化后的節(jié)點(diǎn),繼續(xù)優(yōu)化,直到S逼近O且O逼近S,優(yōu)化結(jié)束后將獲得至少一條優(yōu)化路徑。慣性條件是指從保持原有運(yùn)動(dòng)且無(wú)障礙的行進(jìn)線路方向。采用雙向逼近優(yōu)化可以獲得多重解,為智能體回到出發(fā)點(diǎn)提供路線參考,有助于進(jìn)一步提升算法的適應(yīng)性。

  設(shè)pi-1(xi-1,yj-1)為上一個(gè)節(jié)點(diǎn),當(dāng)前節(jié)點(diǎn)為pi(xi,yj),pi+1(xi+1,yj+1)為pi周圍可選取的8個(gè)節(jié)點(diǎn),pi+1為慣性點(diǎn)的條件為滿足式(2)或式(3):

  23.png

  為防止慣性過(guò)于突出而找不到最優(yōu)路徑,慣性優(yōu)化方法可以在尋找過(guò)程中自動(dòng)調(diào)整方向,但最多只能調(diào)整一次,也就是優(yōu)化后最多存在1個(gè)轉(zhuǎn)折點(diǎn)。由于前期在節(jié)點(diǎn)選擇上具有較強(qiáng)的方向性(按照到目標(biāo)點(diǎn)位置最短),因而慣性優(yōu)化能在降低轉(zhuǎn)彎次數(shù)的同時(shí)確保路徑最短,對(duì)于降低智能體整體運(yùn)行時(shí)間具有實(shí)際意義。慣性優(yōu)化流程(以S到O為例)如圖2所示。

002.jpg

  1.4 信息素動(dòng)態(tài)調(diào)整

  每次迭代結(jié)束后,對(duì)當(dāng)前最優(yōu)路徑進(jìn)行信息素全局動(dòng)態(tài)更新:

  45.png

  其中,?駐τij為此次循環(huán)的信息素增量,lmin表示當(dāng)前最短路徑的長(zhǎng)度,ltmin為此次迭代最短路徑的長(zhǎng)度。?駐τij越大說(shuō)明路徑越短(新的更短路徑已經(jīng)產(chǎn)生),應(yīng)當(dāng)將后面的螞蟻引向此路徑上,因此應(yīng)當(dāng)增加信息素濃度。當(dāng)找到最短路徑時(shí),信息素以一個(gè)較小的量增加,避免陷入死循環(huán)。

  1.5 算法求解過(guò)程

  根據(jù)以上描述,本算法步驟如下:

  (1)柵格法建立工作環(huán)境,參數(shù)初始化,構(gòu)造啟發(fā)式信息。

 ?。?)每只螞蟻根據(jù)式(1)選擇下一節(jié)點(diǎn),記錄已走過(guò)的節(jié)點(diǎn)位置和路徑長(zhǎng)度,更新禁忌表。

 ?。?)循環(huán)執(zhí)行步驟(2),直到所有螞蟻都搜尋完畢。

  (4)對(duì)最短的路徑進(jìn)行端點(diǎn)逼近慣性優(yōu)化,并保存更新后的節(jié)點(diǎn)位置和路徑長(zhǎng)度。

 ?。?)根據(jù)式(4)和(5)對(duì)全局進(jìn)行信息素更新。

 ?。?)循環(huán)執(zhí)行步驟(2)~步驟(5),直到迭代結(jié)束。

  2 仿真分析與參數(shù)測(cè)試

  為驗(yàn)證此算法的可行性,在MATLAB7.11平臺(tái)上進(jìn)行仿真測(cè)試,所選參數(shù)設(shè)置如下:螞蟻數(shù)M=50,最大迭代次數(shù)K=100,q為(0,1]的隨機(jī)值,q0=0.7~0.8,?琢=1,?茁=10,ρ=0.3。實(shí)驗(yàn)結(jié)果如圖3、圖4所示。

  由圖3可知,雖然在路徑長(zhǎng)度上優(yōu)化前后并沒(méi)有發(fā)生變化,仍然為29.799,但可以看到優(yōu)化后的路徑質(zhì)量明顯優(yōu)于優(yōu)化前,在轉(zhuǎn)彎次數(shù)上由14次降為4次。圖4的橫坐標(biāo)代表迭代次數(shù),縱坐標(biāo)代表每輪迭代的最短路徑,由圖4可知優(yōu)化后的算法在收斂性上要優(yōu)于前者。不同環(huán)境下的測(cè)試表明,改進(jìn)后的蟻群算法表現(xiàn)出較強(qiáng)的優(yōu)越性,尤其在轉(zhuǎn)彎次數(shù)和收斂性方面。仿真結(jié)果表明改進(jìn)后的蟻群算法在降低轉(zhuǎn)彎次數(shù)和運(yùn)算時(shí)間方面有顯著提高,從而證明了此算法的有效性和可行性。

  在節(jié)點(diǎn)選擇上采用方向性和隨機(jī)選擇相結(jié)合的方式既節(jié)約了收斂時(shí)間又可避免陷入死循環(huán)。采用端點(diǎn)逼近慣性優(yōu)化對(duì)最短路徑進(jìn)行進(jìn)一步優(yōu)化,可以有效降低轉(zhuǎn)彎次數(shù),提高線路質(zhì)量,降低滅火機(jī)器人在運(yùn)動(dòng)過(guò)程中的時(shí)間,同時(shí)為機(jī)器人回到出發(fā)點(diǎn)提供了路線參考。通過(guò)自適應(yīng)方式動(dòng)態(tài)調(diào)整信息素,改善算法適應(yīng)能力。仿真結(jié)果表明,相比傳統(tǒng)的蟻算法,通過(guò)以上改進(jìn)能有效提升路徑質(zhì)量,可有效降低滅火機(jī)器人在室內(nèi)環(huán)境中尋找火源的時(shí)間,提高滅火效率。

  參考文獻(xiàn)

  [1] 賈翠玲,李衛(wèi)國(guó),郭文霞.改進(jìn)蟻群算法在滅火機(jī)器人路徑規(guī)劃中的應(yīng)用[J].內(nèi)蒙古工業(yè)大學(xué)學(xué)報(bào),2013,32(1):50-55.

  [2] 陳晉音,楊東勇,鄒青華.AS-R移動(dòng)機(jī)器人的動(dòng)態(tài)避障與路徑規(guī)劃研究[J].計(jì)算機(jī)科學(xué),2012,39(3):222-226.

  [3] BENNET D J, MCINNES C R. Distributed control of multiro-bot systems using bifurcating potential fields[J]. Robotics and Autonomous Systems, 2010,58(3):256-264.

  [4] 何少佳,劉子揚(yáng).基于慣性蟻群算法的機(jī)器人路徑規(guī)劃[J].計(jì)算機(jī)工程與應(yīng)用,2012,48(15):245-248.

  [5] 周明秀,程科,汪正霞.動(dòng)態(tài)路徑規(guī)劃中的改進(jìn)蟻群算法[J].計(jì)算機(jī)科學(xué),2013,40(1):314-316.

  [6] 許瑞.基于蟻群優(yōu)化算法的批調(diào)度問(wèn)題研究[D].合肥:中國(guó)科學(xué)技術(shù)大學(xué),2011.

  [7] 賴智銘,郭躬德.基于自適應(yīng)閾值蟻群算法的路徑規(guī)劃算法[J].計(jì)算機(jī)系統(tǒng)應(yīng)用,2014,23(2):113-119.

  [8] 王沛棟.改進(jìn)蟻群算法及在路徑規(guī)劃問(wèn)題的應(yīng)用研究[D].青島:中國(guó)海洋大學(xué),2012.

 ?。ㄊ崭迦掌冢?014-03-12)


此內(nèi)容為AET網(wǎng)站原創(chuàng),未經(jīng)授權(quán)禁止轉(zhuǎn)載。