多机器人存取系统动态调度方法

　　摘要：针对多机器人存取系统实时性要求高，动态事件发生时易偏离调度计划的难题，提出一种动态调度方法解决此问题。对系统内发生的动态事件进行分析，确定不同动态事件造成的后果和对调度的影响。建立以完成时间最小为目标的动态调度模型。提出动态调度方法实现系统内的实时订单到达情况下的预调度和动态事件发生后的重调度。根据动态事件的不同影响，确立动态事件发生时的重调度规则。通过实例证实，相比现有调度方法所提出的动态调度方法能够及时响应紧急订单到达和机器人故障等动态事件的发生，获得完成时间更小且路径长度更短的调度方案。选择在故障时间后对受影响机器人重调度对重调度结果的影响更小。

　　关键词：多机器人存取系统;动态调度;实时调度;重调度规则

　　0引言

　　多机器人存取系统(roboticmobilefulfillmentsystem，RMFS)能够利用货架存储商品，通过自寻址机器人车(autonomousvehicle，AV)搬运货架至工作站，工作人员无需进入储区，在工作站内进行各种操作即可，完成操作后再将货架搬运回储区。相比传统拣货系统，RMFS具有更高的拣货效率、更好的系统可扩展性和柔性[1]。自2008年Kivasystems公司将其用于亚马逊的仓储作业以来[2]，MFS系统被广泛用于各大电商企业。

　　机器人论文范例： 人工智能、物联网、机器人技术对安全和责任框架的影响

　　中间的存储区域摆放货架，两边为工作站，承担拣货或补货任务。为了避免MFS系统内的AV相向冲突和死锁，大部分系统内的道路都是和图类似的单向道。空载按照道路方向运行，并可以在货架下穿行，负载只能按照道路方向运行。很多学者都针对MFS系统内的调度和优化问题展开研究，包括订单指派问题、任务分配问题、路径规划问题7]、无冲突调度问题[89]、储位优化问题10等，或是多种问题的结合问题1113。

　　但这些研究多是针对静态MFS系统，而电商企业中的订单是实时到达并要求立即响应的，对系统的实时性要求高。 针对实时RMFS系统，大部分研究都集中于任务分配、路径规划和无冲突调度等问题。Ma等(2017)[14]将AV路径规划问题建模为以最小任务完成时间为目标的多代理路径寻找问题，开发了令牌传递算法和带有任务交换的令牌传递算法，实验验证了算法规划任务的能力能否用于实时调度系统中。Yoshitake等(2019)[15]以拣货人员空闲时间为目标，建立一种实时整体调度方法，AV同时搬运RMFS系统中的货架和工作站中的拣货架。

　　Lee(2019)[16]在RMFS系统中验证了动态无冲突调度策略，采用改进A*算法根据对实时数据进行处理得到的当前状态规划路径，利用离开、绕路和启动前等待三种方式避开间的持续冲突、对头冲突和交叉口冲突。Keung等(2020)[17]在Lee研究的基础上，对多层多深度仓库布局中的六种冲突进行处理，实现实时调度。Guney和Raptis(2020)[18]开发了一个基于优先级的车辆运动协调算法解决单向网络MFS中的冲突问题，在实时调度中获得了鲁棒性更强的调度结果。这些研究的多采用启发式规则和智能算法实现任务分配，利用动态路径规划算法规划AV的路径，通过启发式规则规避动态运行时AV间的冲突，调度结果表现很好。

　　系统布局也不再局限于单向道，能够较好的在实时环境中解决之间的冲突问题。但在实际运行时，除了实时到达的订单外，MFS系统内常会出现很多动态不确定事件，导致AV调度计划与实际运行难以完全符合，甚至偏差过大导致系统停摆。因此，对MFS系统内的动态事件分析并及时处理就成为研究的关键。这些动态事件包括紧急订单到达、AV故障、路块不可用等。

　　部分学者对MFS系统内的动态事件加以研究，例如Gong等(2020)[19]建立了多机器人存取系统的高维马尔可夫模型，考虑到加急订单的实时到达，实验了机器人速度、机器人数量和拣选站数量对系统吞吐量的影响。但是由于MFS系统对实时性要求高，动态事件发生时系统情况复杂，加剧了系统内的冲突。因此现有的研究对动态事件的考虑不足，很少考虑到AV故障、路块不可用等事件以及对这类事件的处理。在其他类似的调度系统中，针对这类动态事件的处理方式可以被分为完全反应式调度、预反应式调度、预反应式鲁棒调度和主动鲁棒调度[2。其中，预反应式调度是最常用的调度方法。

　　预反应式调度方法是首先生成一个预调度方案，发生动态事件时再触发重调度。现已经被用于作业车间[2、混合流水车间[2、车辆路径问题[2等动态调度问题中，且取得了良好表现，保证动态事件发生后能够及时调整调度计划，得到新的调度方案。预反应式调度方法分为预调度和重调度两个部分。预调度的方式和静态调度类似，重调度方式包括右移重调度、部分重调度和完全重调度等25]。在MFS实际应用时，也多是通过类似的方法确保调度计划顺利进行，即先确定调度计划，在运行中根据实际情况动态调整。

　　但是由于动态事件造成的后果复杂，受影响的和路块又会发生连锁反应，造成连环冲突和死锁。工业界应用时只能用简单的启发式规则处理动态事件发生后的重调度问题，其所用规则的有效性待验证。如AV故障后，其他受影响的只有在即将进入故障路块时才能确定当前路块被占用，再进行重调度选择其他路线，由于重调度反应时间长，可能会造成死锁现象。本文针对实时MFS系统建立了多机器人存取系统动态调度方法，提出动态调度算法进行实时到达订单的任务分配、路径选择和无冲突调度以生成预调度方案，再根据系统内出现的各类动态事件，通过分析动态事件的后果，确定不同事件的处理方式，确立重调度规则，最后通过实例验证动态调度方法的有效性。

　　1问题描述

　　MFS的调度首先需要根据系统实时输入的订单，将一段时间的订单到达后统一拆分成任务。即订单是实时到达的，但待分配的任务是周期性到达的。之后，为每个可接取任务的确定当前情况下要执行的任务，完成任务分配。

　　再为接取任务的确定途径的各个路块，完成路径规划。最后，为确定各路块的进入时间和离开时间，保证多辆AV间运行时互不干扰，完成无冲突调度。调度的目的是先确定到达的任务，哪些接取哪些任务，如何完成这些任务，保证完成任务时不产生碰撞和死锁现象。

　　当出现动态事件时，需要根据调度计划和当前的动态事件，进行重调度，以保证任务顺利完成，继而完成所有订单。在调度中，路径规划部分的路径和接取的任务相关。AV接取任务后，分三个阶段完成任务：从当前路块到货架所在路块;从货架路块到工作站;从工作站返回储区。

　　完成任务需要对这三个阶段的路径进行规划。由于任务的货架所在路块和工作站不会变动，即无论哪个接取任务都需要经过这两段路径，那么这两段路径规划可以提前规划，即在任务到达后分配前规划。为了增加计划的柔性，在这两个阶段的路径规划时不只规划单条路径，而是规划出路径集。在后续调度中，对任务的第二阶段和第三阶段的路径只在路径集内进行路径选择。通过提前规划路径集，减少不必要的路径规划时间，以增加调度的效率。此外，还能在系统中单个或几个路块无法通行时，为提供备选路径。调度中的路径规划只包括在接取任务之后从当前路块到货架所在路块这一段的路径。大大减少了实时调度中所需的时间。

　　2动态调度方法

　　动态调度方法包括预调度和重调度两部分。预调度不考虑动态事件，主要包括任务分配、路径规划和无冲突调度三部分;只有在动态事件如故障发生时才进行重调度，重调度时需要分析故障情况，选取合适的重调度规则，最后得到新的调度方案。动态调度方法流程如图所示。初始输入包括初始任务数据、AV数据，实时输入包括新到达任务数据、离开工作站时间、任务完成时间、产生异常时间和异常情况。实时输出的是当前时间调度方案。如果有紧急订单到达，紧急订单到达后立刻确定紧急任务的各项信息。考虑到调度方案的稳定性，在调度中将紧急任务的优先级提高，在新一轮任务分配时和其他任务一起调度。

　　3应用实例

　　实验在IntelCorei75557、3.10GHzCPU、4.00GRAM、64位Windows10操作系统和Matlab2016a编程环境下编译运行。运行参数包括：st=0.5，turn=2.5，across=0.5，lr=3。每次禁忌搜索参数包括：种群数量，代数50。Merschformann等人设计了图所示的系统布局，通过单行道的方式避免系统内的相向冲突，但也造成了不必要的绕路。本文的数学模型可以用于任何道路方向，能够处理间的相向冲突，因此在存储区内道路可以任意通行。对图的布局修改后，本文RMFS系统布局和道路方向如图所示，箭头表示道路方向，为工作站。

　　布局图中间的存储区域全部为双向道，空载可以无障碍的穿行，负载在过道中运行。为了避免在工作站内的死锁，左右两侧工作站道路仍为单向道。辆AV同时在系统内运行，随机给定初始位置，将一定时间内的订单拆分成任务，按照一定时间间隔作为任务输入系统。任务分波到达，随机生成货架点和工作站，一共包括50个任务数据。

　　4结束语

　　针对多机器人存取系统中存在的订单实时到达、紧急订单到达、AV故障等问题，建立一种动态调度方法。首先分析系统内的不同动态事件并确定其对调度的影响，提出以最小完成时间为目标的多机器人存取系统动态调度模型。建立实时系统的动态调度方法，利用动态调度算法实现系统内的预调度和重调度。通过禁忌搜索、改进A*算法和无冲突调度方法解决任务分配、路径规划和无冲突调度问题。根据动态事件的不同影响，确立重调度规则。实例证明动态调度方法能够解决订单实时到达即任务分波次到达的情况下的AV调度问题，保证系统内的AV顺利完成所有任务，且多辆AV运行时无冲突死锁现象。

　　相比传统方法，动态调度方法获得的调度方案完成时间更小，调度时间更短，紧急订单到达时能够确保紧急订单优先完成。当出现AV故障时，能够顺利完成重调度并保证当前任务受到的影响最小。对比不同故障时间重调度的触发时机，相比传统方法中在故障路块前重调度，在故障时间后重调度任务的当前阶段完成时间更小，重调度路径长度更短，甚至能够获得比重调度前完成时间更短的调度方案。通过对比证实如果故障时有受影响，对调度的影响最大。本文目前的研究还集中于紧急订单到达和AV故障两种动态事件中，缺少对人员相关的动态事件的预测和重调度规则的研究，下一步将结合数字孪生技术针对人员暂停工作、人员突然进入系统内等事件进行预测并研究相关重调度规则。

　　参考文献：

　　[1]XUXiangin,MAZhongqiang.RoboticMobileFulfillmentSystems:StateofthertandProspects[J].ActaAutomaticaSinica,2020.(inChinese)[徐翔斌，马中强.基于移动机器人的拣货系统研究进展.自动化学报,2020.

　　[2]WURMANPR,D’ANDREAR,MOUNTZM.Coordinatinghundredsofcooperative,autonomousvehiclesinwarehouse[J].AIMagazine,2008,29(1):919.

　　ERSCHFORMANNM,LAMBALLAIST,KOSTERMBM,etal.Decisionrulesforroboticmobilefulfillmentsystems[J].OperationsResearchPerspectives,2019,6:115.

　　作者：孙阳君，赵宁

转载请注明来自发表学术论文网：http://www.fbxslw.com/jjlw/28918.html