一種基于改進蟻群算法的山地三維路徑規劃算法

黃勁潮

(龍巖學院繼續教育學院，福建龍巖 364012)

0 引言

當前社會，出現了很多自助游愛好者，他們需要在復雜的山地地形，尋找一條沒有前人走過的路徑來到達目的地。如何快速、準確的規劃山地三維路徑，成為一個值得研究的新課題。所謂三維路徑規劃，是在三維地圖中規劃出一條避開了無法通過的障礙，同時滿足某些指標最優的三維路徑。目前常用的路徑規劃算法，大多數只能規劃二維平面路徑;而一般的三維規劃算法，大多運算算法復雜、需要很大的存儲空間，同時無法在宏觀全局角度來進行路徑規劃。目前常用的三維規劃算法有粒子群算法、遺傳算法、A*算法等，但粒子群算法與遺傳算法只是準三維算法，而A*算法當維數增加時計算量會急劇增加［1－3］。本文在已有三維山地地圖的基礎上，采用一種改進的蟻群算法來解決上述問題。

1 改進的蟻群算法

Dorigo M等人在90年代初提出了蟻群算法，它是基于仿生螞蟻搜索行為的一種進化算法。觀察者發現，螞蟻在搜索找尋食物時，會在爬過的路上留下分泌物，這種分泌物包含了螞蟻的信息素。這種信息素會慢慢揮發，但是后續的螞蟻能夠檢測到這種信息素的存在;并且后續螞蟻會優先選擇信息素濃度較高的路徑點，同時它們在進過的時候還會再次留下信息素。這樣該路徑點的信息素濃度會不斷增大，同時也會更加吸引后續的螞蟻［4－5］。蟻群算法根據螞蟻的覓食行為設計，它具有群體智能并有分布式計算的優點，因此它在路徑選擇上具有很大的潛力。

1.1 三維空間抽象建模

三維路徑規劃算法首先需要從三維地圖中抽象出三維空間模型，模型抽象方法如下:首先三維地圖左下角的頂點作為三維空間的坐標原點A，在點A中建立三維坐標系，其中，x軸為沿經度增加的方向，y軸為沿緯度增加的方向，z軸為垂直于海平面方向。在該坐標系中以點A為頂點，沿x軸方向取三維地圖的最大長度AB，沿y軸方向取三維地圖的最大長度AA’，沿z軸方向取三維地圖的最大長度AB，這樣就構造了包含三維地圖的立方體區域ABCD–A’B’C’D’，該區域即為三維路徑的規劃空間。三維路徑規劃空間如圖1所示。

三維路徑空間建立起來之后，采用等分空間的方法從三維空間中抽取出三維路徑規劃所的網格點。首先沿邊AB把規劃空間ABCD–A’B’C’D’進行等分，得到n+l個平面∏i(i=1，2，…，n)，然后對這n+l個平面沿邊AD進行m等分，沿邊AA’進行l等分，并且并且求解出里面的交點。

通過以上步驟，整個規劃空間ABCD–A’B’C’D’就離散化為一個三維點集合，集合中的任意一點對應著兩個坐標，即序號坐標a1(i，j，k)(i=0，1，2，…，n，j=0，l，2，…，m，k=0，1，2，…，l)和位置坐標a2(xi，yi，zi)，其中，i，j，k分別為當前點a沿邊AA、邊AD、邊AA’的劃分序號。蟻群算法即在這些三維路徑點上進行規劃，最終得到連接出發點和目標點滿足某項指標最優的三維路徑。

圖1 三維路徑規劃空間

1.2 信息素更新

蟻群算法使用信息素吸引螞蟻搜索，信息素位置設定及更新方法對于蟻群算法的成功搜具有非常重要的意義。在1.1節中已經把整個搜索空間離散為一系列的三維離散點，這離散點為蟻群算法需要搜索的節點。因此，把信息素存儲在模型的離散點中，每個離散點都有一個信息素的濃度值，該濃度值表征了對后續螞蟻的吸引力，值越大，吸引力也越大，該值在螞蟻經過改點后更新。

信息素在更新時可以采用全局更新或者局部更新兩種方式。螞蟻經過一個路徑點時，信息素濃度降低，這就是局部更新。信息素濃度的降低是為了讓螞蟻們可以去探索未經探索過得路徑點，在宏觀全局角度來更好地規劃線路。局部信息素更新隨著螞蟻的搜索進行，信息素更新公式為

其中，τijk是點(i，j，k)上所帶的信息素濃度值;ζ是衰減系數。

螞蟻搜索完一條完整的路徑，以該路徑的長度作為評價值，從路徑集合中選擇出最短路徑，增加最短路徑各節點的信息素值，這就叫全局更新。信息素更新公式如下:

其中，length(m)為第m只螞蟻經過的路徑長度;ρ為信息素更新系數;K是系數。

1.3 可視搜索空間

取z軸方向作為三維路徑規劃的主方向，探險者沿x軸方向前進，為了降低規劃復雜程度，將探險者的運動簡化為前向運動、橫向運動和縱向運動三種運動方式。在前向運動一定單位長度距離Lx，max情況下，設定機器人最大橫向移動允許距離為Ly，max，最大縱向移動距離為Lz，max。這樣，當螞蟻沿著x軸方向前進時，當位于點H(i，j，k)時，對下一個點的搜索就存在一個可視區域，可視區域如圖2所示。

這樣，當螞蟻由當前點向下一個點移動時，可搜索的區域限制在螞蟻搜索可視區域之內，簡化了搜索空間，提了蟻群算法的搜索效率。

1.4 蟻群搜索策略

螞蟻從當前點移動到下一個點時，根據啟發函數來計算可視區域內各點的選擇概率，啟發數為

圖2 螞蟻搜索可視區域

其中，D(i，j，k)為兩點間路徑長度，促使螞蟻選擇距離較近的點;S(i，j，k)為安全性因素，選擇點不可達到時，該值為0，促使螞蟻選擇安全點;Q(i，j，k)為下一點到目標點的路徑長度，促使螞蟻選擇距離目標更近的點;wl，w2，w3為系數，代表上述各因素的重要程度。

D(i，j，k)的計算公式如下:

其中，a為當前點;b為下一個點。

S(i，j，k)的計算公式如下:

其中，Num表示在點(i，j，k)中可視點的數量;UNum表示可視點中不可達區域的點的數量。

Q(i，j，k)的計算公式如下:

其中，b表示下一點;d表示目標點。

螞蟻在平面∏i上的當前點pi選擇平面∏i+1上下一個點pi+1的步驟如下:

1)根據抽象環境確定平面∏i+1內的可行點集合;

2)根據啟發函數公式(4)依次計算點pi到平面∏i+1內的可行點集合的啟發信息值Ha+1，u，v;

3)計算在平面∏i+1內任一點(i+1，u，v)的選擇概率p(i+1，u，v):

其中τa+1，u，v為平面∏i+1點P(a+1，u，v)的信息素值。

4)根據各點的選擇概率采用輪盤賭法選擇平面∏i+1內的點。

1.5 算法流程

基于蟻群算法的三維路徑搜索算法的算法流程如圖3所示。

圖3 三維路徑規劃算法

其中，三維環境建模模塊根據1.1節抽取出三維環境數學模型;搜索節點模塊根據啟發函數搜索下個節點;信息素更新模塊更新環境中節點的信息素值。

1.6 本設計對基本蟻群算法的改進

采用局部信息素與全局信息素相結合的更新策略，縮短了基本蟻群算法的計算時間，也避免了易陷于停滯的缺陷;基本蟻群算法信息素釋放在節點邊上，本設計把信息素釋放在節點上，大大降低了運算量的同時也節約了存儲空間。

2 山地三維路徑規劃設計

2.1 問題描述

采用蟻群算法在跨度為24 km×24 km的一片山地中搜索從起點到終點，并且避開所有障礙物的路徑，為了方便問題的求解，取該區域內最低點的高度為0，其他點高度根據和最低點高度差依次取得。路徑規劃起點坐標為(1，10，800)，終點坐標為(21，4，1 000)，規劃環境和起點、終點如圖4所示。整個搜索空間為24 km×24 km的山地，其中，起點坐標為(1，10，800)，終點坐標為(21，4，1 000)。

圖4 規劃環境、起點、終點圖

2.2 主要函數MATLAB編程實現

1)啟發值計算函數

2)適應度計算函數

2.3 仿真結果

蟻群算法進行三維路徑規劃，規劃空間范圍為20 km×20 km的山地，把規劃空間抽象為24 km× 24 km×2 km的規劃空間，其中，x軸、y軸方向每個節點的間距為1 km，z軸方向每個節點間距為200 m。路徑起點在規劃空間的序號為［1 10 4］，終點在規劃空間的序號為［21 4 5］。算法的基本設置為種群規模為20，算法迭代為400次，路徑規劃結果如圖5所示。

圖5 規劃結果

對比圖4和圖5，我們可以看出，本算法從出發點到目標點規劃出了一條能夠避開難以攀爬和翻越的障礙、同時長度較短的三維路徑。仿真結果證明了該算法是有效可行的。

3 結論

通過對山地空間的三維空間抽象建模，本設計得到了一個給定山地的三維空間模型。并基于改進的蟻群算法，在三維空間模型中規劃了一條三維最優路徑。使用MATLAB軟件進行仿真，結果顯示基于改進蟻群算法的山地三維路徑規劃算法在路徑最優值計算和規劃時間上都能夠較好的滿足需求。

［1］Emilio Frazzoli.Real－time motion planning for agile autonomous vehicles［J］.Journal of Guidance，Control and Dynamics，2002，21(1):25.

［2］史峰，王輝，胡斐，等.MATLAB智能算法30個案例分析［M］.北京:北京航空航天大學出版社，2011.

［3］李愛萍，李元宗.移動機器人路徑規劃方法的研究［J］.機械工程與自動化，2009(5):194－196.

［4］朱慶保.動態復雜環境下的機器人路徑規劃螞蟻預測算法［J］.計算機學報，2005，28(11):1 898－1 906.

［5］郭必祥.基于蟻群算法的智能機器人全局路徑規劃方法研究［D］.哈爾濱:哈爾濱工程大學，2005.