基于多智能體系統的自動化碼頭多AGV無沖突路徑規劃

郭昆侖，朱 瑾

（上海海事大學 物流科學與工程研究院，上海 201306）

0 引言

自動導引車（Automated Guided Vehicle，AGV）是自動化碼頭運輸集裝箱的主要運輸工具，是碼頭自動化的重要設備之一。在人工作業難度不斷提高、作業大型化、碼頭智能化的影響下，AGV的數量一直在增加，同時數量增加也導致其作業過程中的設備等待、沖突、死鎖等頻繁發生，現已成為自動化碼頭更加關注和急需解決的問題。

針對多AGV的無沖突路徑規劃問題，很多學者已經做出了研究，例如，王雨等[1]用改進蟻群算法解決AGV無沖突路徑規劃問題，方華等[2]用A～*算法求解三維的AGV無沖突路徑規劃模型。張素云等[3]建立了多參數優化控制模型，模型中考慮了路徑中AGV數量、AGV的安全距離和速度，同時改進了速度控制策略解決沖突。仲美酥等[4]考慮到AGV的行駛速度、AGV重載率和沖突時間，以最小化AGV在岸橋和堆場之間的行駛距離為目標建立多AGV無沖突路徑規劃模型，采用速度控制策略解決沖突。曹小華等[5]提出了基于沖突預測的多AGV避碰決策優化方法，將改進粒子群算法應用到避碰策略的優化中，解決沖突問題。Liu等[6]以最小化AGV任務完成時間為目標建模，考慮AGV的行駛速度來進行定位和避免沖突的約束，通過仿真驗證了模型和算法能夠避免AGV發生沖突和擁堵。現有大量文獻對于多AGV無沖突路徑的研究規模是在20臺～30臺，然而目前國內主要自動化碼頭AGV的數量是18、38、50臺，洋山四期的設計規模更是多達130臺，因此，解決30臺以上AGV的無沖突路徑規劃更具有實際意義。

目前大量文獻主要是將多智能體系統（Multi-Agent System，MAS）應用在車間、物流倉庫AGV上，李曉萌等[7]建立了基于Agent的多級決策和協作學習方法的AGV調度系統，同時設計了AGV的分布式動態調度策略。Koen H等[8]引入了智能體概念，提出了一種通過應用協作控制的方式來改善多車輛系統的事故處理，通過與現有自動化碼頭中多AGV系統進行比較，發現基于MAS的控制方式更能提高系統的運行效率。Fauadi等[9]提出了基于MAS的分布式架構來控制制造業中的AGV操作系統和代理體系結構，旨在實現控制物料搬運活動。Erol Rizvan等[10]提出了基于MAS的實時環境下的AGV和制造系統的協同調度，并采用MAS中投標、中標機制作為多AGV系統的協商策略。經建峰[11]建立了基于Agent的分布式多AGV控制系統，為AGV任務分配后，可以自主進行路徑規劃，同時AGV發生沖突時可以相互通信協作完成任務。然而，由于自動化碼頭AGV的運行環境更加復雜、地圖規模更大，現有文獻將MAS應用到碼頭AGV上求解多AGV的無沖突路徑規劃文獻更是少之又少。

綜上所述，本文針對30臺以上的AGV無沖突路徑規劃問題，以最小化AGV在岸橋和堆場之間的作業堵塞率為目標，考慮AGV的行駛速度、作業時間和沖突距離，建立自動化碼頭多AGV無沖突路徑規劃模型，同時設計了基于MAS的多AGV體系結構，改進Dijkstra算法規劃多條AGV路徑，改進速度控制策略控制AGV到達沖突節點前的速度，解決沖突。設計基于MAS的控制方式和任務優先級的控制方式的對比實驗，比較不同數量下AGV的平均堵塞率、平均等待時間和平均完成任務時間。

1 模型建立

1.1 模型假設

1）岸橋和堆場位置固定不變且已知，同時一個岸橋對應所有堆場；

2）在岸橋和堆場處設置緩沖區，使AGV在岸橋作業區和堆場作業區排隊等待作業時與路徑中其他運行AGV不會形成沖突；

3）不考慮AGV在行駛過程中故障、天氣等不可抗因素的影響；

4）AGV在轉彎過程中速度保持不變。

1.2 變量設定

在表示自動化碼頭多AGV的運行路徑網時，用G=（N，W）有向加權圖表示AGV的路徑網。其中N為AGV運行地圖中所有節點編號的集合，W為的G邊集，Wk（i，j）表示路徑k上第i個節點到第j個節點的邊的長度。下面引入以下變量，方便進行表示。

L為AGV設備的自身長度；

R為AGV行駛過程中沖突距離傳感器的檢測范圍半徑長度；

Ls為行駛過程中AGV間的安全距離；

v為AGV的作業時的平均速度；

α為檢測到沖突時AGV的加/減速度；

Dk為第k條路徑的長度，k=1，2，…，K，且K為AGV的所有路徑的集合；

AGVkm為路徑k中第m臺AGV的編號；

C（k1，k2）為兩臺發生沖突的AGV的路徑k1和k2，且k1，k2∈K；

w為路徑k中第m臺AGV發生沖突的次數；

s為路徑k中的起點；

e為路徑k中的終點；

Akm為路徑k中第m臺AGV的優先級；

tkms為路徑k中第m臺AGV的起始時間；

tkmep為路徑k中第m臺AGV的運行結束時間；

tkmeop為路徑k中第m臺AGV的預計完成任務時間；

tck為路徑k中AGV在沖突節點的等待時間；

t為路徑中AGV因沖突延誤的時間；

T為AGV從初始位置到達終止位置的總時間消耗。

1.3 分布控制模型

對于AGV路徑沖突問題構建模型如下：

在AGV運行過程中，式(1)和式(2)表示同一時間每個節點至多被AGV訪問一次，即路徑中AGV不重復行駛同一路段，且同一節點只能有一輛AGV通過；式(3)表示任意一臺AGV在任意路徑中行駛的長度；式(4)表示任意路徑中任意一臺AGV完成任務的結束運行時間。

為AGV分配任務后，AGV運行過程中行駛速度不變為，且為了避免從同一出發點出發的同一路徑中多臺AGV之間的沖突，AGV之間需要保持最小的安全距離，即安全檢測距離。

若不同路徑中兩臺或多臺AGV同時到達兩條路徑的交叉節點時，則AGV可能在交叉節點處發生沖突，若發生沖突AGVs需經過協商確定其中某臺AGV通過沖突節點，解決沖突問題。當發生沖突時，AGVs先提取AGV編號進行協商，首先比較AGV的優先級。式(5)為根據單臺AGV的路徑規劃計算預計完成任務時間；式(6)為根據預計完成任務時間判斷AGVs的優先級，完成任務時間長的AGV優先級低，否則，優先級高。

AGVs協商后根據自身優先級做出調整，優先級低的AGV到達沖突節點前開始減速可能直到停止，優先級高的AGV則勻速通過沖突節點。式(7)為k1中AGV與k2中的AGV通過距離傳感器檢測到對方時，兩臺AGV的安全距離小于沖突檢測范圍距離；式(8)為k1中AGV與k2中的AGV通過距離傳感器檢測到對方時，進行協商和同意k2中的AGV先通過沖突節點，而k1中AGV從v0減速到v1的距離ls；式(9)為k1中AGV從v0減速到v1的時間tc11，同時也是AGV加速恢復到原速的時間tc12；式(10)為k1中AGV解決沖突過程中的最終減速度v1；式(11)k1中第m臺AGV發生w次沖突后到達終點的時間為Tk1m；式(12)～式(13)為n臺AGV在路徑中因沖突延誤的等待時間，以及n臺AGV完成任務的總時間；式(14)為最小化n臺AGV作業過程中的堵塞率，即總等待時間和任務完成時間的比值TJ。

2 MAS在自動化碼頭AGV的體系結構

2.1 AGV的運行地圖建模

MAS在自動化碼頭AGV上應用時，AGV作為智能體能夠通過傳感器確定自身位置，然后與已知的坐標值路標進行比較，從而與全局坐標系統進行匹配，得到自身的實時位置。因此，本文在研究基于MAS的自動化碼頭多AGV的運行路徑時，選擇拓撲地圖，拓撲法將碼頭中的岸橋、堆場、路徑中的交叉點作為拓撲地圖中的節點，節點與節點之間的連線表示實際碼頭中AGV的運行路線。

單車道單向路徑網絡，就是一條路徑上的車道只有一個方向一個車道，不存在雙向雙車道，并且在每一條路徑的垂直方向上只可能有一輛AGV。同時，實際碼頭中AGV運行線路為正值，所以建立的拓撲地圖是一張加權有向圖，邊的權值均為正值。使用鄰接表的方法來建立有向加權圖，鄰接表方法是將所有與某一個頂點相連接的其他頂點存入到一個鏈表中，并且將這個鏈表關聯到該頂點。此外，碼頭中的AGV運行路徑大多為直角彎，即在拓撲地圖中路徑節點的上下左右四個方向上，才可能存在與其他節點相連接的邊。

對于鄰接表實現拓撲地圖的設計代碼如下：

2.2 基于黑板模型的交互協議

在基于MAS的自動化碼頭多AGV的體系結構中，交互協議是AGV與AGV、AGV與控制臺的通信。AGV在運行過程中需要發送和接收信息，即AGV給控制臺需要發送的小車編號、小車任務、當前所在位置、當前時間、以及下一個節點位置；控制臺則需要給所有AGV發送路徑表中某臺即將AGV占用某個節點，以便AGVs到達沖突節點前做出協商解決問題；AGV與AGV之間的交互信息主要是AGV發生沖突時，進行協商，需要發送各自的當前位置、當前時間和自身優先級。

根據本文需要的交互信息，對共享資源的同步和認知是AGV之間協作的重要前提。在MAS中黑板模型能夠較大程度上管理全局資源，所以本文采用黑板模型設計了多AGV交互協議，如圖1所示。

圖1 基于黑板模型的多AGV交互協議

1）黑板的主要作用是將地圖中岸橋到堆場、堆場到岸橋的路徑分配給每臺AGV，監控每臺AGV的位置、速度、時間，并以向量的形式保存，即vector::iterator it，it是可以讀寫的位置、速度、時間元素，同時，黑板也需將每臺AGV的位置、速度、時間以向量的形式發送到每臺AGV上。

2）系統中運行的AGV是黑板模型中的知識源。（1）每臺AGV都有各自運行特征，如可能發生的沖突以及自身運行的參數（速度、時間、優先級等），都是黑板控制機制需要的信息；（2）AGVs即將發生沖突時，黑板控制機制允許AGV進行協商，從黑板中提取優先級等信息協商處理。

3）系統中的黑板控制單元功能由無線網絡完成，并且本文中AGV與AGV交互信息、AGV與黑板的交互信息的間隔時間為0.02s。

2.3 多AGV的沖突協商策略

多AGV的協商策略主要是根據AGV的優先級進行判斷，然后進行讓步，解決沖突。本文采用基于時間成本的方法確定AGV的優先級，并結合速度控制方式作為AGV的協商策略。

2.3.1 基于時間成本的AGV優先級確定

本文采用了一種基于時間成本的方法確定AGV的優先級，如圖2所示，為每臺AGV分配任務后，AGV根據起始點和終點，使用最短路徑算法得到最短路徑，同時計算完成該任務的預計完成任務時間，根據時間的長短確定AGV的預計優先級。當解決沖突過程中，優先級低的AGV通過減速，直到優先級高的AGV通過沖突節點，此時，優先級低的AGV花費更多的時間，并將時間重新計算到預計優先級中，優先級的高低也會隨之發生變化。

圖2 基于時間成本的AGV優先級流程圖

2.3.2 基于改進速度控制的沖突協商策略

AGV沖突情況如圖3所示，當兩臺AGV即將到達同一交叉口，AGV1、AGV2自身的沖突檢測傳感器設置半徑為R1、R2的檢測半徑，并且R1=R2，R1與R2的長度根據AGV車身長度和路徑長度等因素設置，檢測臨界圓隨著AGV移動而移動。在圖3(a)中，AGV1和AGV2同時向路徑交叉口行駛，此時AGV1、AGV2的檢測臨界圓沒有發生相交，所以兩臺AGV并沒有檢測到沖突；當兩臺AGV繼續運行到圖3(b)情形時，兩個檢測臨界圓開始相交，表明AGV1和AGV2可能會發生交叉節點處的沖突，此時需要AGV協商讓步，解決沖突。

圖3 AGV沖突示意圖

下面以發生沖突的兩臺AGV中一臺AGV為例解釋解決沖突的過程：

1）當AGV的檢測臨界圓與別的檢測臨界圓開始相交，AGV根據黑板模型提供的信息確認即將發生沖突。

2）AGV提取對方AGV編號，確定協商對象AGV并與之通信，請求通過前方可能沖突節點。

3）雙方根據自身優先級得到結果，確定其中一臺AGV鎖定沖突節點，并勻速通過。

4）優先級低的AGV減速，等到優先級高的AGV通過該節點，再恢復原速通過該節點，解決沖突問題。

2.4 改進Dijkstra算法

Dijkstra算法可以有效地求解帶有權值的有向連接的拓撲地圖上的最短路徑，在確定起始點和終點后，以起點為中心，采用貪心算法的思想，每次遍歷搜索相鄰接點中距離始點最近的且從未訪問過的節點，直至擴展到目標點出現在搜索范圍中。在AGV路徑規劃中，權值代表的是該邊的長度，如果兩點不相連，那么它們的權值對應的值為無窮大。但是，Dijkstra算法要遍歷計算每個節點，計算時間效率低，浪費運算空間。因此，本文采用堆優化改進Dijkstra算法。

堆優化能夠有效減少算法運行時間，其思想就是使用一個優先隊列的方法，該方法主要是每次彈出的元素一定是整個隊列中最小的元素，最小元素代替每次查找的最短距離的邊，即用鄰接表代替鄰接矩陣，堆優化能夠大幅減少計算時間。堆優化方法實現如下：首先，需要定義一個優先隊列，優先隊列存儲并快速尋找距離最近的點，該隊列的元素為節點編號和該節點到下個節點的距離；其次，起始點需要初始化，即將起點加入優先隊列中，起點的編號就是在優先隊列元素的節點編號，此時計算過程中該節點與起始點的距離為0；最后，如果在其他運算過程中，優先隊列中的某個節點到起始點的最短距離發生了變化，原本優先隊列中的元素無需刪除，而是將變化后最短節點元素再次存入作為優先隊列作為最小元素彈出。改進Dijkstra算法流程圖如圖4所示。

圖4 改進Dijkstra算法流程圖

3 實驗分析

3.1 多AGV的實驗與分析

建立了如圖5所示的單向單通道路徑網，以岸橋到堆場、堆場到岸橋的運行方式選擇起始點和終點，其中3、8、13為岸橋位置，59、60、63、64、67、68為堆場箱區的位置。岸橋到堆場、堆場到岸橋共有36種組合，對應36臺AGV；每臺AGV的速度不變，為2m/s；AGV加/減速度為0.5m/s2；AGV的長度為2m；AGV的沖突檢測距離為2m；地圖頂點數目為69；實驗次數為100次；采用c++編寫多AGV系統的控制程序，在Inter（R）Core（TM）i7-8750H CPU @ 2.20GHz 2.21 GHz、16GB內存的Windows10計算機上實現。

圖5 AGV路徑圖

為36臺AGV隨機分配任務，根據起始點和終點用改進Dijkstra生成每臺AGV的路徑，如表1所示，且同一頂點出發的多臺AGV出發時間依次間隔2s，即1號車第0s出發，2號車第2s出發，3號車第4s出發。同時，36臺AGV的路徑必須包含所有起點的路徑，目的是避免36臺AGV同時選擇一條路徑，不會發生沖突。

表1 路徑起始點、終點表

36臺AGV實驗100次的堵塞率分布情況如圖6所示，堵塞率為0的情況主要是為AGV隨機分配的起始點和終點時，重復選擇相同的路徑，導致沖突次數為0；而當為AGV隨機分配路徑重復率低時，AGV的沖突次數增加，堵塞率的平均值為0.48%。

圖6 基于MAS控制方式的多AGV堵塞率

3.2 不同控制方式實驗對比及分析

基于MAS的控制方式和任務優先級的控制方式的堵塞率分布情況如圖7所示。任務優先的控制方式主要是指根據每臺AGV優先級確定避碰決策，優先級別低的AGV 在避碰過程中需要為其他AGV等待讓行。圖中虛線代表任務優先級的控制方式，實線代表本文基于MAS的控制方法。在100次實驗中，每種控制方式的實驗都對36臺AGV進行隨機分配起始點和終點，并對同一條件進行模擬，從圖7中可知，基于MAS的控制方式堵塞率明顯整體低于任務優先級的控制方式。

圖7 不同控制方式的多AGV堵塞率

結合表2，基于MAS的控制方式與任務優先級的控制方式相比，平均等待時間減少7.8s和平均堵塞率降低0.22%，該方法明顯優于任務優先級的控制方式。

表2 不同控制方式的實驗數據表

同時，本文考慮了在不同數量AGV下兩種方式的平均堵塞率、平均等待時間和平均完成時間的變化。

從圖8中可知，1）AGV數量在20～30臺時，任務優先級的控制方式與基于MAS的控制方式平均堵塞率相差為0.08%和0.14%，平均堵塞率曲線近乎平行，這是因為AGV數量相對較少，發生沖突頻率低且沖突不會影響系統運行效率；2）AGV數量超過30臺時，尤其在36臺時，基于MAS的控制方式平均堵塞率下降了0.22%，曲線下降幅度更大，說明基于MAS的控制方式能夠減少解決沖突時間和降低沖突AGV對系統運行的影響，更加適合解決30臺以上AGV無沖突路徑規劃問題。

圖8 不同數量AGV對應平均堵塞率的變化圖

表3中GAP=（任務優先級的平均等待時間-基于MAS的控制方式的平均等待時間）/任務優先級的平均等待時間。當20～30時，GAP在20.3%～23.6%變化，變化幅度較小，說明在30臺以下時，速度策略比等待策略解決沖突所用時間短；當超過30臺時，GAP在23.6%～30.4%，在基于MAS的控制方式的AGV平均等待時間明顯減少，而采用任務優先級的控制方式時，解決沖突過程中AGV等待時間較長，影響系統運行效率。

表3 不同數量AGV對應平均完成運行時間表

由表4縱向來看，兩種控制方式的平均完成時間差為1.4s、2.2s、4.3s、6.2s和8.9s，時間差值隨著AGV數量的增加而增加，說明基于MAS的控制方式能夠大幅度減少30臺以上AGV的運行時間，提高了AGV的運行效率。

表4 不同數量下平均等待時間和平均堵塞率表

4 結語

本文以最小化AGV作業堵塞率為目標，考慮AGV的行駛速度、作業時間和沖突距離，建立了多AGV無沖突路徑規劃模型，同時設計了基于MAS的碼頭多AGV體系結構，將改進速度控制作為AGV的協商策略。設計了基于MAS的控制方式和任務優先級的控制方式對同一條件下的平均堵塞率、平均等待時間和平均完成任務時間的對比試驗。實驗結果表明當AGV數目少于30臺時，兩種控制方式在平均堵塞率上相差0.08%～0.14%，變化幅度較小；超過30臺AGV時，基于MAS的控制方式在平均堵塞率上減少了0.14%～0.22%，幅度變化大，同時基于MAS的控制方式比任務優先級的控制方式的AGV平均等待時間減少7.8s，平均完成時間減少8.9s，實驗結果驗證了本文模型的可行性，以及基于MAS的控制方式更加適合解決30臺以上規模的AGV無沖突路徑規劃問題。