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

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

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

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

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

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

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

1 基于改進(jìn)K-means算法的地圖處理

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

（1）初始聚類中心點(diǎn)的確定

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

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

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

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

樣本圓密集度定義如下：

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

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

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

其中，ce1、ce2分別為聚類中心點(diǎn)ce的橫坐標(biāo)和縱坐標(biāo)。

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

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

對(duì)于每個(gè)分區(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ù)計(jì)算式（4）、（5）、（6），直到式（6）保持不變，確定最終k個(gè)聚類分區(qū)，并按照式（7）、（8）分別輸出每個(gè)分區(qū)的擁擠度和疏通度。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 U型障礙物防死鎖處理

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

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

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

4 算法步驟

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

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

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

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

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

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

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

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

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

5 仿真實(shí)驗(yàn)與結(jié)果分析

實(shí)驗(yàn)1 20×20的柵格地圖

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

表1 20×20實(shí)驗(yàn)仿真結(jié)果對(duì)比Table 1 Comparison of 20×20 experimental simulation results

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

圖6 文獻(xiàn)[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 最小距離曲線對(duì)比Fig.8 Comparison of minimum distance curves

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

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

圖5 文獻(xiàn)[8]算法路徑Fig.5 Algorithm path of literature[8]

實(shí)驗(yàn)2 50×50的柵格地圖

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

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

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

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

表2 50×50實(shí)驗(yàn)仿真結(jié)果對(duì)比Table 2 Comparison of 50×50 experimental simulation results

6 總結(jié)

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

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