搬運(yùn)機(jī)器人多場(chǎng)景任務(wù)調(diào)度與仿真平臺(tái)開(kāi)發(fā)

翁 迅 張經(jīng)天 胡 曉

(1. 北京郵電大學(xué)現(xiàn)代郵政學(xué)院，北京 100876；2. 北京郵電大學(xué)人工智能學(xué)院，北京 100876)

隨著人工智能技術(shù)、5G技術(shù)、物聯(lián)網(wǎng)技術(shù)等飛速發(fā)展，面對(duì)以新技術(shù)、新產(chǎn)業(yè)、新業(yè)態(tài)和新模式為特征的新經(jīng)濟(jì)背景，相關(guān)技術(shù)從專業(yè)知識(shí)點(diǎn)的分割體系轉(zhuǎn)向多學(xué)科知識(shí)點(diǎn)的跨界交叉融合[1]。隨著搬運(yùn)機(jī)器人等智能裝備在各種新經(jīng)濟(jì)領(lǐng)域的應(yīng)用日益廣泛，其所涉及的知識(shí)結(jié)構(gòu)已經(jīng)突破了傳統(tǒng)物流工程的范疇：比如在電商的貨到人系統(tǒng)中考慮充電的搬運(yùn)機(jī)器人排班模型[2]；倉(cāng)儲(chǔ)環(huán)境下的移動(dòng)搬運(yùn)機(jī)器人的融合定位系統(tǒng)[3]；或者針對(duì)搬運(yùn)機(jī)器人完成行李智能搬運(yùn)現(xiàn)場(chǎng)試驗(yàn)平臺(tái)的搭建[4]；針對(duì)貨架搬運(yùn)機(jī)器人揀選系統(tǒng)的訂單排序與動(dòng)態(tài)儲(chǔ)位分配問(wèn)題[5]；針對(duì)機(jī)器人倉(cāng)儲(chǔ)作業(yè)系統(tǒng)的作業(yè)流程得出魚骨型貨架布局性能最優(yōu)設(shè)計(jì)[6]，也有針對(duì)基于改進(jìn)雞群優(yōu)化算法的食品揀取機(jī)器人路徑規(guī)劃方法研究[7]；針對(duì)食品倉(cāng)庫(kù)的全向搬運(yùn)機(jī)器人跟蹤能力提出改進(jìn)路徑跟蹤控制方法研究[8]?，F(xiàn)有的相關(guān)研究在驗(yàn)證階段采用主流物流系統(tǒng)仿真平臺(tái)如Automod、Flexsim等，往往不支持基于實(shí)際訂單數(shù)據(jù)的算法接口測(cè)試，導(dǎo)致系統(tǒng)建模仿真的驗(yàn)證效果和實(shí)際使用的情況差距較大，進(jìn)而影響了搬運(yùn)機(jī)器人系統(tǒng)在行業(yè)的應(yīng)用推廣。

研究擬探討開(kāi)發(fā)多場(chǎng)景下搬運(yùn)機(jī)器人任務(wù)調(diào)度與仿真平臺(tái)，旨在通過(guò)對(duì)搬運(yùn)機(jī)器人在物流中心的整箱揀選、訂單拆零作業(yè)、出入庫(kù)搬運(yùn)作業(yè)等各個(gè)場(chǎng)景搭建，利用場(chǎng)景特性分析，探索研究搬運(yùn)機(jī)器人的多智能體任務(wù)分配、多車調(diào)度及交通規(guī)劃、單車路徑實(shí)時(shí)優(yōu)化等特定算法開(kāi)發(fā)，并通過(guò)仿真平臺(tái)實(shí)現(xiàn)對(duì)所設(shè)計(jì)的算法進(jìn)行模擬和仿真驗(yàn)證，最終構(gòu)建并驗(yàn)證基于實(shí)際訂單數(shù)據(jù)的搬運(yùn)機(jī)器人任務(wù)調(diào)度和算法測(cè)試平臺(tái)的可行性。

1 搬運(yùn)機(jī)器人多場(chǎng)景任務(wù)調(diào)度與仿真平臺(tái)構(gòu)建

該任務(wù)調(diào)度與仿真平臺(tái)的搭建，以Marius等[9]開(kāi)發(fā)的開(kāi)源仿真框架RAWSim-O為基礎(chǔ)進(jìn)行二次開(kāi)發(fā)，結(jié)合國(guó)內(nèi)物流行業(yè)的實(shí)際情況為應(yīng)用場(chǎng)景，在此平臺(tái)基礎(chǔ)上實(shí)現(xiàn)符合物流行業(yè)標(biāo)準(zhǔn)的搬運(yùn)機(jī)器人多場(chǎng)景任務(wù)調(diào)度與仿真驗(yàn)證。通過(guò)調(diào)研食品、醫(yī)藥、飲料等物流中心的實(shí)際場(chǎng)景應(yīng)用特性，允許自主設(shè)計(jì)對(duì)應(yīng)的智能算法并在平臺(tái)上進(jìn)行程序?qū)崿F(xiàn)和驗(yàn)證。針對(duì)以上的目標(biāo)進(jìn)行如下平臺(tái)設(shè)計(jì)。

1.1 仿真場(chǎng)景設(shè)置

(1) 場(chǎng)景一：針對(duì)移動(dòng)機(jī)器人的上架過(guò)程的策略仿真。

食品和醫(yī)藥等產(chǎn)品的上架過(guò)程涉及貨位指派問(wèn)題，即將商品的SKU與倉(cāng)庫(kù)中貨位進(jìn)行綁定的過(guò)程，仿真優(yōu)化目標(biāo)是使得訂單后續(xù)的揀選時(shí)間代價(jià)最小。

(2) 場(chǎng)景二：針對(duì)多揀選臺(tái)作業(yè)的訂單波次分批策略仿真。

現(xiàn)代化物流中心的訂單分批是指將截止到當(dāng)前到達(dá)訂單池中的所有訂單按照一定的規(guī)則分若干波次，每次揀選臺(tái)處理一個(gè)波次的訂單，其目的是為了降低訂單揀選時(shí)貨架的搬運(yùn)次數(shù)、機(jī)器人的行走距離或作業(yè)時(shí)間。

(3) 場(chǎng)景三：針對(duì)存在任務(wù)分級(jí)的多揀選機(jī)器人任務(wù)分配策略仿真。

機(jī)器人搬運(yùn)物流系統(tǒng)中，“貨到人”機(jī)器人系統(tǒng)的任務(wù)分配是按照一定的規(guī)則，把空閑的搬運(yùn)機(jī)器人資源和系統(tǒng)待執(zhí)行任務(wù)進(jìn)行最佳匹配的過(guò)程。

(4) 場(chǎng)景四：針對(duì)有存儲(chǔ)規(guī)則限制的多機(jī)器人路徑規(guī)劃與協(xié)調(diào)策略仿真。

不同的存儲(chǔ)規(guī)則設(shè)置對(duì)機(jī)器人的路徑選擇有較大影響。合理地進(jìn)行多機(jī)器人路徑動(dòng)態(tài)規(guī)劃，可以有效避免出現(xiàn)通道擁塞等問(wèn)題。

1.2 仿真驗(yàn)證要求

1.2.1 場(chǎng)景一：針對(duì)移動(dòng)機(jī)器人的上架過(guò)程的策略仿真

以食品和醫(yī)藥物流中心為例，在滿足食品質(zhì)量管理規(guī)范的情況下，通?？紤]SKU的關(guān)聯(lián)性、貨物周轉(zhuǎn)率等因素進(jìn)行優(yōu)化。比如藥品要根據(jù)GSP的相關(guān)要求，需要滿足藥品和非藥品分開(kāi)、外用用藥和內(nèi)服用藥分開(kāi)、監(jiān)管類藥品和非監(jiān)管類藥品分開(kāi)、易串味藥品和其他藥品分開(kāi)等規(guī)則。這樣的上架過(guò)程和傳統(tǒng)的電商上架策略有明顯區(qū)別。在仿真平臺(tái)中可以針對(duì)物流上架過(guò)程的策略進(jìn)行算法設(shè)計(jì)并進(jìn)行模擬驗(yàn)證。

1.2.2 場(chǎng)景二：針對(duì)多揀選臺(tái)作業(yè)的訂單波次分批策略仿真 由于食品物流中心需要嚴(yán)格進(jìn)行先進(jìn)先出的批次管理。在多個(gè)揀選臺(tái)同時(shí)作業(yè)的情況下，如果設(shè)計(jì)的訂單波次分批策略中訂單波次分批的聚類度不高，則容易導(dǎo)致機(jī)器人的搬運(yùn)次數(shù)較多，系統(tǒng)需要配置較多的搬運(yùn)機(jī)器人才能滿足需求；如果設(shè)計(jì)的訂單波次分批的聚類度過(guò)高，則容易導(dǎo)致存在某個(gè)批次的尾訂單箱在各個(gè)揀選臺(tái)之間的揀選任務(wù)耦合的問(wèn)題，導(dǎo)致整個(gè)揀選作業(yè)的效率難以提升。食品行業(yè)的特性導(dǎo)致訂單波次分批策略和傳統(tǒng)電商系統(tǒng)的處理策略有較大區(qū)別。在試驗(yàn)過(guò)程中可以針對(duì)實(shí)際的訂單數(shù)據(jù)進(jìn)行訂單波次分批策略算法設(shè)計(jì)，并針對(duì)設(shè)計(jì)的算法進(jìn)行仿真模擬以驗(yàn)證其效果。

1.2.3 場(chǎng)景三：針對(duì)存在任務(wù)分級(jí)的多揀選機(jī)器人任務(wù)分配策略仿真 任務(wù)分配通常需要考慮機(jī)器人行駛距離的最優(yōu)、機(jī)器人的電量情況、任務(wù)執(zhí)行的時(shí)間窗等。由于任務(wù)分配是一個(gè)動(dòng)態(tài)分配的過(guò)程，因?yàn)椴粩嘤袡C(jī)器人完成釋放任務(wù)，不斷有新的任務(wù)到達(dá)。另外，還有充電任務(wù)也要根據(jù)充電策略及時(shí)插入機(jī)器人的任務(wù)序列中，且優(yōu)先級(jí)最高。在食品物流中心，由于訂單存在截單時(shí)間要求等問(wèn)題，任務(wù)是非均勻下發(fā)至機(jī)器人調(diào)度系統(tǒng)；部分訂單還存在緊急配送的需求、需要進(jìn)行緊急插單或者需要增補(bǔ)訂單內(nèi)容等情況。物流中心的業(yè)務(wù)特性導(dǎo)致的機(jī)器人任務(wù)分批策略和傳統(tǒng)電商的任務(wù)分批策略有較大區(qū)別。平臺(tái)可以針對(duì)實(shí)際的物流中心場(chǎng)景進(jìn)行任務(wù)分配算法設(shè)計(jì)，并針對(duì)設(shè)計(jì)的任務(wù)分配算法進(jìn)行仿真模擬以驗(yàn)證其效果。

1.2.4 場(chǎng)景四：針對(duì)有存儲(chǔ)規(guī)則限制的多機(jī)器人路徑規(guī)劃與協(xié)調(diào)策略仿真 傳統(tǒng)的電商物流系統(tǒng)中，儲(chǔ)位分配是基于銷售品種的熱銷情況決定具體分布方式。通常而言，熱銷品種設(shè)置得離揀選站臺(tái)較近，冷門商品設(shè)置得離揀選站臺(tái)較遠(yuǎn)。這種儲(chǔ)位分配方式下的多機(jī)器人路徑規(guī)劃，相對(duì)比較簡(jiǎn)單。在食品物流中心，由于各自產(chǎn)品的存儲(chǔ)需要遵循相關(guān)的存儲(chǔ)規(guī)則，比如巧克力、酸奶等產(chǎn)品必須在溫度控制區(qū)進(jìn)行存儲(chǔ)等。不同存儲(chǔ)特性的產(chǎn)品必須分區(qū)存放，在訂單執(zhí)行過(guò)程中，要實(shí)現(xiàn)跨區(qū)揀選的任務(wù)需求，平臺(tái)可以針對(duì)食品物流的儲(chǔ)位分配特點(diǎn)進(jìn)行多機(jī)器人路徑規(guī)劃與協(xié)調(diào)算法設(shè)計(jì)，通過(guò)實(shí)際場(chǎng)景的布局和任務(wù)對(duì)算法進(jìn)行仿真驗(yàn)證，從而測(cè)試多機(jī)器人路徑規(guī)劃與協(xié)調(diào)算法的效果。

1.3 搬運(yùn)機(jī)器人多場(chǎng)景任務(wù)調(diào)度與仿真平臺(tái)框架

搬運(yùn)機(jī)器人多場(chǎng)景任務(wù)調(diào)度與仿真平臺(tái)的本質(zhì)是搭建一個(gè)離散事件系統(tǒng)仿真平臺(tái)。其核心是針對(duì)搬運(yùn)機(jī)器人作業(yè)的任務(wù)場(chǎng)景，模擬搬運(yùn)機(jī)器人的隨機(jī)和動(dòng)態(tài)發(fā)生的事件，最終構(gòu)建各個(gè)事件之間的關(guān)聯(lián)關(guān)系。在搬運(yùn)機(jī)器人多場(chǎng)景任務(wù)調(diào)度與仿真平臺(tái)的基礎(chǔ)上，通過(guò)算法接口完成某個(gè)具體場(chǎng)景下的大量隨機(jī)試驗(yàn)，最終對(duì)試驗(yàn)結(jié)果進(jìn)行統(tǒng)計(jì)，從而獲得相應(yīng)場(chǎng)景下的算法優(yōu)劣性評(píng)估。基于代理(agent)的仿真建模方法被認(rèn)為是研究復(fù)雜系統(tǒng)的有效途徑，這種建模仿真技術(shù)，在建模的靈活性、層次性和直觀性方面較傳統(tǒng)的建模技術(shù)都有明顯的優(yōu)勢(shì)，非常適合機(jī)器人搬運(yùn)系統(tǒng)的建模與仿真。

基于代理的仿真建模方法，通過(guò)從個(gè)體到整體、從微觀到宏觀來(lái)研究復(fù)雜系統(tǒng)的復(fù)雜性，從而克服了復(fù)雜系統(tǒng)難以自上而下建立傳統(tǒng)數(shù)學(xué)模型的困難，有利于研究復(fù)雜系統(tǒng)具有的偶發(fā)性、非線性、隨機(jī)性等特點(diǎn)。因此該仿真驗(yàn)證平臺(tái)考慮采用基于代理和離散事件系統(tǒng)建模的方法進(jìn)行仿真平臺(tái)的構(gòu)建，其基本框架見(jiàn)圖1。

圖1 仿真平臺(tái)系統(tǒng)框架Figure 1 System framework of simulation platform

在仿真平臺(tái)的系統(tǒng)框架中，“代理”主要是模擬搬運(yùn)機(jī)器人系統(tǒng)中的物理世界對(duì)象(如機(jī)器人、貨架、貨位、工作站、商品等)，也可以模擬搬運(yùn)機(jī)器人系統(tǒng)中的虛擬實(shí)體(如模擬訂單流等)。

“仿真器”在整個(gè)仿真平臺(tái)系統(tǒng)的任務(wù)包括：① 更新代理的屬性；② 將“代理”觸發(fā)的事件傳遞給“控制器”，“控制器”可以立即做出決策，也可以緩沖多個(gè)請(qǐng)求，稍后通過(guò)優(yōu)化算法后再發(fā)布決策；③ 將最終的信息公開(kāi)給可視化組件，用戶通過(guò)界面觀測(cè)仿真系統(tǒng)的運(yùn)行情況，也可以與界面進(jìn)行交互，改變策略，實(shí)時(shí)干涉仿真的運(yùn)行。

仿真平臺(tái)模擬的揀選作業(yè)仿真流程如圖2所示。

圖2 揀選作業(yè)仿真流程Figure 2 Simulation of picking process

在仿真平臺(tái)的系統(tǒng)框架中，“控制器”是決策問(wèn)題的具體實(shí)現(xiàn)，在該仿真驗(yàn)證平臺(tái)中，所有的算法都體現(xiàn)在“控制器”的算法接口當(dāng)中，仿真平臺(tái)僅定義與控制器交互的接口，“控制器”包括訂單分配(POA)控制器、任務(wù)分配(TA)控制器、路徑規(guī)劃(PP)控制器、貨架儲(chǔ)位分配(PSA)控制器、揀選貨架選擇(PPS)控制器等。當(dāng)“控制器”運(yùn)行優(yōu)化算法時(shí)，允許控制器緩沖某些決策(如分揀訂單的波次分配)，并行運(yùn)行優(yōu)化過(guò)程，并稍后提交決策。由于部分算法需要較長(zhǎng)的計(jì)算時(shí)間以得出決策，在這種情況下，可以通過(guò)軟件上的多線程技術(shù)在算法運(yùn)算的同時(shí)計(jì)算和更新其他與此無(wú)關(guān)對(duì)象的狀態(tài)，從而加快仿真平臺(tái)的推進(jìn)速度。

2 基于記憶精英種群的災(zāi)變自適應(yīng)大鄰域搜索算法(MEPCALNS)

針對(duì)場(chǎng)景三“針對(duì)存在任務(wù)分級(jí)的多揀選機(jī)器人任務(wù)分配策略仿真”，根據(jù)醫(yī)藥物流中心的作業(yè)特點(diǎn)，考慮在揀選工作站排隊(duì)約束和“待揀選”貨架的唯一性約束，以機(jī)器人完工時(shí)間最小為目標(biāo)建立任務(wù)分配數(shù)學(xué)模型，并進(jìn)行仿真驗(yàn)證。構(gòu)建的典型地圖布局示意圖如圖3所示。

圖3 典型地圖布局示意圖Figure 3 Typical diagram of map layout

任務(wù)分配問(wèn)題可以描述為：考慮下發(fā)給拆零揀選工作站某個(gè)批次的揀選任務(wù)可以按訂單行拆分為M個(gè)揀選作業(yè)任務(wù)(簡(jiǎn)稱任務(wù))；現(xiàn)有N個(gè)機(jī)器人共同執(zhí)行這些任務(wù)，每個(gè)搬運(yùn)任務(wù)只能由一個(gè)機(jī)器人進(jìn)行執(zhí)行，滿足每個(gè)機(jī)器人同時(shí)只能執(zhí)行一個(gè)搬運(yùn)作業(yè)任務(wù)；任務(wù)分配算法需要在滿足客戶訂單設(shè)置的優(yōu)先級(jí)約束下為每個(gè)機(jī)器人分配一個(gè)任務(wù)列表，機(jī)器人按優(yōu)化后的作業(yè)流程順序執(zhí)行任務(wù)列表中相應(yīng)的任務(wù)，目標(biāo)期望達(dá)到所有機(jī)器人完成其對(duì)應(yīng)的任務(wù)列表的最大完工時(shí)間最短。

建立數(shù)學(xué)模型，各參數(shù)含義見(jiàn)表1。

表1 數(shù)學(xué)模型參數(shù)說(shuō)明Table 1 Description of mathematical model parameters

目標(biāo)函數(shù)

(1)

約束于

J1J2∪…∪JN=J，

(2)

Jr∩J2=?,?r∈R,?s∈R,r≠s，

(3)

(4)

(5)

其中，目標(biāo)函數(shù)式(1)表示所有機(jī)器人的最大任務(wù)列表的完工時(shí)間最小化。約束條件式(2)表示所有任務(wù)均可以被分配，式(3)表示機(jī)器人所分配到的任務(wù)不會(huì)重復(fù)，式(4)、式(5)為客戶訂單執(zhí)行的優(yōu)先級(jí)約束。式(4)表示任務(wù)隊(duì)列中，內(nèi)部排序中后序任務(wù)的優(yōu)先級(jí)不能高于前序任務(wù)的優(yōu)先級(jí)；式(5)表示任務(wù)隊(duì)列之間后序任務(wù)隊(duì)列的優(yōu)先級(jí)不能高于前序任務(wù)隊(duì)列的優(yōu)先級(jí)。

針對(duì)上述模型的求解，提出基于記憶精英種群的災(zāi)變自適應(yīng)大鄰域搜索算法(Memory Elite Population based Catastrophe Adaptive Large Neighborhood Search，MEPCALNS)，其算法流程見(jiàn)圖4。

圖4 MEPCALNS流程圖Figure 4 MEPCALNS flow chart

MEPCALNS在仿真平臺(tái)設(shè)置參數(shù)見(jiàn)表2。

表2 平臺(tái)參數(shù)設(shè)置Table 2 Experimental parameter settings

基于大、中、小3種訂單規(guī)模以及5種地圖規(guī)模隨機(jī)生產(chǎn)正交算例RAND1-1～RAND1-5、RAND2-1～RAND2-5、RAND3-1～RAND3-5。具體算例設(shè)置見(jiàn)表3。

表3 算例設(shè)置Table 3 Example settings

采用仿真平臺(tái)對(duì)派遣規(guī)則、自適應(yīng)大領(lǐng)域搜索算法(Adaptive Large Neighborhood Search，ALNS)和試驗(yàn)設(shè)計(jì)的基于記憶精英種群的災(zāi)變自適應(yīng)大鄰域搜索算法MEPCALNS進(jìn)行實(shí)驗(yàn)驗(yàn)證，結(jié)果見(jiàn)表4。

表4 算法有效性試驗(yàn)結(jié)果?Table 4 Experimental results of algorithm effectiveness

由表4可知，啟發(fā)式算法在所有算例中的求解效果均明顯優(yōu)于傳統(tǒng)的派遣規(guī)則。而基于記憶精英種群的災(zāi)變自適應(yīng)大鄰域搜索算法(MEPCALNS)相對(duì)ALNS算法而言，算例的提升效率比較穩(wěn)定，說(shuō)明MEPCALNS算法在求解“場(chǎng)景三”的相關(guān)問(wèn)題時(shí)，相比ALNS算法存在優(yōu)越性，算法效率平均提升3.16%。

3 結(jié)論

試驗(yàn)表明，通過(guò)搬運(yùn)機(jī)器人多場(chǎng)景任務(wù)調(diào)度與仿真平臺(tái)的構(gòu)建，可以根據(jù)使用者所選擇的場(chǎng)景進(jìn)行實(shí)際調(diào)研，設(shè)計(jì)各種優(yōu)化算法，并在平臺(tái)上采用同樣的參數(shù)配置和場(chǎng)景地圖，將設(shè)計(jì)的算法和傳統(tǒng)的算法進(jìn)行仿真驗(yàn)證，有效解決了現(xiàn)有仿真平臺(tái)的不足。該任務(wù)調(diào)度與仿真平臺(tái)目前是基于仿真時(shí)鐘的事件驅(qū)動(dòng)模式，隨著5G和數(shù)字孿生技術(shù)的進(jìn)一步發(fā)展，未來(lái)存在通過(guò)5G技術(shù)采集現(xiàn)場(chǎng)實(shí)時(shí)狀態(tài)信息，升級(jí)為數(shù)字孿生平臺(tái)的可能性。