基于轉角約束的改進蟻群優化算法路徑規劃

李開榮，劉 爽，胡倩倩，唐亦媛

（揚州大學信息工程學院，江蘇揚州 225127）

（*通信作者電子郵箱973279727@qq.com）

0 引言

隨著智能化時代的到來，移動機器人越來越普及，其中一項重要的研究工作即移動機器人的路徑規劃問題。移動機器人的工作環境中往往存在著一定數量的障礙物，需要從初始點準確且快速地尋找一條能夠避開所有障礙物到達目標點的最優路徑［1］。傳統的路徑規劃算法有柵格法、人工勢場法等［2］。柵格法屬于全局路徑規劃算法，用于構建移動環境，將機器人的路徑轉換為網格之間的連接，算法簡單易實現；但是當移動環境變大時，網格數量急劇增加，數據存儲空間大，計算速度慢。人工勢場法是一種局部路徑規劃算法，實時性強、計算量小，對硬件平臺的要求低；但是其存在的局部最小點問題很容易引起路徑規劃的失敗。因此，隨著移動環境復雜度和任務難度的增加，傳統的路徑規劃算法無法達到預期的效果。隨著人工智能的發展，例如遺傳算法［3］、蟻群優化（Ant Colony Optimization，ACO）算法［4］、煙花算法［5］、粒子群算法［6］等智能算法也被應用到路徑規劃領域中，并且取得了豐富的成果。

在上述路徑規劃方法中，蟻群優化算法［7］具有較強的魯棒性和搜索能力，作為一種啟發式算法，對螞蟻群體的覓食過程進行學習模擬，得出螞蟻們共同規劃的解路徑，具有正反饋、并行計算以及易融合等特點，但也存在迭代次數多和易忽略全局最優解等問題。針對這些問題，許多國內外學者進行了探索與改進，文獻［8］針對傳統蟻群優化算法易陷入局部最優、初期搜索能力差等問題，采用改進的頭尾搜索機制，引入獎懲因子與信息素最大最小閾值，添加遺傳算法變異因子，使規劃出來的路徑得到了進一步的優化。文獻［9］為避免初期尋優的盲目性，在柵格地圖中劃定優選區域，設置新的初始信息素濃度模型，提高了算法的收斂速度。文獻［10］使用偽隨機狀態轉移規則選擇路徑，根據當前最優解和迭代次數計算狀態轉移概率，自適應地調整確定選擇和隨機選擇的比例，引入最優解和最差解改進全局信息素更新方法，仿真實驗結果表明，改進后的蟻群優化算法收斂速度更快、全局搜索能力更強。文獻［11］在蟻群優化算法中融合免疫算法，大大緩解了抗體種群的“早熟”問題。文獻［12］將蟻群優化算法生成的路徑進行平滑操作，減少了轉彎次數。

以上改進蟻群優化算法大多致力于優化路徑長度以及提高尋路效率，很少有學者在尋找下一步移動節點時就考慮到轉彎角度次數過多導致機器人運行時間增長、能耗增加的問題，部分學者在路徑規劃出來后對其進行平滑操作，但這種方式增加了算法的復雜性，且最終路徑未必就是全局最優路徑。鑒于此，本文提出了一種基于轉角約束的改進蟻群優化算法，用于移動機器人路徑規劃。為降低搜索初期的盲目性，該算法首先增加起始點與終止點之間的初始信息素濃度；并且在啟發函數中加入A*算法的估價函數和轉彎角度因子，使搜索到的路徑是綜合路徑長度和累計轉角最小的最優路徑，有利于減少移動機器人損失的能耗，防止出現局部最優的情況；在信息素更新公式中，引進狼群算法的獵物分配原則，同時借鑒最大最小蟻群（Max and Min Ant System，MMAS）算法給路徑上的信息素規定上限和下限，進一步提高收斂速度，便于快速搜索到一條綜合指標最優的路徑。

1 基本蟻群優化算法

蟻群優化算法即螞蟻種群從起始點出發，至目標位置獲取食物的過程，螞蟻的信息素會被留在其走過的路徑上，它們利用信息素相互通信，當某一條路徑上通過的螞蟻越來越多時，該路徑的信息素濃度就會越高，其他螞蟻就有更大的概率選擇這條路徑，起到正反饋作用，然而也容易導致局部最優或死鎖情況的出現［13］。

通過對信息素濃度、啟發因子、路徑方向等因素進行綜合判斷選擇下一步移動的柵格，并利用輪盤賭法計算當前節點到下一節點的概率［14］，如式（1）～（3）所示。

其中：τij是網格i到網格j的信息素值；ηij是網格i到網格j的啟發式信息；α為信息素激勵因子，代表信息素值對路徑選擇的影響程度，α越大則信息素對于路徑選擇的影響越大，大多數螞蟻走過的路徑將有更大幾率被選中；β是期望啟發式因子，代表啟發信息對螞蟻選擇路徑的影響程度，β與影響程度之間是正相關關系；dij代表節點i與節點j之間的歐幾里得距離。（xi，y）i和（xj，y）j是網格i與網格j的坐標；allowedk中存放網格i中螞蟻此時能夠選擇的網格集合。

經過t時刻，當每只螞蟻都進行了一次路徑規劃后，計算所有順利到達目標點的螞蟻走過的路徑長度，從中篩選出最短路徑，并且將每條路徑上的信息素濃度都進行更新，一段時間后，將揮發一部分信息素，如式（4）所示：

其中：ρ是信息素揮發系數。

同時螞蟻也將在路徑上留下一些信息素，如式（5）所示：

式（6）為蟻群模型的信息素更新策略，其中：Q為信息素的強度，若螞蟻搜索到的路徑長度dij越小，依據公式，則將會有更多的信息素被加到路徑上，之后其他螞蟻選中該路徑的可能性也將更大［15］。

2 環境建模

常用的環境建模方法有柵格圖法、可視圖空間法、自由空間法、幾何信息法［16］等。本文選擇柵格圖法對移動機器人二維運動空間進行建模，假設每個柵格的邊長為1，其中：白色柵格為自由柵格，表示可通行區域；黑色柵格為障礙物區域，移動機器人不可通行。如式（7）所示：

移動機器人平行行駛在障礙物邊緣的位置關系如圖1所示。

圖1 機器人與障礙物的位置關系Fig.1 Position relationship between robot and obstacle

假設移動機器人的直徑為W，從圖1 可以看出，當機器人的中心占據柵格距離障礙物邊緣的最小距離小于W/2 時，就會發生碰撞［17］，此時的碰撞概率為100%，即

其中：P（x，y）為柵格（x，y）的碰撞概率；N（x，y）為移動機器人中心所占據的柵格；｛O｝為障礙物所有邊緣柵格的集合；min（｛O｝，N（x，y））表示移動機器人中心占據柵格到障礙物所有邊緣柵格距離集的最小值。

為確保移動機器人在運動中不與障礙物邊緣發生碰撞，且保證每次轉彎的順利進行，本文將障礙物尺寸進行適當膨化后再預留出一定的安全距離，其中安全距離為移動機器人的半徑，進而可將機器人簡化為一個質點來處理，障礙物處理過程如圖2所示。

圖2 障礙物處理圖Fig.2 Obstacle processing diagram

網格模型被放置在二維坐標系中，x為橫軸，y為縱軸，采用序列號的方法標記每個網格。在N*N的網格圖中，起始節點以“起始”命名，目標節點以“目標”命名，其余柵格分別用編號i表示，每個柵格的中心點坐標為（xi，y）i，柵格編號與其坐標的對應關系如式（9）所示：

3 改進蟻群優化算法

基本的蟻群優化算法有以下缺點：每個柵格的初始信息素值相同且啟發式值之間也不存在明顯差異，因此往往搜索時間較長，難以尋找到全局最優解［18］；同時在柵格地圖中，使用基本蟻群優化算法規劃出來的路徑可能會有更多的轉彎次數和較大的累計轉彎角度。為了解決上述問題，本文進行了以下改進。

3.1 初始信息素不均勻分布

在基本蟻群優化算法的初始階段，每個柵格的初始信息素值相同，這就使得螞蟻在初期搜索時存在不小的盲目性，算法運行時間增加。因此本文將初始信息素的分布進行適當調整，使其不均勻分布，并且不會增加算法的復雜性。通過參考其他眾多文獻中的路徑，本文發現最優路徑大部分情況下都存在于起點與終點連線的附近［19］，因此此處取柵格地圖各邊的中點，連接相鄰邊的中點，得到與起點終點連線平行的兩條直線，直線AB與直線CD之間的區域如圖3 所示，增強該區域的初始信息素值，如式（10）所示。

圖3 初始信息素增強區域Fig.3 Initial pheromone enhancement area

其中：τ0為信息素初始值，C為大于τ0的常數。

3.2 改進啟發式信息

基本蟻群優化算法的啟發函數中，相鄰網格之間啟發式值的大小相差無幾，所以往往需要較長的搜尋時間且不易搜索到全局最優路徑。為此，本文將A*算法加入到蟻群優化算法的啟發式信息中，以提高算法的收斂速度并獲得更優的全局路徑［20］。

A*算法有較快的尋路速度，其啟發式成本由估價函數（fn）表示，通過（fn）來指導節點的擴展與搜索，每一次都是搜索從起始點到目標點之間使得（fn）最小的路徑，估價函數方程為：

其中：g（n）為從起始節點到當前節點的最小路徑成本值；h（n）為從當前節點到目標節點的最小路徑成本估計值；nx和ny是當前節點n的坐標；gx和gy是目標節點g的坐標；sx和sy是初始節點s的坐標。

機器人在經過障礙物群時，若只是把路徑最短作為主要因素，則會造成機器人轉彎次數過多，時間和能耗大大增加，也會導致機器人壽命的減少。因此，本文將轉彎角度因子也加入到蟻群優化算法的啟發信息中，使移動機器人盡可能選擇一條轉彎角度更小的路徑，若一條路徑中節點之間的轉彎角度過大，則啟發函數值將降低，路徑中節點之間的轉彎角度示意圖如圖4所示。

圖4 轉彎角度示意圖Fig.4 Schematic diagram of turning angle

圖4中統一按照順時針的方向進行角度測量，（A，B）節點之間的路徑相對于（O，A）節點之間轉彎角度是45°，而（C，D）節點之間的路徑相對于（B，C）節點之間的轉彎角度是90°，轉彎角度值的計算公式如下：

其中：R是轉彎角度因子；γ是轉彎角度（單位：rad）；c是轉彎角度權重系數。

綜上，在蟻群優化算法中，將A*算法的估計函數用作啟發式信息，以便于搜索全局最優路徑、提高收斂速度；同時，將轉彎角度因子也添加到蟻群優化算法的啟發式值中，以減少轉彎次數和累計轉向角度，促使機器人按照路徑長度和轉彎角度雙重因素進行最優選擇。改進后的啟發函數公式如下：

其中：Q1是大于1的常數。

3.3 改進信息素更新

蟻群算法模擬自然界中的蟻群覓食機制，采用分布式正反饋并行計算機制，傳統蟻群算法是各個螞蟻單獨行動且每只螞蟻都執行相同的操作，螞蟻之間的協作不足，可能會導致滯后、算法陷入局部最優、收斂速度慢等問題。在搜索路徑時，存在一部分螞蟻找到的路徑是最差路徑，它們所釋放的信息素將對之后的螞蟻尋路造成負面影響，從而容易使搜索陷入局部最優，還可能出現死鎖情況導致有效螞蟻數量損失；而另一些螞蟻尋得最優路徑，它們所釋放的信息素將對其余螞蟻尋找最優路徑起到促進作用。為了提升收斂速度、獲得最優路徑，此處融合狼群算法，在蟻群算法的信息素更新公式中加入獵物分配原則［21］。

狼群算法是一種智能優化算法，模擬狼群的社會分工和捕食行為，其分配規則為“強者生存”的狼群更新機制，狼群中存在貢獻能力弱的狼，即身體瘦弱的狼，它們獵得食物的數量和可能性都遠小于身體強壯的狼，就如蟻群中存在尋得路徑差的螞蟻，這些螞蟻尋得的路徑要差于尋路能力強的螞蟻。

因此，狼群算法中按照狼“由強到弱”的順序進行獵物分配，身體強壯且善于捕獵的狼會優先獲得食物，反之身體瘦弱的狼則只能分得很少的食物。隨著每次分配的進行，部分身體弱小的狼將越來越難以生存下去，直至餓死；而先前本就強壯的狼將越發強壯，在下一次捕獵時獵得食物的可能性將進一步增大，經過迭代，狼群的生存能力被逐漸提高。

在蟻群算法中融合狼群算法中獵物分配原則的動機是借鑒該分配原則來解決傳統蟻群算法在信息素更新時存在的問題，即尋得最差路徑的螞蟻釋放的信息素將會對隨后的螞蟻尋路造成一定的誤導作用，容易使路徑陷入局部最優，并且尋得最優路徑的螞蟻釋放的信息素不能很好地傳遞給之后的螞蟻。這一融合過程可以理解為，加強蟻群算法中優質路徑上的信息素濃度，較弱個體的經驗由于參考價值少，不應被著重考慮，便于更多的螞蟻吸收優質個體的經驗，提高收斂速度。

采用狼群算法中“強者生存”的更新機制有效傳承了整個螞蟻種群在搜索路徑時形成的“智慧”、提高全局搜索能力、避免陷入局部最優解，符合自然界種群繁衍進化的特點，不斷更新的信息素代表著蟻群在整個路徑搜索過程中形成的尋路智慧，有利于該智能優化算法對解空間進行更好的學習。

借鑒這種思想，本文算法在每次迭代中，計算各個螞蟻的運動軌跡長度，將到達目標點路徑最短的螞蟻所留下的信息素增強，路徑最長的螞蟻所留下的信息素減弱，突出不同路徑之間信息素的差別化。對信息素更新公式作如下改進：

其中：Δ*τij和Δ**τij分別代表每次迭代中最優和最差路徑經過節點i、j的信息素大小；L*和L**分別代表每次蟻群到達目標點的最短運動軌跡和最長運動軌跡；δ和ω分別表示每次搜索時找到最短路徑和最長路徑的螞蟻數量；Q2為增強因子，此處將其設為1；R1為減弱因子，將其值設為0.5。

經過多次迭代后，某條路徑上的信息素值可能遠大于或遠小于其他路徑，使得搜索不能繼續進行下去、過早收斂，為防止這種極端情況產生，借鑒MMAS算法［22］，將信息素的取值范圍限定在τmin到τmax，如式（19）所示：

4 改進算法的步驟

綜上所述，本文對基本蟻群算法改進后，移動機器人路徑規劃的步驟如下：

步驟1 通過柵格法對工作環境進行建模，為移動機器人設定好運動的起始點和目標點。

步驟2 初始化參數：螞蟻數量m，信息素重要程度因子α，啟發函數重要程度因子β，信息素揮發系數ρ，信息素強度系數Q、迭代次數N等，其中初始信息素濃度按式（10）設置。

步驟3 更新禁忌表。將螞蟻k（k=1，2，…，n）放在當前節點上，將當前節點添加到禁忌表中。

步驟4 選擇下一步的網格。根據式（15）計算加入A*估價函數和轉角約束的啟發式函數值，然后依據式（1）～（3）求出狀態轉移概率值。再借鑒輪盤賭法選出下一步將要到達的柵格，若螞蟻抵達目標位置，則轉到步驟5；反之轉到步驟3。

步驟5 如果螞蟻到達目標位置，重復步驟3，直到每個螞蟻在其迭代過程中完成整個搜索過程，之后轉到步驟6。

步驟6 更新信息素。每次迭代完成，如果此時迭代次數小于最大迭代次數，將按照狼群算法的獵物分配原則即式（16）～（18）計算路徑上的信息素濃度，同時要保證其滿足式（19），若滿足收斂條件，則退出；若不滿足，轉到步驟3。反之迭代次數大于最大迭代次數時，則停止計數，輸出最終結果。

本文算法整體流程如圖5所示。

圖5 本文算法流程Fig.5 Flowchart of proposed algorithm

5 仿真分析

為了驗證本文改進蟻群算法的可靠性，使用Matlab 軟件進行仿真。分別使用4 種不同規模的柵格地圖，每次在同樣大小的柵格地圖中，采用相同的實驗條件對8 種不同的算法進行對比分析。

5.1 參數取值

關于蟻群算法主要參數值的確定，目前沒有特別詳盡的理論方法，因此本文根據經驗反復實驗而定，設置不同的參數組合進行仿真，分析實驗結果，選擇最佳參數組合。

對每一個參數設置一組值，以圖3 的柵格地圖為本次實驗環境，起始點和目標點分別用點S和點T在圖中表示，在每次測試中僅改變一個參數的取值，其他參數為常量，分別計算最佳路徑長度和迭代次數。由于對規劃結果影響較大的參數是螞蟻數量m、信息素啟發因子α和期望啟發式因子β，因此本文僅介紹這三個參數的取值過程。其余參數根據經驗及實驗仿真對比，初始化參數值如表1所示。

表1 初始化參數值Tab.1 Initialized parameter values

5.1.1 螞蟻數量m

在蟻群算法中，當螞蟻數目過多時，信息素的作用將被削弱，導致蟻群算法的收斂速度變慢；當螞蟻數目過少時，可能存在路徑未被選擇的情況，無法有效搜索到全局最優解。因此，選擇合適的螞蟻數量至關重要，本文對除螞蟻數目m之外的其他參數取值分別為：α=1，β=7，ρ=0.3，取螞蟻數量m=10，20，30，40，50，60，70，80，90，100。為防止偶然因素，對每組數據運行10次，得到螞蟻數量m對計算結果的影響如圖6所示。

圖6 螞蟻數量m對ACO算法的影響Fig.6 Influence of the number of ants m on ACO algorithm

由圖6 可知，隨著螞蟻數量從10 變化到40，最短路徑的長度急劇下降，之后變化幅度減小至不再變化；迭代次數呈現升降升的趨勢，在螞蟻數量為50 時，迭代次數達到最小。總結發現，當螞蟻數量約為自由柵格數的1/6 時，算法的收斂速度和路徑長度達到最優。

5.1.2 信息素啟發因子α和期望啟發式因子β

α表示當前螞蟻受前代蟻群搜索結果的啟發程度，β反映的是當前環境相關信息對螞蟻的影響程度。α越大，β越小，則螞蟻越依賴信息素的指導，傾向于選擇之前走過的路徑；反之，α越小，β越大，則螞蟻更傾向依據當下的環境選擇較短的路徑抵達目標點。兩者是相互關聯的，因此此處選擇將β/α設為自變量，路徑長度和迭代次數作為因變量。設α=1，β/α取1～10，m=50，ρ=0.3，其余參數取值如表1。對計算結果的影響如圖7所示。

圖7 β/α對ACO算法的影響Fig.7 Influence of β/α on ACO algorithm

由圖7 可知，隨著β/α值的遞增，最短路徑長度逐漸減小直至穩定，迭代次數先減小后增加，在β/α=7 時取最小值。因此，當α=1，β=7時，蟻群算法各方面具有較優的性能。

5.2 小規模柵格環境

首先將基本蟻群算法、文獻［12］、文獻［23］、文獻［24］改進的蟻群算法及本文算法在20×20、30×30規模的柵格地圖上進行對比實驗。此處實驗各相關參數取值為：m=50，α=1，β=7，其余按表1取值。

5.2.1 20×20柵格環境

在20×20 規模的柵格環境中，5 種算法仿真結果如圖8 所示。由圖8可知，基本蟻群算法規劃出的路徑長度為31.4，文獻［23］算法的路徑長度為31.4，文獻［24］算法的路徑規劃長度為29.8，文獻［12］規劃出的路徑長度為28.82，本文算法的最優路徑長度為28.63。

圖8 在20×20地圖上5種算法規劃的路徑Fig.8 Paths planned by five algorithms on 20×20 map

五種算法的路徑長度和迭代次數如圖9 所示。由圖9 可知，本文算法和文獻［23］算法的迭代穩定次數相差不大，比基本蟻群算法和文獻［12］算法減少50%的迭代穩定次數，比文獻［24］的迭代穩定次數也更優，具體指標比較如表2 所示。由表2 可知，在路徑長度上，本文改進之后的算法運行出的最優路徑長度為28.63，較基本蟻群算法和文獻［23］算法縮短8.8%，較文獻［24］算法也縮短了3.9%；在轉彎次數上，本文算法轉彎次數為4，分別較基本蟻群算法和文獻［23］算法減少了75%和50%，大幅減少了轉彎次數；在累計轉彎角度上，較基本蟻群算法、文獻［23］和文獻［24］算法分別減少了720°、270°和180°，規劃出的路徑更加平滑，避免了移動機器人過多的能耗損失，延長了壽命，縮短了轉彎時間。

圖9 在20×20地圖上的路徑長度迭代圖Fig.9 Path length iteration graph on 20×20 map

文獻［12］算法的主要思想是將蟻群算法生成的全局最優路徑再進行平滑處理，將路徑中兩個不在同一直線上的節點連線，若連線中間不穿過障礙物則此連線就是新的路徑，以此法來進行路徑平滑處理。由表2 中可以看出，文獻［12］算法能夠有效縮短路徑長度和累計轉彎角度，但是該算法仍存在明顯不足：在迭代次數上，該算法需要26 次迭代才能達到穩定，而本文算法僅需4 次即可；在程序運行時間上，文獻［12］算法需要10.632 s，本文算法在6.921 s 內即可完成。綜合多種指標來看，在此處柵格環境下本文算法都要優于文獻［12］算法。

表2 在20×20地圖上的仿真結果Tab.2 Simulation results on 20×20 map

綜上，本文算法生成的路徑綜合指標最優，改進之后的算法優勢明顯。

5.2.2 30×30柵格環境

為了進一步驗證本文算法的可靠性，將柵格地圖擴大為30×30，障礙物增多，再次進行仿真。基本蟻群算法、文獻［12］算法、文獻［23］算法、文獻［24］算法以及本文算法的路徑規劃如圖10所示。

圖10 在30×30地圖上五種算法規劃的路徑Fig.10 Paths planned by five algorithms on 30×30 map

由圖10 可以看出，當柵格地圖規模擴大并且障礙物增多時，基本蟻群算法、文獻［12］算法、文獻［23］算法、文獻［24］算法無法很好地適應該類較為復雜環境的全局路徑規劃，其規劃出的最優路徑長度分別為50.2、45.8、47.2和47.5，而本文算法仍然可以很好地執行，尋得的最優路徑長度為43.3，較其他算法有效縮短了路徑長度，路徑長度與迭代次數的關系如圖11所示。

圖11 在30×30地圖上的路徑長度迭代圖Fig.11 Path length iteration graph on 30×30 map

圖11為五種算法在30×30柵格規模下的收斂曲線變化趨勢，可以看出當環境復雜化后，本文算法及文獻［23］算法在迭代穩定次數上比其余三種算法更優，文獻［23］算法的收斂速度比文本算法稍快一些，具體指標比較如表3所示。

表3 在30×30地圖上的仿真結果Tab.3 Simulation results on 30×30 map

由表3 可知，本文的改進蟻群算法在路徑長度、轉彎次數以及累計轉彎角度等指標上都明顯優于基本蟻群算法、文獻［23］及文獻［24］的算法，這三種算法在障礙物增多的環境中都無法很好地適應，其中本文算法在路徑長度上較基本蟻群算法縮短了13.7%、較文獻［23］算法和文獻［24］算法縮短了8.3%和8.8%；轉彎次數也是其中最少的，尤其是較基本蟻群算法減少了64.3%；在累計轉彎角度指標上，本文算法占明顯優勢，較迭代穩定次數表現較優的文獻［23］算法減少了41.2%。另外，可以看出文獻［12］算法、文獻［23］算法和文獻［24］算法在復雜環境下出現多次直角轉彎，而移動機器人面臨直角轉彎時比45°轉彎會消耗更多的能量，本文算法規劃的路徑中不存在直角轉彎的情況。同時在實際運動中，直角轉彎所需要的時間也更多，將大大增加機器人從起始點到目標點的運行時間，而本文算法不僅累計轉彎角度最小，也有效避免了直角轉彎的出現。

目前針對移動機器人轉角減小的研究中，文獻［12］中的平滑方法較為普遍，但該方法存在一定的局限性。由表3 可以看出，在路徑長度上，文獻［12］算法較其他三種算法更優，但本文算法規劃出的路徑長度是43.3，比其更短；在轉彎次數上，兩者相同；但在累計轉彎角度上，本文算法比文獻［12］算法減少了20.4%；除此之外，本文算法在迭代穩定次數和程序運行時間上分別比文獻［12］算法減少了50.0%和21.1%。綜合來看，本文算法在30×30 的柵格地圖中具有更好的計算結果，各方面性能更優，克服了傳統路徑平滑方法的不足。

由兩次不同規模的柵格實驗可以看出，環境變復雜時，本文算法仍有良好的適應性并且優勢更加明顯，可以尋得一條綜合性能更優的路徑。

5.3 大規模柵格環境

5.3.1 100×100柵格環境

為了進一步驗證本文改進算法在規模較大的柵格地圖中的適應性，首先建立100×100 規模的柵格地圖，將文獻［25］的改進A*算法、文獻［26］的改進RRT（Rapidly-exploring Random Tree）算法以及本文算法在該規模的地圖中進行仿真，此處實驗各相關參數取值為：m=100，α=1，β=7，其余按表1 取值。三種算法的路徑規劃如圖12所示。

圖12 在100×100地圖上三種算法規劃的路徑Fig.12 Paths planned by three algorithms on 100×100 map

由圖12可以直觀地看出，相較于改進的A*算法以及RRT算法，本文算法生成的路徑擁有更少的轉彎次數，三種算法的具體仿真結果如表4所示

表4 在100×100地圖上的仿真結果Tab.4 Simulation results on 100×100 map

由表4 可以看出，改進A*算法和改進RRT 算法在路徑長度上相差很小，本文算法規劃的路徑長度上更優；同時，在轉彎次數上，本文算法表現更好，規劃出的路徑最為平滑；本文規劃路徑的累計轉彎角度較前兩種算法分別減少了19.9%和37.6%；但在程序運行時間上，表現得不如改進A*算法優異。綜合來看，本文算法在100×100 規模的柵格地圖中仍具有良好的適應性，規劃路徑的長度和轉角次數是最優的。

5.3.2 200×200柵格環境

將柵格規模再次擴大為200×200，此處將文獻［27］的改進蟻群算法作為本文算法的對比算法。將兩者在柵格地圖中進行仿真分析，兩種算法的路徑規劃如圖13所示。

圖13 在200×200地圖上兩種算法規劃的路徑Fig.13 Paths planned by two algorithms on 200×200 map

由圖13 可知，兩種算法在大規模的復雜環境中均能從起點順利抵達終點，與文獻［27］算法相比，本文算法規劃出的路徑更加平滑，轉彎次數更少，具體實驗結果如表5所示。

表5 在200×200地圖上的仿真結果Tab.5 Simulation results on 200×200 map

由表5 可知，本文算法在運行時間上稍遜于文獻［27］算法，但在路徑長度、轉彎次數以及累計轉彎角度上都更占優勢，分別較文獻［27］算法降低了6.7%、55.6%和65.8%。

由以上實驗結果，驗證了本文改進蟻群算法在復雜地形環境中進行路徑規劃的可行性和有效性。

6 結語

本文針對基本蟻群算法在移動機器人路徑規劃應用上存在的缺陷，提出了基于轉彎角度約束的改進蟻群算法。規劃不同柵格的初始信息素值，在啟發函數中有效融合了A*算法的尋路能力，以路徑長度和轉彎角度兩因素為下一步柵格的選擇指標，使路徑更加平滑，并且在信息素更新中引入了狼群算法的分配原則，同時限制最大最小信息素的值。本文改進之后的算法使螞蟻能在更短的時間內尋得一條綜合路徑長度和轉角次數的最優路徑，降低了移動機器人的能耗損失，延長壽命，使其能高效、安全地移動到目標點，驗證了本文算法在復雜環境中的有效性和適應性。

在今后的研究中，將進一步研究蟻群算法參數的取值問題，利用神經網絡計算出使路徑更優的參數取值，將大大節約調試時間，使算法更加智能化。