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

　　關鍵詞： 蟻群算法；慣性方向；逼近優化；自適應

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

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

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

　　1 算法設計

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

　　1.1 構建工作環境

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

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

　　智能體在柵格空間節點的運行方向及節點距離由矩陣D表示，G為環境模型矩陣。

　　h=size（G，1）//矩陣行數

　　l=size（G，2）//矩陣列數

　　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；

　　//可選節編號及距離

　　end

　　end

　　end

　　end

　　end

　　end

　　1.2 路徑搜索

　　第一步以式（1）選擇節點：

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

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

　　1.3 端點逼近慣性優化

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

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

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

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

　　1.4 信息素動態調整

　　每次迭代結束后，對當前最優路徑進行信息素全局動態更新：

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

　　1.5 算法求解過程

　　根據以上描述，本算法步驟如下：

　?。?）柵格法建立工作環境，參數初始化，構造啟發式信息。

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

　?。?）循環執行步驟（2），直到所有螞蟻都搜尋完畢。

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

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

　?。?）循環執行步驟（2）~步驟（5），直到迭代結束。

　　2 仿真分析與參數測試

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

　　由圖3可知，雖然在路徑長度上優化前后并沒有發生變化，仍然為29.799，但可以看到優化后的路徑質量明顯優于優化前，在轉彎次數上由14次降為4次。圖4的橫坐標代表迭代次數，縱坐標代表每輪迭代的最短路徑，由圖4可知優化后的算法在收斂性上要優于前者。不同環境下的測試表明，改進后的蟻群算法表現出較強的優越性，尤其在轉彎次數和收斂性方面。仿真結果表明改進后的蟻群算法在降低轉彎次數和運算時間方面有顯著提高，從而證明了此算法的有效性和可行性。

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

　　參考文獻

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

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

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

　　[6] 許瑞.基于蟻群優化算法的批調度問題研究[D].合肥：中國科學技術大學，2011.

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

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

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