摘  要： 在傳統(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)境。

　　智能體在柵格空間節(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)：

　　其中，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）：

　　為防止慣性過(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所示。

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

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

　　其中，?駐τ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ù)以上描述，本算法步驟如下：

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

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

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

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

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

　　（6）循環(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）