基于改進A＊算法的AGV調度研究

馮魯波

（四川大學計算機學院，成都610065）

0 引言

自動導引運輸車（automated guided vehicle，AGV）是一種智能運輸設備。AGV是目前無人工廠中的重要組成部分，在自動化流水線中可以取代人工完成搬運的任務。隨著制造業的發展和人工成本的提高，自動化流水線也需要相應的AGV調度系統來滿足日益增長的任務需求?；谝陨媳尘埃瑢Χ郃GV路徑規劃算法的優化提出了更高要求[1]。

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

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

1 靜態路徑規劃

1.1 傳統A*算法

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

其中g(x)表示起點到當前節點x的最短路徑成本，h(x)表示當前節點x到終點最短路徑成本的預估值。

傳統A*算法流程如圖1所示。

1.2 改進A*算法

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

（1）路徑規劃中避免過多轉向。

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

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

圖1 A*算法流程

為了實現上述目標，對A*算法做出如下改進：

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

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

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

在確定路徑之間夾角之后，為了避免AGV選擇轉角過大的路徑，修改啟發函數h(x)，增加啟發權重1-cosθ，轉角小的路徑會被優先選擇。

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

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

式中：wab為路徑ab段的擁堵系數，lab為路徑ab段的長度，nab為該時間段內通過路徑ab的AGV總數，k為擁堵權重系數，路徑ab的距離權重dab。

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

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

2.1 時間窗模型

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

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

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

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

（3）啟動加速及停止減速。AGV由靜止狀態啟動，勻加速至直行速度v，假設加速度a在加速過程中保持不變，時間窗滿足：

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

式中，td為AGV等待時間。

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

2.2 沖突類型

在工廠環境中，節點和路徑資源是有限的，當多輛AGV在工廠中運行時，會有很大的可能性在同一時間占用同一資源，而資源同時只能被一輛AGV占用，此時就會發生沖突。根據沖突位置和AGV的運行狀態，可以分為以下幾種沖突類型：相向沖突、轉向沖突、路徑沖突等。

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

圖2相向沖突

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

圖3轉向沖突

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

圖4路徑沖突

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

圖5工作點沖突

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

圖6沖突規避流程

2.3 沖突解決方式

監測到AGV沖突后，根據沖突類型給出規避策略：

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

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

（3）路徑沖突。首先兩臺AGV暫停，分別檢查兩臺AGV是否有可以后退規避的路徑。令可以后退規避的AGV后退，直到另一臺AGV離開沖突路徑。若兩臺AGV都可以避讓，計算任務優先級，優先級低的AGV進行避讓。

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

3 仿真實驗

3.1 靜態路徑規劃仿真

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

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

表1 3種不同算法路徑規劃表現

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

3.2 沖突避免實驗

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

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

表2不同AGV數量下算法規避性能

圖7 不同任務數量下規避性能

4 結語

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

使用擁堵系數和時間窗模型可以有效減少多AGV調度過程中的沖突問題，提高了系統的運行效率，對多AGV系統的調度問題有很好的指導意義。