基于强化学习的多机器人仓储调度方法研究

陈明智 钱同惠 张仕臻 王嘉前

关键词： 智能仓储系统; 调度系统; 任务分配; 路径规划; 仓库模型; 强化学习

中图分类号： 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.