国防科技大学、克莱姆森大学和SeebitRobot的研究人员合作，利用深度强化学习解决在线装箱问题。这种方法的性能优于现有的启发式算法。用户研究表明，该算法在在线码垛方面达到甚至超过了人类的表现。作者团队还将训练模型部署到工业机器人上，实现了业界首款高效率（连续码放50多个随机大小的箱子，空间利用率大于70%）无序混合码垛机器人。在物流仓储场景中，杂乱混杂的纸箱码垛机器人有着大量的应用需求。对于杂乱无章到货的各种大小规格的箱子，如何利用机器人实现自动高效码垛，节省人力，提高物流周转效率，是物流仓储自动化面临的难题。其核心是解决经典的NP问题BinPackingProblem(BPP)，即规划每个纸箱在集装箱内的放置位置，使集装箱的空间利用率最大化。大多数解决BPP问题的传统方法都是基于启发式规则搜索。在实际应用场景中，机器人往往无法提前看到传送带上所有即将到来的箱子，因此无法对整个箱子序列做出全局最优规划。因此，现有的BPP方法不能直接用于实际物流场景。事实上，人们可以根据即将到来的盒子的形状和大小快速做出决策，没有必要也不可能对整个盒子序列进行全局规划。这种只看到部分装箱序列的装箱问题称为在线装箱问题（OnlineBPP）。物流输送线上的箱子码垛任务一般可以描述为一个在线BPP问题。因此，该问题的解决对于研制真正实用的智能码垛机器人具有重要意义。在OnlineBPP问题中，机器人只能观察到即将到来的k个盒子（即期待k个盒子）的大小信息，我们称之为BPP-k问题。对于按顺序到达的箱子，机器人必须立即完成规划和放置，不允许调整已经放置好的箱子。同时还要满足箱体避障和放置稳定性的要求。最终目标是最大化容器的空间利用率。.OnlineBPP问题的复杂性由框规格、容器大小、框序列分布和前瞻次数等因素决定。由于只有部分框序列的信息有限，以前的组合优化方法无法胜任。最近，国防科技大学、克莱姆森大学和VitexRobotics的研究人员合作，提出使用深度强化学习来解决这个问题。该算法性能优良，实现简单。可适用于任意数量前视箱的情况，放置空间利用率达到甚至超过人类水平。同时，团队结合3D视觉技术，实现了业界首款高效随机混合码垛机器人。论文已被人工智能顶级会议AAAI2021录用。论文链接：https://arxiv.org/abs/2006.14978方法介绍作者使用约束深度强化学习来解决BPP-1问题，即只能向前看一个框的情况。然后基于蒙特卡洛树搜索实现了从BPP-1到BPP-k的扩展。下面的图1显示了BPP-1和BPP-k问题的场景。图1（上）：BPP-1场景图，绿色框为前视框。图1（下）：BPP-k问题的场景图，绿色方框为forwardbox。SolvingBPP-1basedonconstrainedreinforcementlearning强化学习是一种通过自我推演和从经验中学习执行策略的算法，非常适用于解决OnlineBPP等基于动态变化观察的时序决策问题。同时，码垛过程的模拟非常“廉价”，因此可以在模拟环境中大量执行强化学习算法，从经验中学习码垛策略。但是，将强化学习算法应用到OnlineBPP中存在几个挑战：首先，如果将水平面划分为均匀的网格，BPP的动作空间会非常大，样本效率低的强化学习算法并不擅长处理动作空间大的问题；此外，如何让强化学习算法在学习盒子放置过程中的物理约束（如防撞、稳定性支持等）时更加鲁棒和高效，也需要专门设计。为了在保证堆叠的物理可行性和稳定性的同时提高算法的学习效率，作者引入了一种基于Actor-Critic框架的“预测-投影”动作监督机制（图2）。除了学习Actor的策略网络和Critic的Q值（预期未来奖励）网络之外，该方法还允许代理“预测”当前状态下的可行动作空间（可行性掩码）。在训练过程中，根据预测的可行掩码将探索动作“投射”到可行动作空间中，然后对动作进行采样。这样一种有监督的可行性预测方法，一方面可以让强化学习算法快速学习到物理约束，另一方面也尽可能的避免了盒子被放置在一个序列中时的提前终止。训练过程中的不可行位置，从而显着提高训练效率。图2：具有基于预测-投影的动作监督的受限深度强化学习。BPP-kextensionbasedonMonteCarlotreesearch图3：本文算法的空间利用率与前瞻框数量正相关。如果算法在堆叠当前框的同时能够考虑到后续框的大小，则可能会获得更好的堆叠效果（如图3所示）。对于期待k(k>1)个盒子的情况，一种做法是直接学习期待多个盒子的堆叠策略。然而，这种策略通常难以很好地泛化到任意数量的前瞻容器。针对不同的k单独训练一个policy显然不够聪明。对此，本文的处理方法是在BPP-1的基本策略的基础上，通过排序树搜索的方法扩展到BPP-k的情况。事实上，前瞻性多重盒子的基本思想是在放置当前盒子时，为后续的盒子“预留”合适的空间，让这些盒子的整体空间利用率更高。“预留”意味着k个先行分箱的不同排序。因此，我们只需要搜索不同排序的k个前瞻框（图4），找到一个空间利用率最高的排序，该序列对应的当前框就是当前框的最佳放置位置。这样的处理方式相当于在当前框的放置过程中考虑了后续的框。然而，需要注意的是，在这些虚拟放置顺序中，实际顺序中先到的盒子不能放在后到的盒子之上。图4：盒子的真实顺序（左上）和虚拟重排顺序（左下，实际顺序较高的盒子不能放在实际顺序较晚的盒子之上），右侧显示不同序列的排序树。显然，考虑所有顺序会很快导致组合爆炸问题。为此，作者使用蒙特卡洛树搜索(MCTS)来减少搜索空间。作者根据critic网络输出的Q值估计了当前状态下可能的奖励。在排序树搜索过程中，优先选择可能获得较高奖励的节点进行扩容。这使搜索复杂度保持在线性水平。此外，作者还介绍了处理盒子水平旋转和多容器堆叠的扩展。如果在stacking过程中允许box水平旋转，只需要同时复制BPP-1模型中的actionspace和feasiblemask，分别处理两个orientation。对于多容器堆叠，算法需要量化将盒子放入每个容器所引起的Q值变化：作者使用critic网络评估盒子代码放入一个容器前后的Q值，并把每次都装进Q值。该值会掉落最小的容器。实验结果在BPP-1上，作者将本文的方法与其他启发式算法进行了比较（图5）。在三个不同的数据集上，基于深度强化学习的算法的性能明显优于人工设计的启发式规则（尤其是对于OnlineBPP）。图5：深度强化学习算法和启发式算法在BPP-1问题上的性能比较（放置的盒子数量和空间利用率）。同样在BPP-1问题上，作者针对不同的约束进行了消融实验（图6）：MP-FeasibleMaskPrediction；MC-可行掩模投影；FE-动作熵（多样性）最大化。实验结果表明，在训练过程中加入可行动作约束可以显着提高训练效果。图6：本文算法在BPP-1问题上的消融实验作者在BPP-k上验证了排序树搜索随着look-ahead数k的增加可以提高空间利用率（图7b），同时使用蒙特卡洛树搜索可以显着减少排序树搜索的时间开销，而不会显着影响性能（图7a）。另外，作者对BPP-1进行了用户研究，比较了本文BPP-1算法的空间利用率和人体放置。如图7c所示，本文方法超越humanplacement的性能：在总共1851个高难度随机box序列中，humanwins的次数为406次，平均性能为52.1%，而number强化学习获胜次数为1339次，平均成绩为68.9%。图7(a)：穷举排序号搜索和MCTS算法的时间开销比较；(b)：穷举排序号搜索与MCTS算法的时间开销比较；(c)：本文算法、启发式算法BPH与人类用户的堆叠性能比较。对于不同数量的前瞻框，本文方法与启发式算法BPH的性能比较如图8所示。虽然BPH算法允许任意调整lookaheadbins的顺序而我们的方法不允许，但我们的方法仍然可以获得更好的性能。图8：深度强化学习算法与启发式算法在三个数据集上的BPP-k任务上的性能。为了验证本文算法的有效性，作者团队将模型部署到工业机器人上，实现了智能码垛机器人（图9，查看完整视频）。将在模拟环境中训练的策略应用到真实环境中涉及策略从虚拟环境到真实环境（Sim2Real）的迁移问题。为此，作者基于“Real2Sim”的思想，利用3D视觉算法实时检测箱子在容器上的真实放置，并将其转化为对应于虚拟世界的理想箱子表示，用作强化学习模型的输入。对于乱码到货的大小不一的箱子，该机器人可连续、稳定、快速地码垛数十个箱子，箱位利用率超过70%，远超现有同类型机器人。图9：基于深度强化学习的高效无序混合码垛机器人。
