文摘
解决动态和实时智能仓库系统中的multirobot任务分配问题parts-to-picker模式下,本文提出了一种综合解决方案基于自适应任务池策略和协方差矩阵的适应进化策略(CMA-ES)算法。在第一阶段的解决方案中,一个变量用于存储任务池动态添加的任务,它可以动态连续的和大规模的任务分配问题划分为小型子问题来解决这些问题,以满足动态需求。和一个自适应控制策略是用于自动调整的任务总数在任务池实现吞吐量之间的一种权衡,能源消耗,和等待时间,具有更好的适应性比手动调整任务池的大小。在第二阶段的解决方案中,当任务池已满,任务将分配给机器人任务池中。任务分配问题,本文认为这是一个优化问题,利用CMA-ES算法找到最优任务分配方案的机器人。通过比较与固定阈值法根据56个不同任务池大小,实验结果表明,吞吐量可以接近最优水平,和平均距离由机器人来处理每个单元使用自适应阈值方法较低;所以,自适应任务池解决方案具有更好的适应性和可以找到最优任务池大小本身。这种方法可以满足动态和实时需求,可以有效地应用于智能仓库系统。
1。介绍
近年来,各种电子商务平台的订单飙升,以及配送中心的规模变得越来越大,也带来了巨大的挑战,传统的物流行业(1]。在传统的仓库中,60%到70%的工人的时间花在捡起货物(2,效率非常低。因此,越来越多的自动机器和设备领域的应用仓库(2]。许多公司已经开始采用一种新的parts-to-picker智能仓库系统,如Kiva系统(3]。在系统如图1,机器人工作站传输存储区域的货架上,和工人需要在车站等候。货架上达到工作站时,他们所需要的商品从货架上或存储包到架子上。已经证明,这种智能仓库系统大大节省劳动力成本,提高仓库操作的效率(4]。
合作控制多个移动机器人的关键是实现智能仓储。在一个仓库,如图1,经常有大量的任务,如补充和选择,以及许多机器人来执行这些任务。此外,不同的机器人执行任务的成本也不同。因此,仓库的效率取决于选择合适的机器人来执行特定的任务。这是一个典型的multirobot任务分配(MRTA)问题[5]。与仓库的操作、任务和仓库环境会不断发生改变。如何找到一个更好的任务分配方案pick-task和replenishment-task分配在这样一个高度动态的环境3,4是本文的重点。
MRTA是最具挑战性的问题之一multirobot系统[6]。以市场为基础的方法是目前研究最多的方法,如单一任务拍卖算法提出了裁判。7]。为了解决这个问题,单一任务拍卖算法很难获得最优解,结合拍卖算法,考虑任务之间的相关性提出了裁判。8]。当机器人和任务的数量很小,MRTA可以被看作是一个0 - 1整数线性规划问题,通过单纯形法解决,分支定界法、匈牙利算法(9)等。例如,匈牙利算法采用文献[10解决角色分配问题在机器人足球比赛。还有一些基于阈值的方法,如联盟(11)和广播本地资格(祝福)12),有良好的实时、容错和鲁棒性,但通常只能获得局部最优解。对于大规模问题,启发式算法可以有效地减少解决方案空间,提高了搜索效率。例如,在裁判。13),采用启发式算法来解决多核处理器的任务分配问题。进化算法是成熟的高鲁棒性和广泛适用性的全局优化方法,它能有效地处理复杂的问题,传统优化算法难以解决。各种进化算法,如遗传算法和模拟退火算法已经广泛应用于MRTA问题。在裁判。14),遗传算法是用来解决time-extended multirobot任务分配问题的灾难。提出了一种混合遗传和蚁群算法在裁判。15)改善遗传算法的求解精度。在裁判。16),遗传算法是用来解决MRTA问题的智能仓库。Ref。17)设计了一种改进的量子进化算法基于利基共同进化策略和增强粒子群优化(IPOQEA)来解决机场门口分配问题。在裁判。18),一种改进的量子激发合作所共同进化算法和多策略用于解决背包问题和实际机场大门分配问题。参考文献。(17- - - - - -20.)使用合作共同进化框架来将复杂的优化问题划分为若干子问题,这些子问题被解决由独立搜索以提高效率的解决方案。同样,数量的任务是可变的情况下一个智能仓库可以使用分治的思想研究。参考文献(17- - - - - -20.]。
因此,我们使用一个任务池存储动态添加任务,提出一种自适应控制策略来自动调整任务池大小根据当前环境。当任务池已满,池中分配的任务的机器人。然后,任务分配问题被认为是一个优化问题,解决了由CMA-ES算法(21]。
2。问题公式化
智能仓库系统包括许多可移动的货架和机器人以及一些工作站。机器人运输所需的货架存储区域的工作站,和工人可以完成补充和选择不动。一个典型的智能仓库布局(开源软件的截图RAWSim-O [22)如图2。在图中,左边的四个方块代表补给站,和补充包暂时存储在这里等待货架。右边的四个方块代表站。收到订单后,系统将使用特殊的算法将订单分配给不同的车站。将会有一个上限的订单数量在车站23]。中间的正方形区域的货架,仓库里的货物存储。货架可以解除,机器人所感动。图中的圆圈是机器人。一个机器人可以携带一个书架。当一个机器人不携带一个书架,它可以自由移动的架子上。
为了便于问题分析,我们提出以下假设:(1)机器人都是同构和旅行速度完全相同。他们只能前进,后退,左,和正确的。(2)机器人将架子上的时间,呆在一个工作站很短,可以被忽略。(3)每个机器人携带所需的架子和从书架的位置指定车站,然后带着架子回到原来的位置。
架子上选择算法将为每个工作站根据需求选择货架。选中的货架需要从货架存储区域运送至适当的车站接或补充货物,然后回到原来的位置,这是机器人的任务。如果机器人不分配一个任务,它将移动到一个特殊的区域休息休息。如何合理分配任务,机器人是本文要研究的问题。
指的是裁判。16),假设任务(指所有任务从开始到结束的仓库操作)机器人在仓库,任务的集合 ,和机器人的集合 。一组的任务分配给机器人是 ,这是一个子集的 。 和 。让 和是命令,然后机器人完成的任务的顺序吗是 。机器人的成本完成它的任务序列可以表示为 在哪里表示机器人的成本完成所有的任务。因为所有的机器人以同样的速度旅行,成本可以表示为机器人的距离。机器人只能前进,后退,左,和正确;所以,两个点之间的距离可以表示为曼哈顿距离。
是机器人的成本从初始位置到第一个任务所需要的货架的位置 。让机器人的初始坐标 和第一个任务所需要的架子上的坐标 ,然后
代表机器人完成任务的成本 ,只有相关的任务是什么本身。它可以代表的距离后,机器人携带所需的货架,它从任务的需要架子的位置指定车站,然后返回到架子上的原始位置。我们需要架子的协调任务是 和目标站的坐标 ,然后
是机器人的成本到达下一个任务的起始位置完成任务后 。因为机器人需要运输架子上完成任务后回到原来的位置 ,它可以直接由曼哈顿距离任务所需要的货架上的位置为任务需要架子的位置 。我们需要架子的协调任务是 和任务的协调所需的架子上是 ,然后
为了使整个尽可能最优分配方案,我们认为以下两个优化目标:(1)的最长时间由机器人来完成所有任务( )(2)平均距离时,所有的机器人( )
在哪里
描述了机器人完成任务的效率。较小的是,机器人完成任务的时间越少,效率越高。描述了multirobot系统的功耗。较小的是,所有机器人的总旅行距离越短,功耗越低。方法研究的目的是合理地分配系统中的所有任务时,所有的机器人,这样这两个值可以尽可能小。
3所示。方法
3.1。体系结构
随着新订单,新任务不断生成,必须尽快完成;因此,仓库系统是一个高度动态和实时系统。在这样一个高度动态的系统,很难找到全局最优的解决方案;所以,问题是分成许多子问题。具体来说,我们创建了一个任务池中 。生成一个新任务的时候,立即加入 。当任务在任务池的数量达到阈值的阈值(自动调整将部分中描述3所示。3),CMA-ES方法部分3所示。2用于机器人任务池中分配的任务。机器人分配新任务序列插入后之前的未完成的任务序列,然后清空任务池。机器人执行任务序列,根据自己的任务和执行任务从序列中删除。重新生成新的任务,任务被添加到一次。循环直到仓库停止运行。在图3,具体步骤如下:
步骤1。初始化任务池大小和设置任务池中P是空的。所有的机器人,初始化任务序列每一个机器人 。
步骤2。任务池大小的阈值自动调整使用自适应控制策略3所示。3。
步骤3。新任务不断增加 。跳转到步骤4当任务池中任务的数量达到阈值。
步骤4。任务在任务池中分配给机器人使用CMA-ES方法部分3所示。2所有的机器人,新任务序列分配到机器人序列的末尾插入当前任务吗 。
第5步。明确任务池和跳转到步骤2。
在图上面的解决方案3执行由中央控制器,机器人只需要执行任务根据分配的任务序列。两部分的并行操作使机器人能够很忙,可以节省时间和满足实时存储系统的要求。
3.2。CMA-ES算法
就像前面提到的3所示。1、任务分配给机器人当任务池中任务的数量达到阈值。这个问题被认为是一个优化问题在一个静态环境。这是一个np难问题,CMA-ES算法找到最优解。许多领域的成功应用(24- - - - - -26]证明了CMA-ES算法是一个很好的搜索算法。
3.2.1之上。解决方案的代表
指的是裁判。27),任务分配问题任务和机器人,候选人代表任务分配方案 。 包含真正的数字,每个实数 ,它满足 ,在哪里意味着任务是由机器人 ,和意味着整数的实数 。如果 ,这意味着这个任务和都是分配给相同的机器人,任务之间由较小的号码和先执行。如果 ,这两个任务的执行顺序是随机决定的。
例如,有8个任务(用数字1、2、3、……,8)和3robots (represented by numbers 1, 2, 3), and an individual [1.7, 3.8, 2.2, 1.3, 2.8, 1.5, 3.3, 3.7] is generated. Then, the task sequence assigned to robot 1 is 。任务分配给机器人2序列 。分配给机器人的任务序列3 。
3.2.2。适应度函数
适应度函数是用来评估候选人。CMA-ES算法,较低的个体更优秀的健身价值。节2,两个优化目标提出了整个系统:一个是时间机器人完成所有任务;第二个是指驾驶距离所有的机器人。每个计划都可以被视为整体的子问题。对于每个子问题,为了达到最佳的总体性能,这两个目标仍然认为;所以,适应度函数通过以下方程计算16]: 在哪里是一个常数,可以根据实际需求调整。如果更多的关注单个订单的完成时间,可以增加。如果更多的关注时,所有的机器人的能源消耗,可以减少。机器人的成本吗在当前任务执行任务,然后执行任务序列根据候选人。由机器人的最大时间。是平均距离的机器人。在当前时刻,可能有未完成的任务在任务序列。机器人必须首先执行之前完成这些任务在当前时刻分配的任务。因此,对于 ,我们把它分成两部分来计算: 在哪里的成本是机器人完成任务在当前任务序列,然后呢的成本是根据候选人机器人执行任务。和由机器人的距离,计算使用方程中描述的方法(1)。
适应度函数,我们试图找到最优解的那一刻在每个优化,尝试用这种方法近似全局最优的解决方案。
3.3。自动调整任务池中
任务池中当任务的数量达到阈值时,任务池中分配的任务的机器人。阈值在作业的效率中起着决定性的作用。阈值越大,越将参与优化任务,然后是更多的计划方案将接近全局最优的解决方案。如果一个优化系统中包含的所有任务,找到的最优解的优化将是整个系统的最优解。但订单在仓库添加动态地随着时间的推移,所以任务也动态生成。随着阈值的增加,所需的时间任务池里也将增加,会发生这种情况:机器人完成分配的所有任务,但任务池中任务的数量没有达到阈值;接下来的优化不能开始,机器人只能等待。这就导致浪费时间,不能满足仓库的实时系统。此外,由于每个工作站都有订单容量限制,也有一个上限的总数系统中的任务,如果任务池大小超过了这个上限,任务在任务池的数量永远不会达到阈值,系统将停滞不前。因此,它是非常重要的适当大小的设置一个阈值。
显然,对于不同的仓库,阈值应根据实际情况设置不同。即使对于同一仓库,机器人的数量可能会调整,和订单生成的速率在不同的时间可能会有所不同;所以,不适当的阈值设置为固定值。因此,我们设计一个自适应控制策略动态调整任务池,如算法所示1。
|
||||||||||||||||||||||||||||
首先,初始阈值的设置是很重要的,这决定了寻找最优阈值的速度。我们相信,初始阈值的大小应该是有关机器人的数量和数量上限的任务在仓库里。仓库里的上限数量的任务与工作站的数量和每个工作站的能力。因此,我们提出以下启发式初始阈值计算公式: 在哪里是一个常数代表每个工作站在单位时间内的平均数量的任务,就是根据实际情况设置。站的数量,是机器人的数量。我们设置一个时间间隔(它是一个常数,可以设置根据实际需求),和每一个秒,阈值调整(1号线)。用于记录最后的调整。我们计算机器人完成的任务的总数从最后时刻调整到当前时刻,和任务完成的总数从倒数第二调整时刻最后调整,所表达的和 ,分别。如果是0,表明阈值设置的数量如此之高,以至于任务没有达到阈值,然后简单地削减一半的阈值和设置来(2号线、3号线和4号线)。如果大于或等于什么 ,它表明,最后调整系统上已经产生了积极的效果,同样的调整将(第5行和第6行),如果小于 ,它表明,最后调整系统上有一个负面影响,和反向调整将(7和8号线行)。此外,将逆转(9行)。
4所示。实验
我们使用RAWSim-O [22),一个开源框架由Merschformann et al .,作为实验平台。RAWSim-O是一个模拟框架,模拟一个智能仓库的操作系统,允许我们测试我们自己的方法。
我们使用了仓库布局图所示2。在仓库的布局,有32个机器人和550架。存储位置的架子是中部地区的布局。左边有四个补给站和四个选择站在右边。为了简化问题,我们设置一个机器人的时间呆在一个工作站,一个很小的值为0.1。
业绩评估我们的sku的总和(库存单位)在这两个项目包存储在补给站,订单拣选站作为处理单元。这是仓库的吞吐量,越高越好。我们还看平均距离由机器人来处理每个单元。这可以代表multirobot系统的功耗。
为了测试任务池阈值大小分配的影响效果,我们做了56个实验,每个实验对应不同的池大小。每个实验模拟24小时10个重复。
根据不同任务池大小,单位的数量由机器人蓝色实线,如图所示4,平均距离由机器人来处理每个单元蓝色实线,如图所示5。不同的固定阈值之间的比较结果处理单元和行进距离单位如表所示1。处理单元的最大数量是207583年固定阈值设置为18。旅行距离的最小数量单位为10.73时固定阈值设置为36岁,45岁或47。数据显示4和图5和表1,是不好的设置阈值太大或太小,这是符合我们的猜想。如果阈值设置过小,该解决方案将太远离全局最优的解决方案;因此,处理单位的数量小,旅游单位距离很大。如果阈值设置过大,该解决方案将更接近全局最优的解决方案;所以,旅行距离单位很小,但机器人将有一个长的等待时间;因此,处理单位的数量将会很小。
总之,一个糟糕的阈值可以效率很低;所以,设置手动阈值是非常危险的。因此,自动调节阈值的方法是必要的。我们使用我们自己提出的自适应控制策略进行实验,和所有条件都相同,除了阈值。根据工作站的能力,在方程(8)被设置为 ;所以,初始阈值被计算为32。结果如表所示1。我们比较结果与固定阈值的方法,如图4和5。红色虚线是自适应阈值方法,和蓝色实线是固定阈值的方法。与固定阈值18相比,自适应阈值方法恶化导致处理单位但在旅行距离单位更好的结果。与固定阈值相比,36岁,45岁,47岁,自适应阈值方法在处理单位更好的结果,但更糟糕的是导致旅游距离单位。综上所述,从这两个数据可以看出,自适应阈值方法可以接近阈值设置为最优时的水平在两个索引。实验结果表明,提出的自适应控制策略具有良好的应用效果。
5。结论
为了解决动态和实时multirobot任务分配问题的智能仓库系统,综合解决方案基于自适应任务池策略和CMA-ES算法。在解决方案的早期阶段,divide-to-conquer想法是用于设计变量的任务池,用于存储动态添加任务。设计变量任务池动态连续的和大规模的任务分配问题划分为小型子问题来解决这些问题,以满足动态需求。和一个自适应控制策略用于自动调节阈值的实时任务池大小实现吞吐量之间的一种权衡,能源消耗,和等待时间,具有更好的适应性比手动调整任务池的大小。在解决方案的后期,当任务池已满,任务在任务池中分配给机器人使用CMA-ES算法找到最优任务分配方案等所有的机器人根据适应度函数所需的最长时间和平均距离时,所有的机器人来完成所有的任务。通过比较与固定阈值法根据56个不同任务池大小,实验结果表明,该处理单元可以接近最优水平,和平均出行距离单位较低使用自适应阈值方法;确实如此,自适应阈值的解决方案具有更好的适应性。这种方法可以满足动态和实时需求,可以有效地应用于智能仓库系统。
然而,由于仓库的复杂性和动态的环境,它可能不是精确的测量由曼哈顿距离成本。因此,如何准确介绍机器人运动模型来评估成本将是下一个工作。此外,处理单元之间的关系、旅行距离单位,采取的最长时间,所有的机器人来完成所有任务,平均距离,所有的机器人都需要进一步的研究。此外,通信质量分配的影响没有考虑,将深入研究。
数据可用性
使用的数据来支持本研究的结果包括在本文中。
的利益冲突
作者宣称没有利益冲突有关的出版。
确认
这项工作是由烟台的科技项目,中国(批准号2019 xdhz085),重大基础研究山东省自然科学基金项目,中国(批准号ZR2018ZC0438),中国国家自然科学基金(批准号61673200),在Ludong大学和实验室的机器人。