简介
装箱问题作为一个经典的离散优化问题，已经在计算机图形学领域中出现了引人注目的几何应用，例如纹理图生成、艺术排版、二维面板制造和三维打印等。在这些应用中，仅需优化虚拟对象的装箱效果，以用于显示、存储或制造等场景中。然而，在其他涉及物理对象的实际应用中（如机器人装箱运输等），通常还必须应对更多的约束条件。物理装箱问题的一个重要变化是，在初始时，物体就已经处于某种空间配置中了，例如积累的仓库库存等。因此，物体的移动必须遵循一些先后顺序，比如压在某个物体上面的物体被转移并装箱之前，前者无法被移动。因此，虽然装箱问题本身已经是一个困难的组合优化问题了，本文提出的新变体在其之上又增加了一个新的搜索维度，即转移规划，这使其成为转移和装箱（缩写：TAP）问题。
标题：[SIGGRAPH Asia 2020] TAP-Net: Transport-and-Pack using Reinforcement Learning
作者：Ruizhen Hu (Shenzhen University), Juzhan Xu (Shenzhen University), Bin Chen (Shenzhen University), Minglun Gong (University of Guelph), Hao Zhang (Simon Fraser University), Hui Huang (Shenzhen University)
论文主页：https://vcc.tech/research/2020/TAP
代码开源：https://github.com/Juzhan/TAP-Net
图1 物体转移装箱（TAP）问题示意图1.创新点
本文提出了物体转移装箱问题（transport-and-pack, TAP），对于一组已知摆放状态的物体，本文希望找到一个将它们逐个转移并紧凑装箱的方案。由于物体之间的阻挡等物理限制，相比起单纯的装箱问题，要解决转移装箱问题还需要额外寻找最优且满足限制的转移顺序。为此本文设计了一个基于强化学习的神经网络组合优化方案，输入要进行转移装箱的物体初始状态，输出最后进行装箱的物体顺序、摆放位置与旋转状态。本工作的主要贡献有：
（1）提出了物体转移装箱问题，该问题比起一般的装箱问题有更加普遍的应用场景。
（2）提出了一个神经网络的组合优化算法，其核心为一个使用增强学习训练的基于注意力机制的网络：TAP-Net。
（3）设计了一个扩展机制让本文的算法可以处理比训练数据规模更大更复杂的实例。
2.相关工作
2.1 图形学中的装箱问题
装箱问题在图形学中有大量的应用，学者们对此进行了广泛的探索和研究。例如，在模型图表化问题中，要将三维模型的颜色、纹理或法线等表面信息存储到二维平面，该过程需要最大化二维装箱效率[1]。Ma等人[10]提出了一种在给定容器内以非重叠配置的方式，尽可能多地放置给定不规则物体的方法，以最大程度地减少工业制造过程中的材料浪费。
最近分解装箱问题开始被学者们研究，不同于纯粹的装箱问题，该问题要装箱的形状是从一个输入物体上分解或切割得到的。Limper等人[2]通过允许在原物体上添加新的分割，同时优化形状的分解和装箱，以最大化装箱效率。Koo等人[3]通过允许家具的二维几何形状略微变化，从而指导家具设计的修改。
2.2 装箱问题解决方案
装箱问题作为经典的NP-hard组合问题，目前已有各种启发的技术被提出。一种常见的策略是分两步解决装箱问题：先确定装箱顺序，然后基于某种固定的装箱策略逐个将物体装箱。装箱顺序可以使用传统的遗传算法、模拟退火算法或更先进的基于强化学习的方法[6][7]进行优化。装箱策略也有不同的选择，例如最深最低最左填充策略[4]，最大剩余空间策略[5]等。
2.3 应用神经网络解决组合优化问题
指针网络（缩写：Ptr-Net）[8]是用于解决组合问题的最著名的神经网络结构之一，它被训练用于寻找如平面旅行商问题等组合问题的近似解。Bello等人[7]将强化学习方法应用到Ptr-Net中，获得了一个无监督的学习范例，他们证明了对于旅行商问题而言，有监督训练的Ptr-Net的泛化能力弱于使用强化学习训练的，因为后者探索了更多不同的旅行线路并得到了相应的回馈。这种网络结构输入和输出都是序列。
Nazari等人[9]认为当输入集的顺序没有意义时，Ptr-Net中使用的循环神经网络结构给编码器增加了额外的复杂性，比如他们关注的车辆路径问题和本发明要解决的TAP问题，属于“集合到序列”的问题。此外，由于车辆路径问题的动态特性，他们还允许每个输入的某些元素在每一步解码之后能够进行更改。
3.方法描述图2 TAP-Net算法流程示意图
3.1 算法概要
对于一组已知摆放状态的物体，算法的目标是将这些物体逐个转移装箱到一个目标容器中。本文用物体的包围盒来表示物体的几何信息。
算法将要进行转移装箱的物体集合作为输入，具体包括每个物体包围盒的大小、根据物体初始摆放位置提取得到的优先级图、以及当前目标容器的装箱状态。TAP-Net接收这些输入后，将会选择一个物体及旋转方向作为输出，接着使用一个现有的启发式装箱策略计算该物体装入目标容器的位置，进行装箱。重复以上流程直到所有物体都转移到目标容器中。
3.2 优先级图的提取
为了保证转移过程满足物理上的遮挡约束，算法首先会提取物体装箱的优先级图。在本文希望的应用场景中，物体的转移装箱是由机器人自动操作的，为了保证网络选择的物体可以成功被机器人的机器臂拿起，算法会根据每个物体四周的遮挡情况计算物体的移动优先级，从而得到一个优先级图。
3.3 TAP-Net结构
TAP-Net的结构如下图所示，它由一个编码器和一个带有注意力机制的解码器构成。编码器接收物体的几何大小s_i和物体的优先级图d_i^(t-1)，解码器接收上一个进行装箱物体的几何大小y^(t-1)和当前目标容器的高度图h^(t-1)，最后由注意力机制计算每个可转移物体的概率，概率最高的物体和对应的旋转状态将会被选中作为TAP-Net的输出。
图3 TAP-Net网络结构示意图
3.4 网络训练
本文参考[9]的方法，使用“梯度策略”来训练网络，TAP-Net作为“Actor”，最后输出装箱的序列，然后对这个转移装箱序列得到的装箱结果进行评估，计算一个奖励分数；同时另外还有一个用于预测奖励分数的网络作为“Critic”，它会接收和TAP-Net一样的输入，但是只输出预测的奖励分数，网络将会根据这两个分数进行参数调整。评估装箱结果的奖励分数定义如下：
R = (C+P+S)/3
其中C表示装箱的紧密度，P为锥状程度，S则表示稳定性。下图展示了这几个数值的计算方法。
图4 装箱奖励分数计算。（a）紧密度C使用所有物体包围盒的总面积A_shape和最高高度确定的矩形面积（红色虚线框）的比例计算。（b）锥状程度P定义为A_shape和所有物体包围盒在容器底部方向的投影面积（绿色虚线框）之间的比例。（c-d）稳定性S定义为稳定的物体数量在已放置物体之中的占比，而为了确定一个物体D是否稳定，首先要确定它的支撑点（白色点），如果D的中心在支撑点组成的区域之间，则被认为是稳定的（如c），否则认为是不稳定的（d）。4.实验及其拓展
本文在RAND和PPSG两类数据集上进行了定量实验，使用C、P、S和R作为衡量指标，将TAP-Net与其他启发式算法进行对比。实验结果表明TAP-Net能够在更短时间内寻找到效率更高的装箱方案。
表1展示了本文算法和其他启发式算法在二维的转移装箱问题中的结果对比，表2展示了在三维的转移装箱问题中的结果对比，其中C、P、S和R越接近1，效果越好。
表1 二维的转移装箱问题中的各方法的结果对比表2 三维的转移装箱问题中的各方法的结果对比
除此之外本文还设计了一种“滚动策略”用于处理当输入的物体数量大于网络可处理量时的情况，如下图所示。
图5 基于滚动的装箱策略，用于处理大规模实例。当TAP-Net使用4个物体训练而要处理6个要装箱的物体时，该策略首先选择4个物体进入初始集Ω，然后使用TAP-Net选择第一个要装箱的物体（如例子中的C）。取出并装箱C后，另一个物体（例子中的F）被添加到Ω中。重复该过程，直至装箱完所有物体。
三维转移装箱问题的部分结果展示如下图。此外，本文还设计了将物体装箱至多个目标容器的策略，以及测试了在提高物体分辨率情况下的实验，请见论文原文。
图6 三维转移装箱问题参考文献
[1]Bruno Lévy, Sylvain Petitjean, Nicolas Ray, and Jérome Maillot. 2002. Least squares conformal maps for automatic texture atlas generation. In ACM transactions on graphics (TOG), Vol. 21. ACM, 362–371.
[2]Max Limper, Nicholas Vining, and Alla Sheffer. 2018. BoxCutter: Atlas Refinement for Efficient Packing via Void Elimination. ACM Trans. on Graphics 37, 4 (2018).
[3]Bongjin Koo, Jean Hergel, Sylvain Lefebvre, and Niloy J Mitra. 2016. Towards zero- waste furniture design. IEEE transactions on visualization and computer graphics 23, 12 (2016), 2627–2640.
[4]Korhan Karabulut and Mustafa Murat İnceoğ 2004. A hybrid genetic algorithm for packing in 3D with deepest bottom left with fill method. (2004), 441–450.
[5]A Galrão Ramos, José F Oliveira, José F Gonçalves, and Manuel P Lopes. 2016. A con- tainer loading algorithm with static mechanical equilibrium stability constraints. Transportation Research Part B: Methodological 91 (2016), 565–581.
[6]Haoyuan Hu, Xiaodong Zhang, Xiaowei Yan, Longfei Wang, and Yinghui Xu. 2017.Solving a new 3d bin packing problem with deep reinforcement learning method. arXiv preprint arXiv:1708.05930 (2017).
[7]Irwan Bello, Hieu Pham, Quoc V. Le, Mohammad Norouzi, and Samy Bengio. 2017. Neural Combinatorial Optimization with Reinforcement Learning. (2017). https: //openreview.net/forum?id=Bk9mxlSFx
[8]Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. 2015. Pointer Networks. (2015), 2692–2700. http://papers.nips.cc/paper/5866-pointer-networks.pdf
[9]MohammadReza Nazari, Afshin Oroojlooy, Lawrence Snyder, and Martin Takac. 2018. Reinforcement Learning for Solving the Vehicle Routing Problem. (2018), 9839– 9849. http://papers.nips.cc/paper/8190- reinforcement- learning- for- solving- the- vehicle- routing- problem.pdf
[10]Yuexin Ma, Zhonggui Chen, Wenchao Hu, and Wenping Wang. 2018. Packing irregular objects in 3D space via hybrid optimization. In Computer Graphics Forum, Vol. 37. Wiley Online Library, 49–59.
