基于雙向搜索的改進蟻群路徑規劃算法

張子然，黃衛華，2，3，陳 陽，章 政，2，3，李梓遠

1.武漢科技大學 機器人與智能系統研究院，武漢430081

2.武漢科技大學 冶金自動化與檢測技術教育部工程研究中心，武漢430081

3.武漢科技大學 信息科學與工程學院，武漢430081

隨著生活中自動化程度日趨提高，移動機器人在物流運輸、醫療服務和工廠制造等領域的應用越來越廣泛。路徑規劃作為移動機器人研究中復雜和重要的課題，是移動機器人實現自主定位導航技術的核心技術之一，它是指移動機器人依據一定的規則，在工作空間中找到一條從起點到終點的無碰撞最優路徑[1]。近年來，越來越多的群智能優化算法被用于解決機器人的路徑規劃問題，如遺傳算法[2]、粒子群算法[3]、灰狼優化算法[4]和蟻群算法[5]等。其中，遺傳算法全局搜索能力強，但收斂耗時長；粒子群算法結構簡單、收斂速度快、易于實現，但其存在早熟的問題；灰狼優化算法不易受參數影響，簡單易實現，但該算法穩定性差及其后期局部搜索能力差。蟻群算法基于模擬螞蟻在覓食過程中發現路徑的行為，有效解決復雜環境下最優路徑的搜索問題，具有魯棒性好、分布式計算能力強等特點，已被廣泛應用于移動機器人的全局路徑規劃。

然而，蟻群算法存在收斂速度慢、易陷入局部最優等問題。文獻[6]提出了一種蟻群-聚類自適應動態路徑規劃算法，依據聚類算法對環境進行判別，自動改變螞蟻的尋優半徑，提高收斂速度。文獻[7]引入環境信息因子來改進啟發函數降低死鎖情況的發生，增加了有效螞蟻數量，加快了搜索速度。文獻[8]先利用鳥群算法（BSA）對地圖進行快速搜索，生成蟻群算法初始信息素分布，同時引入自適應期望函數，增加相鄰節點被選擇概率的差距，提高了算法的有效性。目前，關于蟻群算法的改進主要是基于單向路徑搜索策略，對于大規模復雜環境下，如存在U型、L型等特殊障礙物的區域，單向路徑搜索的方式遍歷節點多，直接影響路徑規劃的效率。雙向搜索算法分別從起點和終點同時運行兩個方向的搜索，可有效減少所需的節點搜索量，縮短路徑規劃時間。文獻[9]根據不同環境地圖，從起點和終點同時運行A*算法，減少了算法的遍歷次數和運行時間。文獻[10]改進跳點篩選規則，從兩個方向交替進行路徑搜索，減少路徑搜索時間和擴展節點。文獻[11]將參數自適應調整和雙向搜索并行策略加入蟻群算法，提高螞蟻搜索路徑的效率。此外，針對機器人在復雜程度環境下的路徑尋優誤差較大的問題，國內外學者使用移動邊緣計算（MEC）和模糊預測控制與A*算法等尋優算法結合，均取得不錯的尋優效果[12-15]。

鑒于上述分析，本文設計了一種融合了環境信息和雙向搜索的改進蟻群算法。首先，設計了一種改進的K-means算法對障礙物聚類，根據障礙物的數量和位置量化環境地圖的復雜度，使機器人更大概率選擇復雜度小的區域尋優，減少路徑拐點數量；然后，設計了基于雙向搜索策略的改進蟻群算法，使啟發函數包含了路徑起點與終點的位置關系，以此減少冗余的搜索路徑、提高蟻群搜索方向的精度和全局搜索速度；此外，使信息素揮發系數服從正態分布，增加蟻群算法迭代初期和后期的靈活性；最后，在存在U型障礙物的復雜環境下進行實驗，實驗結果表明，本文所設計的基于雙向搜索的改進蟻群路徑規劃算法具有耗時短、拐點少和收斂速度快等特點。

1 基于改進K-means算法的地圖處理

鑒于地圖的復雜程度對路徑規劃的效率有較大影響，本文設計了一種基于改進K-means算法對地圖預處理。根據障礙物的數量和位置分布對障礙物進行聚類，并通過計算地圖分區的擁擠度和疏通度對地圖的復雜程度進行量化；在此基礎上，讓機器人優先選擇復雜度小的區域進行路徑搜索，減少尋優拐點，提高算法搜索效率。

（1）初始聚類中心點的確定

K-means算法的聚類效果和精度取決于初始聚類中心的選擇，當其選擇不當時，無法有效避免孤立點、噪點對分類結果的影響[16]。本文基于樣本圓和樣本密度的評價確定K-means算法的初始聚類中心點。

設x1,x2,…,xN為柵格地圖中存在的N個障礙物，每個樣本記為xi=(xi1,xi2)，xi1、xi2分別為xi的橫坐標和縱坐標，數據集D={x1,x2,…,xN}。樣本點xi和xj之間的歐氏距離為d(xi,xj)，則數據集D的平均樣本距離公式為：

其中，i,j=1,2,…,N。

定義樣本圓為以任意樣本點xi為圓心，r=dˉ/2為半徑的圓。定義f(x)為位置判斷函數，若樣本點xj到圓心xi的歐式距離小于平均樣本距離dˉ，則判定樣本點xj存在于該樣本圓內，記為1，否則記為0，則有：

樣本圓密集度定義如下：

基于式（3）計算樣本圓密集度并將所有樣本圓密集度從大到小排列，找到樣本圓密集度最大的值所對應的樣本點，將該點作為第一個初始聚類中心點c1，并將該點所對應的樣本圓中的數據樣本從數據集中刪除；重復上述步驟，直到數據集D為空集，由此確定環境地圖的k個初始聚類中心點c={c1,c2,…,ck}。

（2）擁擠度和疏通度的確定

設k個障礙物聚類分區分別為Y={Y1,Y2,…,Ye,…,Yk}，e=1,2,…,k。樣本點xi劃歸到距離它最近的聚類中心ce所在的分區為Ye，則其余各個樣本點到k個初始聚類中心點的歐氏距離為：

其中，ce1、ce2分別為聚類中心點ce的橫坐標和縱坐標。

設Ne為分區Ye中的樣本點的數量，更新第e個分區的聚類中心點位置ce為：

設δSSE為樣本點xi與聚類中心點位置ce的誤差平方和：

對于每個分區中障礙物的數量和位置，定義擁擠度Pe和疏通度Pe0如下：

其中，Pe是分區Ye的擁擠度，Me是分區Ye中柵格總數，Ne是分區Ye中障礙物的數量；Pe0是分區Ye的疏通度，Ne0是分區Ye中連續值為0的柵格數的最大值。

重復計算式（4）、（5）、（6），直到式（6）保持不變，確定最終k個聚類分區，并按照式（7）、（8）分別輸出每個分區的擁擠度和疏通度。

擁擠度描述分區中障礙物的密集程度，擁擠度越大，該分區障礙物越多；疏通度描述機器人在該分區直行通過柵格的能力。本文基于式（7）和式（8）對地圖環境的復雜度進行量化描述。

根據每個分區的擁擠度和疏通度，定義復雜度函數P(v)，如式（9）。P(v)是節點v在其所屬分區的復雜度函數：

由式（9）可知復雜度函數越小，說明節點v在其所屬分區的擁擠度越小，即障礙物密集度小，疏通度越大，即該分區連續為0的柵格越多，機器人在該分區能連續直行通過的柵格越多，拐點越少。

2 基于雙向搜索的改進蟻群算法設計

設定雙向搜索策略使兩組蟻群從初始點和終點并行搜索，相比于單向搜索效率更高；同時也考慮到初始點和終點的位置關系，解決了螞蟻路徑尋優時的方向問題，避免出現與目標點方向相背的路徑，提高螞蟻的方向搜索精度；并融合地圖的復雜度函數，使螞蟻在復雜程度小的區域尋優，減小路徑拐點數量。

2.1 雙向搜索策略的設計

設兩組不同的蟻群A、B，一共m對螞蟻，每只螞蟻記為Ar(r=1,2,…,m)和Br(r=1,2,…,m)。從A、B組中分別取一只螞蟻進行兩兩配對，每對螞蟻記為(Ar,Br)。以一對螞蟻為單位進行路徑雙向搜索，即每對螞蟻分別從正向(Ar→Br)和反向(Br→Ar)同時進行搜索，蟻群雙向搜索機制如圖1所示。

圖1 蟻群雙向搜索機制Fig.1 Ant colony bidirectional search mechanism

在路徑搜索過程中，設兩只螞蟻所經過節點的交集為：

若J不為空集，則說明兩只螞蟻相遇，則停止搜索，如圖1中E點，得到同對中兩只螞蟻的路徑長度LAr（黑色路徑）、LBr（紅色路徑），并計算L=LAr+LBr為蟻群算法的一個可行解；若在某次迭代結束后，J仍然為空集，則放棄此對螞蟻本次的路徑搜索結果。

2.2 狀態轉移概率函數的設計

設整個螞蟻群體中螞蟻的數量為m，在t時刻，節點u與節點v連接路徑上的信息素濃度為τuv(t)。初始時刻，各個城市連接路徑上的初始信息素濃度均為

設螞蟻n在t時刻從節點u轉移到節點v的概率為：

其中，ηuv(t)為啟發函數，表示螞蟻從節點u轉移到節點v的期望程度；allow為螞蟻n待訪問的節點的集合。α為信息素重要程度因子，其值越大，表示信息素的濃度在轉移中起的作用越大；β為啟發函數重要程度因子，其值越大，表示啟發函數在轉移中的作用越大，即螞蟻會以較大的概率轉移到距離短的節點。

復雜度函數量化了地圖復雜程度，體現了螞蟻在地圖直行尋優的能力。本文將地圖復雜度函數P(v)與狀態轉移概率函數結合，由式（11），當節點v的復雜度函數的值越小，則該節點被選擇的概率越大，路徑拐點數量越少。

2.3 啟發函數的設計

傳統蟻群算法的啟發函數沒有考慮到初始點與目標點的方向問題，并且當環境地圖中相鄰里兩節點的距離較短時，且容易造成蟻群尋優方向的偏差。

對于每只螞蟻，定義其目標點位同對螞蟻中另一只螞蟻的當前節點，如圖1中螞蟻Ar的目標點為螞蟻Br的當前節點TBr點。綜合考慮初始點、當前節點、下一節點、目標點和終點的關系，本文設計的改進蟻群算法的啟發函數為：

其中，duv是當前節點u到下一節點v的距離，dvT是下一節點v到目標節點T的距離，dSu為初始點S到當前節點u的距離，dSG為初始點S到終點G的距離。

新的啟發函數把同對中另一只螞蟻的當前搜索節點作為目標點T，并且不再只考慮當前節點u到下一節點v的距離duv，還考慮下一節點v到目標節點T的距離dvT，當dvT越小，節點v被選擇的概率越大，避免路徑偏差過大，螞蟻尋優精度更高。

2.4 自適應信息素更新函數的設計

信息素揮發因子值ρ的設置對算法的性能有重要的影響，若ρ設置得過大，會使信息素揮發得過快，路徑上殘留的信息素量無法吸引螞蟻來搜索，導致搜索能力變低；若ρ設置的過小，當螞蟻找到一條較優路徑時，由于揮發系數太小，導致該路徑殘留信息素較多，螞蟻難以找到其他更優路徑，使蟻群算法得到的可能是局部最優解。因此，本文設定自適應信息素揮發系數在初期取較大值，經過ω迭代后服從正態分布，設定μ=0時取到峰值，讓信息素揮發系數逐漸減小。

自適應信息素揮發因子定義為：

其中，ρ0為初始信息素揮發系數，Z為當前迭代次數，ω為設定的迭代次數。

在初始階段對揮發系數取較大值，增加信息素的正反饋，當迭代次數達到設定值ω時，ρ(Z)逐漸減小，負反饋減弱，搜索路徑上的信息素增加，信息素濃度對螞蟻的導向作用變強。

蟻群每完成一次迭代后，對各節點之間的路徑信息素濃度進行更新，由式（13）定義自適應信息素更新函數為：

其中，Δτuv為本次迭代完成后，路徑(u、v)上信息素的增量，Q表示螞蟻釋放的信息素濃度，Ln表示螞蟻n在本次迭代所走的路徑長度。

3 U型障礙物防死鎖處理

傳統蟻群算法在遇到復雜U型障礙物往往會陷入局部最優，如圖2。當螞蟻經過“父→子4”路徑時，子4的可選下一節點個數為0，此時螞蟻陷入死鎖。

圖2 U型障礙物Fig.2 U-shaped obstacle

在柵格地圖中，螞蟻通常有8個移動方向，除去已走的上一節點，在沒有障礙物的情況下，螞蟻有7個可選下一節點。本文定義死鎖判斷系數ζ，即0≤ζ≤7；當前節點的ζ=0時，則判定該點陷入死鎖，將當前節點加入禁忌表，同時清除當前節點和上一節點路徑上的信息素，且釋放禁忌表選擇上一節點，直至螞蟻走出陷阱。圖2中，父節點的ζ=4，4個可選下一節點分別為：子1、子2、子3、子4；子4的ζ值等于0，按照上述解決辦法，將子4加入禁忌表，清除“父→子4”路徑上的信息素，同時釋放禁忌表，讓下一節點返回父節點，解決死鎖問題。

4 算法步驟

綜合上述內容，本文設計的基于雙向搜索的改進蟻群算法結構如圖3，將其用于移動機器人路徑規劃中，具體流程如下：

圖3 基于雙向搜索的改進蟻群算法流程圖Fig.3 Flow chart of improved ant colony algorithm based on two-way search

步驟1地圖建模。選擇柵格法對地圖環境進行建模，將障礙物柵格化。

步驟2地圖預處理。采用改進的K-means算法實現地圖的預處理。

步驟3參數初始化。初始化兩組蟻群A、B，種群規模m、信息素因子α、啟發函數因子β、初始信息素揮發因子ρ0、信息素常量Q和最大迭代次數Z_max，設定的迭代次數ω，將迭代次數置為0，清空禁忌表，并且對兩組蟻群進行配對。

步驟4節點的選取。每只螞蟻按照式（11）計算下一節點的選擇概率，并采用輪盤賭選擇下一節點；當螞蟻陷入U型障礙物時，采用本文的防死鎖處理方法逃離。

步驟5路徑搜索機制。采用雙向搜索策略，達到搜索結束條件時，計算同對中兩只螞蟻的路徑長度LAr和LBr，記錄本次迭代的路徑長度L=LAr+LBr，并得到本次迭代的全局最優解。

步驟6信息素更新。當所有的m對螞蟻全部搜索完畢，由式（14）更新全局路徑的信息素。

步驟7迭代次數更新。判斷當前迭代次數Z是否達到最大迭代次數，是則結束算法并輸出最終結果；否則迭代次數Z=Z+1，并返回步驟4。

5 仿真實驗與結果分析

實驗1 20×20的柵格地圖

首先隨機生成20×20規模的柵格環境，并初始化相關參數：種群規模m=100，最大迭代次數Z_max=100，信息素因子α=1，啟發函數因子β=8，信息素常量Q=100，信息素揮發因子ρ0=0.9，ω=10，聚類簇數k=7（每一種顏色代表一個聚類分區）。傳統蟻群算法路徑、文獻[8]算法路徑、文獻[11]算法路徑和本文地圖預處理雙向蟻群算法路徑圖如圖4~圖7，最小距離曲線對比如圖8，具體參數如表1。

表1 20×20實驗仿真結果對比Table 1 Comparison of 20×20 experimental simulation results

圖4 傳統蟻群算法路徑Fig.4 Path of traditional ant colony algorithm

圖6 文獻[11]算法路徑Fig.6 Algorithm path of literature[11]

圖7 本文地圖預處理雙向蟻群算法路徑Fig.7 Path of bidirectional ant colony algorithm for map preprocessing in this paper

圖8 最小距離曲線對比Fig.8 Comparison of minimum distance curves

對比圖4和圖7，圖4傳統蟻群算法路徑分別在A和B點陷入U型障礙物，造成其最小距離曲線的波動，對應圖8虛線圓所在位置。圖7中，本文改進蟻群算法設定了防死鎖機制，避免了螞蟻陷入U型障礙物；設定雙向搜索策略，分別從正向(SA→GA)和反向(SB→GB)同時搜索，黑色路徑代表正向搜索的路徑，紅色路徑代表反向搜索的路徑，由于設計了方向機制的啟發函數，沒有出現過大偏差的情況，最終在E點相遇。由表1可知，相較于傳統蟻群算法的單向搜索，本文地圖預處理雙向蟻群算法的機器人移動時間減少了49.6%；引入了服從正態分布的信息素揮發系數，使本文算法有較強的逃離局部最優解的能力，收斂代數減少了68.3%；將地圖預處理后，由于量化了地圖局部的復雜度程度，螞蟻優先選擇復雜程度小的區域尋優。如圖7中，螞蟻在綠色分區和粉紅色分區中選擇了復雜度較小的綠色分區進行尋優，加強機器人直行通過地圖的能力，路徑更加平滑，相較于傳統蟻群算法拐點數減少了47.1%；

圖5 所示文獻[8]改進蟻群算法單向搜索，在復雜地圖中效率較慢，且沒有對地圖預處理，導致路徑拐點多。由表1可知，本文地圖預處理雙向蟻群算法相較于文獻[8]算法的機器人的移動時間減少了31.6%，收斂代數減少了53.3%，拐點數減少了35.7%，綜合性能更優。文獻[11]采用雙向搜索策略，機器人移動時間為9.801 s，與本文算法機器人移動時間8.504 s差距不明顯，但是由于本文引入了服從正態分布的信息素揮發系數，收斂代數相較于文獻[11]減少了37.8%；并且將地圖預處理，路徑更加平滑，拐點數減少了25%。綜上所述，本文地圖預處理雙向蟻群算法機器人移動時間更短，收斂代數更少，路徑更加平滑。

圖5 文獻[8]算法路徑Fig.5 Algorithm path of literature[8]

實驗2 50×50的柵格地圖

為了進一步驗證本文改進蟻群算法，將地圖擴大為50×50規模，蟻群算法的相關參數同實驗1；對于地圖預處理雙向蟻群算法，聚類簇群數k=15（不同顏色或不同形狀的聚類點屬于不同的聚類分區的樣本點）。傳統蟻群算法路徑、文獻[8]算法路徑、文獻[11]算法路徑和本文地圖預處理雙向蟻群算法路徑圖如圖9~12，最小距離曲線對比如圖13，具體參數如表2。

圖9 傳統蟻群算法路徑Fig.9 Path of traditional ant colony algorithm

圖13 最小距離曲線對比Fig.13 Comparison of minimum distance curves

圖11 文獻[11]算法路徑Fig.11 Algorithm path of literature[11]

圖12 本文地圖預處理雙向蟻群算法路徑Fig.12 Path of bidirectional ant colony algorithm for map preprocessing in this paper

圖9 中，在復雜的地圖環境中，傳統蟻群算法機器人尋優方向出現過較大偏差，造成路徑冗余，拐點較多，機器人分別在C、D點陷入了U型障礙物，路徑曲線波動明顯，如圖13虛線圓所示區域，由表2可知，機器人移動時間為139.825 s。本文地圖預處理雙向蟻群算法機器人移動時間為49.326 s，移動時間相較于單向蟻群算法減少了64.7%，較于文獻[8]改進蟻群算法減少了45.1%，較于文獻[11]雙向蟻群算法減少了17.5%；本文算法收斂代數相較于傳統蟻群算法減少了60.4%，相較于文獻[8]減少了47.2%，相較于文獻[11]減少了26.9%；拐點數相較于傳統蟻群算法減少了57.9%，較于文獻[8]改進蟻群算法減少了50.0%，相較于文獻[11]減少了30.0%。綜上所述，本文基于雙向搜索的改進蟻群算法機器人移動時間大幅減少，路徑更平滑，搜索效率更高。

表2 50×50實驗仿真結果對比Table 2 Comparison of 50×50 experimental simulation results

6 總結

本文針對傳統蟻群算法單向搜索在復雜地圖環境中路徑規劃搜索效率低、易陷入局部最優、收斂速度慢等問題，設計了一種基于雙向搜索的改進蟻群路徑規劃算法。將地圖預處理，量化地圖復雜度，改進蟻群算法，使機器人更大概率選擇復雜度小的區域尋優，減少拐點數量；設定雙向搜索策略并行搜索，顯著減小了機器人的移動時間，綜合考慮初始點和終點的位置，提高螞蟻的搜索方向精度，減少盲目搜索；改進信息素揮發系數，使其服從正態分布，增加蟻群算法靈活性；最后，為了解決U型障礙物的死鎖問題，提出死鎖判斷系數，增加有效螞蟻數量，提高算法搜索效率。

實驗結果表明，本文基于雙向搜索的改進蟻群路徑規劃算法相較于傳統蟻群算法機器人路徑規劃時間顯著減少、拐點更少、路徑更短，綜合性能更優。