多載量AGV系統(tǒng)防死鎖路口通行順序優(yōu)化及避碰

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

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

0 引言

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

為避免AGV并發(fā)運(yùn)行時(shí)的運(yùn)動(dòng)沖突，已有研究提出了3類(lèi)沖突避免方法：

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

(2)區(qū)域控制方法[10-11]該類(lèi)方法將路徑網(wǎng)絡(luò)分割為多個(gè)互不重疊、可供不同AGV分時(shí)占用的運(yùn)行區(qū)域，但任意時(shí)刻每個(gè)運(yùn)行區(qū)域還只允許一臺(tái)AGV運(yùn)行[12]。

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

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

除了物理設(shè)施層面的專(zhuān)用運(yùn)行區(qū)域設(shè)置，其他沖突避免方法都必須解決共享交通資源(運(yùn)行區(qū)域、路徑等)的排他性占用，即會(huì)發(fā)生某臺(tái)AGV因?yàn)樗璧慕煌ㄙY源被其他AGV占用而暫時(shí)不能運(yùn)動(dòng)的情況(阻塞)。如果多臺(tái)AGV出現(xiàn)了循環(huán)阻塞，則會(huì)產(chǎn)生因路徑?jīng)_突引發(fā)的死鎖，且死鎖類(lèi)型與所采用的沖突避免方法有關(guān)。MOORTHY等[23]針對(duì)采用區(qū)域控制的AGV系統(tǒng)，提出一種“檢測(cè)目標(biāo)區(qū)域的前一區(qū)域是否空閑”的環(huán)路死鎖預(yù)測(cè)方法。針對(duì)雙向?qū)б窂骄W(wǎng)絡(luò)，SHAO等[24]研究了“直接死鎖”和“因堵塞造成的死鎖”的死鎖避免方法;肖海寧等[17]針對(duì)單向?qū)б窂骄W(wǎng)絡(luò)，提出一種基于有向圖狀態(tài)模型的環(huán)路死鎖搜索與避免方法。

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

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

1 問(wèn)題描述

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

針對(duì)傳統(tǒng)配送準(zhǔn)時(shí)性差的問(wèn)題，考慮到裝配工位物料種類(lèi)多、配送要求差異性大的實(shí)際需求，本文采用多載量AGV在輔料庫(kù)與裝配工位之間配送標(biāo)準(zhǔn)機(jī)械零件和電子元器件，利用單載量AGV在半成品庫(kù)與裝配工位之間配送用于部裝的套件、組件等。整條裝配生產(chǎn)線包括A艙部裝線、C艙部裝線和艙段總裝線，以及外協(xié)生產(chǎn)部裝的B艙、D艙和E艙的3條輸送線，如圖1所示。裝配生產(chǎn)線中的AGV系統(tǒng)采用單向?qū)б窂骄W(wǎng)絡(luò)。

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

(1)當(dāng)某一裝配工作站所需的所有裝配工件都齊套且該工作站已空閑時(shí)，則開(kāi)始下一個(gè)裝配任務(wù)。每個(gè)裝配工作站每次只能裝配一個(gè)部件，且裝配作業(yè)過(guò)程不能中斷。

(2)裝配完成的組件/部件進(jìn)入裝配工作站的輸出緩沖區(qū)，等待AGV搬運(yùn)到下一個(gè)目標(biāo)工作站，完成所有裝配工序的成品經(jīng)輸出工作站離開(kāi)裝配生產(chǎn)線。

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

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

(5)AGV開(kāi)始執(zhí)行物料配送任務(wù)時(shí)，通過(guò)路徑規(guī)劃在單向?qū)б窂骄W(wǎng)絡(luò)中搜索一條從當(dāng)前位置到目標(biāo)工作站的單向最短路徑。并且，在交通管控過(guò)程中不采用路徑重規(guī)劃的方法避免AGV系統(tǒng)的運(yùn)動(dòng)沖突。

(6)空閑AGV停留在特定的任務(wù)等待點(diǎn)等待下一個(gè)物料配送任務(wù)，且不影響其他AGV在路徑網(wǎng)絡(luò)中的通行。

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

2 研究方案

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

2.1 運(yùn)動(dòng)沖突類(lèi)型

在單向?qū)б窂骄W(wǎng)絡(luò)中，AGV系統(tǒng)可能存在4種發(fā)生碰撞的運(yùn)動(dòng)沖突[17]。推廣到多載量AGV系統(tǒng)，運(yùn)動(dòng)沖突的形式如圖2所示。其中，圖2a表示一臺(tái)靜止的AGV2阻礙其后另一臺(tái)AGV1沿路徑運(yùn)行的路徑點(diǎn)沖突，圖2b表示兩條導(dǎo)引路徑相距較近而引發(fā)的AGV轉(zhuǎn)向空間沖突，這兩種沖突避免方法與單載量AGV系統(tǒng)類(lèi)似，因此不再贅述。

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

圖2d表示交叉路口沖突，即兩臺(tái)AGV因意圖同時(shí)通過(guò)同一交叉路口發(fā)生運(yùn)動(dòng)沖突。為避免該沖突，文獻(xiàn)[17]已在交叉路口的入口點(diǎn)定義加鎖點(diǎn)，在出口點(diǎn)定義解鎖點(diǎn)。只有加鎖點(diǎn)在交通管控系統(tǒng)中未加鎖，AGV才能被允許進(jìn)入該路口；且AGV進(jìn)入路口后加鎖點(diǎn)加鎖。當(dāng)AGV離開(kāi)出口點(diǎn)時(shí)，觸發(fā)解鎖點(diǎn)的解鎖信號(hào)，對(duì)加鎖點(diǎn)進(jìn)行解鎖。可見(jiàn)，傳統(tǒng)方法僅采用互斥機(jī)制解決多AGV在交叉路口的沖突，并未考慮AGV在交叉路口的通行順序。

2.2 總體研究方案

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

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

2.3 路段避碰方法

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

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

(1)

對(duì)于第j條路徑段，假設(shè)其總長(zhǎng)度為L(zhǎng)tj，在作業(yè)時(shí)刻t，該路徑段的AGV數(shù)量為m，AGV之間的安全間距為L(zhǎng)s，則該路徑段的剩余長(zhǎng)度

(2)

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

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

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

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

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

(1)綜合競(jìng)標(biāo)價(jià)模型

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

(2)AGV緊迫度

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

1)多載量AGV緊迫度。

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

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

(3)

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

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

(4)

對(duì)第i臺(tái)多載量AGV的第j個(gè)配送任務(wù)，假設(shè)其截止時(shí)間為T(mén)ij，則任務(wù)緊迫度

(5)

對(duì)執(zhí)行Nj個(gè)配送任務(wù)的多載量AGV，其緊迫度

(6)

2)單載量AGV緊迫度。

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

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

(7)

假設(shè)該任務(wù)的截止時(shí)間為T(mén)i，則AGV緊迫度

(8)

(3)交通負(fù)荷均衡度

由圖5可知，交通負(fù)荷均衡度受AGV所在路徑段和下一路徑段的交通流影響。對(duì)第i臺(tái)多載量AGV，在作業(yè)時(shí)刻t，假設(shè)其當(dāng)前所處路徑段的總長(zhǎng)度為L(zhǎng)tp，已有mp臺(tái)AGV；申請(qǐng)進(jìn)入的下一路徑段的總長(zhǎng)度為L(zhǎng)tq，已有mq臺(tái)AGV；則當(dāng)前所處路徑段的交通負(fù)荷ηp和下一路徑段的交通負(fù)荷ηq分別為：

(9)

(10)

則第i臺(tái)AGV在交叉路口的路徑段交通負(fù)荷均衡度

(11)

(4)綜合競(jìng)標(biāo)價(jià)

在圖5所示的綜合競(jìng)標(biāo)價(jià)模型中，假設(shè)融合AGV緊迫度與交通負(fù)荷均衡度時(shí)所用的權(quán)重分別為w1和w2(具體數(shù)值需要通過(guò)仿真實(shí)驗(yàn)獲得)，則綜合競(jìng)標(biāo)價(jià)

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

(12)

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

3.3 死鎖預(yù)測(cè)與避免

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

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

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

4 實(shí)驗(yàn)

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

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

表1 實(shí)驗(yàn)參數(shù)設(shè)置

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

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

表2 不同權(quán)值w1和w2的任務(wù)準(zhǔn)時(shí)率

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

4.2 實(shí)驗(yàn)數(shù)據(jù)分析

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

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

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

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

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

5 結(jié)束語(yǔ)

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

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

值得注意的是，本文研究多載量AGV系統(tǒng)的交通管控問(wèn)題僅針對(duì)單向?qū)б窂骄W(wǎng)絡(luò)。未來(lái)，還可將該問(wèn)題拓展到雙向?qū)б窂骄W(wǎng)絡(luò)的復(fù)雜場(chǎng)景進(jìn)行研究。