改進蟻群算法的移動機器人三維路徑規劃

李志錕

(1.廣東科技學院 機電工程學院，廣東 東莞 523083；2.安徽工程大學 高端裝備先進感知與智能控制教育部重點實驗室，安徽 蕪湖 241005)

0 引言

科學技術的高速發展帶來了移動機器人性能的不斷提升，作為集成了動態決策與路徑規劃[1-5]、環境感知、可編程及模塊可拓展等特點的移動機器人，其應用領域不斷拓寬。比如農業、醫療服務、科學實驗和空間探測等，這些領域的應用場景不局限于二維環境，而且大量應用于三維環境。移動機器人的種種應用也基本上都基于三維環境展開，因此，從未來的發展前景以及日常實用性角度出發，研究三維環境下的移動機器人路徑規劃具有十分重要的意義。

目前，由于在三維空間中，三維地圖環境較為復雜，移動機器人可移動方向大幅增加，加上目前有關移動機器人路徑規劃的研究成果較少，因此，移動機器人在三維環境下的路徑規劃難度高于二維環境下的路徑規劃。據此，本文將研究移動機器人應用改進蟻群算法[6-13]的問題以及在三維環境下的路徑規劃問題。

移動機器人三維路徑規劃是指移動機器人在三維地圖環境中尋找出一條從起始點到終點的最優路徑[14-16]，所規劃出的最優路徑必須滿足與所有障礙物安全無碰撞。目前，路徑規劃算法主要是基于二維地圖環境運行，由于應用在三維地圖環境下的路徑規劃算法信息量存儲較大，同時要考慮三個維度導致計算復雜。因此，已有的三維路徑規劃算法較少，主要有：遺傳算法、A*算法、蟻群算法等。蟻群算法具有分布計算、收斂速度相對較快的優勢，非常適合移動機器人路徑規劃，通過對蟻群算法進行改進，不僅適用于移動機器人二維路徑規劃，而且適用于移動機器人三維路徑規劃。

1 三維環境的抽象建模

對移動機器人進行三維路徑規劃前，需要通過對三維地圖構造出三維空間模型。模型構造方法：在三維地圖中挑選合適的頂點作為坐標原點，對該坐標原點建立三維直角坐標系A-XYZ，A點為坐標原點，確定柵格地圖的最大長度AB，最大寬度AD，最大高度AE，構造出了容納三維地圖的立方體ABCD-EFGH，如圖1所示，將直角坐標系上的三維地圖劃分為獨立的立方體，再對立方體柵格化為體積相等的小柵格。然后將三維地圖空間沿著X軸方向進行等分，得到(n+1)個長方體，接著對(n+1)個長方體沿著Y軸方向進行m等分，得到了(n+1)×(m+1)個長方體；后沿著Z軸方向對三維地圖空間進行l等分，得到了(n+1)×(m+1)×(l+1)個正方體，這些正方體就是組成三維地圖的獨立柵格。

圖1 三維環境模型

利用以上三維地圖的構建方法，三維地圖的立方體區域ABCD-EFGH被切割成三維點集合，集合中的每一個點a都將擁有兩個坐標,分別為序號坐標a(1)(i,j,k)(i=0,1,…，n;j=0,1,…,m;k=0,1,…,l)與位置坐標a(2)(xi,yi,zi)，其中：i是當前位置點a沿著AB方向的劃分序號，j是當前位置點a沿著AD方向的劃分序號，k是當前位置點a沿著AE方向的劃分序號。令AB=h，則在三維地圖環境下的任意一點p(i,j,k)與三維坐標A-XYZ中的點p(x,y,z)的對應關系如下：

2 三維環境下移動機器人路徑規劃

2.1 信息素更新策略

蟻群算法利用信息素的分布來吸引蟻群進行路徑尋優，因此，信息素的初始化分布以及信息素的更新策略對于蟻群最終搜索到的最優路徑至關重要。本研究已經介紹了如何將三維地圖離散為一系列的三維柵格節點，這些三維柵格節點組成了蟻群算法可以移動的柵格集合。通過信息素的初始化，在蟻群搜索路徑前，在每個三維柵格節點設定初始信息素值，經過一次迭代后，每個三維柵格節點進行信息素更新。

蟻群在路徑尋優時，通過螞蟻信息素的分泌起到正反饋作用，因此，在三維柵格節點合理分布初始信息素對于蟻群后期尋優至關重要。設定螞蟻從起始點到終點移動時的方向所指向的區域為有利通行區域，增加該區域的信息素初始值，利用信息素的正反饋作用激勵蟻群快速到達終點，設定初始信息素值為τ1，初始信息素不均勻分布公式為

(4)

其中：τ0為信息素初始值；C為大于1的常數；R為有利通行區域。根據三維地圖的復雜程度，合理調整C值的大小，吸引蟻群朝向最優路徑靠攏，既保證了蟻群的搜索效率，又兼顧了全局路徑搜索的目的，有利于提高蟻群算法收斂速度。

通過全局信息素更新和局部信息素更新兩種方式，實現改進信息素更新策略，當螞蟻到達某個三維柵格時，通過降低該柵格的信息素值，增加螞蟻搜索其他三維柵格的概率，達到全局路徑搜索的目的。局部信息素隨著螞蟻的移動動態調整，局部信息素更新公式為

τijk=(1-ζ)τijk+τ1,

(5)

其中：τijk為三維柵格(i,j,k)上已有的信息素值；ζ為信息素值的衰減系數。

為了避免信息素值過高或過低，導致蟻群算法過快的收斂于非最優路徑，限制信息素值τijk∈[τmin,τmax]。當螞蟻從起始點到終點完成一次路徑尋優時，篩選出所有最優路徑，增加最優路徑所涉及的三維柵格信息素值，全局信息素更新公式為

τijk=(1-ρ)τijk+ρΔτijk,

(6)

其中：l(m)表示第m只螞蟻完成一次路徑尋優所爬行的路徑長度；ρ為信息素更新系數；K為常數。

2.2 多元化啟發函數設計

蟻群算法利用啟發函數計算可視區域內下一步可到達節點的概率，通過螞蟻當前位置與終點位置的距離信息吸引螞蟻選擇最優路徑。因此，啟發函數的設計對于螞蟻能否找到最優路徑至關重要，設計后的啟發函數為

H(i,j,k)=D(i,j,k)w1×S(i,j,k)w2×Q(i,j,k)w3,

(8)

其中：D(i,j,k)表示當前位置與下一步可到達節點位置之間的路徑長度，其吸引螞蟻選擇可視區域內路徑更短的節點位置；S(i,j,k)表示安全因素；Q(i,j,k)表示下一步到達節點距離終點的路徑長度，其吸引螞蟻向距離終點更近的節點移動；w1,w2,w3均為系數。

其中：a表示當前節點；b表示下一節點；d表示終點；N(i,j,k)代表點(i,j,k)擁有的所有可視節點的個數；UN(i,j,k)代表所有可視節點內不可到達區域的節點的個數。

2.3 蟻群搜索策略

三維空間環境下，螞蟻可以選擇的柵格節點大幅增加，蟻群算法的計算量也變得更復雜，蟻群從起始點到終點的路徑尋優也變得更難，蟻群甚至在路徑尋優中陷入死鎖現象而無法找到最優路徑。因此，對于蟻群在三維空間環境下的路徑搜索，采取柵格平面和分層前行兩種方案互相結合的搜索策略。如圖2所示，Ps為螞蟻出發的起始點，設定螞蟻每次橫向移動的最大距離為xmax，每次縱向移動的最大距離為ymax，則螞蟻下一步可到達的柵格節點為一個可視區域，簡化了蟻群的搜索空間。螞蟻離開起始點ps后，將在第一個可視區域內找到可到達節點p1(x1,y1,z1)，離開節點p1后，將在第二個可視區域內找到可到達節點p2(x2,y2,z2)，螞蟻每次離開當前節點位置后，都將在下一個可視區域內尋找可達到節點位置，直到搜索到終點pg，則蟻群算法的三維路徑規劃結束。

圖2 三維環境搜索模式

螞蟻從平面Pi上的節點pi搜索到下一平面Pi+1上的節點pi+1的步驟如下：首先，利用抽象環境找到平面Pi+1上螞蟻可視區域內的所有節點的集合，其次，利用啟發函數公式算出節點pi到平面Pi+1上螞蟻可視區域內所有節點集合的啟發信息值Ha+1,u,v，同時，計算出平面Pi+1上的任意一點(i+1,u,v)被選擇的概率P(i+1,u,v)，其結果為

其中τ(a+1,u,v)表示平面Pi+1上的點p(a+1,u,v)的信息素值。最后，通過公式(12)計算出各點被選擇的概率來確定下一個到達的節點。

2.4 算法流程

改進后的蟻群算法運行流程如圖3所示。

圖3 三維環境下蟻群算法流程圖

三維路徑尋優步驟如下：

步驟1：對蟻群所在的三維環境抽象建模，初始化信息素，信息素按照節點位置的重要程度不均勻分布；

步驟2：蟻群從起始點開始搜索路徑，根據式(12)計算可視區域內到達各點的概率，確定螞蟻下一步要到達的節點位置；

步驟3：螞蟻在搜索路徑時，進行局部信息素更新，當蟻群算法完成一次迭代后，更新全局信息素；

步驟4：蟻群算法達到最大迭代次數時，螞蟻結束路徑尋優，保存最優三維路徑，當蟻群算法沒有達到最大迭代次數，繼續搜索路徑；

步驟5：輸出最優三維路徑，結束蟻群算法。

為解決移動機器人在三維地圖環境中尋找出一條從起始點到終點的最優路徑問題，提出一種改進蟻群算法，將三維地圖離散成一系列的三維柵格節點，這些三維柵格節點組成了蟻群算法可以移動的柵格集合，通過全局信息素更新和局部信息素更新兩種方式，對柵格集合實現改進信息素更新策略，設計多元化啟發函數，吸引蟻群選擇最優路徑，提高算法的收斂速度。

3 實驗與結果

本研究對改進蟻群算法以及傳統蟻群算法分別進行仿真實驗并作對比分析，兩次實驗的三維地圖環境保持一致，起始點坐標均為(1,3,1)，終點坐標均為(21,10,10)，螞蟻數量取值為100，蟻群算法的最大迭代次數取值為100，對兩種算法分別運行3次，選擇其中最佳實驗結果。傳統蟻群算法的三維路徑軌跡如圖4所示，改進蟻群算法的三維路徑軌跡如圖5所示，傳統蟻群算法、改進蟻群算法的收斂曲線圖分別如圖6和圖7所示。

圖4 傳統蟻群算法三維路徑軌跡 圖5 改進蟻群算法三維路徑軌跡

圖6 傳統蟻群算法收斂曲線 圖7 改進蟻群算法收斂曲線

實驗結果顯示，應用傳統蟻群算法進行三維路徑尋優搜索的最優路徑長度為77.78 m，應用本文改進蟻群算法進行三維路徑尋優搜索的最優路徑長度為71.36 m，改進蟻群算法在搜索最優路徑長度方面相比于傳統蟻群算法提高了8.3%；改進蟻群算法迭代16次搜索到全局最優路徑，同時達到穩定狀態，傳統蟻群算法迭代44次搜索到最優路徑，同時達到穩定狀態，在收斂速度方面，改進蟻群算法比傳統蟻群算法提高了63.7%。以上數據表明，本文改進蟻群算法要明顯優于傳統蟻群算法，能更快更穩定的完成三維路徑規劃。

4 結論

本研究通過分析傳統蟻群算法的不足，對該蟻群算法進行改進。首先，通過對三維空間環境進行建模，改進信息素更新策略，利用初始化信息素的不均勻分布，吸引蟻群每次搜索路徑時優先選擇距離終點更近的柵格位置。然后采用信息素全局更新及局部更新兩種方式，達到全局路徑搜索的目的。最后通過多元啟發函數計算出螞蟻選擇三維可視區域內各點的概率，促進螞蟻能完成起點到終點的路徑搜索，提高算法收斂速度。在三維空間下進行傳統蟻群算法與改進蟻群算法的仿真實驗并作對比分析，結果顯示，改進后的蟻群算法在路徑搜索速度方面及最優路徑軌跡方面均優于傳統蟻群算法。

(責任編輯：潘姝靜)