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

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

改進(jìn)蟻群算法的局部信息動態(tài)路徑規(guī)劃

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

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

針對傳統(tǒng)蟻群算法收斂速度慢、對動態(tài)路徑變化適應(yīng)性低的局限性，提出了一種基于局部信息獲取策略的動態(tài)改進(jìn)型蟻群算法。該算法利用局部信息獲取策略，進(jìn)行最優(yōu)局部目標(biāo)點的獲取，然后調(diào)用改進(jìn)蟻群算法獲取局部區(qū)域內(nèi)的最優(yōu)路徑，再重復(fù)循環(huán)獲取新的最優(yōu)局部目標(biāo)點，直到找到全局目標(biāo)點；與此同時，將提出的改進(jìn)型蟻群算法應(yīng)用于動態(tài)路徑規(guī)劃中的路徑尋優(yōu)與避障，仿真結(jié)果表明：提出的算法在具有與傳統(tǒng)蟻群算法相當(dāng)?shù)穆窂絻?yōu)化效果的同時，能夠有效適應(yīng)障礙變化、大大提高了路徑規(guī)劃的收斂速度。

蟻群算法；局部信息；局部目標(biāo)點；動態(tài)路徑規(guī)劃

0 引言

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

1 問題描述

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

2 相關(guān)工作

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

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

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

3 LD-ACA實施步驟

3.1 基本定義

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

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

(1)

(2)

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

圖1 柵格圖

3.2 局部信息動態(tài)路徑規(guī)劃

3.2.1 動態(tài)障礙變化設(shè)置

為驗證LD-ACA在動態(tài)路徑變化中相對于T-ACA所展現(xiàn)出的優(yōu)越性，本節(jié)設(shè)計了一種動態(tài)障礙變化規(guī)則，即：把全局環(huán)境劃分成若干個子區(qū)域，并假設(shè)機(jī)器人在所在位置的子區(qū)域行走時，該子區(qū)域的障礙狀況是固定不變的，機(jī)器人所在子區(qū)域外的信息與機(jī)器人本次路徑規(guī)劃無關(guān)。劃分的子區(qū)域數(shù)目越多，則機(jī)器人對動態(tài)路徑障礙適應(yīng)性越強(qiáng)。

3.2.2 邊尋邊走策略

鑒于T-ACA是選擇所有螞蟻行走路徑中的最優(yōu)路徑后，再沿著最優(yōu)路徑行走，這樣它的時效性就會大打折扣?；谝陨显颍覀冊O(shè)計了邊尋邊走的策略，具體策略如圖2所示：機(jī)器人首先會派出若干只螞蟻利用局部信息尋找最優(yōu)局部目標(biāo)點，找到最優(yōu)局目標(biāo)點后，機(jī)器人采用被調(diào)用蟻群算法(Called Ant Colony Algorithm，C-ACA)，尋找到達(dá)該最優(yōu)局部目標(biāo)點的最佳路徑并行走，到達(dá)最優(yōu)局部目標(biāo)點后判斷是否為全局目標(biāo)點，若是全局目標(biāo)點則尋優(yōu)結(jié)束，若不是全局目標(biāo)點，則報告機(jī)器人，繼續(xù)重復(fù)上一步驟，直到找到全局目標(biāo)點為止。

3.2.3 最優(yōu)局部目標(biāo)點的指標(biāo)設(shè)定

當(dāng)LD-ACA的邊尋邊走策略實施時，最優(yōu)局部目標(biāo)點的選取方法在很大程度上決定了是否能夠?qū)ふ业阶顑?yōu)路徑，本文以三種最優(yōu)局部目標(biāo)點確立原則作對比： 1)傳統(tǒng)的輪盤賭算法(Traditional Roulette Algorithm,TRA)； 2)改進(jìn)的輪盤賭算法(Improve The Roulette Algorithm,ITRA) 3)最小值選擇策略算法(Minimum Selection Strategy Algorithm,MSSA)。

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

(3)

其中：allowed為排除已經(jīng)走過的節(jié)點后可以前往的局部目標(biāo)點的集合，ex和ey分別為全局目標(biāo)點的橫坐標(biāo)與縱坐標(biāo)，Z為局部目標(biāo)點到全局目標(biāo)點距離集合的最小值，以取最小值Z所在的節(jié)點位置為最優(yōu)局部目標(biāo)點。

圖2 邊尋邊走策略流程圖

圖3 改進(jìn)輪盤賭算法流程圖

3.2.4 C-ACA基本參數(shù)設(shè)計

3.2.4.1 初始信息素的分布原則

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

3.2.4.2 信息素更新和優(yōu)化原則

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

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

(4)

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

(5)

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

3.2.4.3 路徑選擇概率更新規(guī)則

由基本的數(shù)據(jù)可以求得機(jī)器人在當(dāng)前位置節(jié)點前往下一個可行節(jié)點的公式如(6)式：

(6)

3.2.5 局部可視范圍內(nèi)視野的設(shè)置

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

4 仿真實驗與分析

為了驗證LD-ACA的特點，本節(jié)將T-ACA和LD-ACA分別應(yīng)用于路徑尋優(yōu)的問題求解。

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

(7)

其中:xi表示機(jī)器人運動所處的橫坐標(biāo)。

算法程序采用MATLAB進(jìn)行編程測試，算法的各參數(shù)由文獻(xiàn)[15]得到，初始值設(shè)置如表1和表2所示。

表1 兩種算法的公共參數(shù)設(shè)置

表2 各算法的自有參數(shù)設(shè)置

4.1 動態(tài)環(huán)境的性能比較

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

圖4 T-ACA尋優(yōu)路徑圖

圖5 動態(tài)路徑規(guī)劃對比圖

圖6 動態(tài)路徑規(guī)劃路徑尋優(yōu)對比圖

4.2 對動態(tài)路徑規(guī)劃的性能優(yōu)化

4.2.1 三種最優(yōu)局部目標(biāo)點選取算法的比較

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

圖7 最優(yōu)局部目標(biāo)點選擇比較圖

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

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

圖8 動態(tài)路徑規(guī)劃的性能優(yōu)化圖

4.3 靜態(tài)環(huán)境兩種算法性能比較

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

表3 兩種算法性能比較

5 結(jié)束語

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

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

[2] 劉營營. 基于模糊神經(jīng)網(wǎng)絡(luò)的移動機(jī)器人路徑規(guī)劃研究[D]. 沈陽：東北大學(xué), 2012.

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

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

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

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

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

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

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

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

[11] 王 哲,孫樹棟,曹飛祥.動態(tài)環(huán)境下移動機(jī)器人路徑規(guī)劃的改進(jìn)蟻群算法[J].機(jī)械科學(xué)與技術(shù),2013(1):42-46.

[12] 柳長安, 鄢小虎, 劉春陽,等. 基于改進(jìn)蟻群算法的移動機(jī)器人動態(tài)路徑規(guī)劃方法[J]. 電子學(xué)報, 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ìn)蟻群算法在城市汽車導(dǎo)航中的應(yīng)用[J]. 控制工程, 2016, 23(1):133-137.

[15] 葉志偉, 鄭肇葆. 蟻群算法中參數(shù)α、β、ρ設(shè)置的研究——以TSP問題為例[J]. 武漢大學(xué)學(xué)報(信息科學(xué)版), 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。

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

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

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

1671-4598(2017)08-0130-05

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

TP393

A