翟晶晶，武 星，楊俊杰，胡 亞,2，樓佩煌，肖海寧

(1.南京航空航天大學機電學院，江蘇 南京 210016)(2.天奇自動化工程股份有限公司，江蘇 無錫 214187)(3.鹽城工學院機械工程學院，江蘇 鹽城 224051)

隨著科技的發(fā)展和用戶需求的多樣化，制造模式已經(jīng)由傳統(tǒng)少品種大批量的剛性制造模式轉(zhuǎn)變?yōu)檫m應個性化、多樣化的柔性制造模式。據(jù)有關(guān)統(tǒng)計，在整個柔性制造過程中有大約95%的時間是用在存儲、裝卸、搬運和等待加工等物流環(huán)節(jié)上，工序物流的運行效率直接影響著車間生產(chǎn)活動的有序進行[1]。自動導引車(automated guided vehicle, AGV)是一種最具代表性的物流輸送機器人，而由多臺AGV構(gòu)成的AGV系統(tǒng)作為一種靈活高效的物流系統(tǒng)，在制造系統(tǒng)、倉儲配送系統(tǒng)等領域有著廣泛的應用[2-3]。根據(jù)AGV可同時執(zhí)行配送任務數(shù)的不同，可將AGV分為單載量AGV[4]及多載量AGV[5]。單載量AGV在一次搬運作業(yè)中只能進行一次裝載和卸載，適合大件或半成品的運輸；相對于傳統(tǒng)的每次裝卸一次載荷的單載量AGV，多載量AGV可在一次物料配送任務中，分別從多個發(fā)料點進行多個載荷的裝載，或到多個送料點進行多個載荷的卸載，具有更高的單車運輸能力和更強的配送作業(yè)柔性。

混流生產(chǎn)作為柔性生產(chǎn)的代表，具有物料種類多、配送要求差異性大、作業(yè)協(xié)調(diào)性要求高[6-9]的特點，對調(diào)度系統(tǒng)的調(diào)度性能和準時率提出了更高要求，傳統(tǒng)的單載量AGV運輸已經(jīng)無法滿足要求。針對該問題，本文采用單載量AGV和多載量AGV共同進行物料配送，建立了異構(gòu)AGV調(diào)度控制系統(tǒng)。

1 總體方案

1.1 研究方案

針對傳統(tǒng)配送準時性差的問題，考慮到裝配工位物料種類多、配送要求差異性大的實際需求，本文設計了一種以異構(gòu)AGV為對象的調(diào)度控制軟件。該軟件具有友好的人機交互界面，內(nèi)含電子地圖數(shù)據(jù)，具有任務調(diào)度、交通管控、路徑規(guī)劃、狀態(tài)監(jiān)控、統(tǒng)計分析等功能，能夠直觀地對AGV運行狀態(tài)、任務和設備狀態(tài)進行實時監(jiān)控。其物料配送作業(yè)流程為：系統(tǒng)接收、統(tǒng)計來自叫料器的任務信息，根據(jù)任務的優(yōu)先級進行排序，并依據(jù)AGV的位置和狀態(tài)高效地將任務派發(fā)給最佳AGV；然后采用路徑規(guī)劃算法為執(zhí)行任務的AGV安排行駛路徑，并在AGV行駛過程中進行交通管控以解決路徑?jīng)_突，從而完成物料配送任務。如上所述，系統(tǒng)中的任務調(diào)度、路徑規(guī)劃和交通管控部分是整個調(diào)度控制系統(tǒng)的核心部分，也是本文的研究重點。本文利用Qt開發(fā)框架對系統(tǒng)功能進行了軟件開發(fā)，實現(xiàn)了調(diào)度控制的整體作業(yè)流程。

1.2 AGV調(diào)度控制系統(tǒng)構(gòu)成

根據(jù)典型復雜產(chǎn)品生產(chǎn)車間的問題分析和系統(tǒng)功能需求，本文設計的AGV調(diào)度控制系統(tǒng)主要由上位機管理系統(tǒng)、AGV車輛、導引路徑及輔助設備等部分組成。其中，上位機是一臺裝有AGV調(diào)度系統(tǒng)軟件的計算機，是整個調(diào)度系統(tǒng)的核心。而AGV車輛負責物料的配送任務，其在行駛過程中需通過通信傳輸系統(tǒng)實時反饋自身的位置和狀態(tài)信息，以便上位機能實時監(jiān)控，是執(zhí)行任務的主體。除此之外，輔助設備也是AGV調(diào)度系統(tǒng)正常運行不可或缺的部分，如交換機、無線接入點、定位標識(RFID識別卡)、充電樁、叫料器等。

2 調(diào)度控制系統(tǒng)核心技術(shù)

在AGV調(diào)度控制系統(tǒng)中，為了保證多臺AGV在同一工作空間中有序運行，任務調(diào)度[10]、路徑規(guī)劃[11]和交通管控[12]是三項核心的AGV系統(tǒng)級使能技術(shù)。

2.1 任務調(diào)度

任務調(diào)度的主要研究內(nèi)容是當系統(tǒng)中存在多個物料配送任務及空閑 AGV 時，在滿足一定的約束條件下，為了使系統(tǒng)的某項或某幾項性能達到最優(yōu)，確定各物料配送任務執(zhí)行的先后關(guān)系及其與空閑AGV 的分配關(guān)系。在本文設計的調(diào)度系統(tǒng)中，任務調(diào)度流程圖如圖1所示。當任務調(diào)度系統(tǒng)按周期觸發(fā)時，將任務池的任務分為單載量任務集和多載量任務集，若單載量任務集、AGV集或多載量任務集、AGV集不為空，系統(tǒng)按照任務分類和AGV類別進行物料配送任務執(zhí)行的先后關(guān)系和空閑AGV分配，完成后更新系統(tǒng)狀態(tài)等待下一觸發(fā)周期。其中，物料配送任務執(zhí)行的先后關(guān)系由任務的緊迫度決定，即每個任務都有一個交付時間。將交付時間進行排序，當前時間距離交付時間越近的任務，其緊迫度越高，則需優(yōu)先分配空閑AGV進行搬運?？臻eAGV的分配原則為任務最早完工時間原則，即優(yōu)先選取該任務預測完工時間最早的空閑AGV，完工時間預測與空閑AGV的空載距離、搬運距離、搬運速度、路徑交通流、多載量AGV的容量、多載量AGV已分配任務等因素有關(guān)。

2.2 路徑規(guī)劃

AGV調(diào)度控制系統(tǒng)路徑規(guī)劃的主要研究內(nèi)容是在指定的AGV運行環(huán)境中搜索一條從起始點到目標點的最優(yōu)或近似最優(yōu)的路徑，使系統(tǒng)的某項或某幾項性能達到最優(yōu)或者近似最優(yōu)。常用的路徑規(guī)劃算法有模擬退火法、A*算法、Dijkstra算法、人工勢場法、Floyd算法等[13]，其中，F(xiàn)loyd算法采用三重循環(huán)緊湊結(jié)構(gòu)，相對于其他算法，不需要設定相應的參數(shù)和估計函數(shù)，效率更高。因此，在本文設計的調(diào)度系統(tǒng)中采用Floyd算法計算任務的起點到終點的最短距離和路徑序列，完成路徑規(guī)劃。Floyd算法需要建立兩個n×n(n為節(jié)點總數(shù))的矩陣, 記為D和P。矩陣D中的元素a[i][j](1≤i≤n，1≤j≤n)表示從頂點i到頂點j的距離，若兩點之間沒有直接連接，則距離為∞；而矩陣P中的元素b[i][j]則表示從頂點i到頂點j中間經(jīng)過的頂點, 初始狀態(tài)下為b[i][j]元素的j值，算法流程圖如圖2所示。

圖1 任務調(diào)度流程圖

圖2 Floyd算法流程圖

2.3 交通管控

AGV調(diào)度控制系統(tǒng)的交通管控側(cè)重于解決多臺AGV并發(fā)運行時可能產(chǎn)生的運動沖突、碰撞。在單向?qū)б窂骄W(wǎng)絡中，AGV系統(tǒng)可能存在4種發(fā)生碰撞的運動沖突，如圖3所示。

圖3 異構(gòu)AGV的典型運動沖突

針對這4種沖突，本文調(diào)度系統(tǒng)中采用的解決方案如下：

1)針對圖3(a)中的路徑點沖突，需AGV1提前減速直至停車，待AGV2開始運動時，AGV1重新啟動繼續(xù)運行。若AGV2因故障長時間滯留在行駛路徑上而導致路徑被占用，就會變成不可解決的沖突，此類沖突通常需要人工干預才能順利排除。

2)針對圖3(b)中的AGV轉(zhuǎn)向空間沖突，由于多載量AGV的變長特性，若兩條導引路徑相距較近，AGV轉(zhuǎn)向時可能會產(chǎn)生碰撞。因此當某一時間段有兩輛AGV分別進入兩條相距較近的導引路徑時，系統(tǒng)基于兩輛AGV的長度進行沖突判斷，若不會發(fā)生轉(zhuǎn)向空間沖突，則允許兩輛AGV同時進入對應路徑；否則，需在兩條路徑上設置虛擬加鎖點，當其中一條路徑AGV進入路口后，另一條路徑加鎖點加鎖，阻止其他AGV進入。當AGV離開出口點時，觸發(fā)解鎖點的解鎖信號，對加鎖點進行解鎖。

3)針對圖3(c)中的路徑空間沖突，即AGV1由于即將進入的路徑段無剩余空間而占用交叉路口，進而阻礙AGV4的通行。對于變長型異構(gòu)AGV系統(tǒng)，在AGV通過交叉路口進入目標路徑之前，必須檢測該路徑是否有足夠的剩余長度，如果足夠，則允許該AGV進入目標路徑，否則AGV將在路口等待。

4)針對圖3(d)中的交叉路口沖突，可以將所有請求進入其中的AGV組成AGV等待隊列，并根據(jù)任務緊迫度和路徑段交通流計算等待隊列中所有AGV的綜合競標價，其中競標價最高的獲標AGV獲得該路口的優(yōu)先通行權(quán)。通過此方法可以優(yōu)化AGV通過交叉路口的順序，獲得交叉路口AGV通行序列。最后，采用包含加鎖點和解鎖點的路口互斥機制，控制AGV有序地通過交叉路口。

3 系統(tǒng)功能實現(xiàn)

根據(jù)異構(gòu)AGV調(diào)度控制系統(tǒng)的功能需求和作業(yè)流程，本文設計的AGV調(diào)度控制系統(tǒng)由用戶層、功能層和數(shù)據(jù)層組成，其軟件結(jié)構(gòu)如圖4所示。其中，用戶層及功能層的絕大多數(shù)子模塊均有圖形交互界面，而數(shù)據(jù)層則是抽象的信息流。

圖4 AGV調(diào)度系統(tǒng)軟件結(jié)構(gòu)圖

Qt是一個優(yōu)秀的跨平臺C++圖形用戶界面應用程序開發(fā)框架，能較快捷地搭建用戶界面。數(shù)據(jù)層信息多而分散，且各模塊之間需要共享，故采用數(shù)據(jù)庫作為信息的存儲方式。MySQL是一種關(guān)系型數(shù)據(jù)庫管理系統(tǒng)，關(guān)系數(shù)據(jù)庫將數(shù)據(jù)保存在不同的表中，提高了系統(tǒng)的速度和靈活性。因此，本文基于Qt開發(fā)框架和MySQL數(shù)據(jù)庫，采用面向?qū)ο蟮木幊谭椒ㄟM行軟件開發(fā)。

3.1 任務調(diào)度模塊

任務調(diào)度作為調(diào)度系統(tǒng)三大核心技術(shù)之一，決定著任務的執(zhí)行順序與執(zhí)行對象，直接影響著工位的生產(chǎn)效率。該模塊的數(shù)據(jù)來自新產(chǎn)生任務的數(shù)據(jù)表，該表存有任務的類型、起點終點的裝卸載方式、任務創(chuàng)建時間、交付時間等信息，如圖5所示。基于以上信息可計算新任務列表的緊迫度并進行排序，并結(jié)合空閑AGV信息和路徑信息計算最早完工時間，完成任務分配。其中，任務調(diào)度模塊類結(jié)構(gòu)中成員變量包含裝卸載任務時間、交通系數(shù)、自定義地圖類、操作數(shù)據(jù)庫類、任務池、任務發(fā)布周期等；成員函數(shù)包含任務池開啟函數(shù)、獲取緊迫度最高的任務信息函數(shù)、搜尋最佳AGV函數(shù)、計算任務時間函數(shù)、任務發(fā)布函數(shù)等。

圖5 新產(chǎn)生任務的數(shù)據(jù)表

3.2 路徑規(guī)劃模塊

路徑規(guī)劃模塊依賴電子地圖數(shù)據(jù)，而電子地圖數(shù)據(jù)是實現(xiàn)通過配套的地圖繪制軟件進行環(huán)境建模，包含路徑段、路徑端點、工位點等數(shù)據(jù)信息，最后以XML形式保存。同時，各個交叉點之間的最短距離表和路由表在創(chuàng)建地圖時由路徑規(guī)劃算法得到，任務調(diào)度模塊和路徑規(guī)劃模塊可直接從最短距離表和路由表中提取信息，并根據(jù)任務的起止工位號，在單向路徑上規(guī)劃理論最佳行駛路徑，大大優(yōu)化路徑規(guī)劃流程，提升軟件運行效率。例如：工位0到工位1最短路徑如圖6所示。

圖6 路徑規(guī)劃示意圖

3.3 交通管控模塊

對于交通管控中的4種運動沖突情形，由于AGV裝有避障傳感器，可以避免圖4(a)的路徑點沖突情況，因此系統(tǒng)進行交通管控時主要考慮后3種沖突情形。為保存交叉點加鎖狀態(tài)和路徑容量等信息，本文分別創(chuàng)建交叉點結(jié)構(gòu)體與路徑結(jié)構(gòu)體，交叉點結(jié)構(gòu)體中包含路徑端點編號、加鎖狀態(tài)、占用AGV編號和可讀性信息；路徑結(jié)構(gòu)體包含路徑編號、剩余長度、路徑上存在的AGV數(shù)量和編號信息。當某AGV經(jīng)過加鎖點時，向AGV調(diào)度系統(tǒng)發(fā)送請求進入指令，當交叉點未被占用且即將進入路徑端剩余長度足夠時，調(diào)度系統(tǒng)回復通行指令，否則該AGV將停在加鎖點，并以固定間隔發(fā)布請求進入指令，直至有占用交叉點的AGV解鎖該交叉點或下一路徑段上的AGV離開下一路徑段時，若導致通行條件滿足，即交叉點未被占用且即將進入路徑端剩余長度足夠，則允許停在加鎖點的AGV通行。AGV到達解鎖點后，解除占用該交叉點，同時更新先前路徑與新進入路徑的容量信息。若發(fā)生多輛AGV同時競爭某交叉點，如圖4(d)所示情況，則需要先將所有請求AGV加入隊列，然后查看各AGV執(zhí)行任務信息，最后綜合考慮任務緊迫度和路徑段交通流，優(yōu)化路口通行順序。

3.4 其他模塊

除了上述三大模塊，系統(tǒng)還包含管理功能模塊、狀態(tài)監(jiān)控模塊、通訊傳輸模塊、統(tǒng)計分析模塊，各模塊的功能如下：

管理功能模塊是人機交互的主要界面，包括用戶管理、任務管理、AGV管理，如圖7所示。用戶管理具有創(chuàng)建、刪除賬戶的功能，同時改變各用戶的登錄權(quán)限，保證系統(tǒng)的安全性和靈活性。同時，任務管理可查看并添加/刪除任務，維護正確的任務信息。AGV的添加、刪除、系統(tǒng)配置等功能均可在該模塊實現(xiàn)。

狀態(tài)監(jiān)控包括任務監(jiān)控、AGV運行狀態(tài)監(jiān)控、路徑狀態(tài)監(jiān)控、物料狀態(tài)監(jiān)控。在系統(tǒng)運行過程中，任務和AGV運行狀態(tài)等信息不斷更新，用戶在操作過程中必須實時了解這些變化，掌握全局信息，以便應對突發(fā)情況并獲取目標信息，狀態(tài)監(jiān)控模塊就是為此設計的。其中，用戶界面的表格均與數(shù)據(jù)庫關(guān)聯(lián)，維護數(shù)據(jù)庫表信息即可實時刷新這些表格，并且AGV每個時刻的位置及路徑段、交叉點的狀態(tài)都會同步刷新，且均有相應的圖形化界面。

通訊傳輸模塊中，各設備終端均裝有串口服務器，通過虛擬串口映射至調(diào)度系統(tǒng)主機，調(diào)度系統(tǒng)通過讀取串口方式獲取信息。

圖7 管理功能模塊界面

調(diào)度系統(tǒng)的統(tǒng)計模塊以日期為單位進行數(shù)據(jù)記錄與分析，這些數(shù)據(jù)包含統(tǒng)計準時率、任務個數(shù)、AGV利用率等信息。此外，該模塊還可根據(jù)所選日期范圍查看一段時間內(nèi)某些指標值的變化趨勢。

4 調(diào)度系統(tǒng)實驗

為了測試調(diào)度系統(tǒng)的性能，在調(diào)度系統(tǒng)軟件與異構(gòu)AGV間進行通信，本文在實驗室的環(huán)境下模擬生產(chǎn)環(huán)境，其實驗布置如圖8所示。因為路徑規(guī)劃的結(jié)果直接可以從路由表得到，所以將主要測試系統(tǒng)的交通管控模塊和任務調(diào)度模塊的性能。

圖8 實驗室布置圖

對于系統(tǒng)的交通管控模塊中的沖突，主要是以加解鎖點的方式進行控制，所以需要驗證加鎖點策略的實施效果。以圖3(b)中AGV轉(zhuǎn)向空間沖突為例，當不同長度的AGV經(jīng)過同一個兩條相近路徑段時，實驗結(jié)果如圖9所示。圖9(a)所示為單載量AGV轉(zhuǎn)向空間實驗，因為單載量AGV的長度較短，在通過兩條相近路徑時，不會互相干擾，所以兩輛AGV被允許同時進入對應路徑；圖9(b)所示為多載量AGV轉(zhuǎn)向空間實驗，因為多載量AGV為變長型AGV，當AGV進入距離相近路徑時，會進行預判，結(jié)果表示會發(fā)生碰撞，所以后到的AGV在加鎖點等待另一路徑上的AGV通過。實驗結(jié)果表明，交通管理模塊可以避免AGV之間的沖突。

圖9 轉(zhuǎn)向空間沖突實驗結(jié)果

任務調(diào)度模塊中的任務由系統(tǒng)的叫料器輸入，包括任務的類型、目標工位、產(chǎn)生時間、截止時間等信息。任務將首先添加到未執(zhí)行列表中，按照任務調(diào)度方法對任務進行排序和分配AGV，并將待執(zhí)行任務添加到執(zhí)行任務列表中，同時刪除未執(zhí)行任務列表中與此任務有關(guān)的記錄。為了測試任務調(diào)度模塊的性能，本文統(tǒng)計了系統(tǒng)中的100個完成任務，執(zhí)行任務的信息包含任務編號、任務類型、目標工位、物料組號、任務產(chǎn)生時間、任務截止時間、執(zhí)行編號、執(zhí)行AGV編號、任務的完成狀態(tài)、任務完成時間、AGV的載量。完成的100個任務的準時率如圖10所示，其中單載量任務數(shù)和多載量任務數(shù)分別為41和67，準時率分別為100%和97.1%，綜合任務準時率為98%，綜合停料待產(chǎn)率為1.3%。實驗結(jié)果表明，本文研發(fā)的調(diào)度系統(tǒng)具有較高的準時率和效率。

圖10 已完成任務準時率統(tǒng)計

5 結(jié)束語

對于柔性化的混流生產(chǎn)線而言，系統(tǒng)需快速響應訂單的變化，將物料快速準確運輸?shù)焦の慌?，實現(xiàn)企業(yè)精益生產(chǎn)。而采用異構(gòu)AGV可適應不同種物料的配送，在不降低AGV系統(tǒng)整體運輸能力的前提下減少AGV數(shù)量，有利于減少共享路徑網(wǎng)絡中的沖突，從而保證整條裝配生產(chǎn)線的多種裝配物料準時配送。本文以異構(gòu)AGV為控制對象，利用Qt框架和MySQL數(shù)據(jù)庫開發(fā)設計了一種包含基于緊迫度和最早完工時間的任務調(diào)度方法、基于Floyd算法的路徑規(guī)劃算法的多種運動沖突解決方案的調(diào)度控制系統(tǒng)，實現(xiàn)了調(diào)度控制的整體作業(yè)流程。