在物流仓储场景中，无序混合纸箱码垛机器人有着大量的应用需求。对于乱序到来的、多种尺寸规格的箱子，如何用机器人实现自动、高效的码垛，节省人力的同时提升物流周转效率，是物流仓储自动化的一个难点问题。其核心是求解装箱问题（binpackingproblem，bpp）这一经典的np难题，即为每一个纸箱规划在容器中的摆放位置，以化容器的空间利用率。求解bpp问题的传统方法大多是基于启发式规则的搜索。
在实际应用场景中，机器人往往无法预先看到传送带上即将到来的所有箱子，因而无法对整个箱子序列进行全局最优规划。因而现有的bpp方法无法被直接用于真实物流场景。
事实上，人可以根据即将到来的几个箱子的形状尺寸，很快地做出决策，并不需要、也无法做到对整个箱子序列的全局规划。这种仅仅看到部分箱子序列的装箱问题，称为在线装箱问题（onlinebpp）。物流输送线边上的箱子码垛任务一般都可以描述为onlinebpp问题。因此，该问题的求解对于开发真正实用的智能码垛机器人有重要意义。
在onlinebpp问题中，机器人仅能观察到即将到来的k个箱子的尺寸信息（即前瞻k个箱子），我们称其为bpp-k问题。对按序到来的箱子，机器人必须立即完成规划和摆放，不允许对已经摆放的箱子进行调整，同时要满足箱子避障和放置稳定性的要求，最终目标是化容器的空间利用率。onlinebpp问题的复杂度由箱子规格、容器大小、箱子序列的分布情况、前瞻数量等因素共同决定。由于仅知道部分箱子序列的有限信息，以往的组合优化方法难以胜任。
强化学习是一种通过自我演绎并从经验中学习执行策略的算法，很适合求解onlinebpp这种基于动态变化观察的序列决策问题。同时，堆箱子过程的模拟仿真非常「廉价」，因而强化学习算法可以在模拟环境中大量执行，并从经验中学习码垛策略。
然而，将强化学习算法应用到onlinebpp上面临几个方面的挑战：首先，如果将水平放置面划分成均匀网格，bpp的动作空间会非常大，而样本效率低下的强化学习算法并不擅长应对大动作空间的问题；此外，如何让强化学习算法更加鲁棒、高效地学习箱子放置过程中的物理约束（如碰撞避免、稳定支持等），也是需要专门设计的。
为了提升算法的学习效率，同时保证码放的物理可行性和稳定性，作者在actor-critic框架基础上引入了一种「预测-投影」的动作监督机制。该方法在学习actor的策略网络和critic的q值（未来奖励的期望）网络之外，还让智能体「预测」当前状态下的可行动作空间（可行掩码，feasibilitymask）。在训练过程中，依据预测得到的可行掩码将探索动作「投影」到可行动作空间内，再进行动作采样。这样的有监督可行性预测方法，一方面可以让强化学习算法学习到物理约束，另一方面也尽可能避免了训练中箱子放置到不可行位置而提前终止序列，从而显著提升训练效率。
如果算法能够在码放当前箱子的同时考虑之后到来的箱子尺寸，可能会得到更好的码放效果（如图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）。在三种不同数据集上，基于深度强化学习算法的性能显著优于人为设计启发式规则（尤其是面向onlinebpp的）。
同样在bpp-1问题上，作者针对不同的约束项进行了消融实验（图6）：mp-可行掩码预测；mc-可行掩码投影；fe-动作熵（多样性）化。实验结果表明，在训练过程中加入可行动作约束对训练效果有显著提升。
作者在bpp-k上验证了排序树搜索可以使空间利用率随着前瞻数量k的提升而提升（图7b），而使用蒙特卡洛树搜索可以在不明显影响性能的前提下，显著降低排序树搜索的时间开销（图7a）。此外，作者针对bpp-1进行了用户研究，比较本文bpp-1算法和人摆放的空间利用率。如图7c所示，本文方法超越了人类摆放的性能：在总共个高难度随机箱子序列中，人类获胜的次数是406次，平均性能表现是52.1%，而强化学习获胜的次数是次，平均性能表现是68.9%。
对于不同的前瞻箱子数，本文方法和启发式算法bph的性能对比情况如图8所示。尽管bph算法允许对前瞻箱子的顺序进行任意调整而本文方法不允许，但本文方法仍然能取得更好的性能。
为验证本文算法的有效性，作者团队将模型部署到工业机器人上，实现了一个智能码垛机器人（图9，查看完整视频）。将仿真环境训练的策略应用到真实环境，涉及从虚拟到真实环境的策略迁移（sim2real）问题。为此，作者基于「real2sim」的思路，采用3d视觉算法，实时检测容器上箱子的真实摆放情况，并转换为与虚拟世界对应的理想box表示，作为强化学习模型的输入。对于乱序到来的随机尺寸箱子，该机器人能够连续、稳定、码放数十个箱子，容器空间利用率达到70%以上，性能远超现有同类型机器人。
