徐超毅,龔橋梁

(安徽理工大學(xué) 經(jīng)濟(jì)與管理學(xué)院,安徽 淮南 232001)

隨著機(jī)器人研發(fā)技術(shù)的發(fā)展和節(jié)能環(huán)保理念的推廣,移動機(jī)器人在物流倉儲環(huán)節(jié)的應(yīng)用迅速發(fā)展,機(jī)器人的路徑規(guī)劃問題成為物流應(yīng)用領(lǐng)域的熱點問題[1]。如果機(jī)器人能在最優(yōu)路徑上移動,將會大大縮減物流時間、降低運(yùn)送成本。

路徑規(guī)劃是指在有障礙物的環(huán)境中,搜尋一條從出發(fā)點到目的地?zé)o碰撞的最佳路線[2]。自動導(dǎo)引運(yùn)輸車(Automated Guided Vehicle,AGV)的路徑規(guī)劃一直是國內(nèi)外專家探索的熱門話題,學(xué)者們提出了多種有效的思路解決這個問題。AGV的路線規(guī)劃主要包含兩類方法:地圖信息表達(dá)方法和搜索策略方法[3]。地圖信息表達(dá)方法包括自由空間法、拓?fù)浞ê蜄鸥穹╗4];搜索策略方法包括A*算法[5]、dijkstra方法[5]、蟻群算法[7]以及粒子群算法[8]等。其中,蟻群算法被普遍看作是一個有效且穩(wěn)定的集群算法。該算法具有分布式運(yùn)算、易與其他方法融合以及正反饋等優(yōu)勢。但該算法存在收斂速度慢、路徑狀況差以及在復(fù)雜地圖上搜索效率不高等問題。眾多學(xué)者對這些問題進(jìn)行了研究[9]。文獻(xiàn)[10]提出將蟻群的主要參數(shù)設(shè)為微粒群的定位信息,并設(shè)置適應(yīng)值評估變量,以誘導(dǎo)微粒向評價指數(shù)更高的方位收斂,從而高效地運(yùn)行蟻群算法解決機(jī)器人路徑規(guī)劃難題。文獻(xiàn)[11]提出了采用D*算法的改進(jìn)啟發(fā)變量和子節(jié)點擴(kuò)展形式,將蟻群算法的評價函數(shù)用于運(yùn)算,并利用柵格法構(gòu)建地圖模型,以便在各種難度的柵格環(huán)境上選擇多個目標(biāo)開展仿真對比試驗。文獻(xiàn)[12]修改了蟻群算法的節(jié)點轉(zhuǎn)移概率公式和信息素更新方式,將A*算法快速尋解特性與傳統(tǒng)蟻群算法進(jìn)行融合,使AGV尋優(yōu)效率得到顯著優(yōu)化。由此可見,學(xué)者們一般將蟻群算法與其他算法融合以克服其收斂慢、路徑遠(yuǎn)的缺點。但是蟻群在其他算法的規(guī)劃路線上進(jìn)行擴(kuò)散的隨機(jī)性被削弱,導(dǎo)致容易陷入局部最優(yōu),而降低獲得整體最優(yōu)路徑的可能性。

本文對傳統(tǒng)蟻群算法進(jìn)行了改進(jìn)。在A*單向搜索[13]的基礎(chǔ)上,在柵格環(huán)境中運(yùn)用A*頭尾雙向搜索得出初始路徑,并進(jìn)一步提高算法的收斂速度。文獻(xiàn)[14]采用了在較優(yōu)路徑周邊區(qū)域內(nèi)線性遞減改變信息素的方式,而本文在優(yōu)勢區(qū)域內(nèi)以整體優(yōu)化信息素濃度的方式給予蟻群在區(qū)域內(nèi)更高的搜索自由度,以提高蟻群尋優(yōu)的隨機(jī)性。

1 柵格法環(huán)境建模

環(huán)境建模是解決機(jī)器人路徑規(guī)劃問題的關(guān)鍵,它將實際工作環(huán)境映射到一個虛擬環(huán)境中,以便更好地理解和預(yù)測機(jī)器人的行為。柵格法因其簡單高效、可行性強(qiáng)以及可靠性高,已被廣泛應(yīng)用于解決機(jī)器人路徑規(guī)劃問題[15]。

柵格法是一種用于描述環(huán)境信息的有效方法,它將障礙物所在區(qū)域標(biāo)示為1、可自由通過地區(qū)標(biāo)示為0,以便在創(chuàng)建的環(huán)境模型中找到最佳的可通過途徑。因此,柵格的合理設(shè)定對于路徑規(guī)劃至關(guān)重要。

創(chuàng)建柵格地圖。將地圖左下角首個柵格作為坐標(biāo)原點。每個柵格的坐標(biāo)為(x,y)。將左下角的首個柵格的坐標(biāo)記為(0,0)。任意柵格的編號記為N。從左下角的柵格開始編號,編號從0開始。坐標(biāo)和編號的轉(zhuǎn)換函數(shù)為

x=int(N/Gsize)+1

(1)

y=N%Gsize+1

(2)

式中:Gsize為每行柵格的個數(shù);int為取整函數(shù);%為取余數(shù)。

為真實還原物流AGV在倉儲物流的工作環(huán)境以及提高算法的仿真程度和實用性,本文采用柵格法構(gòu)建一般環(huán)境和復(fù)雜型環(huán)境兩種地圖(見圖1)。

AGV行進(jìn)時一定要占據(jù)柵格。在真實環(huán)境下,AGV會有多個方向可以考慮,為使行進(jìn)方向簡單化,在仿真環(huán)境中將AGV設(shè)置為以各柵格中心點為準(zhǔn),每一步前進(jìn)可供選擇的方向有8種,分別為右前、右后、左前、左后等4個斜方向以及前后左右4個直行方向(見圖2)。

圖2 AGV的行進(jìn)方向

2 傳統(tǒng)蟻群算法基本理論

蟻群算法是以大自然界螞蟻群體從巢穴到食物之間的路徑搜索為基礎(chǔ)的群體智能啟發(fā)式算法。它可以使用正反饋,幫螞蟻尋找最短的路徑[15]。通過觀察各條路線上經(jīng)過的螞蟻數(shù)量,推斷出各條路線的信息因子含量,幫助螞蟻找到最短的路線,從而實現(xiàn)最佳的覓食效率。

2.1 轉(zhuǎn)移概率選擇

傳統(tǒng)的蟻群算法是根據(jù)信息素濃度和距離確認(rèn)螞蟻的位置,其中t時刻第k只螞蟻從當(dāng)前位置到下一個位置的轉(zhuǎn)移概率為

(3)

式中:τij為當(dāng)前節(jié)點與可行節(jié)點路徑的信息素濃度;ηij為距離啟發(fā)因素,為當(dāng)前節(jié)點到可選節(jié)點歐式距離的倒數(shù);allowedk為下一可行節(jié)點的集合;α、β為權(quán)重因子,用于控制信息素濃度和距離啟發(fā)因素在轉(zhuǎn)移概率中的重要程度。

2.2 信息素更新

螞蟻在完成一次路線搜尋后,將信息素留在這條路線上,先前的部分信息素會蒸發(fā)掉,下次搜尋開始時信息素的濃度計算式為

(4)

(5)

3 改進(jìn)的蟻群算法

3.1 雙向搜索的A* 算法

A*算法是一種具有重要應(yīng)用價值的啟發(fā)式搜索算法,它可以有效地幫助AGV避開障礙物并實現(xiàn)路徑規(guī)劃。A*算法的一般評價函數(shù)表達(dá)式為

f(n)=g(n)+h(n)

(6)

式中:f(n)為起點到終點的總代價;g(n)為f(n)的前一部分代價,即起點到當(dāng)前所在點的代價;h(n)為f(n)的后一部分代價,即當(dāng)前所在點到終點的代價。

傳統(tǒng)A*算法的單向搜索在搜索過程中存在著路徑質(zhì)量差和效率低的問題,通過改進(jìn)使蟻群算法能夠得到更優(yōu)的預(yù)搜索路徑。相比傳統(tǒng)A*算法,首尾搜索的A*算法新增了OPEN表單和CLOSED表單,依次標(biāo)記為SOPEN表、EOPEN表和SCLOSED表、ECLOSED表。每一個子節(jié)點都是以當(dāng)前所在柵格為起點,搜索周邊8個柵格,尋找f(n)函數(shù)值極小的拓展節(jié)點,置于CLOSED表中。在找到h(n)函數(shù)值為0的拓展節(jié)點后,A*算法將停止運(yùn)行。先行使用A*算法進(jìn)行雙向搜尋,會使得改進(jìn)的蟻群算法更加高效,能更快地找到最優(yōu)解。

3.2 蟻群算法信息素分布策略改進(jìn)

在傳統(tǒng)的蟻群搜索中,信息素的初始值是平均配置的,這將使螞蟻在初期陷于盲目搜尋的困境,大大降低搜索效率。為了解決這個問題,學(xué)者們提供了諸多信息素優(yōu)化策略,例如李鵬等[13]提出標(biāo)記A*算法搜索的初始通道,然后在路線周圍構(gòu)筑優(yōu)勢區(qū)域,以此優(yōu)化信息素。擴(kuò)張柵格的個數(shù)與柵格圖的尺寸、障礙物的比例有關(guān),具體計算式為

(6)

(7)

式中:SL為擴(kuò)張柵格的數(shù)量;round為取整運(yùn)算;B為障礙柵格;D為地圖斜長;H為柵格總數(shù);X、Y分別為地圖的長和寬。

文獻(xiàn)[14]以線性遞減的方式改變區(qū)域信息素濃度,增強(qiáng)了下一階段較優(yōu)解區(qū)域內(nèi)蟻群搜索的傾向性。這一設(shè)計雖然提高了蟻群的收斂速度,但蟻群容易受到A*算法搜索的初始路徑影響,無法完全發(fā)揮自身全局搜索的尋優(yōu)優(yōu)越性。本文將整個柵格環(huán)境區(qū)分為雙向A*算法搜索得到的優(yōu)勢區(qū)域和其他區(qū)域,對優(yōu)勢區(qū)域整體提高設(shè)定系數(shù)的信息素濃度。這使得改進(jìn)的蟻群算法既吸收了A*算法搜索的快捷性,又能發(fā)揮蟻群隨機(jī)搜索、全局搜索的特點。采用這種方法可以有效避免算法在初始搜索階段出現(xiàn)盲目性,同時也不會完全依賴于初始路徑的指引。A*算法優(yōu)化蟻群信息素分布并形成信息素較稠密區(qū)域的機(jī)理見圖3。

圖3 擴(kuò)展柵格

信息素濃度優(yōu)化方式可以表示為

(8)

式中:μ為增強(qiáng)系數(shù);τ0為初始信息素濃度;Z為初始信息素增強(qiáng)區(qū)域。

4 改進(jìn)的蟻群算法流程

(1)在柵格地圖模型中運(yùn)行A*算法,分別從起始點和終點開始尋優(yōu),以確定較優(yōu)解,并調(diào)整初始信息素濃度。

(2)將A*算法和蟻群算法的信息素進(jìn)行有效融合。

(3)蟻群采用輪盤賭的方法決定前往的下個節(jié)點。

(4)當(dāng)蟻群搜尋結(jié)束后,將其生成的信息素與原有的信息素進(jìn)行融合,以刷新全局的信息素,從而提升搜索效率。

(5)開始新一輪的搜索,使蟻群重新回到起始點,并在達(dá)到預(yù)定的迭代次數(shù)后,結(jié)束搜索,找出最優(yōu)的路徑。

5 算法仿真

將傳統(tǒng)蟻群算法、A*算法、改進(jìn)蟻群算法分別置于20 m×20 m的一般型和復(fù)雜型兩種柵格環(huán)境下運(yùn)行。重點比較蟻群算法改進(jìn)前后的尋優(yōu)表現(xiàn)。

5.1 算法參數(shù)設(shè)置

蟻群算法的性能主要受信息啟發(fā)因子和信息素?fù)]發(fā)因子的影響[16]。設(shè)定機(jī)器人初始坐標(biāo)為(0.5,19.5),終點坐標(biāo)為(19.5,0.5)。依據(jù)文獻(xiàn)[17]對主要參數(shù)進(jìn)行了優(yōu)化:螞蟻數(shù)量為100,最大迭代次數(shù)為100,μ為0.001,ρ為0.5,α、β均為2。

5.2 仿真環(huán)境1

在一般柵格環(huán)境中分別驗證3種算法以驗證改進(jìn)蟻群算法的優(yōu)越性,3種算法求解的路徑如圖4和表1所示。

表1 在仿真環(huán)境1中的各算法結(jié)果對比

表2 仿真環(huán)境2下的運(yùn)行結(jié)果

a 傳統(tǒng)蟻群算法

通過改進(jìn)蟻群算法能夠改善蟻群隨機(jī)搜索導(dǎo)致的盲目性大、路徑拐角過多等缺點,也能夠克服A*算法容易進(jìn)入“凹角”型障礙的不足,得出的最優(yōu)路徑明顯減少了拐彎和迂回次數(shù),尋優(yōu)軌跡較傳統(tǒng)蟻群算法和A*算法路線更為平滑。改進(jìn)蟻群算法得出的尋優(yōu)路徑在距離長短方面明顯優(yōu)于傳統(tǒng)蟻群算法,路徑長度減少了7.622 m;在蟻群搜索前加入了A*的雙向搜索,運(yùn)行時長25.103 s,優(yōu)于傳統(tǒng)蟻群算法的25.742 s。通過對圖表數(shù)據(jù)的分析可知,所提出的改進(jìn)蟻群算法在多個方面均優(yōu)于傳統(tǒng)的蟻群算法。

5.3 仿真環(huán)境2

為了更好地驗證改進(jìn)蟻群算法的可行性和效果,在20 m×20 m的柵格環(huán)境中增加了形狀不規(guī)則障礙的數(shù)量,并將障礙物設(shè)置成小塊、密集的布局,以增加路徑選擇的復(fù)雜性和難度。同時為考驗蟻群搜索和A*算法在面臨陷阱時的回退能力,在柵格環(huán)境中引入了H型和U型障礙。仿真環(huán)境2下3種算法的運(yùn)行軌跡和結(jié)果如圖5和表1所示。

a 傳統(tǒng)蟻群算法

由圖5可以看出,傳統(tǒng)蟻群算法在面臨復(fù)雜柵格環(huán)境時,盲目性較強(qiáng),多次出現(xiàn)回退、轉(zhuǎn)彎現(xiàn)象;而A*算法雖然得出的路徑較為平整,但囿于局部障礙,無法得到整體最優(yōu)解。改進(jìn)蟻群算法與傳統(tǒng)蟻群算法相比,其給予雙向搜索得出的路徑區(qū)域更高信息素的特點,為蟻群提供了范圍更小的較優(yōu)解區(qū)域,規(guī)避了H型和U型障礙,減少了回退和轉(zhuǎn)彎次數(shù),顯著改善了尋優(yōu)能力。改進(jìn)后的算法迭代次數(shù)由24次減至7次,效率顯著提高。相較于傳統(tǒng)A*算法只能單向?qū)?yōu)的不足,改進(jìn)后的蟻群算法首尾搜索方式在復(fù)雜環(huán)境中更能克服單向A*算法易受單個障礙影響路徑走向而無法得到最短尋優(yōu)路徑的缺點,結(jié)果表現(xiàn)為A*算法最短路徑長度為30.385 m,大于改進(jìn)算法的29.213 m,同時尋優(yōu)路線轉(zhuǎn)彎次數(shù)為12次,多于改進(jìn)算法的9次。

6 結(jié)論

(1)改進(jìn)蟻群算法結(jié)合了A*算法快速尋優(yōu)和蟻群算法隨機(jī)尋優(yōu)的特點。利用A*算法進(jìn)行首尾雙向搜尋,給予柵格環(huán)境中雙向A*尋優(yōu)區(qū)域信息素,在較優(yōu)解路徑周圍區(qū)域按設(shè)定系數(shù)增加信息素濃度,提高了蟻群算法的收斂速度,增強(qiáng)了蟻群整體的搜索能力。

(2)對3種算法進(jìn)行了在不同環(huán)境下的仿真試驗。與傳統(tǒng)的蟻群算法和A*算法相比,改進(jìn)蟻群算法具有更強(qiáng)的路徑尋優(yōu)能力,速度更快,路徑轉(zhuǎn)彎次數(shù)少,可為提高物流機(jī)器人的工作效率提供一定參考。

(3)改進(jìn)蟻群算法雖然在路徑距離、路線平滑程度上優(yōu)于傳統(tǒng)蟻群算法和A*算法,但仍存在行進(jìn)路線與障礙物產(chǎn)生接觸的問題。下一步可考慮提升柵格環(huán)境內(nèi)機(jī)器人尋優(yōu)的仿真程度,提高算法的應(yīng)用價值。