改進蟻群算法的局部信息動態路徑規劃

趙 峰，楊春曦，陳 飛，黃凌云，談 誠

(1.昆明理工大學 化學工程學院, 昆明 650500; 2.昆明理工大學 國土資源工程學院, 昆明 650093)

改進蟻群算法的局部信息動態路徑規劃

趙 峰1，楊春曦1，陳 飛1，黃凌云2，談 誠2

(1.昆明理工大學 化學工程學院, 昆明 650500; 2.昆明理工大學 國土資源工程學院, 昆明 650093)

針對傳統蟻群算法收斂速度慢、對動態路徑變化適應性低的局限性，提出了一種基于局部信息獲取策略的動態改進型蟻群算法。該算法利用局部信息獲取策略，進行最優局部目標點的獲取，然后調用改進蟻群算法獲取局部區域內的最優路徑，再重復循環獲取新的最優局部目標點，直到找到全局目標點；與此同時，將提出的改進型蟻群算法應用于動態路徑規劃中的路徑尋優與避障，仿真結果表明：提出的算法在具有與傳統蟻群算法相當的路徑優化效果的同時，能夠有效適應障礙變化、大大提高了路徑規劃的收斂速度。

蟻群算法；局部信息；局部目標點；動態路徑規劃

0 引言

路徑規劃是移動機器人研究領域的一個重要分支[1-3]，它研究的宗旨就是在有障礙物的路徑中，在能夠有效避免障礙物的前提下，尋找一條從給定起始點到給定終止點的最優的路徑。其中最優指標既可以是距離最短，又可以是時間最短，還可以是帶有權值的二者的結合，而障礙物可以分為靜態障礙物和動態障礙物。因此，開展對該領域的研究對于科學實驗、救援搶險、防爆、排雷等工程實施均具有重要意義[4].由于最優路徑問題計算復雜度高，使得傳統算法在面對規模較大、實時性較強的問題時，搜索效率較差[5]。而蟻群算法與其他啟發式算法相比，在求解性能上具有很強的魯棒性和計算復雜度低等特點。因此，該算法被廣泛應用于解決旅行商[6-7]、車間調度[8-9]等問題的研究。

1 問題描述

由于采用傳統蟻群算法(Traditional Ant Colony Algorithm，T-ACA)對靜態障礙物問題的研究相對成熟，因此，人們在使用T-ACA進行路徑尋優取得了一定效果。但T-ACA也存在一定的局限性，比如T-ACA會在機器人出發前設置幾十只甚至上百只螞蟻用來搜索最優路徑，而且在此基礎上還要進行迭代幾十次甚至上百次，這樣要花費大量的時間和計算資源。在路徑尋優完成后，機器人將沿著搜尋到的一條最優路徑行走。如果路徑中的障礙情況發生變化，則原來搜尋到的最優路徑就已經過時，還要再重新進行路徑尋優。在這種情況下既沒能夠避開動態障礙，也浪費了時間。針對T-ACA在此方面的缺陷，國內外各方面的研究學者進行了相應的動態路徑規劃方面的探索。

2 相關工作

文獻[10]從T-ACA中得到啟發，限制信息素的上下限，在動態路徑規劃過程中，對動態障礙物進行了膨化處理，通過減小相應的膨化區域，進一步檢測碰撞是否發生最終獲取無碰最優路徑。文獻[11]引入人工勢場的概念，為目標點定義吸引勢能，障礙物定義排斥勢能，機器人在勢能的引導下可以從起點出發，避開障礙物，達到目標點。仿真結果表明，其算法能夠適用于動態路徑規劃。文獻[12]借鑒狼群分配原則，即：剔除掉最差路徑上螞蟻釋放的信息素。仿真結果結果表明了該方法的可行性和有效性。

文獻[13]的核心思想在于如何求得移動障礙物的線性函數，進而避開移動障礙物。仿真結果表明，該算法具有高實時性，而且非常適合在復雜和動態環境實時導航。文獻[14]針對車輛路徑規劃問題，將A*算法與T-ACA相結合，并且對在螞蟻走進“死胡同”到走出死胡同這條局部路徑上不釋放信息素，降低了其他螞蟻走進“死胡同”的概率。仿真結果表明，改進算法不僅具有很好躲避動態障礙的能力，而且具有較短的尋優時間。

上述與T-ACA算法相關的研究，雖然取得了一定的效果，但是都采用了二次規劃的思想，即：首先進行一次靜態規劃，再進行一次動態規劃，雖然在避障效果方面有了大幅提高，但與此同時，計算復雜度和尋優時間也成比例的提高，而且也沒有以某個具體的環境背景為參考變量。因此，本文，以城市某個區域內交通環境為切入點，側重于整個區域內的各個路口的交通實時狀態更新與規劃，將交通環境簡化為柵格地圖的形式，路口的擁堵狀況簡化為各個柵格變換狀況，并假設各個路口的交通只會在擁堵和暢通兩個狀態之間切換，不需要考慮各種如速度、加速度等運動狀態變化狀況，提出了一種改進蟻群算法的局部信息動態路徑規劃算法 (Local Information Dynamic Path Planning Based on Improved Ant Colony Algorithm，LD-ACA)，該算法采用邊走邊規劃的方式能夠充分利用局部信息動態規劃行走路徑，具有良好的動態環境適應性和較低的計算復雜度。

3 LD-ACA實施步驟

3.1 基本定義

記G為機器人在二維平面內的運動區域，機器人映射實際交通環境中具體某個車輛，運動區域映射實際的交通規劃區域，區域內的柵格編號如圖1所示，在G中建立直角坐標系，以G左下角為坐標零點，橫軸為X軸，縱軸為Y軸。設在相關區域內存在若干個障礙物柵格，在圖1中用黑色柵格表示，實際交通環境中表示為路口擁堵。無障礙物柵格用白色柵格表示，實際交通環境中表示為路口暢通。其中每個柵格為正方形，其邊長已知。假設機器人能夠從起始點經過路徑規劃最終達到目的地點。機器人只在各個柵格內的中心點行走，關系計算公式如下：

X:xi=a·(mod(i,MM)-0.5)

(1)

(2)

關系式中，a為每個柵格的邊長，橫(縱)坐標的最大柵格數值為MM,柵格總數為e=MM·MM，每個柵格的坐標為(xi,yi),i為每個小正方形的柵格編號，mod為求余運算，而ceil為舍余取整運算。其中機器人的起始點和最終目的地點已知。

圖1 柵格圖

3.2 局部信息動態路徑規劃

3.2.1 動態障礙變化設置

為驗證LD-ACA在動態路徑變化中相對于T-ACA所展現出的優越性，本節設計了一種動態障礙變化規則，即：把全局環境劃分成若干個子區域，并假設機器人在所在位置的子區域行走時，該子區域的障礙狀況是固定不變的，機器人所在子區域外的信息與機器人本次路徑規劃無關。劃分的子區域數目越多，則機器人對動態路徑障礙適應性越強。

3.2.2 邊尋邊走策略

鑒于T-ACA是選擇所有螞蟻行走路徑中的最優路徑后，再沿著最優路徑行走，這樣它的時效性就會大打折扣。基于以上原因，我們設計了邊尋邊走的策略，具體策略如圖2所示：機器人首先會派出若干只螞蟻利用局部信息尋找最優局部目標點，找到最優局目標點后，機器人采用被調用蟻群算法(Called Ant Colony Algorithm，C-ACA)，尋找到達該最優局部目標點的最佳路徑并行走，到達最優局部目標點后判斷是否為全局目標點，若是全局目標點則尋優結束，若不是全局目標點，則報告機器人，繼續重復上一步驟，直到找到全局目標點為止。

3.2.3 最優局部目標點的指標設定

當LD-ACA的邊尋邊走策略實施時，最優局部目標點的選取方法在很大程度上決定了是否能夠尋找到最優路徑，本文以三種最優局部目標點確立原則作對比： 1)傳統的輪盤賭算法(Traditional Roulette Algorithm,TRA)； 2)改進的輪盤賭算法(Improve The Roulette Algorithm,ITRA) 3)最小值選擇策略算法(Minimum Selection Strategy Algorithm,MSSA)。

第三種方法是借鑒貪婪算法思想，提出最小值選擇策略算法，核心思想為：以全局目標點為參考變量，選取所有可行的局部目標點中距離全局目標點距離值為最小的點為最優局部目標點，距離計算公式如(3)式：

(3)

其中：allowed為排除已經走過的節點后可以前往的局部目標點的集合，ex和ey分別為全局目標點的橫坐標與縱坐標，Z為局部目標點到全局目標點距離集合的最小值，以取最小值Z所在的節點位置為最優局部目標點。

圖2 邊尋邊走策略流程圖

圖3 改進輪盤賭算法流程圖

3.2.4 C-ACA基本參數設計

3.2.4.1 初始信息素的分布原則

在C-ACA路徑尋優過程中，螞蟻種群在下一步可以前往的節點稱為可行節點，可行節點的選取依據主要有兩方面：1)當前節點到可行節點路徑上的殘留信息素濃度。2)可行節點的啟發式信息。本節取啟發式信息ηij=1/dij，j和i分別為每個小正方形的柵格坐標(節點位置)，dij為當前節點i到可行節點j之間的距離。

3.2.4.2 信息素更新和優化原則

C-ACA信息素更新策略只發生在從起始點到最優局部目標點走通的道路上，更新規則如式(4)：

τij(t)=(1-R)·τij(t-1)+Δτij

(4)

τij(t)為所有螞蟻在當前t時刻在可以走通路徑(i,j)留下的信息素，τij(t-1)為所有螞蟻在t-1時刻在可以走通路徑(i,j)留下的信息素，Δτij為從t-1時刻到t時刻所有螞蟻在可以走通路徑(i,j)增加的信息素，計算公式如(5)式：

(5)

其中：Lk為第k只螞蟻迭代過程中尋找到的可行路徑，Q為第k只螞蟻在其自身尋優路徑上留下的信息素的總和。同時為了避免螞蟻種群在某條路徑上過于扎堆，導致陷入局部最優解的問題，在信息素初步更新完成后，進行信息素的揮發策略，R為揮發因子。

3.2.4.3 路徑選擇概率更新規則

由基本的數據可以求得機器人在當前位置節點前往下一個可行節點的公式如(6)式：

(6)

3.2.5 局部可視范圍內視野的設置

局部信息的獲取方式對于LD-ACA的性能有重大影響，搜索范圍越小，對動態環境變化適應性越強。當搜索范圍逐步增大到全局環境的范圍時，該算法就退化成靜態路徑規劃。為分析局部視野與路徑優化的關系，本文設計了兩種局部信息獲取方式：一步范圍視野和兩步范圍視野，即：一步范圍視野是機器人從當前位置只走一步所能達到的范圍作為所獲得的局部信息；兩步范圍視野是機器人從當前位置走兩步所能達到的范圍作為所獲得的局部信息。

4 仿真實驗與分析

為了驗證LD-ACA的特點，本節將T-ACA和LD-ACA分別應用于路徑尋優的問題求解。

以每行(列)柵格數為20為例，在本文的LD-ACA中，設置了三種不同的障礙環境G1、G2、G3，三種障礙環境會隨著機器人的當前位置變化而變化，障礙環境的變化規律如(7)式：

(7)

其中:xi表示機器人運動所處的橫坐標。

算法程序采用MATLAB進行編程測試，算法的各參數由文獻[15]得到，初始值設置如表1和表2所示。

表1 兩種算法的公共參數設置

表2 各算法的自有參數設置

4.1 動態環境的性能比較

為方便比較，本節為兩種算法設置了相同的算法參數和環境參數：1)兩種算法的局部信息獲取方式為一步范圍視野；2)每行(列)柵格數為20；圖4和圖5中的曲線為T-ACA在靜態環境下的最優路徑曲線，而圖5中的A曲線為LD-ACA在動態環境下的最優路徑曲線，與圖5中的B曲線作對比可知，LD-ACA具有自適應動態環境變化的能力，而T-ACA一直按照原來尋優的路徑行走沒有避開動態障礙物，路徑規劃失敗。為了進一步驗證LD-ACA對動態環境變化的適應性，我們再一次改變了環境路況，如圖6所示，LD-ACA依然能成功的規劃出可行路徑，表明了LD-ACA具有較好的動態環境適應能力。

圖4 T-ACA尋優路徑圖

圖5 動態路徑規劃對比圖

圖6 動態路徑規劃路徑尋優對比圖

4.2 對動態路徑規劃的性能優化

4.2.1 三種最優局部目標點選取算法的比較

為驗證本文所使用的MSSA在最優局部目標點獲取方面的優越性，本文給出了三種最優局部目標點獲取算法在不同柵格數目條件下進行50次試驗得到的平均值。如圖7所示， 以尋優時間為評判指標，可知在柵格數目較小情況下，三者的尋優時間相差不大，當柵格數目大于30時，MSSA的尋優時間明顯短于其他兩種算法；同理，以最優路徑為指標 ，當柵格數目大20時，MSSA找出最優路徑顯短于其他兩種算法。

圖7 最優局部目標點選擇比較圖

4.2.2 局部信息搜索范圍變化比較

為了驗證局部信息的獲取范圍對LD-ACA的影響，我們把局部信息的獲取范圍分別設置為一步范圍視野和兩步范圍視野來對比兩種條件下的性能優劣。給定的兩種算法的相同條件是：1)同等柵格數目；2)最優路徑相等或相近。評判指標為：兩種算法的尋優時間。圖8中的上圖的前提條件為每行(列)柵格數目相同，可知在每行(列)柵格數目小于等于20的情況下，二者的尋優時間相差無幾，但當每行(列)柵格數目為30、40、50時，兩步范圍視野算法尋優時間明顯短于一步范圍算法；同理，圖8中的下圖前提條件為最優路徑相等或相近，可知在最優路徑小于等于33的情況下，二者的尋優時間相差無幾，但當最優路徑超過33時，兩步范圍算法尋優時間明顯短于一步范圍算法。但我們應同時看到在兩步范圍算法的路徑尋優過程中，放置的螞蟻數目和迭代次數都是5，而一步范圍算法放置的螞蟻數目和迭代次數都是2，由此可見，在局部信息獲取方式中，搜索范圍擴大的代價就是增加了計算負擔。

圖8 動態路徑規劃的性能優化圖

4.3 靜態環境兩種算法性能比較

為了驗證T-ACA和LD-ACA在不同柵格數目下的性能差異，本節給出了兩種算法在靜態環境情況下的最優路徑性能表，兩種算法都在每種柵格數目環境條件下進行了50次的仿真實驗，并取平均值。得到如表3所示的仿真結果，由表3可知在每行(列)柵格數小于30，即：柵格數目較少時，兩種算法在最優路徑和尋優時間兩個路徑尋優指標上沒有太大差別，但當每行(列)的柵格數目大于30時，LD-ACA在僅放置5只螞蟻和進行5次迭代的情況下的尋優指標就明顯優于放置50只螞蟻進行50次迭代的T-ACA。

表3 兩種算法性能比較

5 結束語

針對T-ACA在動態環境路徑尋優的過程中的局限性，本文對T-ACA進行了相應的改進，并以實際的區域交通規劃背景為切入點，提出了局部信息動態路徑規劃的改進蟻群算法，所提出的LD-ACA在保證與T-ACA具有相當的優化效果的同時，能夠有效適應障礙變化、大大提高了路徑規劃的收斂速度。與此同時，對LD-ACA在最優局部目標點選擇和局部信息獲取兩個方面進行了優化，優化方法在保證螞蟻種群數目和迭代次數沒有大幅增加的前提下，大幅度地優化了尋優指標。

[1] 趙開新, 魏 勇, 王東署. 改進蟻群算法在移動機器人路徑規劃中的研究[J]. 計算機測量與控制, 2014, 22(11):67-70.

[2] 劉營營. 基于模糊神經網絡的移動機器人路徑規劃研究[D]. 沈陽：東北大學, 2012.

[3] 柏 硌, 趙剛要. 基于MapReduce與蟻群優化的航路規劃算法[J]. 計算機工程, 2015, 41(5):38-44.

[4] 趙娟平, 高憲文, 劉金剛,等. 移動機器人路徑規劃的參數模糊自適應窗口蟻群優化算法[J]. 控制與決策, 2011, 26(7):1096-1100.

[5] 袁亞博, 劉 羿, 吳 斌. 改進蟻群算法求解最優路徑問題[J]. 計算機工程與應用, 2016, 52(6):8-12.

[6] 基于遺傳-模擬退火的蟻群算法求解TSP問題[J]. 計算機測量與控制, 2016,24(3):143-144.

[7] 楊學峰. 蟻群算法求解TSP問題的研究[D].長春. 吉林大學, 2010.

[8] 宋代立, 張 潔. 蟻群算法求解混合流水車間分批調度問題[J]. 計算機集成制造系統, 2013, 19(7):1640-1647.

[9] 周 鵬. 求解置換流水車間調度問題的混合蟻群算法[J]. 計算機工程與應用, 2009, 45(17):191-193.

[10] 屈 鴻, 黃利偉, 柯 星. 動態環境下基于改進蟻群算法的機器人路徑規劃研究[J]. 電子科技大學學報, 2015(2):260-265.

[11] 王 哲,孫樹棟,曹飛祥.動態環境下移動機器人路徑規劃的改進蟻群算法[J].機械科學與技術,2013(1):42-46.

[12] 柳長安, 鄢小虎, 劉春陽,等. 基于改進蟻群算法的移動機器人動態路徑規劃方法[J]. 電子學報, 2011, 39(5):1220-1224.

[13] Zhu Q, Hu J, Cai W, et al. A new robot navigation algorithm for dynamic unknown environments based on dynamic path re-computation and an improved scout ant algorithm[J]. Applied Soft Computing, 2011, 11(8):4667-4676.

[14] 葛延峰, 陳 濤, 孔祥勇,等. 改進蟻群算法在城市汽車導航中的應用[J]. 控制工程, 2016, 23(1):133-137.

[15] 葉志偉, 鄭肇葆. 蟻群算法中參數α、β、ρ設置的研究——以TSP問題為例[J]. 武漢大學學報(信息科學版), 2004,29(7):597-601.

Local Information Dynamic Path Planning Based on Improved Ant Colony Algorithm

Zhao Feng2, Yang Chunxi2, Chen Fei2, Huang Lingyun2, Tan Cheng2

(1.Kunming University of Science and Technology, Faculty of Chemical Engineering, Kunming 650500, China；2.Kunming University of Science and Technology, Faculty of Land Resource Engineering, Kunming 650093, China)

Considering the limitation of traditional ant colony algorithm’s slowish convergence and bad self-adaptability to dynamic path change, a dynamic improved ant colony algorithm based on local information acquisition strategy is proposed in this paper. Firstly,The local information acquisition strategy is used to obtain the optimal local target point. Then, the improved ant colony algorithm is called to obtain the optimal path in the local region.And the new optimal local target point of the neighbor region is obtained by repeating the loop until the global target point is found. Moreover, the improved ant colony algorithm is applied to the path optimization and obstacle avoidance in dynamic path planning. The simulation results show that the new algorithm proposed not only has considerable path optimization performance compared with the traditional ant colony one, but also has self-adaptive capacity faced with time-vary obstacles and faster convergence speed.

ant colony algorithm; local information; local target point; dynamic path planning

2017-01-19；

2017-02-27。

國家自然科學基金(61364002);云南省教育廳科學研究基金(2016YJS020)。

趙 峰(1990-)，男，河北秦皇島人，碩士研究生，主要從事智能算法方向的研究。

楊春曦(1976-)，男，貴州松桃人，博士，教授，主要從事網絡控制系統，智能控制方向的研究。

1671-4598(2017)08-0130-05

10.16526/j.cnki.11-4762/tp.2017.08.034

TP393

A