AGV數量與工作任務匹配方法研究

沈秋英

[提要] 多軌道交互式的AGV生產系統存在多個工作臺、多個AGV和多條運行軌道，生產過程中的各種信息實時進行交互。每個AGV在運行過程當中根據即時的系統狀態選擇當前的工作任務和運行路線。系統的復雜性和AGV決策的即時性使得難以預先將AGV的數量和工作任務進行合理的匹配。本文采用多Agent仿真理論對多軌道交互式AGV調度系統進行仿真模擬，可以預先模擬系統運行狀態，從而將工作任務和AGV的數量進行合理匹配。該方法可以在一定的工作任務下預先確定需要的AGV數量，也可以在一定的AGV數量下確定能夠承擔的最大工作任務，同時還可以在一定的AGV數量和工作任務下，預先確定需要的工作時間。

關鍵詞：多主體仿真;AGV;任務;匹配

中圖分類號：F27 文獻標識碼：A

收錄日期：2018年3月28日

一、引言

無人搬運車（簡稱AGV）是裝備有電磁或光學等自動引導裝置，能夠沿規定的引導路徑行進，具有安全保護以及各種移載功能的運輸車輛。AGV在工業應用中不需要駕駛員，以可充電的蓄電池作為其動力來源，透過計算機系統來控制其行進路線和行為。通常利用電磁軌道來設立AGV的行進路線。電磁軌道貼在地板上，AGV則依循電磁軌道所帶來的信息進行移動與動作。目前，AGV系統在電子、鋼鐵、食品等行業有較為廣泛的應用。AGV系統與其他的物流輸送系統相比，具有環境的適應性強、布局柔性高、方便維護、自動化程度高、便于維護等優點，對提高生產效率、降低生產成本從而加速企業發展有著重要意義。

單臺AGV的簡單系統的活動范圍和作業能力是有限的，隨著工廠自動化規模日益擴大，已不能滿足提高自動化系統生產效率的要求。目前，AGV系統大都是由多臺AGV構成的多軌道、交互式系統。在這類系統中，多個AGV在同一時間和空間內同時運行，形成了一個離散事件的動態系統，進而導致了一系列的管理難題。目前對AGV系統的研究主要集中在路經規劃、任務調度和沖突處理三個方面。文獻建立了單機器人多工作站的制造系統調度模型，并開發了相應的多項式算法。文獻建立了多機器人多工作站的制造系統調度模型，并開發了相應的多項式算法，但是沒有考慮機器人的碰撞問題。文獻開發了兩機器人制造單元調度問題的有效算法，但該方法無法解決超過兩個機器人的調度問題。這些研究都是針對系統某一方面的問題展開，然而由于系統的復雜性、離散性和即時性，系統的總體特征規律尚難以獲取。因此，現有研究尚未解決AGV的數量和工作任務的匹配問題。即對于特定系統，在一定的工作任務下達后，需要多少臺AGV可以按時完成任務;或在一定的AVG數量和工作時間要求下，最多能夠完成多少工作任務。上述問題的存在給企業生產計劃的制定帶來很大困難。同時，由于AGV價格昂貴，購置多余的AGV也給企業增加了大量的生產成本。

本文根據多軌道、交互式AGV生產調度系統所具有的復雜性、離散性和決策的即時性等特點，提出采用多Agent仿真理論對多軌道交互式AGV調度系統進行仿真模擬，通過在特定的系統參數下模擬系統運行狀態，獲取特定系統狀態下工作任務、AGV數量和總工作室間等變量之間的相互關系，從而實現將工作任務和AGV的數量進行合理匹配。采用這一方法可以在一定的工作任務下預先確定需要的AGV數量，也可以在一定的AGV數量下確定能夠承擔的最大工作任務，同時還可以在一定的AGV數量和工作任務下，預先確定需要的工作時間。經過現場的實際工程實施，表明該方法穩定可靠、實施簡便，AGV生產調度系統的設計和實施方面效果明顯。

二、多軌道、交互式AGV生產調度系統描述

多軌道、交互式AGV生產調度系統通常由一系列固定裝置和多臺AGV構成。其中，固定裝置一般包括一個裝載臺、一個卸載臺、多個工作臺和多個AGV等待區，上述四類裝置之間有固定的電磁軌道相連。生產任務啟動后，由AGV將裝載臺上存放的待加工工件運送到不同的工作臺進行加工。各個工作臺的加工時間已知;同一個工件不能同時被兩個或多個工作臺同時加工，一個工作臺也不能同時加工超過額定數量的工件。工件在工作臺上完成加工后，由AGV將其運送至卸載臺進行存放。系統中的多臺AGV可同時運行在預先設定的電磁軌道上，專門負責工件在生產過程中的搬運作業，它們之間在運行過程中不能碰撞;每一個特定搬運工作只能由一個AGV執行，同一個AGV在同一時刻只能完成一項搬運任務。

系統通過掃描裝載臺和工作臺的狀態來觸發任務。首先掃描裝載臺的狀態，當裝載臺不為空時，系統記錄裝載臺上的工件種類和數量，然后掃描相應的工作臺是否空閑。如果沒有空閑的工作臺，則進行等待;如果有相應的空閑工作臺，系統計算所有AGV完成現有任務，然后到裝載臺裝載待加工工件并將其運送到相應工作臺的最短路線和所需要的最短時間。然后將任務指派給所需時間最短的AGV。當工作臺不為空，且完成加工作業時，系統計算所有AGV完成現有任務，然后到工作臺裝載完成加工的工件，并將其運送至卸載臺所需的最短路線和對應的最短時間，將任務指派給所需時間最短的AGV。AGV沿著地面上鋪設的電磁軌道運行，電磁軌道既有單向路段又有雙向路段。AGV完成搬運作業后，如未接到新的指令，則運行至最近的AGV等待區進行等待。當所有工件都完成加工并運送到卸載臺時，工作任務完成。

三、基于多Agent仿真的多軌道、交互式AGV調度系統建模

本文采用多Agent仿真理論對多軌道、交互式AGV生產調度系統進行仿真模擬，通過在特定的系統參數下模擬系統運行狀態，獲取特定系統狀態下工作任務、AGV數量和總工作室間等變量之間的相互關系，從而實現將工作任務和AGV的數量進行合理匹配的目的。本文建模過程主要包括四個步驟：（1）對AGV生產調度系統的設施布局進行測量，獲取系統內部各裝置的具體信息;（2）采用多Agent仿真理論，根據步驟（1）測量獲取的數據，建立AGV調度系統仿真模型，模擬生產過程中各裝置的位置和AGV的運行規則;（3）對任意生產任務，運行步驟（2）所建立的仿真模型，得到不同AGV數量下完成該生產任務所需的工作時間。根據獲得的數據，得到生產任務、AGV數量和工作時間的匹配關系。必要時重復運行多次，得到三者之間的統計規律;（4）根據步驟（3）所獲得的規律，將工作任務和AGV數量進行匹配。

（一）系統固定裝置及其布局的測量。系統的固定裝置主要包括一個裝載臺、一個卸載臺、多個工作臺、多個AGV等待區以及連接這些固定裝置的電磁軌道。另外，系統還包括多個可移動的AGV。對系統進行測量需要獲取的數據包括以下幾類：第一，裝載臺、卸載臺、工作臺、AGV等待區等固定裝置兩兩之間的電磁軌道長度;第二，AGV在裝載臺、卸載臺、工作臺進行裝載、卸載工作需要的時間和每個工作臺的加工時間;第三，AGV的運行速度和遇到障礙物時進行規避的反應時間。

（二）仿真模型的建立。根據上一步測量所獲得的數據，采用多Agent仿真方法對AGV生產調度系統進行建模，對系統的運行過程進行模擬。建模的過程分為以下幾步：

第一，根據裝載臺、卸載臺、工作臺、AGV等待區、電磁軌道等固定裝置的相對位置，在系統中生成工作場所的模擬環境。

第二，生成一定數量的AGV，并為AGV設定運行規則。

對于任意空閑的AGV，當接到指令將一定數量的工件從固定裝置A運送到固定裝置B時，所采取的行動規則如下：（1）路線計算。AGV計算自身位置到固定裝置A的最短路線，以及固定裝置A到固定裝置B的最短路線。（2）移動、裝載與卸載。AGV根據步驟（1）的計算結果，首先由自身位置運動到固定裝置A，然后進行裝載作業;裝載完成后，再由固定裝置A移動到固定裝置B，然后進行卸載作業。

對于任意空閑的AGV，當沒有接到工作指令且不在等待區時，所采取的行動規則如下：（1）路線計算。AGV計算自身位置到所有可用等待區的最短路線;（2）移動到等待區。AGV根據步驟（1）計算出的計算結果，移動到距離最近的等待區進行等待。

根據上述運行規則可得到AGV狀態躍遷圖如1所示。（圖1）

第三，建立系統的任務分配機制。系統任務由兩種裝置觸發，一個是裝載臺，一個是工作臺。當裝載臺或任意一臺工作臺不為空時，即觸發任務分配機制。系統任務分配機制流程圖如圖2所示。（圖2）

裝載臺的任務觸發機制如下：（1）當裝載臺的狀態不為空時，裝載臺首先根據工件種類對工作臺進行匹配，然后在匹配的工作臺中搜尋是否有空閑的工作臺;如果有空閑的工作臺，則進入對AGV的選擇和任務指派程序。如果沒有空閑的工作臺，則等待匹配工作臺完成加工作業。（2）AGV的選擇和任務指派。計算當前沒有作業的每一個AGV到裝載臺裝載工件并運送到每一個工作臺的最短路徑及相應的作業時間。將作業任務指派給相應作業時間最短的AGV，并給該AGV發送指令。

工作臺的任務觸發機制如下：（1）當工作臺狀態不為空，且已完成加工作業時，進入AGV的選擇和任務指派程序;（2）AGV的選擇和任務指派。計算當前沒有作業任務的每一個AGV移動到相應工作臺裝載工件，并將工件運送到卸載臺的最短路徑及相應的作業時間。將作業任務指派給相應作業時間最短的AGV，并給該AGV發送指令。

根據上述規則得到工作臺狀態躍遷圖，如3所示。（圖3）

第四，建立AGV免碰撞機制。在多AGV任務調度系統中，往往存在著AGV之間的沖突問題，如何避免AGV之間的碰撞是多AGV任務調度的重要組成部分。AGV的碰撞問題通常可以分為節點沖突和相向沖突兩類。節點沖突為兩個及兩個以上AGV同時通過一個節點時產生的沖突問題。相向沖突為某個AGV占據其他AGV的運行路線或目標節點時產生的沖突問題。兩類沖突示意圖如圖4所示。（圖4）

為避免相撞，本文設定AGV在移動過程中，實時對沿軌道向前延伸2米處所有可能通路的占用情況進行探測。如軌道被占用，則停止移動并等待3～5秒后繼續向前運動。為防止兩個以上AGV的相互等待陷入死循環，等待時間為3～5秒之間的一個隨機數。

（三）仿真結果的獲取。本文采用仿真軟件Netlogo實現對上述模型的編程工作。然后在不同的生產任務和AGV數量下反復運行上述模型，得到生產任務、AGV數量和完成生產任務所需時間的相互關系。設所需加工的工件數量為N，AGV數量為n，完成生產任務所需的平均時間為T（N，n），將反復運行上述模型得到的數據列入表1。（表1）

（四）AGV數量與工作任務匹配。根據表1所得到的生產任務、AGV數量和總的生產時間之間的相互關系，對生產任務和AGV數量進行匹配。通過三者之間的匹配可以分別對生產任務安排、AGV數量需求和生產時間安排三個方面做出相應決策，具體如下：第一，當AGV數量為n，所需加工的工件數量為N時，通過查表得到完成該生產任務所需的時間為T（N，n）。將時間單位換算為小時（下同）。然后，根據每天工作的小時數，即可得到完成該生產任務所需的天數。如每天工作8小時，則所需工作天數位T（N，n）/8;第二，當AGV數量為n，可供完成生產任務的時間限制為T（N，n）時，通過查表可得到最多能夠加工的工件數目N;第三，當在一定的時間限制T（N，n）下，所需加工的工件數為N時，通過查表可得到所需要的AGV個數n。

四、應用實例

選擇江蘇省電力科學研究院計量中心計量資產自動檢測系統作為實施對象。國家電網江蘇省計量中心擁有全國規模最大的自動化檢定線，年檢定單相電能表800萬只，三向電能表80萬只。檢定過程如下：自動化庫房與檢定區的接駁區共6個接駁位。待檢定的電能表由自動化庫房運送到接駁位，然后由AGV將電能表從檢定區接駁處輸送到檢定臺體，機械臂完成取表、定位、掛表，檢定臺完成檢定任務后，由AGV將電能表輸送回接駁處，送至負一樓自動化封印線進行分揀。AGV的運行路線由地面固定的多條電磁軌道進行導引。該檢定系統為典型的多軌道交互式AGV調度系統。通過實地測量得到該系統的AGV工作環境模擬圖如圖5所示。（圖5）

其中，藍色長條為檢定臺;黃線為AGV運行的有向電磁軌道;白色方格為進貨口和出貨口。本實例實施步驟如下：

（一）本實例中，裝載臺和卸載臺均為接駁區，工作臺為4個電能表檢定臺，另外系統還有4個AGV等待區，以及一個將這些固定裝置連在一起的一個電磁軌道系統。電磁軌道系統為2條主軌道和3條將主軌道連在一起的分軌道。其中，主軌道為單項軌道，分軌道為雙向軌道。對上述各固定裝置進行測量后得到兩兩之間的電磁軌道長度如表2所示。（表2）

AGV在接駁處進行裝載和卸載所需要的時間為每次3秒，在檢定臺進行裝載和卸載所需要的時間為每次9秒，每個檢定臺的檢定時間為180秒。AGV的運動速度為3m/s，遇到障礙物時停車等待的時間為3～5秒之間均勻分布的一個隨機數。

（二）根據接駁處、檢定臺、AGV等待區、電子軌道等固定裝置的相對位置，在系統中生成工作場所的模擬環境。生成12個AGV，并為AGV設定運行規則如下：

對于任意空閑的AGV，當接到指令將一定數量的工件從固定裝置A運送到固定裝置B時，所采取的行動規則如下：（1）路線計算。AGV計算自身位置到固定裝置A的最短路線，以及固定裝置A到固定裝置B的最短路線。（2）移動、裝載與卸載。AGV根據步驟1的計算結果，首先由自身位置運動到固定裝置A，然后進行裝載作業;裝載完成后，再由固定裝置A移動到固定裝置B，然后進行卸載作業。（3）規避碰撞。AGV在移動過程中，實時對沿軌道向前延伸2米處所有可能通路的占用情況進行探測。如軌道被占用，則停止移動并等待3～5秒后進行繼續向前運動。為防止兩個以上AGV的相互等待陷入死循環，等待時間為3～5秒之間的一個隨機數。

對于任意空閑的AGV，當沒有接到工作指令且不在等待區時，所采取的行動規則如下：（1）路線計算。AGV計算自身位置到所有可用等待區的最短路線;（2）移動到等待區。AGV根據步驟1計算出的計算結果，移動到距離最近的等待區進行等待。

（三）建立系統的任務分配機制。系統任務由兩種裝置觸發，一個是接駁區與自動化庫房的接駁位，一個是檢定臺。當接駁區與自動化庫房的接駁位或任意一臺檢定臺不為空時，即觸發任務分配機制。

接駁區與自動化庫房的接駁位的任務觸發機制如下：（1）當接駁區與自動化庫房的接駁位的狀態不為空時，接駁區與自動化庫房的接駁位首先根據工件種類對檢定臺進行匹配，然后在匹配的檢定臺中搜尋是否有空閑的檢定臺;如果有空閑的檢定臺，則進入對AGV的選擇和任務指派程序。如果沒有空閑的檢定臺，則等待匹配檢定臺完成加工作業。（2）AGV的選擇和任務指派。計算當前沒有作業的每一個AGV到接駁區與自動化庫房的接駁位裝載工件并運送到每一個檢定臺的最短路徑及相應的作業時間。將作業任務指派給相應作業時間最短的AGV，并給該AGV發送指令。

檢定臺的任務觸發機制如下：（1）當檢定臺狀態不為空，且已完成加工作業時，進入AGV的選擇和任務指派程序;（2）AGV的選擇和任務指派。計算當前沒有作業任務的每一個AGV移動到相應檢定臺裝載工件，并將工件運送到自動化封印線的接駁處的最短路徑及相應的作業時間。將作業任務指派給相應作業時間最短的AGV，并給該AGV發送指令。

（四）采用仿真軟件Netlogo實現對上述模型的編程工作。然后在不同的電能表檢定任務和AGV數量下反復運行上述模型，得到檢定任務、AGV數量和完成檢定任務所需時間的相互關系如表3所示。（表3）

（五）根據表3所得到的檢定任務、AGV數量和總的生產時間之間的相互關系，對檢定任務和AGV數量進行匹配。

通過上述方法，至今已經完成了3次對電能表檢測任務與AGV數量的匹配工作。第一次檢定任務為80萬只，任務期限為1個月，按照每月4周，每周5天工作制，平均每天需要檢定的任務為4萬只。通過查找表3可得，需要的AGV數量為最少11個。第二次鑒定任務為20萬只，可用AGV數量為8個，通過查找表3可知，需要的工作時間為8.5個工作日。第三次檢定任務為50萬只，可用AGV數量為12個，檢定任務的時間要求為10天，查找表3可知，50萬只電能表在12個AGV的情況下，工作時間需要11天，故對檢定任務進行了修改，降低為40萬只，此時所需的工作時間為9天。通過查表3可知，如果在10天的檢定任務要求下完成相應工作任務需要12臺AGV，因此也可購進1臺新AGV來滿足檢定任務要求。

五、總結

本文提出了采用多Agent仿真方法建立了多軌道、交互式AGV生產調度系統的仿真模型，對系統運行過程進行模擬，并由此對AGV數量及工作任務進行匹配的方法。本文的多軌道、交互式AGV調度系統仿真模型根據對AGV生產調度系統的設施布局進行測量得到具體信息建立，將每個AGV看作獨立決策的離散單元，在系統運行的過程中每個AGV按照自己的行動規則做出行動決策，從而總是可以為系統找出至少一個可行解。通過模擬系統運行的整個過程，最終能夠得出工作任務、機器人數量和工作時間之間的相互關系。采用擁有1個裝載臺、1個卸載臺、4個工作臺、4個AGV等待區以及一個由兩條主軌道和3條分軌道構成的電磁軌道構成的計量資產檢定系統對本文提出的方法進行了驗證，證明了本方法的實用性和有效性。

主要參考文獻：

[1]CHE A，CHU C B，L EVNER E.A polynomial algorithm for 2-degree cyclic robot scheduling[J].European Journal of Operational Research，2003.145（1）.

[2]CHU C B.A faster polynomial algorithm for 22cyclic robotic scheduling[J].Journal of Scheduling，2006.9（5）.

[3]CHE A，CHU C B，CHU F.Multi-cyclic hoist scheduling with constant processing times[J].IEEE Transactions on Robotics and Automation，2002.18（1）.

[4]DAWANDE M，GEISMAR H N，SETHI S P，et al.Sequencing and scheduling in robotic cells：recent developments[J].Journal of Scheduling，2005.8（5）.

[5]AGNETIS A.Scheduling no-wait robotic cells with two and three machines[J].European Journal of Operational Research，2000.123（2）.