基于三維地形的路徑規(guī)劃算法研究

周蘭鳳 錢偉杰 曹國剛* 章民融

1(上海應(yīng)用技術(shù)大學(xué)計算機(jī)科學(xué)與信息工程學(xué)院 上海 201418)2(上海市計算技術(shù)研究所 上海 200040)

0 引 言

路徑規(guī)劃技術(shù)是移動機(jī)器人的關(guān)鍵技術(shù)和研究的重要領(lǐng)域之一，移動機(jī)器人的路徑規(guī)劃是指在有障礙物的工作環(huán)境中，為了給機(jī)器人規(guī)劃一條從給定起始點到目標(biāo)終點的最短或者最優(yōu)的行動路徑，且使得機(jī)器人在運動的過程中能夠安全無碰撞地繞過障礙物。目前國內(nèi)外的研究用于移動機(jī)器人的路徑規(guī)劃的算法主要有：A*算法[1]、遺傳算法[2]、人工勢場法[3]、神經(jīng)網(wǎng)絡(luò)法[4]等，這些路徑規(guī)劃的方法或多或少存在一些不足之處，使得規(guī)劃的效果不盡人意。自蟻群算法提出后，路徑規(guī)劃與蟻群算法相結(jié)合，有效地提高了路徑規(guī)劃的效率。然而傳統(tǒng)蟻群算法在解決路徑規(guī)劃上存在收斂速度慢，易陷入局部最優(yōu)，導(dǎo)致所求的路徑并非最好。對原有的算法進(jìn)行優(yōu)化處理一直是目前學(xué)者們所關(guān)心的問題。文獻(xiàn)[5]為了解決三維路徑規(guī)劃問題中耗時長，過早失去解的多樣性的問題，引入了逆轉(zhuǎn)變異算子和插入變異算子來對蟻群算法進(jìn)行改進(jìn)，文獻(xiàn)[6]改進(jìn)了蟻群算法全局信息素更新策略和信息素增量的計算方法，且在啟發(fā)式函數(shù)引入了安全性因素，實現(xiàn)了機(jī)器人的高效避障。文獻(xiàn)[7]考慮了啟發(fā)函數(shù)中可行節(jié)點到目標(biāo)點的距離因素，提高了搜索方向性和算法搜索的速度。文獻(xiàn)[8]將環(huán)境中的局部的路徑信息加入到信息素的初始化和路徑選擇概率中，提高了算法收斂速度，同時引入交叉操作來改進(jìn)蟻群算法。本文基于以上研究基礎(chǔ)，對蟻群算法中的啟發(fā)式進(jìn)行了設(shè)計，同時考慮到信息素的更新策略，全局信息更新上綜合考慮了螞蟻迭代次數(shù)與最優(yōu)路徑間的關(guān)系進(jìn)行了改進(jìn)。并利用MATLAB軟件進(jìn)行仿真實驗，通過分析實驗結(jié)果來驗證算法改進(jìn)后的可行性。

1 環(huán)境建模

本文采用空間等分網(wǎng)格法進(jìn)行空間抽象建模。首先構(gòu)造一個立方體區(qū)域的規(guī)劃空間ABCD-A′B′C′D′，將三維地圖包含住。將立方體左下角的頂點A作為三維空間的原點，以此建立一個三維坐標(biāo)系，其中x軸定義為沿精度的增加的方向，y軸定義為沿緯度增加的方向，z軸定義為垂直xoy平面的方向，這樣就構(gòu)成了一個三維路徑空間，接下來采用等分空間的方法從這個三維空間中抽取出三維路徑規(guī)劃中需要的網(wǎng)格點。先沿著邊AB把這個規(guī)劃空間進(jìn)行n等分，就得到了n+1個平面∏i(i=0,1,2,…，n)，然后對這n+1個平面沿著AD邊進(jìn)行m等分，再沿邊AA′進(jìn)行m等分，且求出里面的相關(guān)交點。

這樣就將整個規(guī)劃空間離散化成了一個三維點的集合，設(shè)為T*，集合空間中任意一點與兩坐標(biāo)對應(yīng)，即T(i,j,k)(i=0,1,2，…,n;j=0,1,2,…,m,k=0,1,2，…,m)為序號坐標(biāo)，其對應(yīng)的位置坐標(biāo)為T(xi,yi,zi)，其中i,j,k分別為其對應(yīng)的劃分序號。本文定義任意兩點間qi,,qi+1的歐式距離為路徑最短距離。

2 改進(jìn)的蟻群算法

2.1 信息素

(1) 信息素表示 通常在路徑規(guī)劃的過程中，會選擇把任意兩相鄰的節(jié)點之間的路徑存儲信息素，使其作為載體。本文是在三維空間中進(jìn)行路徑規(guī)劃， 模型中的節(jié)點比較多，如果將它們各節(jié)點之間的路徑作為載體的話, 對于前面的網(wǎng)格劃分的平面，每一個平面具有m2個節(jié)點，相鄰的兩個平面節(jié)點連線就會有m4種情況，平面劃分的間隔越小，導(dǎo)致空間的復(fù)雜度就越大。因此，本文選擇節(jié)點表示法，將信息素存在離散點上，即每個點含有一個信息素值，信息素值大小與對螞蟻吸引的程度成正比，因此相鄰的平面間只會有2 m2種連接的情況, 從而降低了信息存儲的空間需求，并降低了信息存儲的空間需求。

(1)

2.2 路徑選擇規(guī)則的改進(jìn)

螞蟻由當(dāng)前節(jié)點移動到下一個節(jié)點的概率與啟發(fā)式函數(shù)相關(guān)聯(lián)，設(shè)有M只螞蟻，而且將它們統(tǒng)一放置在起始點，在路徑的選擇過程中，螞蟻k按照式(2)決定接下來的移向點：

(2)

式中：q為[0,1]區(qū)間的隨機(jī)數(shù) ,q0為[0,1]區(qū)間均勻分布的隨即數(shù)，ηa,a+1為兩相鄰平面之間節(jié)點距離，J為根據(jù)式(3)給出的概率分布產(chǎn)生的一個隨即變量。對M只螞蟻進(jìn)行初始化后，所有螞蟻都位于初始起點的位置。接下來，對位于平面∏a上的任意位置點qa(ia,ja,ka)的螞蟻k如何選擇下一個相鄰平面的qa+1(ia+1,ja+1,ka+1)，根據(jù)節(jié)點的信息素值和啟發(fā)值來進(jìn)行一定概率的選擇，選擇規(guī)則如下：

(3)

式中F為啟發(fā)式值(由式(7)決定)，τa+1表示某個平面節(jié)點a+1上的信息素值，它在某種程度上影響著螞蟻算法在合適的時間找到全局最優(yōu)解的效率。

較好的啟發(fā)式函數(shù)[9]的設(shè)計，在三維路徑規(guī)劃中起著一定的重要性，蟻群算法的好壞收斂性和其穩(wěn)定程度都與之相關(guān)聯(lián)。要想規(guī)劃出一條較優(yōu)的三維路徑， 須構(gòu)造一個合適的啟發(fā)函數(shù)。 而且，在三維路徑規(guī)劃中要綜合考慮各種相關(guān)因素對路徑規(guī)劃的影響，把路徑最短距離和避障作為規(guī)劃中評價函數(shù),障礙物的約束函數(shù)如下：

(4)

螞蟻在尋路的過程中，考慮到最短路徑原則,即將此刻所在平面的節(jié)點和其任意相鄰平面的節(jié)點間的歐式距離作為兩個節(jié)點的路徑最短距離d，相鄰兩點路徑的啟發(fā)函數(shù)為η2：

(5)

盡管螞蟻在相鄰的節(jié)點傾向于與它距離最近的點，但是這會導(dǎo)致選擇的下一個節(jié)點未必與目標(biāo)點相近。因此為了讓算法在搜索上具有一定的方向性，綜合考慮當(dāng)前節(jié)點與相鄰點以及目標(biāo)點的關(guān)系，定義兩個影響因子r1、r2，用它們來衡量qi、qi+1與終點qn之間的分配：

本文所用數(shù)據(jù)均來源于《國家統(tǒng)計年鑒》(2016)和《河北統(tǒng)計年鑒》(2016)，并經(jīng)過計算整理所得。選擇2016年河北省各消費項目人均消費支出與河北省各產(chǎn)業(yè)人均GDP之比作為實際指標(biāo)體系，2016年我國各消費項目人均消費支出與我國各產(chǎn)業(yè)人均GDP之比作為標(biāo)準(zhǔn)指標(biāo)體系。根據(jù)標(biāo)準(zhǔn)指標(biāo)體系，對實際指標(biāo)體系進(jìn)行量化處理，得到河北省2016年消費結(jié)構(gòu)與產(chǎn)業(yè)結(jié)構(gòu)的和諧矩陣，見表1。在計算各項消費支出與產(chǎn)業(yè)結(jié)構(gòu)之間和諧度時，使用的權(quán)重采用德爾菲法確定，具體權(quán)重見表2。據(jù)此可計算各項消費支出與產(chǎn)業(yè)結(jié)構(gòu)之間的和諧度hj(j=1,2,3,…8)。如食品消費支出與產(chǎn)業(yè)結(jié)構(gòu)的和諧度為：

(6)

經(jīng)過多次實驗發(fā)現(xiàn)r1、r2在算法搜索的不同時段影響程度不一樣。初始階段螞蟻選擇的下一節(jié)點與目標(biāo)點的距離對整個算法的好壞起到很大作用，算法前期的r2值越大，傾向于最優(yōu)方向的路徑就越多，算法后期r1越大，搜索到的相鄰點路徑間距越小且靠近目標(biāo)點。將r1取為dqi+1qn與dqsqn的比值，r2=1-r1，這樣隨著后面的待選節(jié)點越來越靠近終點，路徑搜索在目標(biāo)點最優(yōu)與相鄰兩點最短自適應(yīng)的改變，使得搜索向著有利方向前進(jìn)。

因此文中的設(shè)計的啟發(fā)函數(shù)為：

F=η1×η2×η3

(7)

2.3 三維路徑的信息素更新策略

(1) 局部信息素更新的設(shè)計 本文利用局部信息素更新和全局信息素更新相結(jié)合方式對此進(jìn)行改進(jìn)。局部信息素更新在路徑搜索過程中進(jìn)行:

τijk=(1-u)τijk+uτ0

(8)

式中：衰減系數(shù)u是一個介于(0.1)的參數(shù)值，τ0是節(jié)點的初始信息素值。通過減少經(jīng)過點的信息素濃度，提高螞蟻搜索未知點的概率。

(2) 全局信息素更新 為了提高螞蟻的全局搜索能力，本文在這里利用一種正反饋信息素增量進(jìn)行改進(jìn)。每輪結(jié)束后統(tǒng)計所有路徑的平均值，當(dāng)下的螞蟻搜索到的路徑長度值如小于之前所有螞蟻搜索路徑的長度的綜合最優(yōu)值，那么就增強這條路徑上的信息素分布, 從而使得接下來的螞蟻繼續(xù)搜索時能在這個基礎(chǔ)標(biāo)準(zhǔn)上找到更好的路徑。如果當(dāng)前的螞蟻搜索路徑長度大于之前所有的螞蟻搜索路徑的平均路徑值的話， 則不保持信息素的增加，同時這里還引入一種懲罰機(jī)制，對這條路徑的信息素進(jìn)行有條件的減少， 從而使得接下來進(jìn)行的搜索避免了這些較差的路徑。所有螞蟻每輪搜索全圖完成一次迭代后，都會產(chǎn)生一個最優(yōu)的解Lbest和一個最差的解Lwrost，可以利用這兩個解尋找靠近最優(yōu)解的螞蟻來對全局搜索過程的信息素濃度公式進(jìn)行更新：

(9)

(10)

(11)

(12)

式中：ρ為信息素?fù)]發(fā)系數(shù)；Q為一個恒定信息素濃度值；La為第a只螞蟻找到的路徑長度；Ld為當(dāng)前循環(huán)的最佳路徑長度值；Lave為最優(yōu)解和最差解的平均值。這里用來衡量新產(chǎn)生的路徑的信息素濃度增減，以往的基本蟻群算法中的揮發(fā)系數(shù)ρ都是固定不變的一個值，這會導(dǎo)致算法的尋優(yōu)能力不足，容易出現(xiàn)局部的最優(yōu)情況。因此，本文根據(jù)搜索次數(shù)以及每次搜索的最優(yōu)路徑值、最差路徑值，對揮發(fā)系數(shù)ρ進(jìn)行相對應(yīng)的改變[11]，如式(11)引入一個參數(shù)k,令k為每次路徑的最優(yōu)路徑值與最差路徑值的比值，加入到信息素更新公式。前期ρ較小，能夠很好保留路徑上信息素，可以確定最優(yōu)解的大致方向，使得后續(xù)螞蟻沿著這些方向繼續(xù)尋優(yōu)，從而縮小了最優(yōu)路徑與最差路徑間的信息素濃度差距。中后期當(dāng)最優(yōu)路徑與最差路徑相差不大時，說明搜索的解越來越集中在最優(yōu)解的周圍，此時為了防止算法過早進(jìn)入收斂狀態(tài)，ρ的值會相應(yīng)提高，使得算法后期搜索能力增強，從而依靠最優(yōu)解與最差解的關(guān)系自適應(yīng)地更新全局信息素值。這能有效地提高全局搜索的能力，避免了局部收斂和早熟的出現(xiàn)。通過這些信息素的優(yōu)化更新，提高了對路徑搜索的多樣性，同時也能提高算法的收斂速度，增進(jìn)了對最優(yōu)路徑的尋找。

2.4 本文的算法流程設(shè)計

1) 建立抽象的環(huán)境模型，設(shè)置在該模型中的起始點位置、目標(biāo)點位置，確定螞蟻的搜索方向，將所有螞蟻置于起始點。初始化螞蟻蟻群算法的迭代次數(shù)NC_max,螞蟻的個數(shù)M，以及按照式(10)設(shè)置ρ的值。

3) 重復(fù)步驟2，直至本輪所有螞蟻都完成路徑的搜索。

4) 本輪循環(huán)后，求取此次循環(huán)的M條螞蟻路徑的平均值，并以此平均值為標(biāo)準(zhǔn)對較優(yōu)路徑和較差路徑進(jìn)行區(qū)分。

5) 螞蟻按式(9)、式(11)、式(12)進(jìn)行全局的信息素更新,判斷算法的迭代次數(shù)是否達(dá)到NC_max，若滿足條件，則輸出最優(yōu)路徑的解，結(jié)束算法。若無，返回步驟2，繼續(xù)執(zhí)行算法，直至滿足最后迭代次數(shù)。

2.5 仿真實驗

本文采用一臺PC機(jī)(操作系統(tǒng):Win7,2 GB內(nèi)存)，基于MATLAB2013實驗平臺，進(jìn)行仿真，隨機(jī)生成一個三維地形圖。規(guī)劃空間抽象為21×21×21的柵格，設(shè)置尋找路徑的起點和終點以及高度值，種群個數(shù)為21，最大迭代次數(shù)為300，用上述的改進(jìn)蟻群算法進(jìn)行尋路，由圖1、圖2路徑曲線圖看，本文改進(jìn)的算法路徑規(guī)劃效果優(yōu)于基本蟻群算法的路徑規(guī)劃。

圖1 改進(jìn)的蟻群算法路徑圖

圖2 基本蟻群算法路徑圖

本文算法最大迭代值設(shè)為300，分別進(jìn)行多次實驗，統(tǒng)計兩種算法的迭代次數(shù)，并進(jìn)行比較。隨機(jī)選取了兩組不同算法下的路徑長度值與時間作對比，實驗結(jié)果見表1，改進(jìn)的蟻群算法在路徑規(guī)劃所得長度上比基本蟻群算法要短，說明改進(jìn)的算法中的啟發(fā)式函數(shù)發(fā)揮了很大作用，一定程度上降低了螞蟻不合理地移動到下一相鄰節(jié)點可能性的選擇，圖1中的路線上的每一個點相比于圖2，離終點的距離都相對較近。在時間效率上(見表2)，本文的改進(jìn)算法也得到了一些優(yōu)化，由于初始信息素的優(yōu)化分布，以及自適應(yīng)揮發(fā)因子的改變和信息素的懲罰機(jī)制，在一定程度上都對螞蟻搜索的效率進(jìn)行了提高，使得螞蟻搜索的更有合理性。

表1 兩種算法路徑長度結(jié)果比較 km

表2 兩種算法對應(yīng)時間的比較 s

比較兩種算法尋得最優(yōu)路徑的迭代次數(shù)，由表3可知，改進(jìn)算法在迭代速度明顯優(yōu)于基本算法,由于信息素更新規(guī)則的改進(jìn)，使得改進(jìn)算法在路徑搜索的效率得到了極大的提升，不再是對路徑信息素盲目地簡單改變，而是有條件地對路徑上的信息素進(jìn)行提升或降低。

表3 兩種算法性能比較

由圖1中路徑曲線來看，相比于圖2的路徑曲線的跌宕，本文搜索的路徑方向大致是一條偏向于終點的且局部路徑較平穩(wěn)的曲線。

3 結(jié) 語

本文對三維環(huán)境路徑規(guī)劃問題進(jìn)行了探討，運用蟻群算法進(jìn)行路徑規(guī)劃，對算法中的啟發(fā)式函數(shù)進(jìn)行改進(jìn)，考慮當(dāng)前節(jié)點到下一節(jié)點和目標(biāo)點之間的關(guān)系，引入節(jié)點影響因子。在信息素更新策略方向上，利用當(dāng)前循環(huán)的最優(yōu)路徑以及最差路徑信息素，引入了信息素增量的懲罰機(jī)制，結(jié)合信息素?fù)]發(fā)因子的自適應(yīng)取值方式，以提高算法的收斂速度和尋優(yōu)能力。通過在三維模擬環(huán)境中進(jìn)行實驗仿真，改進(jìn)的算法在搜索得到的路徑、時間效率相比基本蟻群算法均得到了改善，表明了本文改進(jìn)的算法在一定的條件下能達(dá)到良好的路徑規(guī)劃效果。隨著科技的進(jìn)步與發(fā)展，路徑規(guī)劃所面臨的環(huán)境充滿復(fù)雜與不確定性，單靠一種算法的路徑規(guī)劃可能難以取得理想的效果，良好的環(huán)境建

模也是路徑規(guī)劃中的重中之重，因此如何構(gòu)建復(fù)雜不穩(wěn)定的三維環(huán)境下的路徑規(guī)劃有待進(jìn)一步的深入研究。