基于強化學習的多機器人倉儲調度方法研究

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

關鍵詞： 智能倉儲系統; 調度系統; 任務分配; 路徑規劃; 倉庫模型; 強化學習

中圖分類號： TN830.1?34; TP18; TP242 ? ? ? ?文獻標識碼： A ? ? ? ? ? ? ? ? ?文章編號： 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

對于智能倉儲而言，一個高效的調度系統是提升整個倉儲系統效率的核心。本文基于倉儲物流機器人[1]，對其在智能倉儲調度系統中，如何有效降低運行代價，提高運行效率進行研究和建模分析。對新時代挑戰下的智能倉儲管理具有積極的作用[2]。

1 ?問題描述

在智能倉儲調度系統中，調度環節運行代價由完成一定數量訂單任務的時間代價和路程代價組成。在設定的倉儲環境中，應用若干機器人對某時段一定數量的訂單任務進行分配、執行，則其時間代價對應的是機器人集群完成所有訂單任務的時間和總路程代價。

智能倉儲調度環境由貨架、一定數量的智能機器人和數個工作臺組成。為了簡化系統，方便對比系統性能，對倉庫地圖柵格化[3]，形成二維平面[50×28]的柵格如圖1所示，其中包含[4×12×6]個貨架，3個工作臺和8個智能機器人。每一個倉儲物流機器人占一格單位的柵格，在空白柵格中移動完成各自任務。從柵格左上角第一個單位柵格開始，按列對每個單位柵格進行編號，形成1～1 400號柵格。并對該智能倉儲調度過程做出如下合理性條件假設：

1） 所有機器人的規格都是完全相同的;

2） 機器人只能通過上、下、左、右四個動作中的一個到達相鄰的網格;

3） 設定機器人在工作臺停留的時間和取貨時舉起貨架的時間為一個常數，以簡化計算;

4） 一個機器人一次只能處理一個訂單的物流任務。

調度過程如下：首先通過多機器人任務分配算法對未完成的訂單進行分配，每個智能機器人將被分配到一個或多個訂單任務，智能機器人根據被分到的任務的具體信息，通過路徑規劃算法從當前位置移動到貨架位置;然后將貨架運輸到指定的工作臺進行相應處理，再從當前位置移動到下一個任務訂單所指向的貨架，依次循環直至完成所有被分到的任務。

本文將調度問題凝練為一個目標規劃問題，根據上文的描述，目標函數綜合時間代價、總路徑代價并增加協同度指標，在發揮機器人適配訂單的個體優勢下，同時也提高機器人集群完成訂單任務的整體協調性。該目標函數的數學表述如下：

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

式中：TT，TTC和BU分別表示完成所有訂單任務的時間代價、總路徑代價和協同度指標;[a]，[b]，[c]分別為TT，TTC，BU的權重，參照實際情況可加以調整。

2 ?算法設計

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

雖然上述的設計可以找到最優的結果，但算法的計算量十分巨大，運行起來耗時嚴重，不適合用于實際倉庫訂單高并發量的現狀和發展趨向。假設遺傳算法的最大遺傳代數為4 000，種群規模設為100，Q?Learning學習8 000次，則代價差異需迭代計算[100×4 000×8 000=3 200 000 000]次?；跂鸥窕瘋}庫模型特點，本文創新的使用倉儲環境中的曼哈頓路徑值為代價估計值，將大量重復的迭代計算轉換為一次線性的估計值計算。利用代價估計值來尋找優秀的染色體，這樣的優化方法可以省去Q?Learning的迭代計算，極大地降低了算法的運行時間。

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

根據所構建倉庫模型，機器人[ri]完成一個物流任務[tj]所花費的路徑代價的估計值用[cij]表示，即智能機器人忽略障礙物，從當前位置[Sxs，ys]到任務[tjxj，yj]的曼哈頓距離和從任務[tjxj，yj]到距離其直線距離最近的工作臺[Gxg，yg]的曼哈頓距離之和，其計算公式為：

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

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

[Ki]中機器人[ri]完成被分到的所有[l]個任務的總代價的估計值為：

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

本文遺傳算法過程適應度函數綜合時間代價估計值、路徑代價估計值和協同度3個指標，設置為：

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

式中，[a]，[b]，[c]分別是對應項的權重。本文結合實際情況，在TT，TTC，BU歸一化后，其權重按照2∶1.5∶1設置。TT為總時間的估計值，即完成所有訂單任務所花費的時間代價的估計值，取機器人中路徑代價估計值最大的表示;TTC為總路程的估計值，即系統所有機器人完成所有任務的路徑代價估計值的總和;BU為協同度，取機器人路徑代價估計值的方差，反映其離散程度。數學描述分別如下：

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

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

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

綜上所述，優化后的算法流程為：

1） 采用多層編碼遺傳算法進行多機器人任務分配;

2） 采用強化學習的Q?Learning算法進行路徑規劃，如圖3所示。根據遺傳算法收斂特性，利用代價估計值快速尋找出最優任務分配方案，輸出結果作為Q?Learning過程的初始條件，最終形成總任務的調度方案。

3 ?仿真實驗與分析

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

由表2可以看出，本文設計的方法相較于文獻[11]的方法，無論是在機器人完成任務的總路程還是在算法的運行時間上都有較大的改善，運算時間可能會有電腦硬件性能影響，但在總路程上，相較于前者平均提高62%。根據表2的相關數據分析，當任務數量呈線性增長時，算法的總路程和運算總時間也是呈線性增加，體現出本文算法良好的性能。

4 ?結 ?語

本文的創新研究如下：

1） 在綜合考慮調度系統全局的時間代價和機器人集群整體運行效率的同時，加入協同度指標，提高機器人個體之間的平衡性;

2） 與相關文獻進行對比，本文的算法在調度過程中，基于機器人集群的總路程減少了62%;

3） 在計算適應度函數時引入代價估計值，優化了算法的結構，算法的運行時間有明顯改善。

綜合以上所提方法更適合解決復雜的大規模的智能倉儲調度問題。在本文中，機器人的路徑規劃算法是在硬性避障條件下的單機器人路徑規劃，將來可以結合以上避障規則下對機器人協同問題進行研究，在取貨和上貨同時進行的情況，設計出效率更高的智能倉儲調度系統。

參考文獻

[1] 鄒爽心.倉儲機器人的應用現狀與發展戰略探討[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] 沈博聞，于寧波，劉景泰.倉儲物流機器人集群的智能調度和路徑規劃[J].智能系統學報，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] 蔣家志，劉國.多機器人智能倉儲系統中智能調度的研究[J].機電工程技術，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] 徐明亮. 強化學習及其應用研究[D].無錫：江南大學，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] 竇佳佳.強化學習及其在智能倉儲中的應用研究[D].南京：南京大學，2016.

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