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

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

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

0 引言

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

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

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

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

1 環(huán)境建模及運動描述

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

圖1 某公司的半導體加熱管道生產(chǎn)車間

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

(1)

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

圖2 柵格法環(huán)境模型圖

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

圖3 AGV運動方向 圖4 AGV防撞設(shè)定

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

(2)

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

2 改進蟻群算法

2.1 信息素初始化

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

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

(3)

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

2.2 狀態(tài)轉(zhuǎn)移公式

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

(4)

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

(5)

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

圖5 傳統(tǒng)蟻群算法規(guī)劃路線圖

(6)

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

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

(7)

(8)

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

2.3 自適應步長

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

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

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

2.4 雙種群蟻群算法

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

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

圖8 雙種群并行結(jié)構(gòu)

在雙種群蟻群算法中，種群間通過信息素交流來相互影響，不恰當?shù)男畔⑺亟涣鞑呗詴е聝煞N群都迅速陷入局部最優(yōu)。因此建立基于種群間最優(yōu)路徑相似度的自適應信息素交流機制，提出種間競爭策略和種間合作策略，根據(jù)兩種群最優(yōu)路徑之間的相似度選擇合適的信息素交流策略。相似度通過式(9)進行判斷。

(9)

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

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

(10)

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

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

(11)

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

2.5 信息素更新

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

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

(12)

(13)

(14)

Pw_p=PW-(PW∩Pb)

(15)

(16)

(17)

(18)

2.6 解決死鎖問題

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

圖9 死鎖解決

3 算法流程

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

圖10 雙種群算法路徑規(guī)劃流程圖

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

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

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

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

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

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

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

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

Step 9：若達到最大迭代次數(shù)，迭代終止，輸出最優(yōu)路徑并繪制收斂曲線，否則迭代次數(shù)加1，跳轉(zhuǎn)Step 4繼續(xù)搜索。

4 實驗驗證

4.1 仿真實驗

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

表1 算法參數(shù)表

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

表2 20*20柵格地圖仿真實驗數(shù)據(jù)

表3 30*30柵格地圖仿真實驗數(shù)據(jù)

圖11 20*20地圖上3種算法的路徑規(guī)劃圖

圖12 30*30地圖上3種算法的路徑規(guī)劃圖

圖13 算法收斂圖

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

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

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

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

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

4.1.3 不同地圖對比實驗

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

圖14 不同地圖上的路徑規(guī)劃圖

4.1.4 真實環(huán)境中的AGV路徑規(guī)劃

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

圖15 AGV小車車間實驗

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

5 結(jié)束語

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