黃 穎，李 薔

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

1 研究的問題與現(xiàn)狀

1.1 無人倉發(fā)展趨勢

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

1.2 大規(guī)模機(jī)器人的使用

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

工業(yè)自動化體系的應(yīng)用，也經(jīng)歷了從單點應(yīng)用到集群化應(yīng)用的發(fā)展過程。越來越多的企業(yè)意識到，與工業(yè)生產(chǎn)的點狀作業(yè)相比，物流體系更需要實現(xiàn)在面上以及立體空間內(nèi)的作業(yè)。通過分布式、并行化的機(jī)器人系統(tǒng)可以實現(xiàn)自動化的物流過程，取代傳統(tǒng)作業(yè)中人的單調(diào)重復(fù)勞動。

相較于單點智能，群體智能具有以下優(yōu)勢：

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

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

（3）對于較為復(fù)雜的任務(wù)和環(huán)境，設(shè)計多異構(gòu)/異能機(jī)器人相互協(xié)作遠(yuǎn)比設(shè)計一個多能力機(jī)器人要容易，且成本更低；

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

（5）群體智能擁有更為完整的數(shù)據(jù)鏈條記錄，有利于上下游協(xié)同決策，提高整體響應(yīng)速度；

（6）多機(jī)器人可以平行作業(yè)且具有冗余性，系統(tǒng)柔性更好、容錯率更高、魯棒性更強(qiáng)；

（7）多機(jī)器人系統(tǒng)模塊化設(shè)計更易擴(kuò)展、執(zhí)行更高效，在時間、功能、布局分布上更靈活。

群體智能較之單點智能，其智慧化程度更高，系統(tǒng)柔性更好，能夠?qū)崿F(xiàn)個體與整體更好的良性迭代，并利用規(guī)模優(yōu)勢實現(xiàn)更低的總成本。

圖1 機(jī)器人發(fā)展歷程

1.3 目前多機(jī)器人任務(wù)分配的方法簡述

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

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

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

1.3.3 基于線性規(guī)劃的方法?；诰€性規(guī)劃的任務(wù)分配方法是將任務(wù)分配的問題看作0-1 線性規(guī)劃問題[17]，常用的有單純型法和匈牙利法。該方法通過矩陣運算，以最小化執(zhí)行代價為目標(biāo)進(jìn)行任務(wù)分配，一些算法雖然可以找到最優(yōu)解[18-20]，但因為其高集中式的特性，該算法擴(kuò)展性差且效率不高，僅適用于單機(jī)器人單任務(wù)問題的解決方案。

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

各任務(wù)分配方法的優(yōu)劣勢對比見表1。

表1 任務(wù)分配方法對比

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

該動態(tài)任務(wù)分配策略由任務(wù)分配方式和任務(wù)執(zhí)行保護(hù)機(jī)制組成，其中任務(wù)分配方式包含單任務(wù)分配和可組合任務(wù)分配，執(zhí)行保護(hù)機(jī)制包括延誤觸發(fā)和合同不可更改兩部分，如圖2所示。

圖2 動態(tài)任務(wù)分配策略框架

2 動態(tài)任務(wù)分配策略的原理

2.1 參數(shù)設(shè)置

2.1.1 任務(wù)參數(shù)。目標(biāo)貨架位置（若該貨架正在揀貨，則該參數(shù)為對應(yīng)的機(jī)器人編號，否則為坐標(biāo)）、目標(biāo)貨物編號、目標(biāo)揀選臺、目標(biāo)貨物揀選數(shù)量、貨架回歸位置。

2.1.2 AMR 參數(shù)。設(shè)置任務(wù)執(zhí)行表TEL（Task Execute List）、任務(wù)隊列表TQL（Task Queue List）；任務(wù)執(zhí)行表狀態(tài)TES（Task Execute Status），任務(wù)隊列表狀態(tài)TQS（Task Queue Status）；正在執(zhí)行任務(wù)的終點位置TEEL（Task Execute End Location）。

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

2.2 任務(wù)分類

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

圖3 任務(wù)分類

2.3 任務(wù)分配邏輯

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

C是擁堵系數(shù)，由目標(biāo)區(qū)域內(nèi)碰撞頻率決定。

當(dāng)前AMR應(yīng)用路徑引導(dǎo)方式主要是利用路徑節(jié)點（二維碼等）和自由路徑引導(dǎo)（激光SLAM等），本文討論路徑節(jié)點引導(dǎo)下的行進(jìn)模式（網(wǎng)格地圖），即利用兩目標(biāo)間的曼哈頓距離作為行走距離。

綜上，動態(tài)任務(wù)分配的流程如圖4所示。

2.4 組合任務(wù)執(zhí)行邏輯

若待分配任務(wù)i是可組合任務(wù)，假設(shè)任務(wù)i是（目標(biāo)貨架i，目標(biāo)貨物m，目標(biāo)揀選臺k,目標(biāo)數(shù)量n1），其對應(yīng)已分配但未完成狀態(tài)的任務(wù)j 是（目標(biāo)貨架i,目標(biāo)貨物q，目標(biāo)揀選臺 l，目標(biāo)數(shù)量 n2）,則任務(wù)j 將擴(kuò)充為（目標(biāo)貨架i,目標(biāo)貨物q，目標(biāo)揀選臺l，目標(biāo)數(shù)量n2；目標(biāo)貨架i，目標(biāo)貨物m，目標(biāo)揀選臺k,目標(biāo)數(shù)量n1）。組合任務(wù)在執(zhí)行時遵循子任務(wù)隊列順序（子任務(wù)隊列順序默認(rèn)進(jìn)入順序，緊急任務(wù)置頂），如圖5所示。

圖4 動態(tài)任務(wù)分配流程

圖5 可組合任務(wù)分配邏輯

2.5 靈活響應(yīng)揀選臺

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

圖6 靈活響應(yīng)揀貨臺流程

2.6 合同不可更改

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

2.7 延誤觸發(fā)邏輯

在本文描述的基于市場的分配機(jī)制中，在建立任務(wù)合同后任務(wù)進(jìn)入任務(wù)隊列表等待，該等待時間可能因為可組合任務(wù)在任務(wù)執(zhí)行表中的插入、任務(wù)執(zhí)行堵塞（在揀選隊列等待時間增長）、機(jī)器故障等原因?qū)е逻^長，影響出貨效率。因此為保護(hù)訂單完成的效率，處于任務(wù)隊列表的任務(wù)仍可能被重新分配，且為避免占用內(nèi)存和計算能力的浪費，設(shè)置延誤觸發(fā)點D（最長等待執(zhí)行時間）。當(dāng)?shù)竭_(dá)延誤觸發(fā)點D時，AMR發(fā)送信息給中央處理器，使該任務(wù)回歸任務(wù)池。若AMR 處于機(jī)器故障（短時間內(nèi)無法自我修復(fù)）等無法執(zhí)行任務(wù)狀態(tài)時，立即將任務(wù)執(zhí)行表和任務(wù)隊列表內(nèi)所有任務(wù)信息發(fā)送給中央處理器，將任務(wù)回歸任務(wù)池。

3 動態(tài)任務(wù)分配與靜態(tài)任務(wù)分配的比較

3.1 訂單處理效率

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

3.2 靈活性

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

3.3 數(shù)據(jù)處理量

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

表2 動靜態(tài)任務(wù)分配模式對比

4 總結(jié)與展望

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