搬运机器人多场景任务调度与仿真平台开发

翁 迅 张经天 胡 晓

(1. 北京邮电大学现代邮政学院，北京 100876；2. 北京邮电大学人工智能学院，北京 100876)

随着人工智能技术、5G技术、物联网技术等飞速发展，面对以新技术、新产业、新业态和新模式为特征的新经济背景，相关技术从专业知识点的分割体系转向多学科知识点的跨界交叉融合[1]。随着搬运机器人等智能装备在各种新经济领域的应用日益广泛，其所涉及的知识结构已经突破了传统物流工程的范畴：比如在电商的货到人系统中考虑充电的搬运机器人排班模型[2]；仓储环境下的移动搬运机器人的融合定位系统[3]；或者针对搬运机器人完成行李智能搬运现场试验平台的搭建[4]；针对货架搬运机器人拣选系统的订单排序与动态储位分配问题[5]；针对机器人仓储作业系统的作业流程得出鱼骨型货架布局性能最优设计[6]，也有针对基于改进鸡群优化算法的食品拣取机器人路径规划方法研究[7]；针对食品仓库的全向搬运机器人跟踪能力提出改进路径跟踪控制方法研究[8]。现有的相关研究在验证阶段采用主流物流系统仿真平台如Automod、Flexsim等，往往不支持基于实际订单数据的算法接口测试，导致系统建模仿真的验证效果和实际使用的情况差距较大，进而影响了搬运机器人系统在行业的应用推广。

研究拟探讨开发多场景下搬运机器人任务调度与仿真平台，旨在通过对搬运机器人在物流中心的整箱拣选、订单拆零作业、出入库搬运作业等各个场景搭建，利用场景特性分析，探索研究搬运机器人的多智能体任务分配、多车调度及交通规划、单车路径实时优化等特定算法开发，并通过仿真平台实现对所设计的算法进行模拟和仿真验证，最终构建并验证基于实际订单数据的搬运机器人任务调度和算法测试平台的可行性。

1 搬运机器人多场景任务调度与仿真平台构建

该任务调度与仿真平台的搭建，以Marius等[9]开发的开源仿真框架RAWSim-O为基础进行二次开发，结合国内物流行业的实际情况为应用场景，在此平台基础上实现符合物流行业标准的搬运机器人多场景任务调度与仿真验证。通过调研食品、医药、饮料等物流中心的实际场景应用特性，允许自主设计对应的智能算法并在平台上进行程序实现和验证。针对以上的目标进行如下平台设计。

1.1 仿真场景设置

(1) 场景一：针对移动机器人的上架过程的策略仿真。

食品和医药等产品的上架过程涉及货位指派问题，即将商品的SKU与仓库中货位进行绑定的过程，仿真优化目标是使得订单后续的拣选时间代价最小。

(2) 场景二：针对多拣选台作业的订单波次分批策略仿真。

现代化物流中心的订单分批是指将截止到当前到达订单池中的所有订单按照一定的规则分若干波次，每次拣选台处理一个波次的订单，其目的是为了降低订单拣选时货架的搬运次数、机器人的行走距离或作业时间。

(3) 场景三：针对存在任务分级的多拣选机器人任务分配策略仿真。

机器人搬运物流系统中，“货到人”机器人系统的任务分配是按照一定的规则，把空闲的搬运机器人资源和系统待执行任务进行最佳匹配的过程。

(4) 场景四：针对有存储规则限制的多机器人路径规划与协调策略仿真。

不同的存储规则设置对机器人的路径选择有较大影响。合理地进行多机器人路径动态规划，可以有效避免出现通道拥塞等问题。

1.2 仿真验证要求

1.2.1 场景一：针对移动机器人的上架过程的策略仿真

以食品和医药物流中心为例，在满足食品质量管理规范的情况下，通常考虑SKU的关联性、货物周转率等因素进行优化。比如药品要根据GSP的相关要求，需要满足药品和非药品分开、外用用药和内服用药分开、监管类药品和非监管类药品分开、易串味药品和其他药品分开等规则。这样的上架过程和传统的电商上架策略有明显区别。在仿真平台中可以针对物流上架过程的策略进行算法设计并进行模拟验证。

1.2.2 场景二：针对多拣选台作业的订单波次分批策略仿真 由于食品物流中心需要严格进行先进先出的批次管理。在多个拣选台同时作业的情况下，如果设计的订单波次分批策略中订单波次分批的聚类度不高，则容易导致机器人的搬运次数较多，系统需要配置较多的搬运机器人才能满足需求；如果设计的订单波次分批的聚类度过高，则容易导致存在某个批次的尾订单箱在各个拣选台之间的拣选任务耦合的问题，导致整个拣选作业的效率难以提升。食品行业的特性导致订单波次分批策略和传统电商系统的处理策略有较大区别。在试验过程中可以针对实际的订单数据进行订单波次分批策略算法设计，并针对设计的算法进行仿真模拟以验证其效果。

1.2.3 场景三：针对存在任务分级的多拣选机器人任务分配策略仿真 任务分配通常需要考虑机器人行驶距离的最优、机器人的电量情况、任务执行的时间窗等。由于任务分配是一个动态分配的过程，因为不断有机器人完成释放任务，不断有新的任务到达。另外，还有充电任务也要根据充电策略及时插入机器人的任务序列中，且优先级最高。在食品物流中心，由于订单存在截单时间要求等问题，任务是非均匀下发至机器人调度系统；部分订单还存在紧急配送的需求、需要进行紧急插单或者需要增补订单内容等情况。物流中心的业务特性导致的机器人任务分批策略和传统电商的任务分批策略有较大区别。平台可以针对实际的物流中心场景进行任务分配算法设计，并针对设计的任务分配算法进行仿真模拟以验证其效果。

1.2.4 场景四：针对有存储规则限制的多机器人路径规划与协调策略仿真 传统的电商物流系统中，储位分配是基于销售品种的热销情况决定具体分布方式。通常而言，热销品种设置得离拣选站台较近，冷门商品设置得离拣选站台较远。这种储位分配方式下的多机器人路径规划，相对比较简单。在食品物流中心，由于各自产品的存储需要遵循相关的存储规则，比如巧克力、酸奶等产品必须在温度控制区进行存储等。不同存储特性的产品必须分区存放，在订单执行过程中，要实现跨区拣选的任务需求，平台可以针对食品物流的储位分配特点进行多机器人路径规划与协调算法设计，通过实际场景的布局和任务对算法进行仿真验证，从而测试多机器人路径规划与协调算法的效果。

1.3 搬运机器人多场景任务调度与仿真平台框架

搬运机器人多场景任务调度与仿真平台的本质是搭建一个离散事件系统仿真平台。其核心是针对搬运机器人作业的任务场景，模拟搬运机器人的随机和动态发生的事件，最终构建各个事件之间的关联关系。在搬运机器人多场景任务调度与仿真平台的基础上，通过算法接口完成某个具体场景下的大量随机试验，最终对试验结果进行统计，从而获得相应场景下的算法优劣性评估。基于代理(agent)的仿真建模方法被认为是研究复杂系统的有效途径，这种建模仿真技术，在建模的灵活性、层次性和直观性方面较传统的建模技术都有明显的优势，非常适合机器人搬运系统的建模与仿真。

基于代理的仿真建模方法，通过从个体到整体、从微观到宏观来研究复杂系统的复杂性，从而克服了复杂系统难以自上而下建立传统数学模型的困难，有利于研究复杂系统具有的偶发性、非线性、随机性等特点。因此该仿真验证平台考虑采用基于代理和离散事件系统建模的方法进行仿真平台的构建，其基本框架见图1。

图1 仿真平台系统框架Figure 1 System framework of simulation platform

在仿真平台的系统框架中，“代理”主要是模拟搬运机器人系统中的物理世界对象(如机器人、货架、货位、工作站、商品等)，也可以模拟搬运机器人系统中的虚拟实体(如模拟订单流等)。

“仿真器”在整个仿真平台系统的任务包括：① 更新代理的属性；② 将“代理”触发的事件传递给“控制器”，“控制器”可以立即做出决策，也可以缓冲多个请求，稍后通过优化算法后再发布决策；③ 将最终的信息公开给可视化组件，用户通过界面观测仿真系统的运行情况，也可以与界面进行交互，改变策略，实时干涉仿真的运行。

仿真平台模拟的拣选作业仿真流程如图2所示。

图2 拣选作业仿真流程Figure 2 Simulation of picking process

在仿真平台的系统框架中，“控制器”是决策问题的具体实现，在该仿真验证平台中，所有的算法都体现在“控制器”的算法接口当中，仿真平台仅定义与控制器交互的接口，“控制器”包括订单分配(POA)控制器、任务分配(TA)控制器、路径规划(PP)控制器、货架储位分配(PSA)控制器、拣选货架选择(PPS)控制器等。当“控制器”运行优化算法时，允许控制器缓冲某些决策(如分拣订单的波次分配)，并行运行优化过程，并稍后提交决策。由于部分算法需要较长的计算时间以得出决策，在这种情况下，可以通过软件上的多线程技术在算法运算的同时计算和更新其他与此无关对象的状态，从而加快仿真平台的推进速度。

2 基于记忆精英种群的灾变自适应大邻域搜索算法(MEPCALNS)

针对场景三“针对存在任务分级的多拣选机器人任务分配策略仿真”，根据医药物流中心的作业特点，考虑在拣选工作站排队约束和“待拣选”货架的唯一性约束，以机器人完工时间最小为目标建立任务分配数学模型，并进行仿真验证。构建的典型地图布局示意图如图3所示。

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

任务分配问题可以描述为：考虑下发给拆零拣选工作站某个批次的拣选任务可以按订单行拆分为M个拣选作业任务(简称任务)；现有N个机器人共同执行这些任务，每个搬运任务只能由一个机器人进行执行，满足每个机器人同时只能执行一个搬运作业任务；任务分配算法需要在满足客户订单设置的优先级约束下为每个机器人分配一个任务列表，机器人按优化后的作业流程顺序执行任务列表中相应的任务，目标期望达到所有机器人完成其对应的任务列表的最大完工时间最短。

建立数学模型，各参数含义见表1。

表1 数学模型参数说明Table 1 Description of mathematical model parameters

目标函数

(1)

约束于

J1J2∪…∪JN=J，

(2)

Jr∩J2=Ø,∀r∈R,∀s∈R,r≠s，

(3)

(4)

(5)

其中，目标函数式(1)表示所有机器人的最大任务列表的完工时间最小化。约束条件式(2)表示所有任务均可以被分配，式(3)表示机器人所分配到的任务不会重复，式(4)、式(5)为客户订单执行的优先级约束。式(4)表示任务队列中，内部排序中后序任务的优先级不能高于前序任务的优先级；式(5)表示任务队列之间后序任务队列的优先级不能高于前序任务队列的优先级。

针对上述模型的求解，提出基于记忆精英种群的灾变自适应大邻域搜索算法(Memory Elite Population based Catastrophe Adaptive Large Neighborhood Search，MEPCALNS)，其算法流程见图4。

图4 MEPCALNS流程图Figure 4 MEPCALNS flow chart

MEPCALNS在仿真平台设置参数见表2。

表2 平台参数设置Table 2 Experimental parameter settings

基于大、中、小3种订单规模以及5种地图规模随机生产正交算例RAND1-1～RAND1-5、RAND2-1～RAND2-5、RAND3-1～RAND3-5。具体算例设置见表3。

表3 算例设置Table 3 Example settings

采用仿真平台对派遣规则、自适应大领域搜索算法(Adaptive Large Neighborhood Search，ALNS)和试验设计的基于记忆精英种群的灾变自适应大邻域搜索算法MEPCALNS进行实验验证，结果见表4。

表4 算法有效性试验结果†Table 4 Experimental results of algorithm effectiveness

由表4可知，启发式算法在所有算例中的求解效果均明显优于传统的派遣规则。而基于记忆精英种群的灾变自适应大邻域搜索算法(MEPCALNS)相对ALNS算法而言，算例的提升效率比较稳定，说明MEPCALNS算法在求解“场景三”的相关问题时，相比ALNS算法存在优越性，算法效率平均提升3.16%。

3 结论

试验表明，通过搬运机器人多场景任务调度与仿真平台的构建，可以根据使用者所选择的场景进行实际调研，设计各种优化算法，并在平台上采用同样的参数配置和场景地图，将设计的算法和传统的算法进行仿真验证，有效解决了现有仿真平台的不足。该任务调度与仿真平台目前是基于仿真时钟的事件驱动模式，随着5G和数字孪生技术的进一步发展，未来存在通过5G技术采集现场实时状态信息，升级为数字孪生平台的可能性。