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

趙 峰，楊春曦，陳 飛，黃凌云，談 誠(chéng)

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

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

趙 峰1，楊春曦1，陳 飛1，黃凌云2，談 誠(chéng)2

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

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

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

0 引言

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

1 問(wèn)題描述

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

2 相關(guān)工作

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

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

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

3 LD-ACA實(shí)施步驟

3.1 基本定義

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

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

(1)

(2)

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

圖1 柵格圖

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

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

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

3.2.2 邊尋邊走策略

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

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

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

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

(3)

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

圖2 邊尋邊走策略流程圖

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

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

3.2.4.1 初始信息素的分布原則

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

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

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

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

(4)

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

(5)

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

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

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

(6)

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

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

4 仿真實(shí)驗(yàn)與分析

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

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

(7)

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

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

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

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

4.1 動(dòng)態(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曲線為L(zhǎng)D-ACA在動(dòng)態(tài)環(huán)境下的最優(yōu)路徑曲線，與圖5中的B曲線作對(duì)比可知，LD-ACA具有自適應(yīng)動(dòng)態(tài)環(huán)境變化的能力，而T-ACA一直按照原來(lái)尋優(yōu)的路徑行走沒(méi)有避開(kāi)動(dòng)態(tài)障礙物，路徑規(guī)劃失敗。為了進(jìn)一步驗(yàn)證LD-ACA對(duì)動(dòng)態(tài)環(huán)境變化的適應(yīng)性，我們?cè)僖淮胃淖兞谁h(huán)境路況，如圖6所示，LD-ACA依然能成功的規(guī)劃出可行路徑，表明了LD-ACA具有較好的動(dòng)態(tài)環(huán)境適應(yīng)能力。

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

圖5 動(dòng)態(tài)路徑規(guī)劃對(duì)比圖

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

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

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

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

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

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

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

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

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

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

表3 兩種算法性能比較

5 結(jié)束語(yǔ)

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

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

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

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

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

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

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

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

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

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

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

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

[12] 柳長(zhǎng)安, 鄢小虎, 劉春陽(yáng),等. 基于改進(jìn)蟻群算法的移動(dòng)機(jī)器人動(dòng)態(tài)路徑規(guī)劃方法[J]. 電子學(xué)報(bào), 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問(wèn)題為例[J]. 武漢大學(xué)學(xué)報(bào)(信息科學(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。

國(guó)家自然科學(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