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

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

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

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

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

　　1 算法設(shè)計

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

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

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

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

　　智能體在柵格空間節(jié)點的運行方向及節(jié)點距離由矩陣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é)編號及距離

　　end

　　end

　　end

　　end

　　end

　　end

　　1.2 路徑搜索

　　第一步以式（1）選擇節(jié)點：

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

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

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

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

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

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

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

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

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

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

　　1.5 算法求解過程

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

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

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

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

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

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

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

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

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

　　由圖3可知，雖然在路徑長度上優(yōu)化前后并沒有發(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)境下的測試表明，改進后的蟻群算法表現(xiàn)出較強的優(yōu)越性，尤其在轉(zhuǎn)彎次數(shù)和收斂性方面。仿真結(jié)果表明改進后的蟻群算法在降低轉(zhuǎn)彎次數(shù)和運算時間方面有顯著提高，從而證明了此算法的有效性和可行性。

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

　　參考文獻

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

　　[2] 陳晉音，楊東勇，鄒青華．AS－R移動機器人的動態(tài)避障與路徑規(guī)劃研究[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] 何少佳，劉子揚.基于慣性蟻群算法的機器人路徑規(guī)劃[J].計算機工程與應(yīng)用，2012，48（15）：245-248.

　　[5] 周明秀，程科，汪正霞.動態(tài)路徑規(guī)劃中的改進蟻群算法[J].計算機科學(xué)，2013，40（1）：314-316.

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

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

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

　　（收稿日期：2014-03-12）