基于三維地形的路徑規劃算法研究

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

1(上海應用技術大學計算機科學與信息工程學院 上海 201418)2(上海市計算技術研究所 上海 200040)

0 引 言

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

1 環境建模

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

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

2 改進的蟻群算法

2.1 信息素

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

(1)

2.2 路徑選擇規則的改進

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

(2)

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

(3)

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

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

(4)

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

(5)

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

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

(6)

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

因此文中的設計的啟發函數為：

F=η1×η2×η3

(7)

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

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

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

(8)

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

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

(9)

(10)

(11)

(12)

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

2.4 本文的算法流程設計

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

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

4) 本輪循環后，求取此次循環的M條螞蟻路徑的平均值，并以此平均值為標準對較優路徑和較差路徑進行區分。

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

2.5 仿真實驗

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

圖1 改進的蟻群算法路徑圖

圖2 基本蟻群算法路徑圖

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

表1 兩種算法路徑長度結果比較 km

表2 兩種算法對應時間的比較 s

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

表3 兩種算法性能比較

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

3 結 語

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

模也是路徑規劃中的重中之重，因此如何構建復雜不穩定的三維環境下的路徑規劃有待進一步的深入研究。