郭昆侖，朱 瑾

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

0 引言

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

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

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

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

1 模型建立

1.1 模型假設(shè)

1）岸橋和堆場位置固定不變且已知，同時一個岸橋?qū)?yīng)所有堆場；

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

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

4）AGV在轉(zhuǎn)彎過程中速度保持不變。

1.2 變量設(shè)定

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

L為AGV設(shè)備的自身長度；

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

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

v為AGV的作業(yè)時的平均速度；

α為檢測到?jīng)_突時AGV的加/減速度；

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

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

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

w為路徑k中第m臺AGV發(fā)生沖突的次數(shù)；

s為路徑k中的起點；

e為路徑k中的終點；

Akm為路徑k中第m臺AGV的優(yōu)先級；

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

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

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

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

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

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

1.3 分布控制模型

對于AGV路徑?jīng)_突問題構(gòu)建模型如下：

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

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

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

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

2 MAS在自動化碼頭AGV的體系結(jié)構(gòu)

2.1 AGV的運行地圖建模

MAS在自動化碼頭AGV上應(yīng)用時，AGV作為智能體能夠通過傳感器確定自身位置，然后與已知的坐標(biāo)值路標(biāo)進(jìn)行比較，從而與全局坐標(biāo)系統(tǒng)進(jìn)行匹配，得到自身的實時位置。因此，本文在研究基于MAS的自動化碼頭多AGV的運行路徑時，選擇拓?fù)涞貓D，拓?fù)浞▽⒋a頭中的岸橋、堆場、路徑中的交叉點作為拓?fù)涞貓D中的節(jié)點，節(jié)點與節(jié)點之間的連線表示實際碼頭中AGV的運行路線。

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

對于鄰接表實現(xiàn)拓?fù)涞貓D的設(shè)計代碼如下：

2.2 基于黑板模型的交互協(xié)議

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

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

圖1 基于黑板模型的多AGV交互協(xié)議

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

2）系統(tǒng)中運行的AGV是黑板模型中的知識源。（1）每臺AGV都有各自運行特征，如可能發(fā)生的沖突以及自身運行的參數(shù)（速度、時間、優(yōu)先級等），都是黑板控制機(jī)制需要的信息；（2）AGVs即將發(fā)生沖突時，黑板控制機(jī)制允許AGV進(jìn)行協(xié)商，從黑板中提取優(yōu)先級等信息協(xié)商處理。

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

2.3 多AGV的沖突協(xié)商策略

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

2.3.1 基于時間成本的AGV優(yōu)先級確定

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

圖2 基于時間成本的AGV優(yōu)先級流程圖

2.3.2 基于改進(jìn)速度控制的沖突協(xié)商策略

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

圖3 AGV沖突示意圖

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

1）當(dāng)AGV的檢測臨界圓與別的檢測臨界圓開始相交，AGV根據(jù)黑板模型提供的信息確認(rèn)即將發(fā)生沖突。

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

3）雙方根據(jù)自身優(yōu)先級得到結(jié)果，確定其中一臺AGV鎖定沖突節(jié)點，并勻速通過。

4）優(yōu)先級低的AGV減速，等到優(yōu)先級高的AGV通過該節(jié)點，再恢復(fù)原速通過該節(jié)點，解決沖突問題。

2.4 改進(jìn)Dijkstra算法

Dijkstra算法可以有效地求解帶有權(quán)值的有向連接的拓?fù)涞貓D上的最短路徑，在確定起始點和終點后，以起點為中心，采用貪心算法的思想，每次遍歷搜索相鄰接點中距離始點最近的且從未訪問過的節(jié)點，直至擴(kuò)展到目標(biāo)點出現(xiàn)在搜索范圍中。在AGV路徑規(guī)劃中，權(quán)值代表的是該邊的長度，如果兩點不相連，那么它們的權(quán)值對應(yīng)的值為無窮大。但是，Dijkstra算法要遍歷計算每個節(jié)點，計算時間效率低，浪費運算空間。因此，本文采用堆優(yōu)化改進(jìn)Dijkstra算法。

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

圖4 改進(jìn)Dijkstra算法流程圖

3 實驗分析

3.1 多AGV的實驗與分析

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

圖5 AGV路徑圖

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

表1 路徑起始點、終點表

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

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

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

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

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

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

表2 不同控制方式的實驗數(shù)據(jù)表

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

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

圖8 不同數(shù)量AGV對應(yīng)平均堵塞率的變化圖

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

表3 不同數(shù)量AGV對應(yīng)平均完成運行時間表

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

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

4 結(jié)語

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