基于雙種群蟻群算法的AGV路徑規劃研究

劉 睿，楊程偉，高長水，李曉東

(1.南京航空航天大學 機電學院，南京 210016；2.江陰市輝龍電熱電器有限公司，江蘇 無錫 214401)

0 引言

隨著電商、新能源等新興產業的崛起，大幅帶動了倉儲智能化的全面發展，為智能工廠的研發和應用注入了新的活力，AGV的路徑規劃是智能工廠領域的一個重要課題，是倉儲應用的關鍵環節之一。在二維地圖的尺度上，有大量算法已被證明可以用于路徑規劃，包括A*算法[1]、人工神經網絡[2]、遺傳算法[3]、麻雀搜索算法[4]、蟻群算法等。

蟻群算法具備良好的尋優能力和較強的魯棒性，但也存在收斂慢，易陷入局部最優等缺陷，許多學者通過改進蟻群算法來提高算法的尋優能力。李開榮[5]提出了一種基于轉彎角度約束的改進蟻群算法，減少了路徑的轉彎次數。王雷[6]提出參數自適應改變，以提高收斂速度和全局搜索能力。Luo等人[7]引入差異化的初始信息素，加快算法收斂速度，并對死鎖路徑的最后兩步進行信息素懲罰，解決了死鎖問題。Jianhua Liu[8]將蟻群算法與人工勢場法結合起來，對搜索過程進行引導，有效提高了算法的收斂速度。李濤等人[9]提出了一種基于達爾文進化論的蟻群算法，提高了搜索效率并有效避免了死鎖問題，楊立煒[10]通過在地圖初始化階段封鎖U型陷阱的入口避免死鎖。白建龍[11]等人在蟻群算法中引入負反饋機制，充分利用失敗信息來指導螞蟻的尋路過程。楊海清[12]將蟻群算法應用到了水下無人機的路徑規劃領域。XianWei Wang[13]設計了基于改進優化蟻群算法的智能停車系統。

近年來，一些學者對蟻群算法的架構組成展開了研究[14]，提出多種群優化算法。游曉明等人[15-18]引入博弈論等機制用于種群間交流。馬飛宇[19]提出了具有自適應步長的異構雙種群蟻群算法，通過差異化蟻群的相互協作提高蟻群算法的收斂速度和尋優能力。Lee[20]結合遺傳算法，提出基于不同視野的異構蟻群算法。

結合以上改進策略，提出基于差異化步長的雙種群蟻群算法，并重新設計了啟發函數和信息素更新方法。為解決死鎖問題，提出將符合條件的單元格視為障礙物的“填充陷阱”策略。通過在柵格地圖上進行對比實驗驗證了改進策略的有效性，并通過ROS小車完成了在真實環境下的AGV自主導航任務，對算法的可行性進行了驗證。

1 環境建模及運動描述

常用的環境建模方法包括拓撲法、柵格法等，拓撲法是將地圖抽象為點和邊的集合，將地圖中的關鍵位置作為節點，將節點之間的路徑視為邊，適用于簡潔工作環境。而柵格法是將環境離散化為柵格，通過定義柵格是否可通行描述環境信息，進而對復雜作業環境進行較精確的描述。以某公司的半導體加熱管道生產車間為例，該車間工位緊湊，且不同區域位置關系不規律，如圖1所示，因此采用柵格法對地圖進行建模。

圖1 某公司的半導體加熱管道生產車間

網格單元通過二進制信息表示，以”0”表示可通行網格，以”1”表示障礙物網格。按從上到下、從左到右順序，依次標記柵格序號1，2，…，i，序號為i的柵格對應柵格坐標中心(x，y)的關系式如式(1)所示。

(1)

式中，mod表示求余運算，ceil表示向上取整運算，M表示柵格地圖橫軸最大值。圖2是一個20*20柵格地圖，其中黑色網格表示障礙物，白色柵格表示可通行區域，左上角柵格表示起點，右下角柵格表示終點。

圖2 柵格法環境模型圖

定義AGV自身占據一個柵格，步長為1個柵格，其運動方向共八個方向，如圖3所示。由于AGV沿45°方向運動時有可能碰撞相鄰的障礙物，規定垂直于運動方向的相鄰柵格均非障礙物時，才能斜向運動，即螞蟻從柵格5直接移動至柵格10的充分條件是柵格9和柵格6是可通行柵格，否則只能沿如圖4所示路線前進。

圖3 AGV運動方向 圖4 AGV防撞設定

由于AGV轉彎時有時間損耗，單純的路徑長度不足以評定路徑質量的好壞，因此以AGV在路徑上的行駛時間代替AGV行駛距離作為路徑優劣的評價函數，如式(2)所示。

(2)

其中：Ti是AGV沿第i只螞蟻所尋路徑行駛需要的時間，Li是第i只螞蟻所尋路徑的總長度，Ri是第i只螞蟻所尋路徑所轉過的總角度，v是AGV的行駛速度，ω是AGV的轉彎角速度，設AGV轉90°所需時間等于其水平或豎直通過一個柵格的時間，AGV轉45°所需的時間等于轉90°所需時間的一半。

2 改進蟻群算法

2.1 信息素初始化

傳統蟻群算法的信息素值在算法初始階段是相同的，導致螞蟻在迭代初期盲目搜索，在復雜環境中，這極大的增加了算法的搜索時間。因此提出一種基于節點位置關系和下一步可選擇方向的數目的初始化信息素方法，設置不均勻分布的初始信息素，減少螞蟻的盲目搜索，提高了算法早期的搜索速度，如式(3)所示：

τij(0)=Q×e((8-obs-1)-(dij+dsi+dje))

(3)

其中：Q是螞蟻一次尋路可釋放的總信息素濃度，obs是節點i周圍8個節點中的障礙物數量，(8-obs-1)則是螞蟻去除掉有障礙物的方向和來時經過的方向后下一步可供選擇的方向數，dsi是起點至當前節點的歐氏距離，dij是當前節點至下一節點的歐氏距離，dje是下一節點至終點的歐氏距離。

2.2 狀態轉移公式

蟻群算法采用如式(4)所示的狀態轉移公式計算候選節點被選中的概率，并通過輪盤賭算法選擇下一個節點。

(4)

其中：Pijk(t)是節點j被選擇的概率，[τij(t)]是節點i和節點j之間信息素濃度，α表示信息素啟發因子，β表示期望啟發因子，Rallow表示候選節點的集合，ηij(t)是節點i與節點j之間的啟發函數值，傳統蟻群算法的啟發函數如式(5)所示。

(5)

由式(5)可知啟發函數值與路徑段的距離成反比，然而柵格地圖中兩相鄰節點間的距離僅有1和兩種情況，啟發函數無法起到有效的導向作用，螞蟻會傾向于選擇距離為1的路徑，造成傳統蟻群算法搜索出的路徑90°拐角過多，如圖5所示。因此，引入候選節點的位置信息和AGV轉彎角度，加強啟發函數的引導能力，修改后的啟發函數如式(6)所示。

圖5 傳統蟻群算法規劃路線圖

(6)

其中：c是常系數，γ是螞蟻選擇下一節點需要轉的角度(rad)。

信息素啟發因子α和期望啟發因子β的大小會影響螞蟻尋找路徑的隨機性，α過大或過小，都有可能陷入局部最優。β取值越大，螞蟻越趨向于選擇離目標點更近的局部最短路徑。所以在算法初始階段，先對α、β設置最小值，在算法初期增加全局搜索能力，并隨迭代次數逐漸增大，α、β按式(7)、(8)從小到大更新，逐步提高算法的收斂性能。

(7)

(8)

其中：αmin、βmin分別為α、β的初始值，αmax、βmax是α、β的最大值，Nc為當前迭代次數，Nmax為最大迭代次數。

2.3 自適應步長

螞蟻的視野指螞蟻下一步搜索可選擇的節點的集合，傳統蟻群算法中螞蟻的步長為1，視野僅局限于自身周圍的八個節點，如圖3所示，這種搜索方式造成算法收斂速度慢且易產生多余的拐點。擴大螞蟻視野，使螞蟻獲得自適應步長，步長沿周圍八個方向進行擴張，直到遭遇障礙物或抵達地圖邊界，而在沿斜向擴大步長時，還需考慮如圖4所示的防撞設定，圖6中透明陰影區域是螞蟻獲得自適應步長后的視野。

圖6 自適應步長 圖7 步長的影響

自適應步長策略可以減少路徑中的冗余拐點，加快算法收斂速度，在如圖7所示的地圖中，需要規劃一條從左上角至右下角的路徑，傳統蟻群算法從起點至終點的路徑可能是路徑①，而具備自適應步長的螞蟻，可以在起點位置將終點位置納入自身步長范圍，從而選擇路徑②。

2.4 雙種群蟻群算法

在單一算法中，提高收斂速度往往會降低搜索的多樣性，反之亦然。由于蟻群算法本身具有良好的并行性，可以建立雙種群蟻群算法，在傳統蟻群算法的基礎上引入了種群間的交流學習機制，讓兩個種群之間可以達到很好的優勢互補，使算法性能得到了進一步提升，雙種群蟻群算法研究的核心在于解的交流策略和信息素更新策略。

以2.1節至2.3節所闡述的改進策略為基礎，建立以單步長改進蟻群算法為種群A，以多步長改進蟻群算法為種群B的雙種群蟻群算法。其中種群A的搜索多樣性較好，而種群B的收斂速度較快，使得算法可以在擴大搜索范圍的同時兼顧收斂速度，種群結構如圖8所示。

圖8 雙種群并行結構

在雙種群蟻群算法中，種群間通過信息素交流來相互影響，不恰當的信息素交流策略會導致兩種群都迅速陷入局部最優。因此建立基于種群間最優路徑相似度的自適應信息素交流機制，提出種間競爭策略和種間合作策略，根據兩種群最優路徑之間的相似度選擇合適的信息素交流策略。相似度通過式(9)進行判斷。

(9)

其中：η是兩種群的相似度，∑Pij是兩種群最優路徑的相同路徑段數目，即兩種群的最優路徑都包含路徑段ij，則Pij為1，否則為0，Pse是兩條路徑所占據的路徑段數目總和。

當兩種群相似度較低時，需要加快算法收斂，進行種間競爭策略。即比較兩種群各自的最優路徑，將其中的更優路徑替換另一種群的最優路徑，如式(10)所示。

(10)

其中：pathb是兩種群最優路徑中的更優路徑，pathA是種群A的最優路徑，pathB是種群B的最優路徑，TimeA是種群A最優路徑的綜合評定值，TimeB是種群B最優路徑的綜合評定值。

當兩種群相似度較高時，需要防止種群陷入局部最優，進行種間合作策略，對兩種群的信息素矩陣進行均化。將兩種群的信息素矩陣相加并取平均值獲得新的信息素矩陣，使用新的信息素矩陣替換原信息素矩陣，然后再進行迭代，如式(11)所示。

(11)

其中：Pheromonenew是進行平均后的新信息素矩陣，Pheromonei是兩種群的原信息素矩陣。

2.5 信息素更新

傳統信息素更新方法如式(12)和式(13)所示，每輪迭代后會更新螞蟻找到的所有路徑上的信息素，導致信息素積累過快，算法容易陷入局部最優。因此雙種群蟻群算法在每輪迭代結束后只對各自的最優、最差路徑進行獎懲，但算法收斂后最優、最差路徑完全重疊，獎懲信息素濃度完全一致，路徑上的信息素只揮發而不累積，導致螞蟻迷失方向。

針對上述問題，綜合考慮兩種群之間的信息素交流，對兩種群最優路徑的重疊部分Pboth進行額外獎勵，在懲罰最差路徑時，定義路徑Pwb為最差路徑Pw和最優路徑Pb的重疊路徑，提出只懲罰Pw與Pwb的差集Pw_p，如式(14)～(17)所示。為了防止算法陷入局部最優，設置路徑上的信息素濃度上下限，使信息素濃度始終在范圍內。

(12)

(13)

(14)

Pw_p=PW-(PW∩Pb)

(15)

(16)

(17)

(18)

2.6 解決死鎖問題

當環境復雜時，螞蟻可能遭遇U型陷阱，由于在蟻群算法中螞蟻不會重復選擇已選擇的節點，此時螞蟻會陷入無路可走的狀態，即發生了死鎖，如圖9(a)所示。針對這一問題，采取“填充陷阱”的策略，排除螞蟻再次陷入同一陷阱的可能性。首先對死鎖螞蟻周圍的節點進行判斷，若該螞蟻周圍的八個節點僅有一個屬于當前螞蟻行走過的路徑，則判定螞蟻此時所在的節點是U型陷阱的底部，將該節點視為“障礙物”，即在地圖矩陣中將該節點置1。隨著迭代的進行，每次死鎖都會在U型陷阱底部填充一個“障礙物”，U型陷阱會逐漸消失，不再引起死鎖問題，填充后的路線圖如圖9(b)所示。

圖9 死鎖解決

3 算法流程

實現雙種群蟻群算法的流程如圖10所示，實現步驟如下。

圖10 雙種群算法路徑規劃流程圖

Step 1：對地圖進行柵格法建模。

Step 2：初始化參數，如螞蟻數量m、迭代次數、信息素啟發因子α、期望啟發因子β等。

Step 3：對兩種群的信息素矩陣按式(3)進行初始化。

Step 4：計算本輪迭代的信息素啟發因子α和期望啟發因子β，判斷本輪兩種群螞蟻數量是否達到最大值，若是則跳轉至Step 8，否則，兩種群螞蟻數量各加1。

Step 5：種群A螞蟻搜索周圍8個柵格，并將符合條件的柵格加入候選列表；種群B螞蟻按照圖6搜索柵格，將符合條件的柵格加入候選列表。

Step 6：按照式(4)計算螞蟻轉移概率，利用輪盤賭確認轉移柵格。

Step 7：判斷螞蟻是否抵達終點或死鎖，若抵達終點，則返回Step 4，若死鎖，則按照2.6節所述方法“填充”柵格，然后返回Step 4，否則返回Step 5。

Step 8：本輪所有螞蟻完成一次搜索后，對所有有效路徑進行排序，按照式(9)～(11)進行信息素交流后，按照式(14)～(18)更新兩種群的信息素矩陣，更新完成后將兩種群初始化。

Step 9：若達到最大迭代次數，迭代終止，輸出最優路徑并繪制收斂曲線，否則迭代次數加1，跳轉Step 4繼續搜索。

4 實驗驗證

4.1 仿真實驗

為驗證雙種群蟻群算法的有效性，采用QT圖形化工具作為開發環境，使用C++語言開發一種AGV路徑規劃仿真平臺，PC配置如下：處理器為Intel(R)Core(TM)i7-10750H，主頻為2.60 GHz，內存為16 GB。實驗設置帶有U型陷阱的20*20柵格地圖和30*30柵格地圖，對比雙種群蟻群算法、單種群蟻群算法以及文獻[19]提出的基于異構雙種群全局視野的蟻群算法。其中單種群蟻群算法由2.1、2.2、2.5、2.6節組成，其信息素更新方式采用式(12)和式(13)。算法參數如表1所示。

表1 算法參數表

圖11～圖13分別3種算法在20*20地圖和30*30地圖中的路徑規劃圖和迭代曲線圖，為避免偶然性對實驗結果的影響，每種算法各進行20次仿真實驗，對實驗數據取平均值，對比4種算法的綜合評價值、路徑長度、90°轉角數目和45°轉角數目，如表2和表3所示。

表2 20*20柵格地圖仿真實驗數據

表3 30*30柵格地圖仿真實驗數據

圖11 20*20地圖上3種算法的路徑規劃圖

圖12 30*30地圖上3種算法的路徑規劃圖

圖13 算法收斂圖

4.1.1 單種群蟻群算法與雙種群蟻群算法對比

對比圖11(a)、(c)和圖12(a)、(c)，可以看出雙種群蟻群算法規劃的路線圖比單種群蟻群算法規劃出的路徑更平滑，冗余拐點少。根據圖13(a)及圖13(b)可以看出雙種群蟻群算法收斂速度更快，路徑質量更高。對比表2和表3的數據，在20*20柵格地圖中，雙種群蟻群算法搜索的路徑長度比單種群蟻群算法減少了2.8%。在綜合指標方面，雙種群蟻群算法比單種群蟻群算法減少了1.7%。相比于單種群蟻群算法，雙種群蟻群算法減少了3.9%的拐角總數。而在30*30柵格地圖中，地圖復雜度更高，雙種群蟻群算法搜索的路徑長度比單種群蟻群算法減少了4.1%。在綜合指標方面，雙種群蟻群算法比單種群蟻群算法減少了3.4%。這是由于雙種群蟻群算法具有自適應步長，可有效減少AGV在兩點間的非必要拐彎，雙種群蟻群算法依靠種群A與種群B在迭代早期的競爭搜索和迭代后期的合作搜索獲得質量更高的解，雙種群策略加快了算法早期的收斂速度，擴大了搜索范圍，減少了路徑的冗余拐點。

4.1.2 雙種群蟻群算法與文獻[19]算法對比

從圖13可以看出文獻[19]算法收斂速度更快，但雙種群蟻群算法具有更強的突破局部最優的能力，其收斂曲線多次呈階梯型下降，展現了良好的突破局部最優的能力。文獻[19]將蟻群分為首領、中堅群體和追隨者，通過兩個種群分別進行深度搜索和廣度搜索來尋找路徑，并使用交叉算子融合種群最優解來進行種群間信息交流。而雙種群蟻群算法在搜索早期兩種群解的差異較大時，主要進行種間競爭策略，以此加快收斂速度，當算法逐漸收斂時，啟用種間合作策略，均化兩種群信息素矩陣，獲得更大的搜索多樣性，使得迭代曲線呈階梯下降，更好的逼近最優解。

對比兩者在不同尺寸柵格地圖中的實驗數據，在20*20柵格地圖中，雙種群蟻群算法搜索的路徑長度比文獻[19]算法減少了1.4%。對比兩者的綜合指標，雙種群蟻群算法比文獻[19]算法減少了1.2%。較之于文獻[19]算法，雙種群蟻群算法減少了2.5%的拐角總數。隨著地圖的進一步復雜化，在30*30柵格地圖中雙種群蟻群算法規劃的路徑長度比文獻[19]算法減少了4.0%。在綜合指標方面，雙種群蟻群算法比文獻[19]算法減少了3.2%，此外，雙種群蟻群算法的拐角總數比文獻[19]減少了2.3%。結果表明雙種群蟻群算法在路徑長度、AGV運行時間、轉彎次數3個方面均優于文獻[19]算法，說明雙種群蟻群算法通過差異化種群步長和自適應交流策略獲得了更優秀的尋優能力，且隨著環境的復雜化，算法性能之間的差距被進一步放大，雙種群蟻群算法依靠種群間信息素的相互交流兼顧了收斂速度和路徑質量，使其在復雜環境下依然有良好的收斂性及路徑質量。

4.1.3 不同地圖對比實驗

為驗證算法的通用性，分別使用文獻[5]、文獻[9]、文獻[10]、文獻[19]中柵格地圖進行路徑規劃，其中文獻[10]地圖為凹槽地圖，存在大量U型陷阱，文獻[19]地圖是回廊地圖，回廊地形空間狹小，容易陷入局部最優，4種地圖的規劃結果如圖14所示，雙種群蟻群算法在回廊地圖、凹槽地圖中都可以規劃出一條可行的較優路徑，且基于圖4所所示的防撞設定，雙種群蟻群算法規劃出的路徑更為安全。

圖14 不同地圖上的路徑規劃圖

4.1.4 真實環境中的AGV路徑規劃

為了保證理論的準確性，將雙種群蟻群算法應用于實際的工程環境中。以圖15所示為某公司半導體加熱管道生產車間為實驗對象，實現加熱管道的自動運輸，車間內環境復雜，工位之間較為緊湊，障礙物眾多。采用搭載樹莓派的ROS小車進行物料運輸，小車尺寸為410*407*153，搭載RPLIDAR A1型激光雷達、MPU6050慣性傳感器，通過PC端使用SSH遠程登錄的方式連接樹莓派實現小車的遠程控制，小車在樹莓派中安裝ubuntu18.04操作系統，并通過ROS系統實現建圖、定位和導航，小車的運動控制由STM32單片機分別控制4個麥克納姆輪實現，使用拓展平臺承載貨箱，載重30 kg，如圖15(a)所示。小車勻速行駛速度為0.4 m/s，最大角速度為0.5 rad/s。

圖15 AGV小車車間實驗

利用SLAM算法在ROS系統下構建環境地圖，使用雙種群蟻群算法進行全局路徑規劃，并利用Rviz組件在所得環境地圖上實時顯示導航結果，如圖15(b)所示，其中深色部分為加工工位和檢測區。當遭遇行人等動態障礙物時，小車以雙種群蟻群算法規劃出的全局路徑為引導使用動態窗口法(DWA，dynamic window approach)進行局部路徑規劃，繞過障礙物。如圖15(c)所示，圖中圓圈標出的位置為行人的路徑軌跡，小車在原路徑受阻后進行局部規劃，繞開行人后回歸到雙種群蟻群算法規劃的全局路徑。實驗結果表明該算法可以為小車規劃一條安全可靠的行駛路徑，實現物料的有效運輸，驗證了雙種群蟻群算法的可行性和準確性。

5 結束語

隨著智能化工廠等產業的飛速發展，倉儲物流相關技術成為研究熱點之一。雙種群蟻群算法針對斜向運動可能存在的AGV碰撞問題，提出嚴格的判定條件，有效保證了路徑的安全性；為了解決蟻群算法中常出現的死鎖問題，提出了將符合條件的死鎖單元格視為障礙物的“填充陷阱”策略；針對蟻群算法初期盲目搜索、容易陷入局部最優、原啟發函數引導作用弱等問題，采用了差異化初始信息素、修改啟發函數、使螞蟻獲得自適應步長、雙種群合作搜索以及對部分路徑進行信息素獎懲等策略。仿真實驗表明，雙種群蟻群算法可以有效減少路徑長度和冗余節點，該算法具有良好的收斂速度和突破局部最優的能力。為驗證該算法在實際工程環境下的可靠性，采用ROS小車在某車間環境下進行路徑規劃，驗證了算法的可行性。