基于強(qiáng)化學(xué)習(xí)的多機(jī)器人倉(cāng)儲(chǔ)調(diào)度方法研究

陳明智 錢同惠 張仕臻 王嘉前

關(guān)鍵詞： 智能倉(cāng)儲(chǔ)系統(tǒng); 調(diào)度系統(tǒng); 任務(wù)分配; 路徑規(guī)劃; 倉(cāng)庫(kù)模型; 強(qiáng)化學(xué)習(xí)

中圖分類號(hào)： TN830.1?34; TP18; TP242 ? ? ? ?文獻(xiàn)標(biāo)識(shí)碼： A ? ? ? ? ? ? ? ? ?文章編號(hào)： 1004?373X（2019）14?0165?04

Research on multiple robot warehouse scheduling method

based on reinforcement learning

CHEN Mingzhi， QIAN Tonghui， ZHANG Shizhen， WANG Jiaqian

（College of Physics and Information Engineering， Jianghan University， Wuhan 430056， China）

Abstract： The scheduling system as one of the cores of intelligent storage. The high?degree collaboration scheduling system can greatly improve the efficiency of intelligent robots in the intelligent warehousing system. In this paper， the scheduling of logistics robot in intelligent storage system is studied， and the rasterized warehouse model is analyzed and modeled. The multi?agent task allocation algorithm for integrated time cost， path cost and synergy cost is proposed on the basis of multi?layer coding genetic algorithm. Q?Learning algorithm is used to optimize the path of each intelligent agent. In order to optimize the performance of the algorithm， based on the characteristics of the rasterized warehouse model， the estimation value operation of path cost is introduced into the genetic fitness evaluation function according to the Manhattan path. In comparison with the MATLAB simulation result of the same period， the computational performance is increased by more than 20%. It is more suitable to solve the complex large?scale intelligent storage scheduling problem.

Keywords： intelligent storage system; scheduling system; task allocation; path planning; warehouse model; reinforcement learning

對(duì)于智能倉(cāng)儲(chǔ)而言，一個(gè)高效的調(diào)度系統(tǒng)是提升整個(gè)倉(cāng)儲(chǔ)系統(tǒng)效率的核心。本文基于倉(cāng)儲(chǔ)物流機(jī)器人[1]，對(duì)其在智能倉(cāng)儲(chǔ)調(diào)度系統(tǒng)中，如何有效降低運(yùn)行代價(jià)，提高運(yùn)行效率進(jìn)行研究和建模分析。對(duì)新時(shí)代挑戰(zhàn)下的智能倉(cāng)儲(chǔ)管理具有積極的作用[2]。

1 ?問(wèn)題描述

在智能倉(cāng)儲(chǔ)調(diào)度系統(tǒng)中，調(diào)度環(huán)節(jié)運(yùn)行代價(jià)由完成一定數(shù)量訂單任務(wù)的時(shí)間代價(jià)和路程代價(jià)組成。在設(shè)定的倉(cāng)儲(chǔ)環(huán)境中，應(yīng)用若干機(jī)器人對(duì)某時(shí)段一定數(shù)量的訂單任務(wù)進(jìn)行分配、執(zhí)行，則其時(shí)間代價(jià)對(duì)應(yīng)的是機(jī)器人集群完成所有訂單任務(wù)的時(shí)間和總路程代價(jià)。

智能倉(cāng)儲(chǔ)調(diào)度環(huán)境由貨架、一定數(shù)量的智能機(jī)器人和數(shù)個(gè)工作臺(tái)組成。為了簡(jiǎn)化系統(tǒng)，方便對(duì)比系統(tǒng)性能，對(duì)倉(cāng)庫(kù)地圖柵格化[3]，形成二維平面[50×28]的柵格如圖1所示，其中包含[4×12×6]個(gè)貨架，3個(gè)工作臺(tái)和8個(gè)智能機(jī)器人。每一個(gè)倉(cāng)儲(chǔ)物流機(jī)器人占一格單位的柵格，在空白柵格中移動(dòng)完成各自任務(wù)。從柵格左上角第一個(gè)單位柵格開始，按列對(duì)每個(gè)單位柵格進(jìn)行編號(hào)，形成1～1 400號(hào)柵格。并對(duì)該智能倉(cāng)儲(chǔ)調(diào)度過(guò)程做出如下合理性條件假設(shè)：

1） 所有機(jī)器人的規(guī)格都是完全相同的;

2） 機(jī)器人只能通過(guò)上、下、左、右四個(gè)動(dòng)作中的一個(gè)到達(dá)相鄰的網(wǎng)格;

3） 設(shè)定機(jī)器人在工作臺(tái)停留的時(shí)間和取貨時(shí)舉起貨架的時(shí)間為一個(gè)常數(shù)，以簡(jiǎn)化計(jì)算;

4） 一個(gè)機(jī)器人一次只能處理一個(gè)訂單的物流任務(wù)。

調(diào)度過(guò)程如下：首先通過(guò)多機(jī)器人任務(wù)分配算法對(duì)未完成的訂單進(jìn)行分配，每個(gè)智能機(jī)器人將被分配到一個(gè)或多個(gè)訂單任務(wù)，智能機(jī)器人根據(jù)被分到的任務(wù)的具體信息，通過(guò)路徑規(guī)劃算法從當(dāng)前位置移動(dòng)到貨架位置;然后將貨架運(yùn)輸?shù)街付ǖ墓ぷ髋_(tái)進(jìn)行相應(yīng)處理，再?gòu)漠?dāng)前位置移動(dòng)到下一個(gè)任務(wù)訂單所指向的貨架，依次循環(huán)直至完成所有被分到的任務(wù)。

本文將調(diào)度問(wèn)題凝練為一個(gè)目標(biāo)規(guī)劃問(wèn)題，根據(jù)上文的描述，目標(biāo)函數(shù)綜合時(shí)間代價(jià)、總路徑代價(jià)并增加協(xié)同度指標(biāo)，在發(fā)揮機(jī)器人適配訂單的個(gè)體優(yōu)勢(shì)下，同時(shí)也提高機(jī)器人集群完成訂單任務(wù)的整體協(xié)調(diào)性。該目標(biāo)函數(shù)的數(shù)學(xué)表述如下：

[min Zcost=aTT+bTTC+cBU] ? （1）

式中：TT，TTC和BU分別表示完成所有訂單任務(wù)的時(shí)間代價(jià)、總路徑代價(jià)和協(xié)同度指標(biāo);[a]，[b]，[c]分別為TT，TTC，BU的權(quán)重，參照實(shí)際情況可加以調(diào)整。

2 ?算法設(shè)計(jì)

借助于Q?Learning算法在未知環(huán)境下強(qiáng)大的自主學(xué)習(xí)能力[4?7]，以及遺傳算法求解的快速收斂特性[8?10]，本文的調(diào)度方案分別采用多層編碼遺傳算法進(jìn)行多機(jī)器人任務(wù)分配，采用強(qiáng)化學(xué)習(xí)的Q?Learning算法進(jìn)行路徑規(guī)劃。一般而言，算法流程如圖2所示。在整個(gè)算法中，路徑規(guī)劃算法計(jì)算出種群中隨機(jī)生成的每個(gè)染色體完成任務(wù)的路徑代價(jià)，根據(jù)它們之間差異的大小，作為判斷染色體好壞的指標(biāo)，以此挑選出種群中優(yōu)秀的染色體進(jìn)行后續(xù)的操作，直到選出最優(yōu)。

雖然上述的設(shè)計(jì)可以找到最優(yōu)的結(jié)果，但算法的計(jì)算量十分巨大，運(yùn)行起來(lái)耗時(shí)嚴(yán)重，不適合用于實(shí)際倉(cāng)庫(kù)訂單高并發(fā)量的現(xiàn)狀和發(fā)展趨向。假設(shè)遺傳算法的最大遺傳代數(shù)為4 000，種群規(guī)模設(shè)為100，Q?Learning學(xué)習(xí)8 000次，則代價(jià)差異需迭代計(jì)算[100×4 000×8 000=3 200 000 000]次?；跂鸥窕瘋}(cāng)庫(kù)模型特點(diǎn)，本文創(chuàng)新的使用倉(cāng)儲(chǔ)環(huán)境中的曼哈頓路徑值為代價(jià)估計(jì)值，將大量重復(fù)的迭代計(jì)算轉(zhuǎn)換為一次線性的估計(jì)值計(jì)算。利用代價(jià)估計(jì)值來(lái)尋找優(yōu)秀的染色體，這樣的優(yōu)化方法可以省去Q?Learning的迭代計(jì)算，極大地降低了算法的運(yùn)行時(shí)間。

具體操作如下：假定當(dāng)前時(shí)間段有n個(gè)任務(wù)，[T=t1，t2，…，tn]，有m個(gè)機(jī)器人，[R=r1，r2，…，rm]，根據(jù)多機(jī)器人任務(wù)分配算法將其分為m組，[K=K1，K2，…，Km]。其中，[Ki]表示機(jī)器人[ri]所分到的[l]個(gè)任務(wù)，[Ki=Ki1，Ki2，…，Kil]。指定每一個(gè)單元柵格的右下角坐標(biāo)為該柵格的坐標(biāo)。

根據(jù)所構(gòu)建倉(cāng)庫(kù)模型，機(jī)器人[ri]完成一個(gè)物流任務(wù)[tj]所花費(fèi)的路徑代價(jià)的估計(jì)值用[cij]表示，即智能機(jī)器人忽略障礙物，從當(dāng)前位置[Sxs，ys]到任務(wù)[tjxj，yj]的曼哈頓距離和從任務(wù)[tjxj，yj]到距離其直線距離最近的工作臺(tái)[Gxg，yg]的曼哈頓距離之和，其計(jì)算公式為：

[cij=xs-xj+ys-yj+xj-xg+yj-yg] ? ?（2）

式中：[s]，[g]代表當(dāng)前位置和工作臺(tái)的狀態(tài)信息;[j∈[0，n]];[1≤xs，xj，xg≤50];[0≤ys，yj，yg≤27]。

[Ki]中機(jī)器人[ri]完成被分到的所有[l]個(gè)任務(wù)的總代價(jià)的估計(jì)值為：

[Wri=ci1+ci2+ci3+…+cil] ?（3）

本文遺傳算法過(guò)程適應(yīng)度函數(shù)綜合時(shí)間代價(jià)估計(jì)值、路徑代價(jià)估計(jì)值和協(xié)同度3個(gè)指標(biāo)，設(shè)置為：

[Fitness（i）=aTTi+bTTCi+cBUi] （4）

式中，[a]，[b]，[c]分別是對(duì)應(yīng)項(xiàng)的權(quán)重。本文結(jié)合實(shí)際情況，在TT，TTC，BU歸一化后，其權(quán)重按照2∶1.5∶1設(shè)置。TT為總時(shí)間的估計(jì)值，即完成所有訂單任務(wù)所花費(fèi)的時(shí)間代價(jià)的估計(jì)值，取機(jī)器人中路徑代價(jià)估計(jì)值最大的表示;TTC為總路程的估計(jì)值，即系統(tǒng)所有機(jī)器人完成所有任務(wù)的路徑代價(jià)估計(jì)值的總和;BU為協(xié)同度，取機(jī)器人路徑代價(jià)估計(jì)值的方差，反映其離散程度。數(shù)學(xué)描述分別如下：

[TT=max{Wr1，Wr2，…，Wrm}] ? ?（5）

[TTC=i=1mWri] ? （6）

[BU=i=1mi=1mW（ri）m-W（ri）2m] ?（7）

綜上所述，優(yōu)化后的算法流程為：

1） 采用多層編碼遺傳算法進(jìn)行多機(jī)器人任務(wù)分配;

2） 采用強(qiáng)化學(xué)習(xí)的Q?Learning算法進(jìn)行路徑規(guī)劃，如圖3所示。根據(jù)遺傳算法收斂特性，利用代價(jià)估計(jì)值快速尋找出最優(yōu)任務(wù)分配方案，輸出結(jié)果作為Q?Learning過(guò)程的初始條件，最終形成總?cè)蝿?wù)的調(diào)度方案。

3 ?仿真實(shí)驗(yàn)與分析

對(duì)本文所設(shè)計(jì)算法的有效性進(jìn)行驗(yàn)證，硬件配置為Intel[?] CoreTM i7?2600，Matlab 2017a，對(duì)其進(jìn)行仿真實(shí)驗(yàn)，相關(guān)參數(shù)設(shè)置如表1所示。訂單任務(wù)數(shù)量分別設(shè)置為50，100，150，200，250，進(jìn)行了5組測(cè)試。將最終的實(shí)驗(yàn)結(jié)果與文獻(xiàn)[11]中所設(shè)計(jì)的一種基于虛擬任務(wù)遺傳算法的多機(jī)器人任務(wù)分配和Q?Learning單智能體路徑規(guī)劃算法所得到的結(jié)果進(jìn)行比較，主要比較了運(yùn)行時(shí)間和機(jī)器人所走的總路程這兩個(gè)主要指標(biāo)。其仿真結(jié)果如表2所示。

由表2可以看出，本文設(shè)計(jì)的方法相較于文獻(xiàn)[11]的方法，無(wú)論是在機(jī)器人完成任務(wù)的總路程還是在算法的運(yùn)行時(shí)間上都有較大的改善，運(yùn)算時(shí)間可能會(huì)有電腦硬件性能影響，但在總路程上，相較于前者平均提高62%。根據(jù)表2的相關(guān)數(shù)據(jù)分析，當(dāng)任務(wù)數(shù)量呈線性增長(zhǎng)時(shí)，算法的總路程和運(yùn)算總時(shí)間也是呈線性增加，體現(xiàn)出本文算法良好的性能。

4 ?結(jié) ?語(yǔ)

本文的創(chuàng)新研究如下：

1） 在綜合考慮調(diào)度系統(tǒng)全局的時(shí)間代價(jià)和機(jī)器人集群整體運(yùn)行效率的同時(shí)，加入?yún)f(xié)同度指標(biāo)，提高機(jī)器人個(gè)體之間的平衡性;

2） 與相關(guān)文獻(xiàn)進(jìn)行對(duì)比，本文的算法在調(diào)度過(guò)程中，基于機(jī)器人集群的總路程減少了62%;

3） 在計(jì)算適應(yīng)度函數(shù)時(shí)引入代價(jià)估計(jì)值，優(yōu)化了算法的結(jié)構(gòu)，算法的運(yùn)行時(shí)間有明顯改善。

綜合以上所提方法更適合解決復(fù)雜的大規(guī)模的智能倉(cāng)儲(chǔ)調(diào)度問(wèn)題。在本文中，機(jī)器人的路徑規(guī)劃算法是在硬性避障條件下的單機(jī)器人路徑規(guī)劃，將來(lái)可以結(jié)合以上避障規(guī)則下對(duì)機(jī)器人協(xié)同問(wèn)題進(jìn)行研究，在取貨和上貨同時(shí)進(jìn)行的情況，設(shè)計(jì)出效率更高的智能倉(cāng)儲(chǔ)調(diào)度系統(tǒng)。

參考文獻(xiàn)

[1] 鄒爽心.倉(cāng)儲(chǔ)機(jī)器人的應(yīng)用現(xiàn)狀與發(fā)展戰(zhàn)略探討[J].物流工程與管理，2013，35（6）：171?172.

ZOU Shuangxin. Application status and development strategy of warehousing robot [J]. Logistics engineering & management， 2013， 35（6）： 171?172.

[2] 沈博聞，于寧波，劉景泰.倉(cāng)儲(chǔ)物流機(jī)器人集群的智能調(diào)度和路徑規(guī)劃[J].智能系統(tǒng)學(xué)報(bào)，2014，9（6）：659?664.

SHEN Bowen， YU Ningbo， LIU Jingtai. Intelligent scheduling and path planning of warehouse logistics robot cluster [J]. Journal of intelligent systems， 2014，9（6）： 659?664.

[3] 蔣家志，劉國(guó).多機(jī)器人智能倉(cāng)儲(chǔ)系統(tǒng)中智能調(diào)度的研究[J].機(jī)電工程技術(shù)，2017，46（9）：82?84.

JIANG Jiazhi， LIU Guo. Research on intelligent scheduling in multi?robot intelligent warehousing system [J]. Electromechanical engineering technology， 2017， 46（9）： 82?84.

[4] CHEN C， DONG D， LI H X， et al. Fidelity?based probabilistic Q?learning forc ontrol of quantum systems [J]. IEEE transactionson neural networks&learning systems， 2014， 25（5）： 920?933.

[5] KONAR A， CHAKRABORTY I G， SINGH S J， et al. A deterministic improved Q?leaming for path planning of a mobile robot [J]. IEEE transactions on systems man & cybernetics systems， 2013， 43（5）： 1141?1153.

[6] 徐明亮. 強(qiáng)化學(xué)習(xí)及其應(yīng)用研究[D].無(wú)錫：江南大學(xué)，2010.

XU Mingming. Study on reinforcement learning and its application [D]. Wuxi： Jiangnan University， 2010.

[7] ZHOU Luowei， ?YANG Pei， ?CHEN Chunlin， et al. Multi agent reinforcement learning with sparse interactions by negotiation and knowledge transfer [J]. IEEE transactions on cybernetics， 2015（2）： 1?13.

[8] LI J， SUN Q， ZHOU M， et al. A new multiple traveling salesman problem and its genetic algorithm?based solutio [C]// Proceedings of 2013 IEEE International Conference on Systems， Man， and Cybernetics （SMC）. [S.l.]： IEEE， 2013： 627?632.

[9] ZHANG Yuhui， GONG Yuejiao， GU Tianlong， et al. Flexible genetic algorithm： A simple and generic approach to node placement problems [J]. Applied soft computing， 2017， 52： 457?470.

[10] ZHAN Z L， WANG Q. Intelligent robot motion control system based on immune genetic algorithm [J]. Applied mechanics and materials， 2014， 608： 703?707.

[11] 竇佳佳.強(qiáng)化學(xué)習(xí)及其在智能倉(cāng)儲(chǔ)中的應(yīng)用研究[D].南京：南京大學(xué)，2016.

DOU Jiajia. Study on reinforcement learning and its application in intelligent warehousing [D]. Nanjing： Nanjing University， 2016.