Pick-and-place process sequencing for transformation of rasterized 3D structures

问题背景

建筑可以用砖块或预制构件搭建；同样，一个结构也可以由尺寸相同的零件（即体素）通过取放（pick-and-place，PnP）方式组装：机器每次抓起一个零件，再把它放到另一个位置。论文把这一任务表述为：将一个栅格化结构（源结构）变换为另一个栅格化结构（目标结构）。用料垛中的材料搭建新结构，是源结构恰为料垛形状的特例。要回答的问题是：机器应按怎样的顺序搬运，才能使总工作量尽可能小。

难点有两个。其一，决定哪个零件搬到哪个位置是一个指派问题：暴力搜索需要比较 n! 种序列，而实验中的结构各有约 2,250 至 2,550 个体素。其二，代价最低的对应关系未必能够执行。本文研究的机器是至少三轴的笛卡尔机器人，配有从零件顶面吸附的真空吸盘，因此只能在结构的顶面取放体素。

方法原理

两个形状均以封闭三角网格输入。每个网格先栅格化为体素，并用泛洪填充标出内部体素；随后对齐两个体素模型；剩下的工作是运动排序，即决定每个体素搬到哪里、按什么顺序搬。

1. 对齐与分类。 假设两个结构在竖直方向上已经对齐，只在水平面内对平移量做穷举搜索，使两者的重叠体积最大。只在源结构中的体素称为搬运体素（Mover，M），只在目标结构中的体素称为空位（Void，V），两者重叠的体素保持不动。若 M 与 V 的数量不等，多出的体素放到料垛上或从料垛中取用，料垛取为一个线性堆叠。
2. 单次搬运的代价。 把 M_i 搬到 V_j 的代价为 c_ij = |x_j − x_i| + |y_j − y_i| + 2z_max − z_i − z_j，以体素尺寸为单位（式 1）。零件先被提升到安全平面 z_max，为避免碰撞，只在这一高度上沿 x、y 方向移动，然后下降到 V_j。
3. 在完整代价矩阵上应用匈牙利算法。 所有 M–V 配对的代价构成一个 n × n 矩阵。匈牙利算法的时间复杂度为 O(n³)，输出总代价最小的 n 个配对。这一全局优化策略（GOS）给出总代价的下界，但并不给出可执行的运动序列。
4. 顶面取放约束。 代价最低的配对未必对应可行的序列。在论文的八体素示例中，一组总代价最小（27）的配对可以按合适的顺序执行，而另一组代价相同的配对在两步之后陷入死锁。
5. 局部优化策略（LOS）。 LOS 只用位于顶面的 M 和 V 构造代价矩阵，并对其应用匈牙利算法；当 M 多于 V 时，算法会让部分 M 暂不参与这一阶段。哪些 M 暂不参与，取决于使所选配对总代价最小。得到的配对可以按任意顺序搬运；随后更新顶面，重复上述过程，直到所有 M 搬运完毕。在该示例中，LOS 分两个阶段完成，总代价为 27，恰好等于下界。

论文还将 LOS 与另外两种同样能生成有效序列的策略比较。贪心选择策略（GSS）使用相同的顶面代价矩阵，但不用匈牙利算法，每一步只搬运代价最低的一个配对；随机选择策略（RSS）每一步随机搬运一个顶面配对。

实验结果

实验使用八个模型（wall、pyramid、starfish、cube、igloo、castle、stairs 和 Eiger mountain，即墙、金字塔、海星、立方体、冰屋、城堡、阶梯和艾格峰），栅格化为 2,250 至 2,550 个体素的相近规模，并两两相互变换。计时基于在 Intel Core i3-2310M 2.10 GHz、8 GB 内存的 PC 上运行的 C++ 程序。工作量取决于 M–V 配对的数量，而非体素总数：金字塔 → 墙需要 1,643 个配对，金字塔 → 冰屋只需 325 个，因为这两个形状更相似、对齐得更好。按代价衡量，GOS 最优，因为它给出的就是下界，但它的配对并不直接给出运动序列，有时甚至根本无法执行。LOS 居第二，其各阶段的分组自然构成运动序列；GSS 略逊于 LOS，但明显优于 RSS。按时间衡量，RSS 最快，GSS 与 LOS 相近，而 GOS 要在一个巨大的矩阵上运行一次匈牙利算法，耗时最长。作者的结论是：LOS 在代价与计算时间之间取得了良好的平衡，并优于其他能生成可行序列的策略。

在海星 → 城堡这一变换上，以六种分辨率（139 至 2,016 个 M–V 配对）重复实验，总代价随配对数量大致线性增长；除 GOS 外，各策略的计算时间也是如此。LOS 虽然基于 O(n³) 的匈牙利算法，其计算时间却不会随分辨率呈三次方增长。所有结果均来自计算机仿真。顶面取放约束也使悬挑结构无法搭建，例如带天花板的房间或开窗的墙；作者认为，LOS 的思路，即先挑出满足约束的体素、再优化 M–V 配对，可以推广到其他零件和约束。