火马电竞_基于带约束强化学习的BPP-1求解

发布时间 : 2021-06-27 02:18  浏览次数 : 111 次

  国防科技大学、克莱姆森大学和视比特机器人的研究人员合作使用深度强化学习求解在线装箱问题,该方法的性能表现优于现有的启发式算法。用户研究显示,该算法达到甚至超越了人类的在线码垛水平。作者团队还将训练模型部署到了工业机器人上,实现了业界首个高效能(连续码放 50 个以上随机尺寸箱子,空间利用率大于 70%)无序混合码垛机器人。

  在物流仓储场景中,无序混合纸箱码垛机器人有着大量的应用需求。对于乱序到来的、多种尺寸规格的箱子,如何用机器人实现自动、高效的码垛,节省人力的同时提升物流周转效率,是物流仓储自动化的一个难点问题。其核心是求解装箱问题(Bin Packing Problem,BPP)这一经典的 NP 难题,即为每一个纸箱规划在容器中的摆放位置,以最大化容器的空间利用率。求解 BPP 问题的传统方法大多是基于启发式规则的搜索。

  在实际应用场景中,机器人往往无法预先看到传送带上即将到来的所有箱子,因而无法对整个箱子序列进行全局最优规划。因而现有的 BPP 方法无法被直接用于真实物流场景。

  事实上,人可以根据即将到来的几个箱子的形状尺寸,很快地做出决策,并不需要、也无法做到对整个箱子序列的全局规划。这种仅仅看到部分箱子序列的装箱问题,称为在线装箱问题(Online BPP)。火马电竞物流输送线边上的箱子码垛任务一般都可以描述为 Online BPP 问题。因此,该问题的求解对于开发真正实用的智能码垛机器人有重要意义。

  在 Online BPP 问题中,机器人仅能观察到即将到来的 k 个箱子的尺寸信息(即前瞻 k 个箱子),我们称其为 BPP-k 问题。对按序到来的箱子,机器人必须立即完成规划和摆放,不允许对已经摆放的箱子进行调整,同时要满足箱子避障和放置稳定性的要求,最终目标是最大化容器的空间利用率。Online BPP 问题的复杂度由箱子规格、容器大小、箱子序列的分布情况、前瞻数量等因素共同决定。由于仅知道部分箱子序列的有限信息,以往的组合优化方法难以胜任。

  近日,国防科技大学、克莱姆森大学和视比特机器人的研究人员合作提出了使用深度强化学习求解这一问题。该算法性能优异,实现简单,可适用于任意多个前瞻箱子的情形,摆放空间利用率达到甚至超过人类水平。同时,该团队结合 3D 视觉技术,实现了业界首个高效能无序混合码垛机器人。论文已被人工智能顶会 AAAI2021 大会接收。

  作者使用带约束的深度强化学习求解 BPP-1 问题,即只能前瞻一个箱子的情形。然后基于蒙特卡洛树搜索实现了从 BPP-1 到 BPP-k 的拓展。下图 1 给出了 BPP-1 和 BPP-k 问题的场景示意。

  强化学习是一种通过自我演绎并从经验中学习执行策略的算法,很适合求解 Online BPP 这种基于动态变化观察的序列决策问题。同时,堆箱子过程的模拟仿真非常「廉价」,因而强化学习算法可以在模拟环境中大量执行,并从经验中学习码垛策略。然而,将强化学习算法应用到 Online BPP 上面临几个方面的挑战:首先,如果将水平放置面划分成均匀网格,BPP 的动作空间会非常大,而样本效率低下的强化学习算法并不擅长应对大动作空间的问题;此外,如何让强化学习算法更加鲁棒、高效地学习箱子放置过程中的物理约束(如碰撞避免、稳定支持等),也是需要专门设计的。

  为了提升算法的学习效率,同时保证码放的物理可行性和稳定性,作者在 Actor-Critic 框架基础上引入了一种「预测 - 投影」的动作监督机制(图 2)。该方法在学习 Actor 的策略网络和 Critic 的 Q 值(未来奖励的期望)网络之外,还让智能体「预测」当前状态下的可行动作空间(可行掩码,feasibility mask)。在训练过程中,依据预测得到的可行掩码将探索动作「投影」到可行动作空间内,再进行动作采样。这样的有监督可行性预测方法,一方面可以让强化学习算法快速学习到物理约束,另一方面也尽可能避免了训练中箱子放置到不可行位置而提前终止序列,从而显著提升训练效率。

  如果算法能够在码放当前箱子的同时考虑之后到来的箱子尺寸,可能会得到更好的码放效果(如图 3 所示)。对于前瞻 k(k》1)个箱子的情况,一种方法是直接学习前瞻多个箱子的码放策略。但是,这种策略往往难以在任意前瞻箱子数目上很好地泛化。针对不同的 k 单独训练一种策略显然是不够聪明的做法。

  对此,本文的处理方法是基于 BPP-1 这一基础策略,通过排序树搜索的方法拓展到 BPP-k 的情况。事实上,前瞻多个箱子的基本思想,就是在摆放当前箱子时,为后续箱子「预留」合适的空间,以使得这些箱子的整体摆放空间利用率更高。「预留」暗含了对于 k 个前瞻箱子的不同排序。因此,我们只需要搜索 k 个前瞻箱子的不同排序(图 4),找出一种空间利用率最高的排序,该序列所对应的当前箱子的摆放位置,即为当前箱子的最佳摆放位置。这样的处理方式,等同于在当前箱子的摆放过程中考虑了后来的箱子。不过,需要注意的是,在这些虚拟的摆放序列中,实际顺序中先到的箱子不能摆在后到的上面。

  图 4:箱子的真实顺序(左上)和虚拟重排顺序(左下,实际顺序靠前的箱子不能放在实际顺序靠后箱子的上面),右边展示了不同序列的排序树。

  显然,考虑所有的排序可能很快带来组合爆炸问题。为此,作者使用蒙特卡洛树搜索(MCTS)来减小搜索空间。作者基于 critic 网络输出的 Q 值,对从当前状态之后可能得到的奖励进行估计。在排序树搜索过程中,优先选择可能得到更高奖励的节点进行展开。这样可将搜索复杂度控制在线性级别。

  此外,作者还介绍了处理箱子水平旋转和多容器码放的扩展情况。如果码放过程中允许箱子水平旋转,则只需将 BPP-1 模型中的动作空间和可行掩码同时复制,分别处理两种朝向。针对多容器码放,算法需要对箱子放入每个容器所带来的 Q 值变化进行量化:作者使用 critic 网络对箱子码放到某个容器前后的 Q 值进行评估,每次都将箱子放入 Q 值下降最小的容器内。

  在 BPP-1 上,作者将本文方法和其他启发式算法进行了对比(图 5)。在三种不同数据集上,基于深度强化学习算法的性能显著优于人为设计启发式规则(尤其是面向 Online BPP 的)。

  图 5:深度强化学习算法和启发式算法在 BPP-1 问题上的性能(摆放箱子数目和空间利用率)对比。

  同样在 BPP-1 问题上,作者针对不同的约束项进行了消融实验(图 6):MP - 可行掩码预测;MC - 可行掩码投影;FE - 动作熵(多样性)最大化。实验结果表明,在训练过程中加入可行动作约束对训练效果有显著提升。

  作者在 BPP-k 上验证了排序树搜索可以使空间利用率随着前瞻数量 k 的提升而提升(图 7b),而使用蒙特卡洛树搜索可以在不明显影响性能的前提下,显著降低排序树搜索的时间开销(图 7a)。此外,作者针对 BPP-1 进行了用户研究,比较本文 BPP-1 算法和人摆放的空间利用率。如图 7c 所示,本文方法超越了人类摆放的性能:在总共 1851 个高难度随机箱子序列中,人类获胜的次数是 406 次,平均性能表现是 52。1%,而强化学习获胜的次数是 1339 次,平均性能表现是 68。9%。

  图 7 (a):穷举排序数搜索和 MCTS 算法的时间开销对比;(b):穷举排序数搜索和 MCTS 算法的时间开销对比;(c):本文算法、启发式算法 BPH 和人类用户的码放性能对比。

  对于不同的前瞻箱子数,本文方法和启发式算法 BPH 的性能对比情况如图 8 所示。火马电竞_尽管 BPH 算法允许对前瞻箱子的顺序进行任意调整而本文方法不允许,但本文方法仍然能取得更好的性能。

  图 8:在三个数据集上的 BPP-k 任务中,深度强化学习算法与启发式算法的性能对比。

  为验证本文算法的有效性,作者团队将模型部署到工业机器人上,实现了一个智能码垛机器人(图 9,查看完整视频)。将仿真环境训练的策略应用到真实环境,涉及从虚拟到真实环境的策略迁移(Sim2Real)问题。为此,作者基于「Real2Sim」的思路,采用 3D 视觉算法,实时检测容器上箱子的真实摆放情况,并转换为与虚拟世界对应的理想 box 表示,作为强化学习模型的输入。对于乱序到来的随机尺寸箱子,该机器人能够连续、稳定、快速码放数十个箱子,容器空间利用率达到 70% 以上,性能远超现有同类型机器人。

  文章出处:【微信号:vision263com,微信公众号:新机器视觉】欢迎添加关注!文章转载请注明出处。

  众包是一种应用群体智慧的分布式问题求解机制,目前广泛存在于以人工智力活动为基础的互联网应用场景中,利。。。。

  为对港口货运量进行科学精准预测,结合夭牛须搜索( beetle antennae search,BA。。。。

  数值流形方法中网格加密是提高精度的方法辶一,全局加密会严重导致计算α率低下,因此需要硏究在数值流形法。。。。

  针对分切机收卷过程中存在的非线性、时变性、干扰性等问题,结合遺传算法(ε netic algorit。。。。

  为了解决传统粒子群算法存在早熟收敛、搜索空间受限、精度不高等问题,通过四元数理论和粒子群算法,提岀了。。。。

  针对存在移动车辆遮挡等强干扰的情况,提岀了一种基于轮廓筛选的车道线裣测方法。首先基于轮廓角度和像素数。。。。

  边坡变形监测是滑坡灾害防治和预警的重要手段,基于图像分析的近澋摄影测量方法凭借全场、非接触的优势在边。。。。

  针对多类别车辆检测任务中存在计算复杂、检测精度不高的问题,提岀一种基于中心点的多类别车辆检测算法。该。。。。

  信息采集技术日益发展导致的高维、大规模教据,给据挖掘带来了巨大挑战,针对K近邻分类算法在高维数据分类。。。。

  根据蚁群算法收敛速度较慢,易陷入局部最优等冋题,提岀了一种改进烟花-蚁群( improved fir。。。。

  (每隔 12 ms 一次)循环写入一个模拟输出端。ANOUT 将触发预进停止。机器人控制系统拥有 3。。。。

  晨检,是幼儿园一项重要的保健措施,已纳入幼儿园一日常规管理工作之中,是保证幼儿健康成长的重要关口,每。。。。

  $PRO_IP 参照解释器,使用过程指针的数据进行结构化 该变量包含将在解释器中接下来执行的块的数据。。。。

  “老板老板,城管叔叔说,您超门线经营的行为是不对的,城管叔叔希望您能自行纠正,谢谢您为美丽南坑做出贡。。。。

  简易的机器人和PLC信息提取。 ----Socket程序结构分析: --------- privat。。。。

  所有夹具和机器人的释放安全信号是A/E80-57,通过PLC顺序块控制机器人工作,如上件,焊接,下件。。。。

  BE23A是存储区3满位的检测开关。 BE12A是存储区1满位的检测开关。 BE13A是存储区2满位。。。。

  为了提高既有线路整正维修效率以及满足铁路快速发展对线路髙泙顺性的要求,结合蚁群算法在空间组合优化的优。。。。

  针对室内场景中存在获取目标对象相对位置的需求,RFⅠD( Radio Frequency Ident。。。。

  如今,人类社会存储和交换的信息总量呈几何级数飞速増长,数据传输的吞吐量和实时性亟待提升。然而,现有的。。。。

  5月22日的技术开放日则面向更广泛的科技爱好者,以科技博览会的形式,展现科技会给未来生活带来的改变。

  同时定位与地图构建( Simultaneous lolaliκ ation And Mapping,。。。。

  实时系统的错误往往十分危险甚至是致命的,使用模型检测来保证复杂实时系统的正确性是十分有效的。针对模型。。。。

  今天要分享的案例,就是隆博科技近期在光伏组件制造标杆企业落成的,柔性AMR自主备料上线解决方案,机器。。。。

  三维语义地图在移动杌器人的导航、路径规划、智能抓取、人机交互等任务中有着关键的作用,因此如何实时地构。。。。

  标记分布学习是在以标记分布标注的示例上学习的新型学习范式,近年来已成功应用于面部年龄估计、头部姿势估。。。。

  标记分布学习是在以标记分布标注的示例上学习的新型学习范式,近年来已成功应用于面部年龄估计、头部姿势估。。。。

  今天要分享的案例,就是隆博科技近期在光伏组件制造标杆企业落成的,柔性AMR自主备料上线解决方案,机器。。。。

  宇通客车是全球知名客车品牌,其客车、商用车等广泛服务于城市公交、城际客运、旅游团体等。宇通客车实行客。。。。

  无论是使用传统的方法进行人脸识别,还是使用神经网络进行人脸识别,都存在运算量大、运算时间长等问题,很。。。。

  近年来,随着深度学习在图像质量讦价领域的快速发展,泙面图像质量评价得到了有效的改善,但是立体图像质量。。。。

  通过传统的单图像超分辨率(Sυ per Resolution,SR)算法重建的高分辨率图像往往存在高。。。。

  本手册包含用于对基于IRC5的机器人系统进行故障排除的信息、步骤和描述 。

  近日,联核科技宣布完成数千万元战略融资,投资方为行业龙头企业——新松机器人。所融资金将用于人才引进以。。。。

  “大数据”已经成为计算机领域使用频率最高的专业词汇之一,而且已经逐渐变成了一个商品名称。无论是从学术。。。。

  通过精确的电力负荷预测,智能电网可以提供比传统电网更高效、可靠和环保的电力服务。现实生活中,电力负荷。。。。

  数据库作为数据存储与交互的平台,其中包含了机密与重要信息,是恶意人员攻击的对象。外部人员的攻击可通过。。。。

  近年来,学者们对静态图的研究越来越全面、深入,已经形成了完善的理论体系。但是,对于生活中的一些应用问。。。。

  随着基于位置的社交网络( Location-based Social Networks,LBSN)的。。。。

  不过千万不要小看它,这款机器人通过空气加压使尖端挤出新材料,长度可以增加到原来的数十倍,移动速度可达。。。。

  丰田汽车的子公司 Woven Planet Holdings 将以 5。5 亿美元的现金收购 Lyf。。。。

  GCC( GNU Compiler Collection)编译器编译¢语言源程序所生成的抽象语法树文。。。。

  程序控制流的设计是为实现正确的数据流服务的,数据流测试是非常重要的。文中将面向al-uses数据流准。。。。

  “我们正在努力创建一个类似于波士顿动力的组织,不过是在亚洲!” 提起自己参与研发、并创下吉尼斯世界纪。。。。

  研究的主要作者、UOW澳大利亚创新材料研究所的杰弗里·斯宾克斯(Geoffrey Spinks)教授。。。。

  编码器实现指标分析 LDPC码编码器实现编码器方案验证与优缺点分析 。。。

  什么是AES算法? 如何对AES算法进行优化? 怎样快速实现AES算法? 。。。

  本文讨论一种新型的VLD解码结构,它通过并行侦测多路码字,将Buffer中的多个可变长码一次读出,这将极大地提高VLD的吞吐量。。。

  RC5及RC6的参数及运算部件 怎么对RC5和RC6算法进行改进? 。。。

  这里先说一说电动机械的行驶速度与机械减速比的问题:行驶速度顾名思义就是机械装置在单位时间内的行走和移动的距离。而减速比则。。。

  μC/OS-Ⅱ关键算法逻辑 如何去改进μC/OS-II的关键算法? 改进的μC/OS-II在LPC2210上的移植 。。。

  在ARM上改动算法的有什么利弊吗? 什么是μc/Os-Ⅱ就绪表算法? 如何去改动μc/Os-Ⅱ就绪表算法? μc/Os-Ⅱ就绪表算。。。

本文由:火马电竞提供

上海市火马电竞
Copyright © 2015-2023 上海市火马电竞 版权所有 网站地图 ICP备17040322号-1