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

張子然，黃衛(wèi)華，2，3，陳 陽，章 政，2，3，李梓遠

1.武漢科技大學(xué) 機器人與智能系統(tǒng)研究院，武漢430081

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

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

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

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

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

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

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

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

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

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

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

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

樣本圓密集度定義如下：

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

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

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

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

設(shè)Ne為分區(qū)Ye中的樣本點的數(shù)量，更新第e個分區(qū)的聚類中心點位置ce為：

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

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

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

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

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

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

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

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

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

2.1 雙向搜索策略的設(shè)計

設(shè)兩組不同的蟻群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

在路徑搜索過程中，設(shè)兩只螞蟻所經(jīng)過節(jié)點的交集為：

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

2.2 狀態(tài)轉(zhuǎn)移概率函數(shù)的設(shè)計

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

設(shè)螞蟻n在t時刻從節(jié)點u轉(zhuǎn)移到節(jié)點v的概率為：

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

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

2.3 啟發(fā)函數(shù)的設(shè)計

傳統(tǒng)蟻群算法的啟發(fā)函數(shù)沒有考慮到初始點與目標點的方向問題，并且當環(huán)境地圖中相鄰里兩節(jié)點的距離較短時，且容易造成蟻群尋優(yōu)方向的偏差。

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

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

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

2.4 自適應(yīng)信息素更新函數(shù)的設(shè)計

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

自適應(yīng)信息素揮發(fā)因子定義為：

其中，ρ0為初始信息素揮發(fā)系數(shù)，Z為當前迭代次數(shù)，ω為設(shè)定的迭代次數(shù)。

在初始階段對揮發(fā)系數(shù)取較大值，增加信息素的正反饋，當?shù)螖?shù)達到設(shè)定值ω時，ρ(Z)逐漸減小，負反饋減弱，搜索路徑上的信息素增加，信息素濃度對螞蟻的導(dǎo)向作用變強。

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

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

3 U型障礙物防死鎖處理

傳統(tǒng)蟻群算法在遇到復(fù)雜U型障礙物往往會陷入局部最優(yōu)，如圖2。當螞蟻經(jīng)過“父→子4”路徑時，子4的可選下一節(jié)點個數(shù)為0，此時螞蟻陷入死鎖。

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

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

4 算法步驟

綜合上述內(nèi)容，本文設(shè)計的基于雙向搜索的改進蟻群算法結(jié)構(gòu)如圖3，將其用于移動機器人路徑規(guī)劃中，具體流程如下：

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

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

步驟2地圖預(yù)處理。采用改進的K-means算法實現(xiàn)地圖的預(yù)處理。

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

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

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

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

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

5 仿真實驗與結(jié)果分析

實驗1 20×20的柵格地圖

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

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

圖4 傳統(tǒng)蟻群算法路徑Fig.4 Path of traditional ant colony algorithm

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

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

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

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

實驗2 50×50的柵格地圖

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

圖9 傳統(tǒng)蟻群算法路徑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 本文地圖預(yù)處理雙向蟻群算法路徑Fig.12 Path of bidirectional ant colony algorithm for map preprocessing in this paper

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

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

6 總結(jié)

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

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