偏微分高程圖環(huán)境蟻群算法的三維路徑規(guī)劃

肖秦琨, 王　弋, 羅藝闖

(西安工業(yè)大學(xué)電子信息工程學(xué)院, 陜西 西安 710021)

?

偏微分高程圖環(huán)境蟻群算法的三維路徑規(guī)劃

肖秦琨, 王弋, 羅藝闖

(西安工業(yè)大學(xué)電子信息工程學(xué)院, 陜西 西安 710021)

摘要：針對在三維空間路徑規(guī)劃中建模與避障問題,提出了一種新的在偏微分高程建模環(huán)境下蟻群算法的三維路徑規(guī)劃方法。首先,利用抽象建模和高程建模方法分別構(gòu)建三維空間環(huán)境,并用偏微分對高程環(huán)境進(jìn)行最優(yōu)數(shù)據(jù)提取,在此基礎(chǔ)上利用高程數(shù)學(xué)建模方法進(jìn)行三維空間重建,最終形成偏微分高程環(huán)境。其次,首次將種群對于環(huán)境的最佳適應(yīng)度值作為目標(biāo)函數(shù)評判蟻群尋找最優(yōu)路徑的決策能力。最后,在不同的建模環(huán)境中應(yīng)用蟻群算法進(jìn)行路徑尋優(yōu),輸出最優(yōu)路徑。通過對仿真結(jié)果和實驗數(shù)據(jù)分析,驗證了所提方法的有效性和正確性。

關(guān)鍵詞：偏微分高程建模建模; 蟻群算法; 抽象建模; 三維路徑規(guī)劃; 建模與避障

0引言

三維路徑規(guī)劃的建模方法和路徑規(guī)劃算法是機(jī)器人野外作業(yè)面臨的關(guān)鍵技術(shù)難題[1-3],針對這個問題,許多學(xué)者進(jìn)行了深入的探索,并取得了一系列研究成果[4-5]。

為了解決機(jī)器人在三維空間環(huán)境中路徑規(guī)劃問題,一些研究者提出了高程建模思想[6-7]。核心理論是利用二維柵格先將三維空間環(huán)境數(shù)據(jù)離散化,再將三維空間環(huán)境數(shù)據(jù)所對應(yīng)的2.5維地形高度信息存入每一個相對應(yīng)二維柵格中,進(jìn)而整個三維空間環(huán)境的地形特征將被存儲在各個區(qū)域中。文獻(xiàn)[8-9]通過對三維空間環(huán)境中較大曲率的地形信息數(shù)據(jù)點進(jìn)行提取,并對連續(xù)多幅的三維空間場景進(jìn)行掃描匹配,最終將多足機(jī)器人所在的三維空間環(huán)境用高程圖進(jìn)行表示。文獻(xiàn)[10]在高程建模的三維空間環(huán)境中,提出了通過概率定位算法進(jìn)行行星探測器的設(shè)計。文獻(xiàn)[11]將市區(qū)路面、陸島以及空間環(huán)境中的障礙物用高程圖進(jìn)行表示,然后對其進(jìn)行檢測。文獻(xiàn)[12]提出一種基于拓?fù)涓叱棠Ｐ偷娜S環(huán)境建模方法,進(jìn)行路徑規(guī)劃。

蟻群算法[13]是受螞蟻的集體覓食行為及在覓食過程中具有其獨特優(yōu)勢的啟示,提出的一種模仿蟻群覓食過程的算法。通過實驗觀察發(fā)現(xiàn),盡管個體螞蟻在覓食過程中的覓食行為比較簡單,但是蟻群卻能夠在實時復(fù)雜多變的外部環(huán)境中將其所具有的群體行為能力出色地發(fā)揮出來,它們不但能通過蟻群所具有的獨特的行為能力——將大于自身大小成十上百倍的食物安全完整地送回自己的巢穴,而且蟻群一旦在覓食途中遇到障礙物,蟻群便能夠很迅速地重新找到一條能夠到達(dá)目標(biāo)點的最優(yōu)路徑。

在通過對高程建模以及蟻群算法的研究基礎(chǔ)上,本文提出一種結(jié)合偏微分高程建模與蟻群算法的三維路徑規(guī)劃方法,該方法的優(yōu)勢在于:①能夠?qū)⒃诔橄蠼：透叱探７椒ㄖ谐霈F(xiàn)冗余的空間數(shù)據(jù)通過偏微分高程數(shù)學(xué)方法進(jìn)行極值化處理,從而能夠?qū)θS空間環(huán)境的主要信息進(jìn)行更簡單明了地表述。②與抽象建模方法、高程建模方法相比,通過對蟻群適度值的計算并將所獲取的數(shù)據(jù)進(jìn)行二次曲線擬合輸出,以此能夠顯示出在偏微分高程環(huán)境下,蟻群在進(jìn)行路徑規(guī)劃過程中具有更強(qiáng)的目標(biāo)決策能力,以及對外部環(huán)境的適應(yīng)能力,并且輸出的路徑更為安全合理,避障效果更好。③通過計時函數(shù)對于時間資源消耗的計算,可以得出在偏微分高程建模方法下蟻群算法的所消耗的時間資源最少。

1三維空間抽象建模

在三維空間地圖中建立以左下角的頂點為坐標(biāo)原點O,經(jīng)度、緯度增加的方向分別為x軸、y軸,空間高度增加的方向為z軸的三維空間坐標(biāo)系。在所建立的三維空間坐標(biāo)系中取點O為坐標(biāo)原點,ON為x軸所對應(yīng)經(jīng)度增加方向上的最大長度,OO′為y軸所對應(yīng)緯度增加方向上的最大長度,OP為z軸所對應(yīng)空間高度增加方向上的最大長度。最終,形成三維空間立方體區(qū)域OPMN-O′P′M′N′,即蟻群算法將要在該三維空間區(qū)域內(nèi)進(jìn)行路徑規(guī)劃[14]。

當(dāng)三維空間路徑規(guī)劃區(qū)域構(gòu)建起來之后,從所建立的三維空間區(qū)域OPMN-O′P′M′N′中,將該三維空間區(qū)域利用等分方法對三維空間路徑規(guī)劃時所需的搜索數(shù)據(jù)點進(jìn)行提取。先將三維空間區(qū)域在經(jīng)度增加方向(x軸延伸方向)的最大長度ON進(jìn)行n等分,得到n+1個平面Πi(i=1,2,…,n),然后再將所形成的n+1個平面沿y軸延伸方向的最大長度OP進(jìn)行m等分,然后沿z軸延伸方向最大長度OO′進(jìn)行l(wèi)等分,最后,利用抽象建模的數(shù)學(xué)方法,求解出里面的交點,如圖1所示。

圖1　三維空間抽象建模空間圖與平面圖

通過以上步驟,立體的三維路徑規(guī)劃區(qū)域OPMN-O′P′M′N′就離散化為一個三維空間數(shù)據(jù)點的集合,而且每一個數(shù)據(jù)點都有兩個坐標(biāo)與其相對應(yīng),即編號坐標(biāo)q1(i,j,k) (i=0,1,…,n; j=0,1,…,m; k=0,1,…,l)和位置坐標(biāo)q2(xi,yi,zi),其中,i,j,k分別為當(dāng)該點當(dāng)前所對應(yīng)的劃分編號。蟻群算法將在通過抽象建模方法構(gòu)建的三維空間環(huán)境中的這些空間數(shù)據(jù)點上進(jìn)行路徑尋優(yōu),最終輸出一條從起點到目標(biāo)點并且滿足某項最優(yōu)路徑輸出指標(biāo)的最優(yōu)路徑。

為了方便解決在構(gòu)建的三維空間進(jìn)行路徑規(guī)劃,本文設(shè)定坐標(biāo)軸原點為路徑規(guī)劃區(qū)域內(nèi)的最低點0,并將該點作為對應(yīng)的平面環(huán)境視為海平面高度,設(shè)定高度為600 m的平面為主要進(jìn)行路徑規(guī)劃陸地平面;在z軸延伸方向上,將高度區(qū)域(0,2 km),以100 m為高度差進(jìn)行等分;在(x,y)平面內(nèi),分別在x軸和y軸的延伸方向上,將平面區(qū)域(21 km,21 km)以1 km為距離差進(jìn)行等分。首先通過抽象建模方法建立一個區(qū)域跨度為 21 km×21 km×2 km的三維空間不平坦路面環(huán)境的仿真圖。其次,在上述所建立的三維空間區(qū)域內(nèi),保持海平面高度和主要進(jìn)行路徑規(guī)劃的陸地平面不變,將在x軸延伸方向上(5 km,9 km)平面范圍內(nèi),所對應(yīng)的z軸延伸方向上的高度值設(shè)置為600 m;在y軸延伸方向上(3 km,19 km)平面范圍內(nèi),所對應(yīng)的z軸延伸方向上的高度值設(shè)置為600 m,最終利用抽象建模方法構(gòu)建一條三維空間平坦路面，如圖2、圖3所示。

圖2　抽象建模三維空間不平坦路面

圖3　抽象建模三維空間平坦路面

2三維空間高程與偏微分高程建模

2.1三維空間高程建模

2.1.1場景柵格劃分

假設(shè)設(shè)定xy平面內(nèi)所有通過激光采集的數(shù)據(jù)點的分布服從相互獨立的正態(tài)分布f(x,y)~(μ,σ2):

(1)

(2)

式中,xc,yc是所采集空間區(qū)域內(nèi)激光數(shù)據(jù)點的期望值。那么通過某一激光數(shù)據(jù)點ri對與其相應(yīng)的柵格Cij的影響程度的計算,則將該激光數(shù)據(jù)點標(biāo)定為該柵格內(nèi)與之相對應(yīng)的第h個數(shù)據(jù)點。最后通過大量的參數(shù)賦值運算,可以計算出每一組通過激光采集到的數(shù)據(jù)點ri={r1,r2,…,rn}對與其相對應(yīng)的柵格影響度μh={μ1,μ2,…,μn}。將影響程度大于閾值μthreshold的點存入柵格中,便完成了將三維空間激光數(shù)據(jù)點存入與之相對應(yīng)的柵格的過程。通過對激光點ri所在柵格cij中對應(yīng)的μ進(jìn)行規(guī)一化處理,可知柵格的高度值由柵格中所有激光點高度的加權(quán)平均得出,即

(3)

2.1.2可行區(qū)域劃分

根據(jù)柵格內(nèi)激光數(shù)據(jù)點在高度方向上的分布情況,可以計算每個柵格Cij的平均高度:

(4)

從而可以通過計算每兩個柵格之間的高度差,以此來獲得在某一激光數(shù)據(jù)采集區(qū)域內(nèi)道路的平坦程度并判斷這一區(qū)域是否可行。判斷某一區(qū)域是否可行,柵格間的高度差需滿足公式:

(5)

式中,Hij為柵格Cij所在區(qū)域的平均高度；Hthresh為根據(jù)無人地面自主戰(zhàn)車自身情況所設(shè)定的閾值。此過程不對鄰域空閑柵格進(jìn)行計算。

根據(jù)以上公式,利用高程建模方法形成如圖4所示的高程環(huán)境。

圖4　高程建模環(huán)境圖

2.2三維空間偏微分高程建模

由式(2)和式(3)可以獲取某一時間點在高程建模環(huán)境內(nèi)通過激光采集的空間點數(shù)據(jù),然后通過偏導(dǎo)求極值的數(shù)學(xué)計算,利用偏微分高程數(shù)學(xué)方法進(jìn)行空間數(shù)據(jù)采集,以獲取最優(yōu)數(shù)據(jù),計算過程如下:

(6)

(7)

--------------------式中

則可以根據(jù)極值公式,求得最優(yōu)解進(jìn)而可以求出最優(yōu)的數(shù)據(jù)集合。偏微分高程建模環(huán)境的可行區(qū)域劃分根據(jù)柵格內(nèi)激光點在高度方向上的分布情況,可以計算每個柵格Cij的平均高度:

(8)

從而可以通過計算每兩個柵格之間的高度差,以此來獲得在某一激光數(shù)據(jù)采集區(qū)域內(nèi)道路的平坦程度并判斷這一區(qū)域是否可行。判斷某一區(qū)域是否可行,柵格間的高度差需滿足公式:

(9)

式中,Hij為柵格Cij所在區(qū)域的平均高度；Hthresh為根據(jù)機(jī)器人自身情況所設(shè)定的閾值。此過程不對鄰域空閑柵格進(jìn)行計算。

根據(jù)以上公式,利用偏微分高程圖建模方法形成如圖5所示的偏微分高程圖環(huán)境。

3蟻群算法的三維空間路徑規(guī)劃

在上述3種不同的建模方法所建立的三維空間環(huán)境中,應(yīng)用蟻群算法進(jìn)行路徑規(guī)劃。

步驟 1蟻群通過啟發(fā)函數(shù)來計算到達(dá)下一個搜索點的概率,并判斷該點是否可行。啟發(fā)函數(shù)為

(10)

式中,D(i,j,k)w1為螞蟻移動的兩個搜索點之間距離,促使其選擇與當(dāng)前所在節(jié)點距離較近的搜索點;S(i,j,k)w2為安全因子,當(dāng)搜索節(jié)點無法到達(dá)時,該值為0,促使其選擇可以達(dá)到的搜索點;Q(i,j,k)w3為下一點到終點的距離長度,促使其選擇到目標(biāo)點距離更近的點;w1、w2、w3為系數(shù),代表上述各因素的重要程度。

圖5　偏微分高程建模環(huán)境圖

螞蟻在平面Πi上的當(dāng)前點pi選擇平面Πi+1上下一個點pi+1:

(11)

式中,τa+1,u,v為平面Πi+1上點p(i+1,u,v)的信息素值。

步驟 2信息素更新:蟻群算法將三維環(huán)境搜索空間的散點wi={w1,w2,…,wn}作為節(jié)點進(jìn)行搜索。

信息素的更新包括局部更新和全局更新兩部分,局部更新能夠使螞蟻對未經(jīng)過搜索的節(jié)點的搜索概率增加,以達(dá)到全局搜索的目的。局部信息素的更新會隨著螞蟻對搜索點搜索同時進(jìn)行更新,信息素更新公式為

(12)

式中,τijk為點(i,j,k)上所帶的信息素值;ξ為信息素的衰減系數(shù)。

全局更新是指當(dāng)螞蟻對一條路上所有數(shù)據(jù)點完成搜索以后,將所搜索路徑的長度設(shè)定為評價值,從該次蟻群所輸出的所有路徑中,選擇其中搜索路徑長度最短路徑,增加搜索路徑長度最短路徑上各搜索點的信息素值,信息素更新公式為

(13)

式中,length(m)為第m只螞蟻移動過的距離長度;ρ為信息素更新系數(shù);K為常量系數(shù)。Δτijk為兩點之間留下的殘留信息素濃度。

當(dāng)完成一次全局路徑規(guī)劃后,蟻群就會在路徑集合中選擇出一條最優(yōu)路經(jīng)。

步驟 3通過蟻群在不同建模環(huán)境適應(yīng)度值的計算與提取輸出最優(yōu)路徑。蟻群對三維空間各個路徑搜索點適應(yīng)度值大小的選擇,體現(xiàn)了蟻群尋找最優(yōu)路徑時的決策能力,適應(yīng)度值越小,說明選擇該條路徑越合理。當(dāng)蟻群經(jīng)過每一個搜索點時,螞蟻會保存該搜索點所對應(yīng)適應(yīng)度值,蟻群對三維環(huán)境的適應(yīng)度值計算公式為

(14)

式中,D(i,j)表示蟻群通過兩個搜索點時路徑的長度;H(i,j,k)為該搜索點所對應(yīng)空間的高度值。

當(dāng)蟻群算法在不同的建模環(huán)境下進(jìn)行路徑規(guī)劃時并且經(jīng)過若干次迭代后,輸出最優(yōu)路徑(即最佳適應(yīng)度值所對應(yīng)的路徑)。適應(yīng)度值越小,表明蟻群的決策能力越強(qiáng),輸出的路徑越安全合理。

4實驗結(jié)果及數(shù)據(jù)分析

在Matlab環(huán)境下采用計時函數(shù)(計時函數(shù)可以定量計算完成制定程序所消耗的時間資源)計算出蟻群從相同起點到目標(biāo)點在不同建模環(huán)境下所消耗的時間資源。通過對適應(yīng)度值(適應(yīng)度值越小,路徑規(guī)劃時的決策能力越強(qiáng)、避障效果更好,輸出的最優(yōu)路徑更為合理)的計算,并將所有最佳適應(yīng)度值提取利用最小二乘法曲線擬合的輸出,從曲線圖中可以體現(xiàn)出蟻群在最優(yōu)路徑尋找過程中的決策能力和避障效果。

4.1三維路徑規(guī)劃步驟及仿真結(jié)果

在本次實驗中取不平坦路面環(huán)境,平坦路面環(huán)境,高程建模不平坦路面環(huán)境,高程建模平坦路面環(huán)境,偏微分高程建模不平坦路面環(huán)境和偏微分高程平坦路面等6種不同建模環(huán)境的起點為starty=10,starth=3;終點為endy=9,endh=3;蟻群算法的初始參數(shù)設(shè)置為:w1=3,w2=1,w3=2,K=120,空間離散點n=21,螞蟻移動步長m=1,螞蟻在(x,y)平面內(nèi)進(jìn)行一次尋優(yōu)過程的最大縱向和橫向移動距離為2,迭代次數(shù)為100次。在不同的種群數(shù)量和信息素參數(shù)下進(jìn)行試驗,①信息素ρ=0.9,種群數(shù)量PopNumber=10;②信息素ρ=0.7,種群數(shù)量PopNumber=10;③信息素ρ=0.5,種群數(shù)量PopNumber=10。

4.1.1仿真結(jié)果

圖6~圖11分別為在參數(shù)ρ=0.9,種群數(shù)量PopNumber=10時,抽象建模不平坦路面(見圖6)、抽象建模平坦路面(見圖7)、高程建模不平坦路面(見圖8)、高程建模平坦路面(見圖9)、偏微分高程建模不平坦路面(見圖10)、偏微分高程建模平坦路面(見圖11)中所輸出的最優(yōu)路徑。

圖6　抽象建模不平坦路面路徑規(guī)劃圖

圖7　抽象建模環(huán)境平坦路面路徑規(guī)劃圖

圖8　高程建模環(huán)境不平坦路面路徑規(guī)劃圖

圖9　高程建模環(huán)境平坦路面路徑規(guī)劃

圖10　偏微分高程建模環(huán)境不平坦路面路徑規(guī)劃圖

圖11　偏微分高程建模環(huán)境平坦路面路徑規(guī)劃

圖12~圖17分別為在參數(shù)ρ=0.7,種群數(shù)量PopNumber=10時,抽象建模不平坦路面(見圖12)、抽象建模平坦路面(見圖13)、高程建模不平坦路面(見圖14)、高程建模平坦路面(見圖15)、偏微分高程建模不平坦路面(見圖16)、偏微分高程建模平坦路面(見圖17)中所輸出的最優(yōu)路徑。

圖12　抽象建模環(huán)境不平坦路面路徑規(guī)劃圖

圖13　抽象建模環(huán)境平坦路面路徑規(guī)劃圖

圖14　抽象建模環(huán)境不平坦路面路徑規(guī)劃圖

圖15　高程建模環(huán)境平坦路面路徑規(guī)劃圖

圖16　偏微分高程建模環(huán)境不平坦路面路徑規(guī)劃圖

圖17　偏微分高程建模環(huán)境平坦路面路徑規(guī)劃圖

圖18~圖23分別為在參數(shù)ρ=0.5,種群數(shù)量PopNumber=10時,抽象建模不平坦路面(見圖18)、抽象建模平坦路面(見圖19)、高程建模不平坦路面(見圖20)、高程建模平坦路面(見圖21)、偏微分高程建模不平坦路面(見圖22)、偏微分高程建模平坦路面(見圖23)中所輸出的最優(yōu)路徑。

圖18　抽象建模環(huán)境不平坦路面路徑規(guī)劃圖

圖19　抽象建模環(huán)境平坦路面路徑規(guī)劃圖

圖20　高程建模環(huán)境不平坦路面路徑規(guī)劃圖

圖21　高程建模環(huán)境平坦路面路徑規(guī)劃圖

圖22　偏微分高程建模環(huán)境不平坦路面路徑規(guī)劃圖

圖23　偏微分高程建模環(huán)境平坦路面路徑規(guī)劃圖

4.1.2實驗數(shù)據(jù)

在6種不同的路面環(huán)境中進(jìn)行路徑規(guī)劃時,將最佳適應(yīng)度值作為目標(biāo)函數(shù),并利用時間函數(shù)計算在上述不同建模環(huán)境的路徑規(guī)劃下所消耗的時間資源,驗證了所提方法的有效性和可行性。實驗數(shù)據(jù)如圖24~圖26和表1所示。

圖24　種群適應(yīng)曲線(ρ=0.9)

圖25　種群適應(yīng)曲線(ρ=0.7)

圖26　種群適應(yīng)曲線(ρ=0.5)

4.2實驗數(shù)據(jù)分析

首先,通過表1實驗數(shù)據(jù)的對比,可以看出在信息素大小不同,蟻群數(shù)量相同的情況下,偏微分高程環(huán)境中進(jìn)行路徑規(guī)劃是所消耗的時間資源要比在抽象建模和高程建模環(huán)境下少。并且實驗數(shù)據(jù)也可以得出信息素?fù)]發(fā)程度的大小對于路徑規(guī)劃結(jié)果會產(chǎn)生重要的影響。通過對大量相關(guān)資料研究與分析,當(dāng)ρ=0.5時,蟻群算法在二維平面環(huán)境下,找尋最優(yōu)路徑時所消耗的時間最短。但通過對本文的實驗數(shù)據(jù)分析可知,當(dāng)ρ=0.9時,蟻群算法在抽象建模環(huán)境中尋找到最優(yōu)路徑耗時最短,而當(dāng)ρ=0.7,蟻群算法在高程建模和偏微分高程建模環(huán)境下,尋找到最優(yōu)路徑所用時間最少。綜上所述,在不同的建模方法所建立的三維環(huán)境中,信息素的大小會對蟻群算法的路徑規(guī)劃結(jié)果產(chǎn)生影響。

其次,通過圖24~26可知,種群的最佳適應(yīng)度值所獲取的數(shù)據(jù)擬合曲線可知,當(dāng)同種群數(shù)目、不同信息素大小時,在偏微分高程建模環(huán)境中,蟻群算法在尋找最優(yōu)路徑過程中,種群的適應(yīng)度值在經(jīng)過若干次迭代后,所產(chǎn)生的適應(yīng)度值最小即表明,在此過程中蟻群的適應(yīng)能力最好,以及對于最優(yōu)路徑選取的決策能力最強(qiáng),從而使得蟻群輸出一條避障效果最好并且能夠安全到達(dá)目標(biāo)點的路徑。

表1　相同種群數(shù)目、不同信息素濃度(PopNumber=10,ρ=0.9,0.7,0.5)情況下的時間資源的消耗

然而,在實驗過程中發(fā)現(xiàn),在偏微分高程建模環(huán)境和高程建模環(huán)境中,蟻群在不平坦路面進(jìn)行路徑尋優(yōu)時所用時間比相同建模環(huán)境中平坦路面進(jìn)行路徑尋優(yōu)時所用的時間少。該實驗結(jié)果與當(dāng)初預(yù)想的實驗結(jié)果和在抽象建模環(huán)境中不平坦路面和平坦路面所得出的實驗結(jié)果完全相反。后大量實驗對該結(jié)果進(jìn)行驗證,得出此結(jié)果并不只是偶然在某一個信息素或者蟻群數(shù)量的一次路徑規(guī)劃過程中在才產(chǎn)生的,而是在整個建模環(huán)境中。由此可以得出一個結(jié)論:不同的建模方法或方式會對信息素的揮發(fā)程度產(chǎn)生影響,而信息素的揮發(fā)程度會對蟻群算法最后的尋優(yōu)結(jié)果產(chǎn)生影響。

綜上所述,在偏微分高程建模方法下構(gòu)建的三維空間場景相比于高程建模和抽象建模方法構(gòu)建的三維空間場景所利用的存儲空間量小,所表達(dá)的空間環(huán)境信息更明了。所以,蟻群在尋找目標(biāo)點時對環(huán)境的適應(yīng)能力、目標(biāo)點的決策能力更好,并且所消耗的時間更少。因此，蟻群在偏微分高程建模環(huán)境中進(jìn)行三維路徑規(guī)劃時所輸出的路徑最優(yōu)及避障效果更好,從而驗證了所提方法的有效性。

5結(jié)論

本文重點對三維空間環(huán)境建模和在三維空間環(huán)境建模基礎(chǔ)上蟻群算法的路徑規(guī)劃問題進(jìn)行了研究。本文提出一種新的偏微分高程建模環(huán)境下蟻群算法的三維路徑規(guī)劃方法,該方法解決了以下問題:①將在抽象建模和高程建模方法中出現(xiàn)冗余的空間數(shù)據(jù),通過對空間數(shù)據(jù)采集過程中信息數(shù)據(jù)進(jìn)行偏微分的極值化處理,獲得最優(yōu)空間信息數(shù)據(jù),從而對三維空間環(huán)境的主要信息進(jìn)行簡單明了的表達(dá)。②提高了蟻群在路徑規(guī)劃過程中對于環(huán)境的適應(yīng)能力、尋找最優(yōu)目標(biāo)點的決策能力,并且在整個路徑規(guī)劃中,輸出了更為安全合理并且避障效果更好的路徑。③減少了蟻群算法在路徑規(guī)劃過程中所需要時間資源的消耗。

通過在Matlab環(huán)境下的仿真實驗的結(jié)果和數(shù)據(jù)分析,驗證了在偏微分高程建模環(huán)境下,蟻群在進(jìn)行三維空間的路徑規(guī)劃時,具有更好的環(huán)境適應(yīng)、決策尋優(yōu)的能力,并且需要消耗的時間資源更少。此外蟻群所輸出的路徑更為安全合理,避障效果更好。

在實驗過程中發(fā)現(xiàn),在復(fù)雜的完全未知的環(huán)境進(jìn)行路徑規(guī)劃時,蟻群的可視點的數(shù)目,直接對其能否進(jìn)行路徑規(guī)劃產(chǎn)生決定性的影響,所以下一步工作,將重點對蟻群算法在復(fù)雜的、完全未知的三維空間道路環(huán)境中的可視點數(shù)量與可視區(qū)域進(jìn)行研究，從而完善蟻群算法在更為復(fù)雜的信息完全未知三維空間環(huán)境中進(jìn)行路徑規(guī)劃研究。

參考文獻(xiàn)：

[1] Zhou B, Dai X Z, Han J D. Real-time 3D outdoor environment modeling for mobile robot with a laser scanner[J].Robot, 2012, 34(3):321-328.(周波,戴先中,韓建達(dá).基于激光掃描的移動機(jī)器人3D室外環(huán)境實時建模[J].機(jī)器人,2012,34(3):321-328.)

[2] Xu A Q, Chatavut. Optimal complete terrain coverage using an unmanned aerial vehicle[C]∥Proc.oftheIEEEInternationalConferenceonRoboticsandAutomation,2011:2513-2519.

[3]Nationalresearchcouncilofthenationalacademies.Technologydevelopmentforarmyunmannedgroundvehicle[M]. Fu M Y, Wang M L, trans.Beijing: National Defense Industry Press,2008.(軍用無人地面車輛技術(shù)的發(fā)展[M].付夢印,王美玲,譯.北京:國防工業(yè)出版社,2008.)

[4] Lartigue C, Quinsat Y, Mehdi-Souzani C.Voxel-based path planning for 3D scanning of mechanical parts[J].Computer-AidedDesignandApplications,2014,11(2):220-227.

[5] Olivieri P, Birglen L, Maldague X, et al. Coverage path planning for eddy current inspection on complex aeronautical parts[J].RoboticsandComputer-IntegratedManufacturing,2014,30(3):305-314.

[6] Ye C.Borenstein J.A novel filter for terrain mapping with laser rangefinders[J].IEEETrans.onRobtics,2004,20(5):913-921.

[7] Plagemann C,Mischke S,Prentice S,et al. A Bayesian regression approach to terrain mapping and an application to legged robot locomotion[J].JournalofFieldRobotics,2009,26(10):789-811.

[8] Olson C F. Probabilistic self-localization for mobile robots[J].IEEETrans.onRoboticsandAutomation, 2000,16(1):55-66.

[9] Oniga F, Nedevschi S. Processing dense stereo data using elevation maps: road surface, trafficisle and obstacle detection[J].IEEETrans.onVehicularTechnology,2010,59(3):1172-1182.

[10] Olson C F. Probabilistic self-localization for mobile robots[J].IEEETrans.onRoboticsandAutomation,2000,16(1):55-66.

[11] Oniga F, Nedevschi S. Processing dense stereo data using elevation maps: road surface, traffic isle and obstacle detection[J].IEEETrans.onVehicularTechnology,2010,59(3):1172-1182.

[12] Yan F, Zhuang Y, Bai M, et al. 3D outdoor environment modeling and path planning based on topology-elevation model[J].ActaAutomaticaSinica,2010,36 (11):1493-1501.(閆飛,莊嚴(yán),白明,等.基于拓?fù)涓叱棠Ｐ偷氖彝馊S環(huán)境建模與路徑規(guī)劃[J].自動化學(xué)報，2010,36(11):1493-1501.)

[13] Dorigo M, Maniezzo V, Colorni A. The ant system: optimization by a colony of cooperating agents[J].IEEETrans.onSystems,ManandCybernetics,PartB:Cybernetics,1996,26(1):29-41.

[14] Shi F, Wang H, Yu L, et al. 30samplesofMATLABintelligentalgorithm[M]. Beijing：Beihang University Press,2011:229-236.(史峰,王輝,郁磊,等.MATLAB 智能算法30個案例分析[M].北京:北京航空航天大學(xué)出版社,2011:229-236.)

肖秦琨(1974-),男,教授,博士,主要研究方向為動態(tài)貝葉斯網(wǎng)絡(luò)及多媒體信息檢索。

E-mail:xiaoqinkun10000@163.com

E-mail:wangyi860205@126.com

羅藝闖(1987-),男,碩士,主要研究方向為模式識別。

E-mail:luoyichuang@163.com

網(wǎng)絡(luò)優(yōu)先出版地址：http://www.cnki.net/kcms/detail/11.2422.TN.20141209.0119.005.html

3D path planning of ant colony algorithm using partial

differential elevation modeling

XIAO Qin-kun, Wang Yi, LUO Yi-chuang

(DepartmentofElectronicsandInformationEngineering,Xi’anTechnologicalUniversity,Xi’an710021,China)

Abstract:A novel three-dimensional (3D) path planning method of the ant colony algorithm under the partial differential elevation modeling is proposed to tackle the problem of scene modeling and obstacle avoidance. Firstly, the 3D abstract scene and elevation scene are built by their modeling respectively, and then the optimal data is extracted from the elevation scene to construct partial differential scene by using the partial differential mathematical method. Furthermore, the best fitness value of the ant colony firstly treated as objective function is employed to display the decision-making capacity of the ant colony in the 3D path planning. Finally, the ant colony algorithm is combined with abstract scene, elevation scene or the partial differential elevation scene, and the best path planning is shown out in 3D scene. Experimental results and statistics analysis show the effectiveness and validity of the proposed algorithm.

Keywords:partial differential elevation modeling; ant colony algorithm; abstract modeling; three-dimensional (3D) path planning ; modeling and obstacle avoidance

通訊作者王弋(1986-),,男,碩士研究生,主要研究方向為無人戰(zhàn)車野外路徑規(guī)劃。

作者簡介：

中圖分類號：V 279

文獻(xiàn)標(biāo)志碼：A

DOI:10.3969/j.issn.1001-506X.2015.07.14

基金項目：國家自然科學(xué)基金(61271362)；陜西省自然科學(xué)基金(2012JM8028)；陜西省教育廳專項科研基金(12JK0510，12JK0727)；中省共建-跨平臺研究項目(ZXXM01)資助課題

收稿日期：2014-04-17；修回日期：2014-10-16；網(wǎng)絡(luò)優(yōu)先出版日期：2014-12-09。