原文:Real-time order dispatching for a fleet of autonomous mobile robots using multi-agent reinforcement learning(2020)
摘要
自主移动机器人(AMRs)越来越多地被用于动态生产环境中实现高效的物料流动。由于环境的快速变化带来的复杂性,以及调度、路径规划和路径执行之间的紧密耦合,在这样的环境中调度运输订单非常困难。对于订单调度,提出了一种使用多agent强化学习的方法,其中AMR agent根据各自的观察学习对订单进行投标。在机器人仿真环境中研究了该方法。结果表明,与常用的调度规则相比,该算法的订单分配效率更高。
1. 绪论
移动物资运输系统通常由自动引导车辆(agv)组成——无人驾驶的移动车辆能够遵循预定的运输路线。这些路线通常是由放在地板上的磁带来确定的。然而,最近一种被称为自主移动机器人(AMRs)的更先进的车辆正在被越来越多地使用。amr与agv的导航能力不同。它们配备了各种传感器,可以探测周围的静态和动态物体,从而实现自主定位和导航。它们的路径是根据静态和动态障碍物实时生成的,使amr可以自由移动,而不需要预定义的路由。
虽然系统的灵活性得到了提高,但实时路径生成带来了车队管理系统(FMS)必须满足的额外挑战,该系统执行诸如运输订单调度、车辆路由和任务执行调度等活动。在amr的情况下,这些可能是紧密耦合的,这导致整个系统的计算复杂度很高。例如,当考虑到执行的所有可能AMR路径和时间窗口时,即使将几个传输命令分配给两个AMR也会遭受组合爆炸的影响。因此,集中的AMR车队管理和订单执行优化往往无法实时执行。
这可以通过分离FMS活动并分别考虑它们来解决。例如,为了单独考虑调度问题,必须在问题制定中排除路由和调度。从调度的角度来看,AMR只需要能够从A点(例如取货点)移动到B点(例如落货点)。它选择哪条路线,如何避开障碍等等都是由AMR自主解决的。然后,通常使用集中方法,其中简单规则(启发式)定义对amr的顺序分配。这些规则通常没有考虑到特定问题的设置,如工厂布局或单个AMR能力,并可能导致次优解决方案,甚至导致系统作为一个整体的不稳定行为,例如死锁。
为此,本文提出了一种基于多智能体强化学习(RL)的分布式实时订单调度方法。该方法使调度适应特定的情况,这是由于工厂布局和运输订单到达的动态而产生的。amr由代理代表,代理根据对环境的观察学会对单个运输订单出价。该方法通过基于物理的AMR仿真验证。并与常用的实时调度规则进行了比较。
2. 移动运输系统的订单调度
在工场,运输订单可能是多种多样的,它们的到达可能很难****,使长期规划变得困难。由于上述计算的复杂性,往往更好的是实时进行调度决策,即在新订单出现时,使用简单的规则将订单与车辆进行匹配。可以在订单端启动对合适匹配的搜索,其中必须为订单从车队中选择合适的车辆,或者在车辆端启动对最合适的订单的搜索,并将其分配给单个车辆[3]。
单属性调度规则分为三类:1)基于距离的调度规则,考虑了出行距离;(2)基于工作量的调度规则,考虑了工作站队列占用;(3)基于时间的调度规则,考虑了运输订单[4]的到达顺序。
利用离散事件模拟进行的评估表明,不同调度规则的性能受到各种因素的强烈影响,如工厂布局、订单到达间隔时间、AGV行程时间与装配时间的比例等。
选择**规则并不简单。在[6]中,为了提高调度效率,利用机器学习分析了各种调度规则的性能。当考虑自由移动的机器人车辆行驶时间的变异性较大时,调度规则的选择就更加困难。此外,在动态变化的环境中运行良好的调度规则在系统重构后可能会变得不够用。
另外,调度也可以作为分布式问题来处理,其中代理[7]通过竞标过程进行交互,以分配交付任务或通过多代理强化学习制定调度策略。由于大部分计算分布在各个代理之间,这种方法的好处包括更好的可伸缩性和对更改的更快响应,而不需要系统范围内的重新计算。分布式系统也可以更加健壮,但另一方面,它们也可能表现出不可预测的新行为。然而,随着新的框架和学习算法的发展,分布式方法的能力正在迅速提高。
3.多智能体强化学习
在强化学习(RL)中,代理通过试错、观察环境、选择和执行动作以及收集奖励来学习。他们的目标是学习以一种能最大化获得奖励的方式行动。
4. 基于多agent RL的实时订单调度
要将RL应用到实时订单调度中,定义状态空间和状态之间的转换具有挑战性,因为糟糕的定义可能会受到大的状态空间或行动和奖励之间的延迟的影响,从而模糊因果关系。后者是调度设置中的一个关键问题,因为只有在运输订单完全执行之后才会颁发奖励或惩罚,而这可能是在发送订单很久之后。在制定调度问题时,必须考虑到这个问题。
订单调度被建模为一个多agent RL问题,其中学习agent是代表AMR车辆的决策单元,并与学习环境相互作用,如图1所示。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容,请联系我们,一经查实,本站将立刻删除。
如需转载请保留出处:https://51itzy.com/kjqy/115083.html