無人倉自動搬運系統策略研究—動態任務分配

黃 穎，李 薔

（1.江蘇科技大學張家港校區，江蘇 張家港 215600；2.上海大學 管理學院，上海 200444）

1 研究的問題與現狀

1.1 無人倉發展趨勢

根據eMarketer 數據，2017年全球網絡零售交易額較2016年增長24.8%，占全球零售總額的比重進一步提升，網絡零售已成全球零售市場的強勁拉動力[1]。電商行業的高速發展，使得物流需求結構不斷改善，且在提升運營效率、降低物流成本、提高用戶體驗等方面對市場提出了更高的要求，無人倉儲系統得到了廣泛的關注。該系統通過自動化手段，實現貨物從入庫存儲到分揀出庫全流程的智能化和無人化，滿足系統柔性擴張的要求。

1.2 大規模機器人的使用

機器人的發展經歷了萌芽期、產業孕育期、快速發展期，現今已經處于智能應用階段（如圖1所示）。隨著感知、控制等技術的升級和人工智能技術在機器人領域的應用，工業機器人成為全球范圍內第一大應用市場。從2012年亞馬遜收購kiva 機器人到2017年菜鳥建立并投入運行大規模機器人倉群、京東建立完全無人倉，近年來機器人倉庫已經從過去的單點小規模使用走向了大規模使用。

工業自動化體系的應用，也經歷了從單點應用到集群化應用的發展過程。越來越多的企業意識到，與工業生產的點狀作業相比，物流體系更需要實現在面上以及立體空間內的作業。通過分布式、并行化的機器人系統可以實現自動化的物流過程，取代傳統作業中人的單調重復勞動。

相較于單點智能，群體智能具有以下優勢：

（1）群體智能基于經驗與數據共享，去除單點智能模式“中心”的概念，使數據更開放和自由，決策準確率更高且整體數據成本更低；

（2）群體智能在信息交互的過程中可以更好的完成全局行為的優化，實現1+1＞2的效果；

（3）對于較為復雜的任務和環境，設計多異構/異能機器人相互協作遠比設計一個多能力機器人要容易，且成本更低；

（4）大規模使用簡單機器人比單點使用復雜機器人的成本更低，靈活性更高；

（5）群體智能擁有更為完整的數據鏈條記錄，有利于上下游協同決策，提高整體響應速度；

（6）多機器人可以平行作業且具有冗余性，系統柔性更好、容錯率更高、魯棒性更強；

（7）多機器人系統模塊化設計更易擴展、執行更高效，在時間、功能、布局分布上更靈活。

群體智能較之單點智能，其智慧化程度更高，系統柔性更好，能夠實現個體與整體更好的良性迭代，并利用規模優勢實現更低的總成本。

圖1 機器人發展歷程

1.3 目前多機器人任務分配的方法簡述

多機器人任務分配問題可以視作調度問題，通過合理的任務分配方案使得資源獲得有效的配置以達到提高效率、降低成本等目的。目前針對該問題使用的方法主要有：基于市場機制的任務分配方法、群體智能方法、基于線性規劃的方法、基于行為的任務分配方法等。隨著人工智能的不斷發展，一些研究也將智能優化算法借鑒到了多機器人分配中，如利用SOM（自組織神經網絡算法）的子分類映射原理尋找最適合目標任務的機器人等。

1.3.1 基于市場機制的任務分配方法。基于市場機制的任務分配方法源于經濟學中的拍賣模型，其中較為經典的是R.Smith[2]在1980年提出的通過招標、投標、競標進而合同建立的合同網協議的分配方法。該方法具有適用性好、可彈性擴張的優勢，但是對于通信能力的要求較高[3]，不太適用于較大規模的多機器人，通常用于任務和機器人狀態可知的中小型環境中分布式問題的求解。在該思想下有集中式和分布式兩種應用。集中式任務分配是利用中央處理器進行任務拍賣和任務分配，分布式任務分配則是指自利的AMR（Automatic Mobile Robot）直接參與虛擬市場。集中式任務分配算法設計難度較低，但通信和計算集中，容易造成信息堵塞，對于較大規模的多機器人任務分配處理能力受限，且中央節點作為系統核心，對其穩定性的要求非常高，整體系統的魯棒性較差，因此僅適用于規模較小的系統。分布式任務分配具有應對動態環境的能力，通信負荷均衡，且系統可以并行處理問題，魯棒性較高，數據處理能力更強。在實際運用中，該任務分配方法又分為單目標拍賣、組合目標拍賣、單層拍賣、任務樹拍賣等[4-12]。針對該任務分配的結果，高梓豪[13]強調任務分配完成的不可更改性以確保通訊的效率。

1.3.2 基于群體智能的方法。基于群體智能的方法是利用社會性的昆蟲模擬出的算法，該方式中合作的個體呈現分布式的特點，具有較強擴張性和魯棒性。由于該方式中的通訊方式屬于非個體直接通訊，因此其擴充任務池所帶來的通訊增量并不大。最經典的算法有閾值法、蟻群算法等[14-16]。該方法在多機器人系統環境未知時可以發揮良好的效用。

1.3.3 基于線性規劃的方法。基于線性規劃的任務分配方法是將任務分配的問題看作0-1 線性規劃問題[17]，常用的有單純型法和匈牙利法。該方法通過矩陣運算，以最小化執行代價為目標進行任務分配，一些算法雖然可以找到最優解[18-20]，但因為其高集中式的特性，該算法擴展性差且效率不高，僅適用于單機器人單任務問題的解決方案。

1.3.4 基于行為的任務分配。基于行為的任務分配方法是將效益最高的機器人與任務相配對，每次匹配后將其從待分配任務列表中刪除，進行下一組配對[21]。典型的算法代表有ALLIANCE[22]、Broadcast of Local Eligibility（BLE）[23]等。該分配方法實時性、容錯性、魯棒性都存在優勢，但求得局部最優解的可能性較大。

各任務分配方法的優劣勢對比見表1。

表1 任務分配方法對比

根據以上分析，基于市場機制的任務分配方法在已知倉庫環境的前提下可以發揮較優的效用，但仍可能存在計算復雜、通信量大等問題。為解決此問題，進一步提高倉庫揀選效率并降低任務完成所需的系統代價，本文提出了一種多層次的適用于無人倉自動搬運系統的分布式合同網動態任務分配策略。

該動態任務分配策略由任務分配方式和任務執行保護機制組成，其中任務分配方式包含單任務分配和可組合任務分配，執行保護機制包括延誤觸發和合同不可更改兩部分，如圖2所示。

圖2 動態任務分配策略框架

2 動態任務分配策略的原理

2.1 參數設置

2.1.1 任務參數。目標貨架位置（若該貨架正在揀貨，則該參數為對應的機器人編號，否則為坐標）、目標貨物編號、目標揀選臺、目標貨物揀選數量、貨架回歸位置。

2.1.2 AMR 參數。設置任務執行表TEL（Task Execute List）、任務隊列表TQL（Task Queue List）；任務執行表狀態TES（Task Execute Status），任務隊列表狀態TQS（Task Queue Status）；正在執行任務的終點位置TEEL（Task Execute End Location）。

2.1.3 任務看板設置。任務看板內任務數量為1，包含信息有：任務起點位置TSL（Task Start Location）、任務終點位置TEL（Task End Location）、任務商品數量TQ(Target Quantity)、競標位置范圍BLR（Bidding Location Range）、競標池BP（Bidding Pool）。當任務看板為空時，推入新任務信息并發送任務到達提醒。

2.2 任務分類

本文所提出的任務分配策略中將任務分為單任務和可組合任務兩種。若任務的目標貨架（非目標貨物）存在于機器人的任務列表中，則該任務可以和任務列表中的任務進行組合，稱為可組合任務，否則稱為單任務，如圖3所示。

圖3 任務分類

2.3 任務分配邏輯

任務分配應用分布式模型，即AMR 自主參與虛擬市場的競標。若待分配任務為可組合任務，將其與已分配任務相組合可以增強作業的連續性，減少貨架的出入庫次數，進而提高作業效率和資源利用率，因此對于可組合任務，擁有相關任務的機器人擁有最高的競標值，此時直接接收任務并創建合同可以提高響應速度，減少不必要的通訊。對于單任務而言，機器人的競標值排序未知，因此需要自主競標，在市場競標模式中，競標評價函數Bi由完成當前任務預計耗費時間tm1與到達任務貨架所需時間tm2組成，即Bi=tm1+tm2。其中：

C是擁堵系數，由目標區域內碰撞頻率決定。

當前AMR應用路徑引導方式主要是利用路徑節點（二維碼等）和自由路徑引導（激光SLAM等），本文討論路徑節點引導下的行進模式（網格地圖），即利用兩目標間的曼哈頓距離作為行走距離。

綜上，動態任務分配的流程如圖4所示。

2.4 組合任務執行邏輯

若待分配任務i是可組合任務，假設任務i是（目標貨架i，目標貨物m，目標揀選臺k,目標數量n1），其對應已分配但未完成狀態的任務j 是（目標貨架i,目標貨物q，目標揀選臺 l，目標數量 n2）,則任務j 將擴充為（目標貨架i,目標貨物q，目標揀選臺l，目標數量n2；目標貨架i，目標貨物m，目標揀選臺k,目標數量n1）。組合任務在執行時遵循子任務隊列順序（子任務隊列順序默認進入順序，緊急任務置頂），如圖5所示。

圖4 動態任務分配流程

圖5 可組合任務分配邏輯

2.5 靈活響應揀選臺

由于組合任務中同一貨架響應多個揀選臺，所以當因揀選臺的處理能力不同（基于揀選站臺內操作人員的效率、工作狀態等差異）而導致AMR當前執行的子任務需在揀選隊列中排隊時間預計高于臨界值時，觸發靈活響應揀貨臺機制。即讀取下一子任務預計排隊時間，若符合要求，終止原子任務，開始新子任務。若子任務列表所有任務均不符合要求，繼續執行當前任務。靈活響應揀選臺機制可以降低部分揀選臺前等待隊伍較長而部分揀選臺前無貨可揀的不均衡狀態出現的概率，提高整體揀選效率和倉庫出庫效率，減少機器人的無效等待時間，如圖6所示。

圖6 靈活響應揀貨臺流程

2.6 合同不可更改

合同自任務進入任務執行表起開始履行，此時合同除特殊情況（如機器人故障等）不可更改，即使在該機器人還未到達目標貨架點時存在其他機器人距離任務點更近的情況，也不會再分配給其他機器人，以防止機器人任務執行過程中終止重新獲取任務所產生的空載運動，避免資源浪費，也避免重復運算所造成的內存和計算能力的浪費。

2.7 延誤觸發邏輯

在本文描述的基于市場的分配機制中，在建立任務合同后任務進入任務隊列表等待，該等待時間可能因為可組合任務在任務執行表中的插入、任務執行堵塞（在揀選隊列等待時間增長）、機器故障等原因導致過長，影響出貨效率。因此為保護訂單完成的效率，處于任務隊列表的任務仍可能被重新分配，且為避免占用內存和計算能力的浪費，設置延誤觸發點D（最長等待執行時間）。當到達延誤觸發點D時，AMR發送信息給中央處理器，使該任務回歸任務池。若AMR 處于機器故障（短時間內無法自我修復）等無法執行任務狀態時，立即將任務執行表和任務隊列表內所有任務信息發送給中央處理器，將任務回歸任務池。

3 動態任務分配與靜態任務分配的比較

3.1 訂單處理效率

傳統靜態任務分配下，AMR 需完成搬運指定貨架到揀貨臺揀選完成并將指定貨架卸載到存儲位置才被釋放，成為可用資源，即此時AMR的訂單行處理能力為1。而動態任務分配方式下，AMR的任務接收量增大，搬運指定貨架到揀選臺揀選完成即完成單任務循環，有效減少貨架的出入庫次數和無效行走，當所載貨架可以滿足多個揀選臺需求時，作業連續性增強，訂單處理速度提高。同時，可接收多個任務的特性使得AMR 在執行任務時依然屬于可用資源，因此同等數量的AMR 運行時，動態任務分配模式中可響應任務的資源數量高于靜態任務分配，提高了訂單響應速度。

3.2 靈活性

傳統靜態任務分配下，AMR 完全被動接收中央處理器指令，系統靈活性差，當遇到機器故障等情況時，無法及時對任務進行處理，進而影響整體出庫效率。而動態任務分配模式下，AMR 具有一定的自主能力，通過與中央處理器的信息交互，提高異常情況的響應速度與處理速度。同時，動態任務分配模式下延誤觸發的機制，使得任務具有一定的靈活性，提高資源配置的合理性，提高揀貨效率。

3.3 數據處理量

傳統靜態任務分配下，數據處理完全集中在中央處理器上，一次只能處理一條任務，其內存要求較高，數據處理量較大，任務處理速度不高，無法滿足實時化任務調度的要求。而在動態任務分配下，中央處理器將計算過程和資源屬性數據分散到AMR上，降低了數據處理量，提高了數據處理速度，在同等數據處理能力下，單位時間內可以處理更多的任務，且在增減AMR時，無需更新資源池內的屬性等數據，二者對比見表2。

表2 動靜態任務分配模式對比

4 總結與展望

隨著提高運營效率、降低物流成本等市場要求的提高，倉儲系統的柔性需求日益增加。本文所描述的自動搬運系統的動態任務分配策略通過集中式和分布式資源調度相結合的模式，提高了系統的智能化水平和靈活程度，對于無人倉自動搬運系統柔性的提升提供了一定的幫助。對于已提出的動態任務分配模式下，AMR 的需求數量與倉庫規模及訂單數量之間的關系等問題在未來需要進一步的研究。