馮魯波

（四川大學(xué)計算機學(xué)院，成都610065）

0 引言

自動導(dǎo)引運輸車（automated guided vehicle，AGV）是一種智能運輸設(shè)備。AGV是目前無人工廠中的重要組成部分，在自動化流水線中可以取代人工完成搬運的任務(wù)。隨著制造業(yè)的發(fā)展和人工成本的提高，自動化流水線也需要相應(yīng)的AGV調(diào)度系統(tǒng)來滿足日益增長的任務(wù)需求?；谝陨媳尘?，對多AGV路徑規(guī)劃算法的優(yōu)化提出了更高要求[1]。

Rajotia等[2]提出了基于半動態(tài)時間窗約束的路徑規(guī)劃算法，經(jīng)過實際驗證后，證明該策略可以有效降低AGV運行過程中的擁堵概率，提高系統(tǒng)的運行效率。Fan[3]設(shè)計了一種基于動態(tài)串聯(lián)回路的AGV路徑設(shè)計方法，針對于降低AGV運行回路并建立數(shù)學(xué)模型，可以有效防止AGV沖突。梁承姬[4]提出了一種無沖突的AGV路徑規(guī)劃方法，通過計算每一段路徑上的時間窗實現(xiàn)沖突規(guī)避，從而給出多AGV的無沖突路徑規(guī)劃。泰應(yīng)鵬等[5]通過時間窗與A*算法的結(jié)合，提出了一種改進的A*算法，規(guī)劃好的路徑會通過計算時間窗進行避障。

本文通過設(shè)置擁堵閾值，改進傳統(tǒng)A*算法的啟發(fā)函數(shù)；并減少轉(zhuǎn)彎次數(shù)和約束轉(zhuǎn)向角度，以減少運行時間；設(shè)計基于時間窗的規(guī)避算法以解決沖突問題，分析多AGV的沖突問題以及常見的沖突類型，預(yù)測和規(guī)避可能發(fā)生的沖突，最終獲得全局最優(yōu)路徑。

1 靜態(tài)路徑規(guī)劃

1.1 傳統(tǒng)A*算法

A*算法是一種啟發(fā)式路徑規(guī)劃算法，通過建立合適的啟發(fā)函數(shù)，對周圍的環(huán)境進行求解，獲得啟發(fā)信息，利用這些信息選擇最優(yōu)的目標(biāo)，從而搜索到最優(yōu)路徑[6]。這種啟發(fā)式求解不需要遍歷整個地圖，因此時間復(fù)雜度低，廣泛應(yīng)用于游戲地圖尋路以及AGV路徑規(guī)劃領(lǐng)域[7]。

其中g(shù)(x)表示起點到當(dāng)前節(jié)點x的最短路徑成本，h(x)表示當(dāng)前節(jié)點x到終點最短路徑成本的預(yù)估值。

傳統(tǒng)A*算法流程如圖1所示。

1.2 改進A*算法

針對工廠環(huán)境特點和AGV的運行特征，A*算法需要滿足如下約束條件：

（1）路徑規(guī)劃中避免過多轉(zhuǎn)向。

（2）避開車流量較大的節(jié)點和路段，盡量避免與其他AGV發(fā)生沖突。

約束（1）是為了降低時間成本，AGV轉(zhuǎn)向時需要經(jīng)歷減速、轉(zhuǎn)向、加速的過程，會浪費一定時間；約束（2）可以避免部分AGV采用同一部分路徑導(dǎo)致路段擁擠，通過調(diào)控路徑的交通流量，可以降低多AGV沖突的可能性。

圖1 A*算法流程

為了實現(xiàn)上述目標(biāo)，對A*算法做出如下改進：

（1）為了避免轉(zhuǎn)向過多，需要確定路徑之間的角度關(guān)系，盡量減少AGV路徑的轉(zhuǎn)向次數(shù)。路徑之間的角度計算：

式中：θ為兩路徑之間的夾角，x1、y1為前一段路徑的起點坐標(biāo)，x2、y2為前一段路徑的終點坐標(biāo)，后一段路徑的起點坐標(biāo)，x3、y3為后一段路徑的終點坐標(biāo)。

cosθ有以下3種情況：①cosθ>0方向基本相同，夾角在0°到90°之間；②cosθ=0正交，相互垂直；③cosθ<0方向基本相反，夾角在90°到180°之間。

在確定路徑之間夾角之后，為了避免AGV選擇轉(zhuǎn)角過大的路徑，修改啟發(fā)函數(shù)h(x)，增加啟發(fā)權(quán)重1-cosθ，轉(zhuǎn)角小的路徑會被優(yōu)先選擇。

（2）對于避免擁堵和沖突規(guī)避，引入路徑的擁堵系數(shù)ω和時間窗算法，時間窗會在第2.3小節(jié)詳細說明。為了對路徑的擁堵情況進行定量監(jiān)控，同時避免算法時間復(fù)雜度過高，計算每條路徑在接下來要經(jīng)過的AGV總數(shù)，在啟發(fā)函數(shù)中引入擁堵系數(shù)來表示路徑的擁堵情況，實現(xiàn)AGV對較擁堵路段的規(guī)避，擁堵系數(shù)計算如所示。

通過式（2）可以求出路徑ab的擁堵系數(shù)

式中：wab為路徑ab段的擁堵系數(shù)，lab為路徑ab段的長度，nab為該時間段內(nèi)通過路徑ab的AGV總數(shù)，k為擁堵權(quán)重系數(shù)，路徑ab的距離權(quán)重dab。

當(dāng)路徑ab沒有AGV通過時，nab=0，則路段的擁堵系數(shù)wab=0，對啟發(fā)函數(shù)沒有任何影響；有多輛AGV通過時，擁堵系數(shù)隨AGV數(shù)量增加，距離權(quán)重dab相應(yīng)增加，通過需要的時間越長，這條路徑被選擇的概率會更小。

2 基于時間窗的沖突避免策略

2.1 時間窗模型

時間窗是用來記錄地圖中所有AGV的運行狀態(tài)的模型，時間窗的橫坐標(biāo)表示時間段，縱坐標(biāo)表示資源，即節(jié)點和路徑，通過橫縱坐標(biāo)可以描述資源在一段時間內(nèi)的占用情況[8-9]。以下是AGV運動過程的幾種變速情況以及時間窗計算方法：

（1）直行通過節(jié)點或路徑。從AGV到達節(jié)點邊緣到AGV完全離開節(jié)點，此時AGV完全不會減速，可以按照勻速直線運動計算，通過下式計算：

式中，L為節(jié)點寬度或路徑長度，v為AGV經(jīng)過路口時的速度，tin為AGV進入節(jié)點的時間，tout為AGV離開節(jié)點的時間。

（2）在節(jié)點處轉(zhuǎn)向。AGV在節(jié)點轉(zhuǎn)向時，會先減速至轉(zhuǎn)向速度，以轉(zhuǎn)向速度通過節(jié)點，之后加速至直行速度。使用下式計算：

（3）啟動加速及停止減速。AGV由靜止?fàn)顟B(tài)啟動，勻加速至直行速度v，假設(shè)加速度a在加速過程中保持不變，時間窗滿足：

（4）等待。AGV在規(guī)避或異常時的時間窗分布滿足：

式中，td為AGV等待時間。

在計算出每臺AGV時間窗后，可以描述地圖上所有資源在時間軸的占用情況。通過尋找各AGV的時間窗的重疊位置，即兩臺AGV在同一時間段需要占用同一段路徑或節(jié)點，從而確定沖突節(jié)點、路徑和AGV，根據(jù)沖突的類型進行相應(yīng)的調(diào)整，進行時間窗的重計算，從而解決擁堵和沖突問題。同時，運行中的AGV的時間窗信息可以為后加入的AGV路徑規(guī)劃提供參考，避免擁堵。

2.2 沖突類型

在工廠環(huán)境中，節(jié)點和路徑資源是有限的，當(dāng)多輛AGV在工廠中運行時，會有很大的可能性在同一時間占用同一資源，而資源同時只能被一輛AGV占用，此時就會發(fā)生沖突。根據(jù)沖突位置和AGV的運行狀態(tài)，可以分為以下幾種沖突類型：相向沖突、轉(zhuǎn)向沖突、路徑?jīng)_突等。

（1）相向沖突。多輛AGV在可雙向行駛的路徑上相向行駛發(fā)生沖突，在沒有外力干預(yù)的情況下無法自發(fā)解鎖，需要有AGV前往相鄰路徑避讓或后退。

圖2相向沖突

（2）轉(zhuǎn)向沖突。不同路徑的多輛AGV在很短的時間內(nèi)前往相同的節(jié)點，并且其路徑互相被占用，這樣就會產(chǎn)生節(jié)點沖突，需要為這些AGV規(guī)劃避讓策略，避免同時占用同一節(jié)點。

圖3轉(zhuǎn)向沖突

（3）路徑?jīng)_突。AGV在同一條路徑上，且方向相反，必須有AGV退讓才可以解決沖突。

圖4路徑?jīng)_突

（4）工作點沖突。一輛AGV在工作點進行裝卸操作時，另一輛AGV需要通過該點。由于AGV裝卸操作需要一段時間，因此另一輛AGV的路徑會受阻，需要進行規(guī)避或等待。

圖5工作點沖突

在A*算法規(guī)劃完路徑后，計算每臺AGV的時間窗，檢查地圖中運行的AGV的時間窗是否有沖突，根據(jù)時間窗的重疊情況判斷沖突類型，然后進行沖突的規(guī)避，流程如圖6所示。

圖6沖突規(guī)避流程

2.3 沖突解決方式

監(jiān)測到AGV沖突后，根據(jù)沖突類型給出規(guī)避策略：

（1）相向沖突。首先計算兩臺車的優(yōu)先級，優(yōu)先級低的AGV避讓。其次尋找空閑路徑，令A(yù)GV前往空閑路徑規(guī)避。重新計算時間窗，檢查是否有沖突，若無沖突，則按新路徑執(zhí)行；若有沖突，重新尋找路徑。

（2）轉(zhuǎn)向沖突。首先判斷路徑暫時不會被占用的AGV，令其按原路運行，另一臺AGV暫時等待。前一臺AGV離開沖突節(jié)點后，暫停的AGV繼續(xù)運行。

（3）路徑?jīng)_突。首先兩臺AGV暫停，分別檢查兩臺AGV是否有可以后退規(guī)避的路徑。令可以后退規(guī)避的AGV后退，直到另一臺AGV離開沖突路徑。若兩臺AGV都可以避讓，計算任務(wù)優(yōu)先級，優(yōu)先級低的AGV進行避讓。

（4）工作點沖突。對于這種工作點占用問題，可以選擇原地等待和重新規(guī)劃路徑兩種方式。首先查詢占用工作點的時間窗，估計等待時間。然后鎖住工作點，為等待的AGV重新規(guī)劃一條路徑，并計算時間窗。比較兩種方式的時間成本，選擇成本較低的方案。

3 仿真實驗

3.1 靜態(tài)路徑規(guī)劃仿真

為驗證改進A*算法的有效性，分別對傳統(tǒng)A*算法、蟻群算法和改進A*算法進行實驗對比。

實驗使用1000×1000的柵格圖進行仿真，預(yù)設(shè)AGV平均速度10 m/s，在地圖中可通行位置隨機產(chǎn)生起點和終點，并進行路徑搜索，重復(fù)200次，最終實驗結(jié)果如表1所示。

表1 3種不同算法路徑規(guī)劃表現(xiàn)

通過表1可以看出，改進的A*算法相比于傳統(tǒng)A*算法和蟻群算法，路徑長度分別縮短了6.5%和1.7%，效果不明顯；但是AGV運行耗時分別減少了17.6%和12.5%，由于避免了部分沖突，有效縮短了AGV的運行時間。同時，路徑的拐點分別減少25%和33.3%，避免了AGV運行過程中的頻繁轉(zhuǎn)向。

3.2 沖突避免實驗

針對時間窗的避碰策略進行測試，分別測試10臺、20臺、30臺AGV同時在地圖中運行時的規(guī)避能力，實驗結(jié)果如表2所示。

由仿真實驗可以看出，在30臺AGV運行的情況下，基于時間窗的避碰策略相對于停止-等待法可以節(jié)約19.8%的等待時間，且隨著AGV數(shù)量的增加，其性能較為穩(wěn)定，可以滿足實際需要。隨著任務(wù)數(shù)量的增加，規(guī)避算法的性能在正常范圍內(nèi)波動，保持穩(wěn)定。

表2不同AGV數(shù)量下算法規(guī)避性能

圖7 不同任務(wù)數(shù)量下規(guī)避性能

4 結(jié)語

本文對A*算法的多AGV優(yōu)化進行了研究，加入了擁堵系數(shù)和時間窗模型。使用擁堵系數(shù)改進A*算法的啟發(fā)函數(shù)，避免經(jīng)過擁擠的路段；通過對轉(zhuǎn)角的約束，減少了AGV的轉(zhuǎn)彎次數(shù)，減少了時間消耗。使用時間窗模型進行路徑?jīng)_突的監(jiān)測，并根據(jù)沖突類型給出解決策略。最后對提出的算法進行了模擬測試，驗證了算法的有效性。

使用擁堵系數(shù)和時間窗模型可以有效減少多AGV調(diào)度過程中的沖突問題，提高了系統(tǒng)的運行效率，對多AGV系統(tǒng)的調(diào)度問題有很好的指導(dǎo)意義。