武 星，翟晶晶，肖海寧，胡 亞，樓佩煌

(1.南京航空航天大學 機電學院，江蘇 南京 210016;2.鹽城工學院 機械工程學院，江蘇 鹽城 224051)

0 引言

自動導引車(Automated Guided Vehicle, AGV)是一種最具代表性的物流輸送機器人，而由多臺AGV構成的AGV系統(tǒng)廣泛應用于各種制造業(yè)及倉儲配送領域[1-2]。為了保證多臺AGV在同一工作空間中有序運行，需要對AGV系統(tǒng)的任務調度[3]、路徑規(guī)劃[4]和交通管控[5]3項關鍵技術進行研究。其中，交通管控側重于解決多臺AGV并發(fā)運行時可能產生的運動沖突、碰撞和死鎖。

為避免AGV并發(fā)運行時的運動沖突，已有研究提出了3類沖突避免方法：

(1)路徑網絡設計方法 該類方法將路徑網絡設計為多個相互獨立的、僅供單臺AGV專用的運行區(qū)域，如單環(huán)路布局[6-7]或串級配置布局[8]。顯然，該種路徑網絡布局難免降低AGV系統(tǒng)的運行效率和路徑柔性[9]。

(2)區(qū)域控制方法[10-11]該類方法將路徑網絡分割為多個互不重疊、可供不同AGV分時占用的運行區(qū)域，但任意時刻每個運行區(qū)域還只允許一臺AGV運行[12]。

(3)路徑規(guī)劃方法 包括：①集中式無碰撞靜態(tài)路徑規(guī)劃[13-15]，通過時間窗方式預先為每臺AGV規(guī)劃互不沖突的運行路徑，然而各種非理想條件或隨機因素可能干擾AGV偏離與已規(guī)劃路徑關聯(lián)的既定時間窗，在實際運行時產生一系列連鎖的運行沖突[16];②分布式路徑規(guī)劃+集中式交通管控[17]，多臺AGV自主規(guī)劃路徑，但在路徑網絡資源共享時采用集中式管控方法。

本質上看，多AGV運動沖突避免是對共享路徑網絡資源的協(xié)調與管控。路徑網絡設計方法是從物理設施的層面將路徑網絡劃分為AGV專用的運行區(qū)域，系統(tǒng)柔性最低；區(qū)域控制方法則是在軟件層面定義分時專用、錯時共享的運行區(qū)域，系統(tǒng)柔性次之；而路徑規(guī)劃方法針對的共享交通資源已從運行區(qū)域細化到路徑段，系統(tǒng)柔性較好。根據允許AGV運行的方向，路徑段可分為單向路徑[18-19]和雙向路徑[21-22]，雙向路徑同時具有路徑空間和方向兩種資源，具有更復雜的共享控制機制。

除了物理設施層面的專用運行區(qū)域設置，其他沖突避免方法都必須解決共享交通資源(運行區(qū)域、路徑等)的排他性占用，即會發(fā)生某臺AGV因為所需的交通資源被其他AGV占用而暫時不能運動的情況(阻塞)。如果多臺AGV出現(xiàn)了循環(huán)阻塞，則會產生因路徑沖突引發(fā)的死鎖，且死鎖類型與所采用的沖突避免方法有關。MOORTHY等[23]針對采用區(qū)域控制的AGV系統(tǒng)，提出一種“檢測目標區(qū)域的前一區(qū)域是否空閑”的環(huán)路死鎖預測方法。針對雙向導引路徑網絡，SHAO等[24]研究了“直接死鎖”和“因堵塞造成的死鎖”的死鎖避免方法;肖海寧等[17]針對單向導引路徑網絡，提出一種基于有向圖狀態(tài)模型的環(huán)路死鎖搜索與避免方法。

從某種意義上看，沖突乃至死鎖的發(fā)生，與多臺AGV爭用有限的共享交通資源有關。在不降低AGV系統(tǒng)整體運輸能力的前提下減少AGV數(shù)量，在本質上可減輕共享路徑網絡中的沖突與死鎖。相對于傳統(tǒng)的每次裝卸一個/組載荷的單載量AGV，多載量AGV[25](如一臺牽引AGV拖帶多個數(shù)量可變的掛車)可在一次物料配送任務中，分別從多個發(fā)料點進行多個載荷的裝載，或到多個送料點進行多個載荷的卸載，顯然具有更強的單車運輸能力和更大的配送作業(yè)柔性。然而，當前有關多載量AGV的研究主要集中于任務調度[25-28]，較少考慮多載量AGV的運動沖突與死鎖。

本文以多載量AGV系統(tǒng)為對象，研究與單載量AGV差異較大的兩種運動沖突(路徑空間沖突、交叉路口沖突)與環(huán)路死鎖，在設計變長度AGV路徑空間沖突避免方法的基礎上，提出一種帶防死鎖策略的交叉路口通行順序優(yōu)化方法。

1 問題描述

典型復雜軍工產品的生產計劃與物料配送過程，既涉及機械、電氣組件的外協(xié)與采購，也包含機械零部件、電子元器件、組件、部件等各種物料與在制品在不同車間、不同工位之間的配送、轉運和出入庫等。按照傳統(tǒng)的裝配生產線布局與裝配人員工作安排，各工序操作現(xiàn)場分散，車間內部半成品周轉耗時長，配送準時性差，裝配工位可能待料停產。

針對傳統(tǒng)配送準時性差的問題，考慮到裝配工位物料種類多、配送要求差異性大的實際需求，本文采用多載量AGV在輔料庫與裝配工位之間配送標準機械零件和電子元器件，利用單載量AGV在半成品庫與裝配工位之間配送用于部裝的套件、組件等。整條裝配生產線包括A艙部裝線、C艙部裝線和艙段總裝線，以及外協(xié)生產部裝的B艙、D艙和E艙的3條輸送線，如圖1所示。裝配生產線中的AGV系統(tǒng)采用單向導引路徑網絡。

為了聚焦多載量AGV物流輸送系統(tǒng)的研究，本文對裝配生產工藝及其所需的物料配送過程進行如下假設：

(1)當某一裝配工作站所需的所有裝配工件都齊套且該工作站已空閑時，則開始下一個裝配任務。每個裝配工作站每次只能裝配一個部件，且裝配作業(yè)過程不能中斷。

(2)裝配完成的組件/部件進入裝配工作站的輸出緩沖區(qū)，等待AGV搬運到下一個目標工作站，完成所有裝配工序的成品經輸出工作站離開裝配生產線。

(3)輸入緩沖區(qū)中的工件按先入先出順序等待工作站進行裝配，輸出緩沖區(qū)中的工件按任意順序離開工作站。

(4)多載量AGV可按任務需求裝載不同種類和數(shù)量的工件，且工件裝載和卸載的時間固定。若有多臺AGV需要訪問同一個裝卸工作點，則按照排隊等待、逐一訪問的方式處理。

(5)AGV開始執(zhí)行物料配送任務時，通過路徑規(guī)劃在單向導引路徑網絡中搜索一條從當前位置到目標工作站的單向最短路徑。并且，在交通管控過程中不采用路徑重規(guī)劃的方法避免AGV系統(tǒng)的運動沖突。

(6)空閑AGV停留在特定的任務等待點等待下一個物料配送任務，且不影響其他AGV在路徑網絡中的通行。

由此可見，為保證整條裝配生產線的高效有序運行，必須首先保證各裝配工位的多種裝配物料準時配送。這對多載量AGV系統(tǒng)的交通管控提出了極高的要求，必須設法避免多AGV在導引路徑網絡中的各種運動沖突與環(huán)路死鎖。

2 研究方案

導引路徑網絡的基本元素包括路徑段和交叉路口，多載量AGV系統(tǒng)的交通管控旨在解決多臺AGV共享路徑段和交叉路口時可能產生的運動沖突和環(huán)路死鎖。本文先介紹AGV在單向導引路徑網絡中的4種運動沖突，再針對與單載量AGV差異較大的路徑空間沖突和交叉路口沖突，提出一種多載量AGV交通管控總體方案，最后研究用于運動沖突和環(huán)路死鎖避免的具體方法。

2.1 運動沖突類型

在單向導引路徑網絡中，AGV系統(tǒng)可能存在4種發(fā)生碰撞的運動沖突[17]。推廣到多載量AGV系統(tǒng)，運動沖突的形式如圖2所示。其中，圖2a表示一臺靜止的AGV2阻礙其后另一臺AGV1沿路徑運行的路徑點沖突，圖2b表示兩條導引路徑相距較近而引發(fā)的AGV轉向空間沖突，這兩種沖突避免方法與單載量AGV系統(tǒng)類似，因此不再贅述。

圖2c表示路徑空間沖突，即AGV1由于即將進入的路徑段無剩余空間而占用交叉路口，進而阻礙AGV4的通行。為避免該沖突，針對長度不變的單載量AGV，文獻[17]已定義路徑段的總容量和剩余容量。在AGV通過交叉路口進入目標路徑之前，必須檢測該路徑是否具有剩余容量。然而，多載量AGV在一次物料配送任務中可進行多次裝載和卸載，數(shù)量可變的掛車導致AGV的長度不斷變化。因此，通過管控路徑容量的沖突避免方法不再適合多載量AGV，第2.2節(jié)將從更本質的路徑空間角度分析該問題。

圖2d表示交叉路口沖突，即兩臺AGV因意圖同時通過同一交叉路口發(fā)生運動沖突。為避免該沖突，文獻[17]已在交叉路口的入口點定義加鎖點，在出口點定義解鎖點。只有加鎖點在交通管控系統(tǒng)中未加鎖，AGV才能被允許進入該路口；且AGV進入路口后加鎖點加鎖。當AGV離開出口點時，觸發(fā)解鎖點的解鎖信號，對加鎖點進行解鎖?？梢姡瑐鹘y(tǒng)方法僅采用互斥機制解決多AGV在交叉路口的沖突，并未考慮AGV在交叉路口的通行順序。

2.2 總體研究方案

為解決多載量AGV系統(tǒng)共享路徑段和交叉路口時可能產生的運動沖突和環(huán)路死鎖，本文提出一種用于運動沖突和環(huán)路死鎖避免的交通管控總體方案，如圖3所示。針對多載量AGV長度不斷變化的特點，設計一種變長度AGV路徑空間沖突避免方法；針對交叉路口沖突，考慮到多載量AGV變長特性對阻塞環(huán)路死鎖的影響，提出一種帶防死鎖策略的交叉路口通行順序優(yōu)化方法。

當?shù)趇臺多載量AGV期望進入第j條路徑段時，首先采用變長度AGV的路長避碰方法，判斷第j條路徑段的剩余長度是否足夠。若足夠長，則該AGV再繼續(xù)申請進入位于該路徑段入口的交叉路口。通過綜合競標價模型和環(huán)路死鎖檢測方法優(yōu)化多AGV通過交叉路口的順序，獲得無環(huán)路死鎖的多載量AGV通行序列。最后，采用包含加鎖點和解鎖點的路口互斥機制[17]，控制多載量AGV有序地通過交叉路口。

2.3 路段避碰方法

如圖2所示，數(shù)量可變的掛車導致AGV的長度不斷變化，針對單載量AGV定義的路徑段剩余容量概念不適用于多載量AGV。因此，本節(jié)將從更本質的路徑空間角度分析該問題。對于第i臺多載量AGV，假設其可攜帶ni個掛車，拖車和掛車的長度分別為la和lb，則在作業(yè)時刻t，第i臺多載量AGV的長度

li(t)=la+ni(t)lb。

(1)

對于第j條路徑段，假設其總長度為Ltj，在作業(yè)時刻t，該路徑段的AGV數(shù)量為m，AGV之間的安全間距為Ls，則該路徑段的剩余長度

(2)

為避免如圖2c所示的路徑空間沖突，本文提出一種變長度AGV的路長避碰方法。當?shù)趇臺多載量AGV進入第j條路徑段之前，必須檢測該路徑段的剩余長度是否足夠。若剩余長度不足，即li(t)>Lrj(t)，則暫時禁止該AGV進入相應路徑段及其關聯(lián)的交叉路口，從而避免該交叉路口被其長期占用，影響其他AGV通行。

3 防死鎖路口通行順序優(yōu)化

針對多AGV在交叉路口的運動沖突，現(xiàn)有文獻僅對交叉路口定義了包含加鎖點和解鎖點的路口互斥機制，并未深入研究多載量AGV在交叉路口的通行順序對潛在運動沖突和環(huán)路死鎖的本質影響。然而，AGV任務緊迫度、路徑段交通負荷均衡度等因素，對多載量AGV通過交叉路口后，可能引發(fā)的潛在運動沖突和環(huán)路死鎖具有更加本質的影響。因此，本節(jié)在分析路徑空間沖突如何影響環(huán)路死鎖臨界條件的基礎上，提出一種帶防死鎖策略的交叉路口通行順序優(yōu)化方法，如圖4所示。

首先，以某一交叉路口為對象，將所有請求進入其中的AGV組成AGV等待隊列。然后，根據綜合競標價模型計算等待隊列中所有AGV的綜合競標價，并暫定競標價最高的獲標AGV獲得該路口的優(yōu)先通行權。進而，假設該AGV通過交叉路口并進入目標路徑段后，預測多載量AGV系統(tǒng)的路徑網絡阻塞圖。最后，采用前瞻性環(huán)路死鎖檢測方法搜索潛在的環(huán)路死鎖。若無死鎖，則將新獲標的AGV加入AGV通行序列末端；否則，通過環(huán)路死鎖避免方法，搜索等待隊列中不會引發(fā)死鎖的AGV并將其加入。

3.1 通行順序優(yōu)化

(1)綜合競標價模型

針對多載量AGV物流輸送系統(tǒng)的特點，本文以物料配送準時化與交通負荷均衡化為目標，構建交叉路口AGV系統(tǒng)的綜合競標價模型，如圖5所示。一方面，根據AGV當前位置和目標工位，預測任務剩余行程時間，再根據任務最優(yōu)送達時間、工位點裝卸載時間等約束，設計任務緊迫度與AGV緊迫度的評價函數(shù)。另一方面，以待評價AGV所占路徑段空間、所在路徑段交通流和下一路徑段交通流為基礎，設計路徑段交通負荷均衡度評價函數(shù)，從而構建交叉路口AGV綜合競標價模型。

(2)AGV緊迫度

由于單載量AGV與多載量AGV在一次物料配送任務中的任務載量不同，下面分別討論兩種類型AGV的緊迫度。

1)多載量AGV緊迫度。

對在某交叉路口等待的第i臺多載量AGV，假設有j(j=1,2,…,Nj)個配送任務，每個配送任務的卸載時間為Td(j)，從第j-1個配送任務的卸載點到第j個配送任務卸載點的距離為S(j-1)j。在作業(yè)時刻t，假設第i輛AGV的第j-1個配送任務的預計完成時間為Ei(j-1)(t)，交通流對配送任務剩余路程時間的影響系數(shù)為α(一般取值范圍為1.2～1.5，具體數(shù)值需要通過仿真實驗獲得)，多載量AGV的平均速度為v，第i輛AGV的第j個配送任務到達目的地的預計時間

Eij(t)=Ei(j-1)(t)+Td(j)+αS(j-1)j/v。

(3)

另一方面，在作業(yè)時刻t，假設正在執(zhí)行的第k個配送任務的剩余路程Sk(t)，則該任務到達目的地的預計時間

Eik(t)=t+Td(k)+αSk(t)/v。

(4)

對第i臺多載量AGV的第j個配送任務，假設其截止時間為Tij，則任務緊迫度

(5)

對執(zhí)行Nj個配送任務的多載量AGV，其緊迫度

(6)

2)單載量AGV緊迫度。

由于單載量AGV每次僅執(zhí)行一個配送任務，則任務緊迫度即為AGV緊迫度。對在某交叉路口等待的第i臺單載量AGV，在作業(yè)時刻t，假設其配送任務的剩余路程為Si(t)，卸載時間為Td(i)，則該任務的預計完成時間

Ei(t)=t+Td(i)+αSi(t)/v。

(7)

假設該任務的截止時間為Ti，則AGV緊迫度

(8)

(3)交通負荷均衡度

由圖5可知，交通負荷均衡度受AGV所在路徑段和下一路徑段的交通流影響。對第i臺多載量AGV，在作業(yè)時刻t，假設其當前所處路徑段的總長度為Ltp，已有mp臺AGV；申請進入的下一路徑段的總長度為Ltq，已有mq臺AGV；則當前所處路徑段的交通負荷ηp和下一路徑段的交通負荷ηq分別為：

(9)

(10)

則第i臺AGV在交叉路口的路徑段交通負荷均衡度

(11)

(4)綜合競標價

在圖5所示的綜合競標價模型中，假設融合AGV緊迫度與交通負荷均衡度時所用的權重分別為w1和w2(具體數(shù)值需要通過仿真實驗獲得)，則綜合競標價

Wi(t)=w1Ui(t)+w2Ai(t)。

(12)

根據AGV在交叉路口的綜合競標價模型，可確定競標價最高的AGV獲標，該AGV具有交叉路口的優(yōu)先通行權。然而，考慮到路徑空間沖突，該AGV通過交叉路口后可能導致環(huán)路死鎖，降低整個AGV系統(tǒng)效率。因此，必須考慮該AGV通過路口后的路徑網絡阻塞圖，進行環(huán)路死鎖預測，并消除潛在的環(huán)路死鎖。

3.3 死鎖預測與避免

針對單載量AGV死鎖預測與避免問題，文獻[17]提出一種前瞻性死鎖預測和避免方法。該方法將“阻塞環(huán)路剩余容量等于1”定義為環(huán)路死鎖臨界條件，再通過前瞻性預測方法判斷當前AGV進入目標路徑段后是否引發(fā)上述環(huán)路死鎖臨界條件。但本文研究的多載量AGV長度不斷變化，無法通過簡單地定義路徑段剩余容量和阻塞環(huán)路剩余容量來尋找環(huán)路死鎖臨界條件。因此，本文在分析多載量AGV長度對阻塞環(huán)路空間資源占用的基礎上，提出一種多載量AGV的前瞻性環(huán)路死鎖檢測與避免方法，如圖6所示。

在作業(yè)時刻t，假設獲標的多載量AGV的目標路徑段為bij，預測其潛在阻塞環(huán)路為Bi={bij,bjk,bkm,…,bni}。首先，搜索該阻塞環(huán)路Bi中長度最大的多載量AGV，令其長度為lmax(t)。假設獲標的多載量AGV的長度為lp(t)，若lmax(t)

若允許交叉路口處某臺AGV進入路徑段bij會引發(fā)阻塞環(huán)路Bi的死鎖，則暫時禁止該AGV進入路徑段bij。然后，根據競標價降序，依次判斷路口等待隊列中其他AGV進入路徑段bij是否會引發(fā)環(huán)路死鎖。若存在某臺AGV不會引發(fā)死鎖，則將其加入AGV通行序列的末端；否則，需要對路口等待隊列中競標價最小的AGV重新規(guī)劃運行路徑，或采取其他人工干預方法解決。理論上看，根據環(huán)路死鎖的形成機制，位于路徑段bni隊列首位的AGV進入路徑段bij不會引發(fā)環(huán)路死鎖。因為每臺AGV進入阻塞環(huán)路前，都必須進行環(huán)路死鎖檢測，若發(fā)現(xiàn)死鎖，則不允許該AGV進入環(huán)路，所以對于已進入環(huán)路、處于其組成路徑段上的AGV，其本身在環(huán)路中運行是不會發(fā)生死鎖的。

4 實驗

4.1 仿真模型創(chuàng)建

為驗證上述帶防死鎖策略的交叉路口通行順序優(yōu)化方法，本文采用仿真軟件Plant Simulation創(chuàng)建裝配線物流系統(tǒng)的仿真模型，如圖7所示。AGV和導引路徑分別使用Transporter和Track對象表示，工位點功能通過在Track對象增加Sensor對象實現(xiàn)，各種交通管控方法通過在Method對象中編制Simtalk程序實現(xiàn)。多載量AGV系統(tǒng)進行仿真實驗的相關參數(shù)如表1所示。

表1 實驗參數(shù)設置

為保證裝配工位的多種裝配物料準時配送，必須設法避免多AGV的運動沖突與環(huán)路死鎖。因此，任務準時率和環(huán)路死鎖次數(shù)是驗證交通管控方法有效性的重要指標。需要注意的是，物流系統(tǒng)中AGV數(shù)量對任務準時率和環(huán)路死鎖次數(shù)有很大影響。AGV數(shù)量過少，勢必造成多個物料配送任務難以及時響應，從而降低整個物流系統(tǒng)的任務準時率；AGV數(shù)量過多，必然加重路徑網絡中的交通負荷和路徑阻塞，運動沖突頻繁并可能引發(fā)環(huán)路死鎖，反而導致任務準時率下降甚至系統(tǒng)運行中斷。

在綜合競標價模型融合AGV緊迫度與交通負荷均衡度時，所用權值w1和w2可能影響AGV競標結果與優(yōu)化方法的有效性，因此本文先通過仿真實驗選取綜合競標價模型的權值w1和w2。假設裝配線的生產節(jié)拍為25 min，單載量AGV和多載量AGV的數(shù)量為3和6，分別設置5組不同的權值。根據綜合競標價模型進行多AGV在交叉路口的通行順序優(yōu)化，獲得的實驗結果如表2所示。

表2 不同權值w1和w2的任務準時率

由表2可知，當權值w1和w2均為0.5時，AGV系統(tǒng)的任務準時率最高。一方面，當交通負荷均衡度的權值高于AGV緊迫度權重時，緊急任務不能及時被處理，從而降低AGV系統(tǒng)的準時率，如組1和組2數(shù)據所示。另一方面，當交通負荷均衡度的權值低于AGV緊迫度權重時，交通負荷不均衡可能引發(fā)路徑網絡堵塞，反而降低AGV系統(tǒng)的準時率，如組4和組5數(shù)據所示。因此，本文充分考慮AGV緊迫度與交通負荷均衡度的共同影響，w1和w2采用相同的權值。

4.2 實驗數(shù)據分析

首先研究物流系統(tǒng)中的AGV數(shù)量對任務準時率和環(huán)路死鎖次數(shù)的影響。假設裝配線的生產節(jié)拍為25 min，分別設置6組數(shù)量不同的單載量AGV和多載量AGV，如表3所示。采用仿真軟件Plant Simulation進行裝配線物流系統(tǒng)的運行仿真，比較分析交叉路口無優(yōu)化、僅考慮交通負荷均衡度、僅考慮AGV緊迫度、綜合競標價優(yōu)化4種方法的實驗結果。

表3 系統(tǒng)AGV數(shù)量配置

由于發(fā)生環(huán)路死鎖后人工干預的處理時間具有不確定性，給任務準時率的計算帶來了較大困難。更重要的是，環(huán)路死鎖會中斷系統(tǒng)運行，為任務準時率帶來災難性后果。因此，本節(jié)在討論任務準時率時，上述4種方法均采用死鎖預測與避免策略，即在無死鎖的前提下比較分析各種方法的任務準時率，實驗結果如圖8所示。

由圖8可知，當物流系統(tǒng)中的AGV數(shù)量較少時，上述4種方法的任務準時率相差很大。若不對多AGV在交叉路口的通行順序進行優(yōu)化，其任務準時率僅有47.12%；若在交叉路口采用綜合競標價進行優(yōu)化，其任務準時率可達93.56%，相對前者提高了98.5%以上。這是因為任務緊迫度高的AGV在交叉路口可優(yōu)先通過。當AGV數(shù)量增加到第2組配置以后，各種方法的任務準時率均有提高。到第7組配置時，無優(yōu)化方法的任務準時率為95.87%，綜合競標價方法的任務準時率可達99.77%，相對前者仍提高了4.0%以上。并且，當AGV數(shù)量配置增加到第3組配置以后，每種方法的任務準時率變化很小。這是因為在仿真實驗中，裝配線的生產節(jié)拍是固定的，即使AGV總量增多，但在實驗過程中采用死鎖預測與避免策略時，用于物料配送的工作AGV數(shù)量增加有限，而空閑AGV在等待點等待，不影響工作AGV在路徑網絡中的通行?？梢姡瑢Χ郃GV在交叉路口進行通行順序優(yōu)化，可保證任務緊迫度高的AGV優(yōu)先通過，降低路口相關路徑段的交通擁堵，減少AGV通過路徑網絡的延誤時間，從而提高任務準時率。

下面研究死鎖預測與避免策略的重要性，比較分析交叉路口無防死鎖且無優(yōu)化、無防死鎖的通行順序優(yōu)化、帶防死鎖的通行順序優(yōu)化3種方法的實驗結果，如圖9所示。當物流系統(tǒng)中的AGV數(shù)量較少時，各路徑段的剩余長度充足，上述3種方法均不會產生環(huán)路死鎖。然而，當AGV數(shù)量增加到第4組配置以后，無優(yōu)化方法首先出現(xiàn)環(huán)路死鎖；到第5組配置時，無防死鎖的通行順序優(yōu)化方法也出現(xiàn)了環(huán)路死鎖；而帶防死鎖的通行順序優(yōu)化方法始終不會產生死鎖。這是因為隨著路徑網絡中AGV數(shù)量的增加，各路徑段的交通負荷愈發(fā)加重。若AGV通過交叉路口時，未考慮目標路徑段的剩余長度，極易造成路徑段阻塞，進而引發(fā)環(huán)路死鎖。即使在交叉路口優(yōu)化AGV通行順序，可實現(xiàn)均衡路徑段交通負荷、降低路徑段阻塞概率的作用；然而，隨著AGV數(shù)量的增加，環(huán)路死鎖不可避免。由此可見，死鎖預測與避免策略在高密度AGV系統(tǒng)交通管控中的必要性。

5 結束語

采用多載量AGV可在不降低AGV系統(tǒng)整體運輸能力的前提下減少AGV數(shù)量，有利于減輕共享路徑網絡中的沖突與死鎖，從而保證整條裝配生產線的多種裝配物料準時配送。

首先分析與單載量AGV差異較大的兩種運動沖突：針對多載量AGV長度不斷變化的特點，設計一種變長度AGV路徑空間沖突避免方法；針對交叉路口沖突，考慮到多載量AGV變長特性對阻塞環(huán)路死鎖的影響，提出一種帶防死鎖策略的交叉路口通行順序優(yōu)化方法。根據AGV緊迫度和交通負荷均衡度構建綜合競標價模型；對獲標AGV目標路徑段的阻塞環(huán)路進行死鎖預測，若其會引發(fā)環(huán)路死鎖，則采用死鎖避免方法選擇其他AGV或采用人工干預方法。仿真實驗結果表明，在交叉路口進行通行順序優(yōu)化，可顯著減少AGV通過路徑網絡的延誤時間，任務準時率最大可提高98.5%以上；隨著系統(tǒng)中AGV數(shù)量的增加，僅采用通行順序優(yōu)化方法無法完全避免環(huán)路死鎖，必須采用死鎖預測與避免策略。

值得注意的是，本文研究多載量AGV系統(tǒng)的交通管控問題僅針對單向導引路徑網絡。未來，還可將該問題拓展到雙向導引路徑網絡的復雜場景進行研究。