馮魯波

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

0 引言

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

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

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

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

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

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

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

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

1.2 改進(jìn)A*算法

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

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

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

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

圖1 A*算法流程

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

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

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

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

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

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

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

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

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

2 基于時(shí)間窗的沖突避免策略

2.1 時(shí)間窗模型

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

（1）直行通過(guò)節(jié)點(diǎn)或路徑。從AGV到達(dá)節(jié)點(diǎn)邊緣到AGV完全離開(kāi)節(jié)點(diǎn)，此時(shí)AGV完全不會(huì)減速，可以按照勻速直線運(yùn)動(dòng)計(jì)算，通過(guò)下式計(jì)算：

式中，L為節(jié)點(diǎn)寬度或路徑長(zhǎng)度，v為AGV經(jīng)過(guò)路口時(shí)的速度，tin為AGV進(jìn)入節(jié)點(diǎn)的時(shí)間，tout為AGV離開(kāi)節(jié)點(diǎn)的時(shí)間。

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

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

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

式中，td為AGV等待時(shí)間。

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

2.2 沖突類(lèi)型

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

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

圖2相向沖突

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

圖3轉(zhuǎn)向沖突

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

圖4路徑?jīng)_突

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

圖5工作點(diǎn)沖突

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

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

2.3 沖突解決方式

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

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

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

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

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

3 仿真實(shí)驗(yàn)

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

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

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

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

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

3.2 沖突避免實(shí)驗(yàn)

針對(duì)時(shí)間窗的避碰策略進(jìn)行測(cè)試，分別測(cè)試10臺(tái)、20臺(tái)、30臺(tái)AGV同時(shí)在地圖中運(yùn)行時(shí)的規(guī)避能力，實(shí)驗(yàn)結(jié)果如表2所示。

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

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

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

4 結(jié)語(yǔ)

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

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